[알고리즘] 05. 동적계획법(Dynamic Programming) & 분할정복(Divide and Conquer)

<본 포스팅은 개인 공부 목적으로 작성되었습니다.>

✅ 동적계획법(Dynamic Programming)

동적계획법(Dynamic Programin)이란 큰 문제를 작은 문제로 나누어 해결 한 뒤 그 해를 활용하여 큰 문제를 해결해 나가서 결국 최종 문제를 해결하는 알고리즘이다.

• Memoization(메모이제이션)기법 : 해결한 문제의 해를 저장해 둔 뒤, 똑같은 문제가 발생하였을 때 저장해 놓은 해를 사용함으로써 중복 연산을 하지 않고 빠르게 해결하는 기법이다.

✔ 동적 계획법 예시

• 피보나치수열 점화식
  • f(0) = 0
  • f(1) = 1
  • f(n) = f(n-1) + f(n-2)

피보나치수열의 점화식을 그림으로 표현해보면 위 그림과 같다. 위 그림을 보면 동일하게 중복돼서 사용되는 함수가 있다. f(0), f(1), f(2)가 반복되어서 사용되고 아마 숫자가 더 커지면 커질수록 반복되는 함수가 많을 것이다. 만약 단순 재귀로 구현하게 된다면 중복되는 연산이 많아지고 그러면 효율성이 떨어지게 된다. 이럴 때 이제 동적계획법(Dynamic Programming)과 메모이제이션(Memoization) 기법을 사용하면 된다.

✔ Bottom-Up

작은 문제부터 차례대로 푸는 방법으로 반복문을 이용한다.

#include <iostream>

using namespace std;

int fibo(int n) {

    int ch[11] = { 0, 1, };

    for (int i = 2; i <= n; i++) {
        ch[i] = ch[i - 2] + ch[i - 1];
    }

    return ch[n];

}

int main() {

    cout << fibo(10);

    return 0;
}

✔ Top-Down

큰 문제를 작게 쪼개면서 푸는 방법으로 재귀로 구현한다. Memoization기법을 사용한다.

#include <iostream>

using namespace std;

int ch[11] = { 0, };

int fibo(int n) {

    if (n < 2) return n;
    if (ch[n]) return ch[n];  // 이미 값이 있다면 그 값을 return ==> Memoization기법

    return ch[n] = fibo(n-2) + fibo(n-1);        // 계산한 값은 ch에 저장 ==> Memoization기법

}

int main() {

    cout << fibo(10);

    return 0;
}

✔ 결과

55

✅ 분할 정복(Divide and Conquer)

분할정복(Divide and Conquer)은 문제를 나눌 수 없을 때까지 나누고 각각 풀면서 다시 합병해 가면서 답을 얻는 알고리즘이다. 일반적으로 재귀 함수를 통해 구현하며, 문제를 잘게 쪼갤 때 부분 문제는 중복되지 않는다.

• Divide(분할) : 문제를 하나 또는 둘 이상으로 나눈다.
• Conquer(정복) : 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고 아니면 또 나눈다.

✔ 분할 정복 예시

• 정렬(퀵 정렬, 병합 정렬)
• 이분 탐색(Binary Search)

✅ 공통점과 차이점

공통점

• 하나의 문제를 잘게 쪼개 작은 단위의 문제로 분할한다.

차이점

• 동적 계획법(Dynamic Programming)
  • 부분 문제는 중복되어, 상위 문제 해결 시 재활용된다.
  • Memoization기법을 사용한다.
• 분할 정복(Divide and Conquer)
  • 부분 문제가 서로 중복되지 않는다.
  • Memoization기법을 사용하지 않는다.