다이나믹 프로그래밍 (Dynamic Programing)

하나의 문제를 단 한번만 풀도록 하는 알고리즘 / 줄여서 DP라고 부른다!

일반적으로 상당수 분할정복 기법은 동일한 문제를 다시 푼다는 단점을 갖고있다. (분할 정복 기법에 대해 알아보기)
단순 분할 정복 기법을 활용했을때 심각한 비효율성을 띄는 대표적 예시 = 피보나치 수열

피보나치 수열 = 특정한 숫자를 구하기 위해 그 앞에 있는 숫자와 두 칸 앞에 있는 숫자의 합
N[i] = N[i-1] + N[i-2]

피보나치 수열을 풀때 단순하게 반으로 나눠 생각하면(분할 정복 기법).... 위 그림처럼 12번째 수열이 3번이나 반복된다. -> 매우 비 효율절
--> 다이나믹 프로그래밍 사용!!

다이나믹 프로그래밍을 사용가능한 상황

1번 가정. 큰 문제를 작은 문제로 나눌 수 있다.
2번 가정. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

(2번이 핵심!!!)

즉, 크고 어려운 문제가 있으면 그것을 먼저 잘게 나눠 해결한 뒤에 처리하여 나중에 전체의 답을 구하는 것!
이 과정에서 메모이제이션(Memoization)이 사용된다.! (이 점이 분할 정복과 다르다)

메모이제이션

이미 계산한 결과는 배열에 저장한다.
이를 통해 나중에 동일한 계산을 해야 할 때는 저장된 값을 단순히 반환하기만 하면 된다!

피보나치 수열 DP로 구현하기 (메모이제이션 X)

# 아래 코드는 C 언어로 작성되었다.
int dp(int x) {
    if(x ==1) retur 1; #초기값 명시해주기
    if(x == 2) return 1; #초기값 명시해주기
    # 위 두줄은 재귀함수가 종료되는 조건이기도 한다!
    return dp(x-1) + dp(x - 2); # 구하고자 하는 수열은 그 수열의 하나 전과 두개전 수열의 합이다
}
# 실습 코드
intmain(void) {
    printf("%d", dp(10));
->
55

그런데 위 코드에서 50번째 수열을 구하려 하면 처리시간이 매우 오래 걸린다... (연산을 2^50번 진행해야 한다)

# 아래 코드는 python 으로 작성되었다.
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + (n-2) # fib(2) = fib(1) - fib(0)
    
print(fib(40))
->
102334155

위 코드도 40번째 수열을 구하면 시간이 꽤 걸린다.

피보나치 수열 DP로 구현하기 (메모이제이션 O)

# 아래 코드는 C 언어로 작성되었다.
int d[100];
int dp(int x) {
    if(x ==1) retur 1; #초기값 명시해주기
    if(x == 2) return 1; #초기값 명시해주기
    # 위 두줄은 재귀함수가 종료되는 조건이기도 한다!
    if(d[x] != 0) return d[x] # 이미 값이 배열에 저장되어 있다면 그 값을 반환한다.
    return d[x] = dp(x-1) + dp(x - 2);
    # 구한 적 없는 값이라 배열에 저장이 안되어 있을때
    # 구하고자 하는 수열은 그 수열의 하나 전과 두개전 수열의 합이다
}
# 실습 코드
intmain(void) {
    printf("%d", dp(30));
->
832040

C언어만 그런건진 모르겠지만 이 상황에서도 50번째 수열을 구하려고 하면 overflow 되어서 단순 정수형을 사용해서는 구할 수 없다! (이상한 음수값이 출력된다.)

def fib(n, lookup):
    if n <= 1:
        return n
    targetValue = lookup[n] # lookup[60]
    return fib(n-2, lookup) + fib(n-1, lookup):

lookup = [None] * 
print(fib(6, lookup))