[알고리즘/Python] 동적계획법 DP

동적 계획법 Dynamic Programming

• 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법

• 한 가지 문제에 대해서 한 번만 풀도록 만들어주는 알고리즘

  • 똑같은 연산을 반복하지 않도록 한다.

• 메모이제이션(Memoization) : 한 번 계산한 문제는 다시 계산하지 않도록 저장해두고 활용하는 방식

사용 조건

1. 최적 부분 구조 (Optimal Substructure)

   • 문제를 해결하는 모든 단계에 대해서 해당 단계의 최적해가 도출되어야 한다.

   • 예) 부분 문제에서 A에서 B까지의 최단 경로 X를 구했을 때, X는 모든 문제에서 최단 경로

2. 겹치는 부분 문제 (Overlapping Subproblems)

   • 동일한 작은 문제들이 중복되어 사용되는 경우

   • 메모이제이션 활용

구현 방식

1. 하향식 (Top-Down)

   • 큰 문제를 풀다가 풀리지 않은 작은 문제가 있다면 그때 해결하는 방법 (재귀)

   • 가독성이 좋지만, 코드를 작성하기 어렵다.

2. 상향식 (Bottom-Up)

   • 작은 문제부터 차근차근 구하는 방법

   • 해결이 용이하지만, 가독성이 떨어진다.

피보나치 수열

Top-Down 방식

def fibo(n):
    if n == 1 or n == 2:
        return 1
    else:
        if memoization[n] != 0: # 리스트에 작은 문제의 결과가 저장되어 있을 때, 반환
            return memoization[n]
        else:
            memoization[n] = fibo(n-1) + fibo(n-2)
            return memoization[n]

if __name__ == "__main__":
    num = 5
    memoization = [0] * (num+1)
    print(fibo(num))

Bottom-Up 방식

if __name__ == "__main__":
    num = 5
    dp = [0] * (num+1)
    dp[1] = 1
    dp[2] = 1
    
    for i in range(3, num+1):
        dp[i] = dp[i-1] + dp[i-2]

    print(dp[num])