Dynamic Programming, DP, 동적 프로그래밍

∴다이나믹 프로그래밍에 대한 개념정리 및 예제풀이

마지막으로 DP 정복하는것을 향해서!!!

---

• 다이나믹 프로그래밍(Dynamic programming, DP)란?

다이나믹 프로그래밍이란 복잡한 하나의 문제를 간단한 여러개의 중복되는 문제로 나누어 같은 방식으로 풀어 답을 구하는 방법을 말한다.

 

나는 보통 동적(Dynamic)이라는 용어를 보면 '계속해서 움직이는' 이라는 뜻으로 이해했다. 그러나 여기서의 동적(dynamics)이라는 단어는 DP를 이해하는데 직관적으로 도움을 주지 못하는듯 하다. 뒤에서 언급하겠지만 그보다는 '작은 중복문제들을 기억하며 푼다'라는 의미로 받아들이는 것이 좋을 것 같다. 그래서 앞으론 dyanmic programming보다는 DP라고 부르려고 한다. (사실 이렇게 해야 나도 헷갈림이 덜할 것 같다.)

 

• DP조건

위의 DP를 설명하기 위해서 적어놓은 한 문장 안에 DP의 핵심 조건 2가지가 들어가있다.

 

(문제해결관점)

첫번째로 '하나의 문제를 간단한 여러개의 중복되는 문제로 나누어' 이다.

중복되는 서브문제(overlapping subproblems)라고 표현할 수도 있는데 말 그대로 하나의 문제를 똑같은 작은 문제들로 나눌수 있다는 뜻이다.

 

(문제의 구조관점)

두번째로는 '같은 방식으로 풀어 답을 구하는 방법' 이다.

최적 부분 구조(optimal substructure)라고도 표현할 수 있으며 큰 문제의 정답은 작은 문제의 답들을 재활용해서 구할 수 있다는 개념이다. 

즉 전체 문제의 최적해가 부분 문제의 최적해들로써 구성된다.

 

• 푸는 방식

1. 탑다운 방식(memoization, 메모이제이션)

: 재귀를 이용해서 위에서 아래로부터 풀어나간다.

 

2. 바텀업 방식(tablation, 타불레이션) 

: 반복문을 통해서 작은문제부터 풀어나간다.

 

• 재귀 vs DP vs 분할정복

사실, 재귀(recursion)을 이용해서 푸는 방법과 DP 그리고 분할정복과의 차이점을 잘 모르겠다.

쓰는 용어가 다르다면 분명히 개념적으로 다른부분이 있을것이다.

그래서 그 차이점들을 비교하기 위해서 정리를 해보았다.

분할정복(divide and conquer) == 재귀 + 최적부분구조(optimal substructure)
DP == 분할정복 + 중복되는 서브문제(overlapping subproblems) 
∴ DP == 재귀 + 최적부분구조 + 중복되는 서브문제

분할정복에는 merge sort(병합정렬), quick sort(퀵 정렬) 같이 재귀를 이용하며 여러개의 문제로 나눌 수 있지만 그 문제들이 모두 같지는 않다.

그러나 DP는 서브문제들이 모두 같으므로 메모이제이션이 가능하다.

---

• 코드 예시 (피보나치 수열)
  • 재귀만 이용

    # 피보나치 수열
    # 시간복잡도 O(2^N)
    
    def fibo(x):
        if x == 1 or x == 2:
            return 1
        else:
            return fibo(x-1) + fibo(x-2)

  • 탑다운 방식(메모이제이션)

    # memoization을 이용한 피보나치 수열
    # 하향식
    # 시간복잡도 O(N)
    
    memo = {}
    def fibo_memo(x):
        if x == 1 or x == 2:
            memo[x] = 1
            return memo[x]
        elif x in memo:
            return memo[x]
        else:
            memo[x] = fibo_memo(x-1) + fibo_memo(x-2)
            return memo[x]

  • 바텀업 방식(반복문)

    # tablation 바텀업, 상향식
    # 반복문을 이용해서 연산
    # 연산이 엄청 빠르다.
    # 시간복잡도 O(N)
    
    n = int(input('n을 입력하세요:'))
    table = [0] * (n+1)
    
    def fibo_table(n):
        table[1] = 1
        table[2] = 1
        for i in range(3,n+1):
            table[i] = table[i-1]+table[i-2]
        return table[n]

 

위의 피보나치 코드들을 직접 숫자를 넣어보며 실행시켜보면 성능의 차이가 확실하게 느껴진다.

20까지만 해보더라도 연산시간이 확연하게 줄어드는것을 알 수 있다.

이유는 그냥 재귀만 이용한 코드는 시간복잡도가 O(2^n)인데 비해 

메모이제이션이나 반복문을 이용한 DP는 시간복잡도가 O(n)으로 선형시간을 보인다.

이처럼 성능적으로도 DP가 유용한것을 확인할 수 있다.

 

마치며...

사실 DP에 대해서 공부하고 개념정리한 것을 이정도로 간단하게 마칠 수 있을것 같긴 하다.

하지만 이 추상적인 개념들을 구체적인 문제들에 직접 적용해보려 할때는 난이도가 급상승하는 것을 느꼈다.

대부분의 코딩 테스트에서 DP문제가 많이 출제된다고 하니 어렵더라도 하나하나 차근차근 풀어봐야겠다...

화이팅!!!