다이나믹 프로그래밍
다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. (동적계획법)
다이나믹 프로그래밍에서는 이미 계산된 결과를 별도의 메모리에 저장하여 다시 계산하지 않도록 해 수행 시간을 비약적으로 향상시킨다.
다이나믹 프로그래밍의 조건
-
최적 부분 구조(Optimal Substructure)
큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
-
중복되는 부분 문제(Overlapping Subproblem)
동일한 작은 문제를 반복적으로 해결해야 한다.
다이나믹 프로그래밍을 통한 피보나치 수열 문제 분석
피보나치 수열은 다이나믹 프로그래밍으로 풀 수 있는 대표적인 문제 중 하나이다.
단순 재귀 함수로 피보나치 수열을 해결하면 지수 시간 복잡도를 가지게 되고 같은 연산이 여러번 호출되는 문제가 발생한다. 이러한 문제를 해결하기 위해 다이나믹 프로그래밍을 활용할 수 있다.
메모이제이션(Memoization)
메모이제이션은 다이나믹 프로그래밍을 구현하는 바법 중 하나로 한 번 계산한 결과를 메모리 공간에 메모하는 기법이다.
같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져오며 값을 기록한다는 점에서 캐싱(Caching)이라고도 한다.
d = [0] * 100
def fibo(x):
if x == 1 or x == 2:
return 1
if d[x] != 0:
return d[x]
d[x] = fibo(x - 1) + fibo(x - 2)
return d[x]
print(fibo(99))Top-Down Bottom-Up
탑다운(메모이제이션)은 하향식, 보텀업은 상향식이라고도 한다.
Top-Down: 재귀 함수를 이용하여 다이나믹 프로그래밍 코드를 작성하는 방법을 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 Top-Down이라고 한다.
Botton-Up: 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 하여 Bottom-up 방식이라고 한다.
다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이며 보텀업 방식에서 사용되는 결과 저장용 리스트는 DP 테이블이라고 부르고 메모이제이션은 탑 다운 방식에 국한되어 사용되는 표현이다.
다이나믹 프로그래밍 문제에 접근하는 방법
- 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요하다.
- 가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토하고 다른 알고리즘으로 풀이 방법이 떠오르지 않으면 다이나믹 프로그래밍을 고려한다.
- 일단 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면 코드를 개선하는 방법을 사용할 수 있다.
- 일반적인 코테 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 ㅁ낳다.
Ref
