다이나믹 프로그래밍
다이나믹 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 여러 개의 작은 부분 문제로 나누어 해결한 뒤, 그 결과를 저장하고 재사용함으로써 전체 문제의 해결책을 찾아내는 방법이다. 이 방법은 주로 최적화 문제에서 사용되며, 각 부분 문제는 한 번만 계산되고 그 결과는 이후의 계산에 재사용되어 계산 시간을 크게 단축시킨다. 😉
핵심 원리
최적 부분 구조(Optimal Substructure): 문제의 최적 해결책이 부분 문제의 최적 해결책으로부터 구성될 수 있음을 의미한다. 즉, 전체 문제를 작은 문제로 나누어 각각을 해결하고, 이 작은 문제들의 해결책을 조합하여 전체 문제의 해결책을 도출할 수 있다.
중복되는 부분 문제(Overlapping Subproblems): 다이나믹 프로그래밍을 적용할 수 있는 문제는 대체로 같은 부분 문제가 반복적으로 발생한다. 이러한 중복되는 부분 문제들의 해결 결과를 저장하고 필요할 때 재사용함으로써 계산량을 줄일 수 있다.
구현 방법
탑다운(Top-Down) 접근 방식 (메모이제이션, Memoization): 이 방식은 재귀를 사용하여 큰 문제를 작은 문제로 나누어 해결한다. 각 부분 문제의 결과는 메모리에 저장되며, 같은 문제를 다시 만나면 메모리에서 결과를 가져와 사용한다.
바텀업(Bottom-Up) 접근 방식: 이 방식은 가장 작은 부분 문제부터 시작하여 점차 큰 문제로 나아가면서 각 문제의 해결책을 테이블에 저장한다. 이후 큰 문제를 해결할 때는 이 테이블에 저장된 결과를 사용한다. 이는 모든 문제를 차례대로 계산하는 방식이다.
다이나믹 프로그래밍의 예
피보나치 수열 계산은 다이나믹 프로그래밍의 대표적인 예이다. 피보나치 수열의 n번째 항을 계산하는 함수를 생각해 보면, 각 항은 바로 앞의 두 항의 합으로 정의된다. 단순한 재귀 호출을 사용하면 중복 계산이 많아지지만, 다이나믹 프로그래밍을 사용하면 각 항의 계산 결과를 저장하고 재사용함으로써 효율적으로 계산할 수 있다.
- 피보나치 수열
- 예시 : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …
- 세 번째 수(1)는 첫 번째(0)와 두 번째(1) 수의 합이다.
- 네 번째 수(2)는 두 번째(1)와 세 번째(1) 수의 합이다.
- 이런 식으로 계속 이어진다.
장단점
- 장점
- 복잡한 문제를 간단하고 효율적으로 해결할 수 있다.
- 계산 시간을 크게 단축시킬 수 있다.
- 단점
- 모든 문제에 적용할 수 있는 것은 아니다. 최적 부분 구조와 중복되는 부분 문제가 있어야 한다.
- 메모리 사용량이 증가할 수 있다. (각 부분 문제의 결과를 메모리에 저장하기 때문에)
예시 코드
1
2
3
4
5
6
7
8
9
10
| def fibonacci_top_down(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci_top_down(n-1, memo) + fibonacci_top_down(n-2, memo)
return memo[n]
# 예제 사용
print(fibonacci_top_down(10)) # 55
|
1
2
3
4
5
6
7
8
9
10
| def fibonacci_bottom_up(n):
if n <= 1:
return n
fib_table = [0, 1] + [0]*(n-1)
for i in range(2, n+1):
fib_table[i] = fib_table[i-1] + fib_table[i-2]
return fib_table[n]
# 예제 사용
print(fibonacci_bottom_up(10)) # 55
|
- 차이점
- 재귀 대 반복: 탑다운은 재귀를 사용하여 문제를 해결하지만, 바텀업은 반복문을 사용한다.
- 메모리 사용: 탑다운 방식은 재귀 호출로 인한 스택 메모리 사용이 증가할 수 있으며, 메모이제이션을 위한 추가 메모리가 필요하다. 바텀업 방식은 주로 반복문을 사용하므로 스택 오버플로의 위험이 적고, 계산된 값을 순차적으로 저장하기 때문에 메모리 사용이 더 효율적일 수 있다.
- 이해 및 구현의 용이성: 일반적으로 탑다운 접근법은 문제를 이해하고 해결하는 데 직관적일 수 있지만, 깊은 재귀로 인해 실행 속도가 느려질 수 있다. 반면, 바텀업 접근법은 구현이 더 단순하고 실행 속도가 빠를 수 있지만, 전체 문제 해결 방식을 한눈에 이해하기 어려울 수 있다.
- 적용 가능성: 어떤 문제들은 탑다운 접근법으로 더 자연스럽게 해결할 수 있으며, 다른 문제들은 바텀업 접근법이 더 적합할 수 있다. 문제의 종류와 요구 사항에 따라 가장 효율적인 접근 방식을 선택해야 한다.