다이나믹 프로그래밍(Dynamic Programming/DP)
다이나믹 프로그래밍(동적 계획법): 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장, 다시 계산 안하도록 함(단순 재귀의 개선안)
메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
DP의 구현은 일반적으로 두가지 방법으로 구성 탑다운(하양식)/보텀업(상향식)
동적(Dynamic)의 뜻
자료구조의 동적 할당(Dynamic Allocation): 프로그램 실행 중 실행에 필요한 메모리를 할당하는 기법
but. 다이나믹 프로그래밍에서 다이나믹은 별 뜻 없.
다이나믹 프로그래밍 문제조건
1. 최적 부분 구조(Optimal Substructure)
- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답이 모여 큰 문제가 해결됌 ex) 피보나치 수열의 점화식
2. 중복되는 부분 문제(Overlapping Subproblem)
- 동일한 작은 문제를 반복적으로 해결해야 함 ex) 피보나치 수열의 초반 항(여러번 호출됌)
예시: 피보나치 수열(a(n) = a(n-1) + a(n-2) (점화식), a(1) = 1, a(2) = 2)
만약 피보나치 수열을 단순 재귀함수로 풀면(O(2^N)) 메모이제이션을 이용한 DP는 다시 호출 받더라도 계산해둔걸 쓰기에 한번씩만 계산해서 O(N) 이 된다. 물론 메모리는 많이 씀
다이나믹 프로그래밍의 구현
메모이제이션(Memoization): 한 번 계산한 결과를 메모리 공간에 메모하는 기법
- 다이나믹 프로그래밍 구현 방법 중 하나 (단. 계산된 결과를 일시적으로 기록해 놓는건 모두 메모이제이션 이므로 다이나믹 프로그래밍에 국한된건 아님)
- 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옴
- 값을 기록해둔다고 캐싱(Caching) 이라고도 함
탑다운(Memoization 활용) vs 보텀업(Tabulation 활용)
다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식
탑다운(Top Down) - 큰 문제 -> 작은 문제로 순으로 쪼개나가는 문제해결 방향, 재귀함수(메모이제이션 활용)로 구현
보텀업(Bottom Up) - 작은 문제 -> 큰 문제 순으로 이어 붙이는 문제해결 방향, 반복문(DP table 활용)으로 구현
Top Down VS Bottom Up
일반적으로 보텀업 방식은 반복문을 사용한다는 점에서 탑다운방식의 재귀호출보다 보통 우월한 성능을 가짐
Bottom Up의 강점
- 재귀 호출에 의한 스택오버플로우 방지
- 재귀 호출에 의한 메모리 낭비 방지(성능 개선)
Top Down의 강점
- 가독성이 좋음
다이나믹 프로그래밍, 분할 정복 비교
공통점: 둘다 최적 부분 구조를 가질때 이용 가능
차이점: 부분 문제의 중복 유무
- 다이나믹: 문제에서 각 부분 문제가 서로 영향을 미치고 중복됌 ex) 피보나치 수열
- 분할 정복 : 문제에서 동일한 부분 문제가 반복적으로 계산되지 않음 ex) 퀵 정렬
실전에서 다이나믹 프로그래밍을 접근하는 방법
주어진 문제가 다이나믹 프로그래밍 유형인지 파악해야 함
- 가장 먼저 그리디, 구현, 완전 탐색 같은 아이디어로 풀어볼 수 있을지 검토하고 다른 방법이 없으면 다이나믹 프로그래밍 고려
- 일단 재귀함수로 비효율적인 완전 탐색 프로그램 구현(탑다운) -> 작은 문제에서 구한 답이 큰 문제에서 그대로 사용할 수 있다면, 코드를 개선
- 일반 코테에서는 기본 유형의 다이나믹 프로그래밍 문제가 빈도 높음
출처
동빈나 나코테
