(알고리즘) Dynamic Programming (동적 계획법)

✋ (알고리즘) Dynamic Programming (동적 계획법)이란?

 

동적 계획법 피보나치 수열

 

큰 문제를 작은문제로 나누어 푸는 문제를 일컫는 말입니다. 대표적으로 피보나치 수열을 구할 때 동적 계획법을 씁니다.

그러면 분할정복과 비슷하다는 말이 있을 텐데 아닙니다. 다릅니다. 

 

 

📌 분할정복과의 다른점

 

결정적인 차이점이 있습니다. 바로 작은 문제가 중복이 일어나는지(동적계획법) 안일어나는지(분할정복기법) 입니다. 분할정복은 큰 문제를 해결하기 어려워 작은 문제로 나누는 알고리즘입니다.

특징은 작은 문제에서 반복이 일어나는 부분이 없다는 점입니다.

반면 동적계획법은 작은 부분문제들이 반복되는 것 (Result 값이 고정: F(0) =1, F(1) = 1) 을 이용해 풀어나가는 방법입니다.

 

즉, 분할정복과의 차이점은 작은 부분문제들이 반복되는 것을 이용해 풀어나가는 알고리즘.

 

 

 

 

⚡️ Dynamic Programming 방법

 

작은 문제들은 한번만 풀어야 합니다. 따라서 정답을 구한 작은 문제를 어딘가에 메모해 놓습니다. 다시 그보다 큰 문제를 풀때 작은 문제가 나타나면 앞서 메모한(Memoization) 작은 문제의 결과값을 이용합니다.

즉, 풀었던 문제의 답을 배열에 저장해놓고 필요할때 다시 사용함으로써 시간복잡도를 줄일 수 있게 됩니다.

 

이러한 과정을 메모이제이션(Memoization)이라 합니다. 이러한 메모이제이션을 거치면 저장할 공간이 필요하기에 공간복잡도는 불리해지지만, 시간복잡도는 유리해집니다.

문제를 통해 예시를 들며 동적계획법과 분할정복기법의 확실한 차이를 보여드리겠습니다.

 

분할정복기법을 사용하여 피보나치 수열의 6번째 수를 구하는 과정은 다음과 같습니다.

D[6] = D[5] + D[4] = D[4] + D[3] + D[3] + 1 = D[3] + 1 + 1 + 1 + 1 + 1 + 1 = 1 + 1 + 1 + 1+ 1 + 1 + 1 + 1
D[6] 을 구하는 과정에서 D[4], D[3] 이 반복적으로 계산되는 것을 볼 수 있습니다. 

반면에, 동적계획법(다이나믹프로그래밍)으로 구하는 과정을 살펴보면 다음과 같습니다.
D[3] = 1 + 1 = 2
D[4] = 2 + 1 = 3
D[5] = 3 + 2 = 5
D[6] = 3 + 5 = 8

두 방법을 비교 해봤을때 동적계획법이 훨씬 간결한 것을 알 수 있습니다. 

 

 

📌 동적계획법이 가능한 상황

 

- 작은 문제가 반복이 일어나는 경우

- 같은 문제는 구할 때마다 정답이 같은 경우

 

 

 

📌 구현 방법

 

Bottom-Up

 

-작은 문제부터 차근차근 구해나아가는 방법입니다.

 

 

def fibonacci_bottom_up(n):
    if n <= 1:
        return n
        
    fir = 0
    sec = 1
    for i in range(0, n-1):
        next = fir+sec
        fir = sec
        sec = next
    return next
    
  n = int(input('구하고 싶은 피보나치 수열을 입력하세요'))    
  print(fibonacci_bottom_up(n))

 

 

Top-Down

 

-재귀함수로 구현하는 경우입니다. 큰 문제를 먼저풀려고 시도하고, 작은 문제가 아직 풀리지 않았다면 그때 작은 문제를 해결합니다.

 

memo = [0 for i in range (100)]
n = int(sys.stdin.readline())
print(fibonacci_top_down(n)) 

def fibonacci_top_down(n):
    if memo[n] > 0:
        return memo[n]

    elif n <= 1:
        memo[n] = n
        return memo[n]

    else:
        memo[n] = fibonacci_top_down(n-1) + fibonacci_top_down(n-2)
        return memo[n]

 

 

두 가지 다 나름대로 장점이 있습니다. Bottom-Up의 경우 코드가 이해하기 쉬울 수 있습니다. 자신이 풀 수 있는 방식으로 선택해서 풀면 됩니다.

 

 

📌 마무리

 

동적계획법 방식으로 풀기 위해서는 dp[0]부터 시작해서 작은 문제들의 규칙성을 발견하는 것이 제일 중요합니다.