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

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

복잡한 문제를 더 작고 관리 가능한 부분 문제로 나누어 해결하는 알고리즘 설계 기법이다.

알고리즘의 기본 아이디어는 각 부분 문제의 해답을 저장하고, 이를 재사용함으로써 중복 계산을 피해 계산 효율을 극대화하는 것이다.

 

 

시간복잡도

동적 계획법 알고리즘의 시간복잡도는 문제에 따라 다양하지만, 일반적으로 부분 문제의 수와 각 부분 문제를 해결하는 데 걸리는 시간의 곱으로 표현된다.

 

1. 피보나치 수열 계산:
   • 각 수를 계산하기 위해 이전 두 수만 알면 되므로, 한 번 계산된 값은 다시 계산할 필요가 없다.
   • 시간복잡도는 O(n)이다.
2. 최장 공통 부분 수열(Longest Common Subsequence, LCS):
   
   • 시간복잡도는 O(m * n)이다.
   • m, n은 두 시퀀스의 길이
3. 배낭 문제:
   
   • 시간복잡도는 O(n * W)이다.
   • n은 항목의 수, W는 배낭의 용량

 

 

동적 계획법의 기본 원리

1. 문제 분할:
   • 복잡한 문제를 작은 부분 문제로 나눈다.
   • 큰 문제의 최적 해결책이 하위 문제의 최적 해결책으로 구성되어야 한다.
2. 중복 계산 방지:
   • 각 부분 문제의 해결책을 메모리에 저장하고, 이를 필요할 때 재사용함으로써 중복된 계산을 피한다.
3. 순차적 계산:
   • 작은 문제부터 시작하여, 이들의 해결책을 차례대로 구축하면서 최종적으로 전체 문제의 해결책을 도출한다.

 

 

예시

피보나치 수열:

• 각 피보나치 수를 저장하여, 각 숫자에 대해 피보나치 수를 계산할 때마다 이전의 두 수를 더하면 됩니다.

def fibonacci(n):
    # n이 0이거나 1이면, 그대로 n을 반환
    if n <= 1:
        return n
    # 결과를 저장할 테이블 초기화
    fib = [0] * (n + 1)
    fib[1] = 1
    # 2부터 n까지 각 숫자에 대해 피보나치 수 계산
    for i in range(2, n + 1):
        fib[i] = fib[i - 1] + fib[i - 2]
    return fib[n]