동적 계획법( DP - Dynamic Programming ), 메모이제이션( Memoization )

동적 계획법 (DP - Dynamic Programming)

동적 계획법 (DP - Dynamic Programming) 은 큰 문제를 작은 문제로 나누어서 풀이하는 방식의 알고리즘입니다. 

 

 

 

 

Dynamic Programming이라는 이름은, 

1953년, 수학자인 리처드 벨만이 큰 문제 안에 작은 문제가 중첩되어 있는 문제를 해결하면서 동적 계획법 Dynamic Programming이라는 이름을 사용했습니다. Dynamic은 벨만이 알고리즘의 시가변적Time-varing이고 다단계적인multistage 특성을 나타내기 위해 사용되었습니다. Programming은 그 당시 근무하던 회사의 소속인 공군 내에서 워드 프로세스 교육이나 군수 물자 운송 등에 사용되던 단어였기 때문에 사용되었습니다. 

 

 

 

 

분할 정복과의 차이점

주어진 문제를 더 작은 문제들로 나눈 뒤, 작은 문제들의 답을 구하고

원래 문제에 대한 답을 구한다는 점에서는 분할 정복 ( Divide Conquer )과 비슷합니다. 

 

분할 정복과 동적 계획법의 가장 큰 차이점은,

나눠진 작은 문제들이 분할 정복에서는 중복되지 않지만 동적 계획법에서는 중복될 수 있다는 점입니다.

 

동적 계획법은 어떤 부분 문제는 두 개 이상의 문제를 푸는 데 사용될 수 있기 때문에

답을 한 번만 계산하고 그 결과를 여러 번 사용하여 속도를 향상할 수 있습니다.

 

 

이때 이미 계산한 값을 저장해 두는 메모리를 캐시(Cache) 라고 하고,

두 번 이상 계산되는 부분 문제를 중복되는 부분 문제 (Overlapping Subproblems) 라고 합니다.

 

 

 

 

동적 계획법 문제는 2가지 속성이 있습니다.

1. Overlapping Subproblem: 겹치는 부분 문제 

2. Optimal Substructure: 최적 부분 구조

 

1. Overlapping Subproblem: 겹치는 부분 문제 

겹치는 부분 문제 (Overlapping subproblem) 는

어떤 문제가 여러 개의 부분 문제로 나눠질 수 있는 문제라는 뜻입니다. 

 

** 부분 문제: 항상 새로운 부분 문제 sub problem을 생성하기 보다는 계속해서 같은 sub problem이 여러번 재사용되거나 재귀 알고리즘을 통해 해결되는 문제입니다.

 

 

 

대표적인 예시로는 피보나치 수열이 있습니다.

• 피보나치 수열은, 앞의 두 수를 더한 수가 다음 수가 되도록 하는 수열입니다.

• 0, 1로 시작합니다.

• 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...

• F(0) = 0, F(1) = 1.

• F(n) = F(n-1) + F(n-2) (n >= 2)

이처럼 겹치는 부분 문제가 있다면, 주어진 문제는 나누어진 작은 문제들을 통해 정답을 구할 수 있습니다.

 

작은 문제와 같은 방법으로 큰 문제의 답을 구할 수 있으며,

모든 문제를 작은 문제로 쪼갤 수 있기 때문입니다.

이는 기저 사례를 제외한 모든 문제에 해당됩니다.

 

피보나치 수열에서 보면 기저 사례는 n이 0 혹은 1일 경우 이며, f(n)의 문제는 f(n-1)과 f(n-2)문제의 답을 이용하여 구할 수 있습니다.

 

 

2. Optimal Substructure: 최적 부분구조

최적 부분 구조 (Optimal Substructure) 는 어떤 문제의 최적의 해결책이 그 부분 문제의 최적의 해결책으로부터 만들어질 수 있는 경우입니다.

 

최적 부분구조일 때는 문제의 정답을

쪼개진 작은 문제의 정답에서부터 구할 수 있습니다.

 

이러한 특성은 동적 계획법와 그리디 알고리즘의 유용성을 판별하는데 사용되기도 합니다.

 

 

이러한 Optimal Substructure에서는 문제의 크기에 상관없이 어떤 하나의 문제 정답은 일정합니다. 이 때 어떤 하나의 문제는 중복되는 문제입니다. 중복되는 문제의 값을 매번 구하는 것은 매우 비효율적입니다. 이러한 비효율성을 개선할 수 있는 방법은 메모이제이션 (Memoization)입니다.

 

메모이제이션 (Memoization)

동적 계획법에서 각 문제는 한 번만 풀이합니다. 중복되는 부분 문제의 경우도 마찬가지로 한 번만 풀이합니다. 동적 계획법은 Optimal Substructure를 만족하기 때문에, 같은 문제는 정답이 같습니다. 이러한 특성을 이용하기 위해, 정답을 한 번 구하면 그 정답을 캐시 (Cache) 에 메모해놓습니다. 이는 배열에 저장하는 것으로 구현할 수 있습니다.

int memo[100];
int fibonacci(int n) {
    if (n <= 1) {
    	return n;
    } else {
        if (memo[n] > 0) {	// memo의 값이 0이 아니면
            return memo[n];	// 그 값을 그대로 사용
        }
        memo[n] = fibonacci(n-1) + fibonacci(n-2);
        return memo[n];
    }
}

memo 배열(Cache)에 지속적으로 값을 저장하고 사용하는 것을 확인할 수 있습니다.

 

 

 

동적 계획법 구현

1. Top-down: 큰 문제를 작은 문제로 쪼개면서 해결, 재귀로 구현합니다.

2. Bottom-up: 작은 문제부터 차례대로 해결, 반복문으로 구현합니다.

Top-down과 Bottom-up의 시간복잡도 차이는 문제에 따라 다를 수 있습니다.

다만, 파이썬의 경우는 재귀 호출을 할 때 Stack Overflow가 발생할 수 있기 때문에 Bottom-up 구현이 더 좋습니다.

대부분의 경우는 두 경우 모두로 해결이 가능하기 때문에 매번 둘 중 하나를 선택하여 풀이하면 됩니다.

 

1. Top-down

큰 문제를 작은 문제로 나누고, 작은 문제를 푼 다음 큰 문제를 푸는 방식으로 진행합니다. 재귀 호출을 사용하여 구현합니다.

 

2. Bottom-up

작은 문제부터 차례대로 풀이합니다. 문제의 크기가 점점 커지며, 작은 문제를 풀면서 진행되기 때문에 매번 큰 문제를 풀 수 있습니다. 반복문을 사용하여 구현합니다.

 

 

 

동적 계획법을 통해서 문제를 풀이할 때는 메모이제이션을 위해 캐시 배열을 만들고, 재귀 호출 혹은 반복문을 이용하여 문제를 해결하면 됩니다. 만약 문제를 풀 때 점화식이 만들어질 수 있는 문제라면 동적 프로그래밍을 이용하기에 좋을 것 같습니다.