의미
최적부분구조 | 중복하위문제
복잡한 문제를 간단한 하위 문제로 나눠 푸는 최적화기법 중에 하나다. 문제가 최적부분구조이고 하위문제들이 중복되는 경우에 동적 프로그래밍 전략을 적용할 수 있다. 최적부분구조란 문제의 최적 해결방법이 하위 문제들의 최적 해결방법으로 구성되는 구조다.
용도
배낭 문제와 동전 교환문제와 같은 최적화 문제, 최장공통 부분수열과 편집거리와 같은 문자열 처리, 최단경로 문제, 최소 비용경로와 같은 경로 찾기, 최적 자산 배분문제, 작업 스케줄링 문제 등 복잡한 문제를 효율적으로 해결하는 데에 쓰인다.
vs 분할정복
유사점
- 문제를 나눠서 푼다
- 작은 문제로 쪼갠다
- 작은 문제도 최적화 문제다
차이점
- 최적화 문제 등 쪼개진 문제에서 중복된 문제들이 발생한다.
구현전략
탑다운
큰 문제를 작은 문제로 쪼개서 푸는 방식을 탑다운 방식이라고 한다. 여행계획을 짤 때 국가를 먼저 정한 다음 도시 단위로 방문순서를 정하는 것과 같다.
버텀업
작은문제를 푼 다음 문제를 키워나가서 해결하는 방식이다. 재귀호출을 사용하지 않아 탑다운 방식보다 일반적으로 빠르다.
구현요령
피보나치수열
피보나치 수열은 최적화 문제는 아니다. 하지만 동적프로그래밍의 구현을 설명하기에 좋아 해당 문제로 구현요령을 설명한다.
동적 프로그래밍은 계산 결과를 활용해서 계산 중복을 막아 알고리즘의 성능을 올린다. 탑다운 방식으로 계산 결과를 표에 정리하는 것을 메모이제이션이라고한다. 버텀업 방식으로 결과를 표에 정리하는 것을 타뷸레이션이라고 한다
탑다운: 메모이제이션
def fib(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib(n-1, memo) + fib(n-2, memo)
return memo[n]
- 장점: 필요한 연산만 하기 때문에 불필요한 연산을 줄여 효율적이다
- 단점: 재귀 호출이 깊어질 경우 함수 스택이 커진다
버텀업: 타뷸레이션
def fib(n):
table = [0] * (n + 1)
table[1] = 1
for i in range(2, n + 1):
table[i] = table[i-1] + table[i-2]
return table[n]- 장점: 재귀호출을 사용하지 않기 때문에 스택 오버플로우 위험이 없다.
- 단점: 모든 하위 문제를 계산해야하므로 메모이제이션보다 계산량이 많아질 수 있다.