[Algorithm] Dynamic Programming

개요

조금씩 알고리즘 공부를 진행하고 있던 중에, DP에 대해 이미 공부를 했지만 아직 많이 빈약한 것 같아 유튜브를 통해 인강을 들은 후 다시 한 번 정리하려고 한다. 강의는 코드없는 프로그래밍님의 Dynamic Programming이다. 강의를 듣고싶다면 아래의 링크로 들어가면 들을 수 있다. 

 

https://www.youtube.com/watch?v=eJC2oetXaNk 

---

Dynamic Programming

다이나믹 프로그래밍은 세가지 조건이 충족되면 바로 적용이 가능하다

 1. Problem이 더 작은 subproblem으로 쪼개질 때

 2. 이런 subproblem들의 솔루션으로 더 큰 규모의 problem의 솔루션을 구할 수 있을 때

 3. 이러한 subproblem들이 겹칠 때 ->  memorization 이용 가능

 

강의에서는 피보나치 수열로 예를 들어주었다.

피보나치 수열의 예시

위의 그림에서 subproblem을 확인할 수 있으며, 동일한 subpromblem 또한 확인할 수 있다. 

 

일반적으로 피보나치 수열을 코드를 구현하면 아래와 같다.

def fib_naive(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        fib = fib_naive(n-1) + fib_naive(n-2)
        return fib

단순하지만, 시간이 아주 오래 걸리는 것을 확인할 수 있다.

 

다음은 recursive DP 방법이다. 아래의 코드를 통해 구현할 수 있다. 

fib_array = [0, 1] # F(0)과 F(1) 저장
def fib_recur_dp(n):
    if n < len(fib_array): # 찾고자하는 수열이 존재할 때
        return fib_array[n] # array에서 값 리턴
    else: # 존재하지 않으면
        fib = fib_recur_dp(n-1) + fib_recur_dp(n-2) # recursive하게 계산
        fib_array.append(fib) # 솔루션을 배열에 저장
        return fib

일반적으로 피보나치 수열을 구현했을 때보다 속도가 빠른 것을 확인할 수 있다. 하지만 recursive DP에는 치명적인 단점이 존재한다. 너무 큰 숫자는 스택에 저장되는 양이 많아지면 오버플로우가 발생할 수 있다. 이를 해결하기 위해 bottom-up DP 방법을 사용하면된다

 

bottom-up DP? subproblem으로 쪼개나가는 것이 아닌, 가장 작은 subproblem의 F(0)부터 F(1), F(2) 순서대로 채워 나가는 것을 의미한다. 

F(0)

F(1)

F(2)

F(3)

...

이렇게 채워나가면 반복문을 통해 채워나갈 수 있다. bottom-up 코드의 예시를 확인해보자.

 

def fib_dp(n):
    if n == 0:
        return 0
    else n == 1:
        return 1
    fib_array = [0, 1]
    for i in range(2, n+1): # 2에서 n까지 array를 채워나감
        num = fib_array[i-1] + fib_array[i-2] # 솔루션을 제시
        fib_array.append(num) # 이 솔루션을 array에 추가
    return fib_array[i] # n번째 element를 반환

위의 코드는 시간 복잡도도 O(n)이며 공간 복잡도도 O(n)인것을 확인할 수 있다. 공간복잡도는 데이터를 지워줄 수 있다면 O(1)까지 내려가는 것을 확인할 수 있다.

 

★ 제일 중요한 것은 problem과 subproblem 정의를 찾아낼 수 있는 것이다. 이는 많은 유형의 문제를 경험해야 터득할 수 있는 부분이다.