1. 다이나믹 프로그래밍(동적계획법)
: 복잡한 문제를 여러 개의 하위 문제로 나눈 후, 그걸 결합해 최종 문제를 해결하는 것
이 때 각 하위 문제의 답을 table에 저장하고 같은 하위 문제가 나타나면 table에 있는 답 활용
-
분할 정복과의 차이점: 문제를 잘게 쪼개서 분할하는 점은 동일하지만, DP는 중복되는 부분 문제를 재활용하는 Memoization/Tabulation 기법 사용
-
동적 프로그래밍의 기법: Memoization & Tabulation
: 프로그램 실행 시 이전 계산 값을 저장하고, 동일한 입력이 들어올 때 저장된 값을 다시 계산하지 않고 반환해 전체 실행 속도를 빠르게 하는 기술 (중복 계산을 피하기 위해 사용)
Memoization (Top-down)
: 주로 재귀를 이용해 값을 위에서부터 계산하기 때문에 하향식 접근 (cache에 값을 기록해 중복 계산 방지)
Tabulation (Bottom-up)
: 주로 반복문을 사용해 밑에서부터 값을 계산하기 때문에 상향식 접근 (list에 값을 기록해 중복 계산 방지)
차이점
- Memoization은 필요에 따라 스택 오버플로우가 발생할 수 있지만, Tabulation은 스택 오버플로우의 위험이 없음
- Memoization은 자동으로 중복된 계산을 피하고, Tabulation은 반복문을 통해 모든 가능한 경우의 수를 한 번에 계산하므로 중복된 계산을 피함
Memoization은 하향식 방법으로 재귀 함수를 호출할 때 해당 값을 저장하기 때문에 불필요한 연산/저장을 하지 않지만, 재귀 호출을 사용하므로 스택 오버플로우가 발생할 수도 있다.
Tabulation은 상향식 방법으로 밑에서부터 모든 가능한 경우의 수를 계산해 값을 모두 저장해놓기 때문에 추가적인 메모리 사용이 있을 수 있으나, 스택 오버 플로우 위험이 없다.
—> 그래서 작은 입력에서는 Memoization이 효율적이고, 큰 입력에서는 Tabluaton이 더 효율적일 수 있다.
상향식 & 하향식 접근법
- 상향식 접근법(Bottom-up): 가장 최하위의 해답을 구한 후 저장, 해당 결과값을 이용해 상위 문제를 풀어가는 방식 (반복문 활용), 작은 문제를 모아 큰 문제 해결
아래 최하위 문제부터 해결하면서 활용하고, 타고 타고 올라가서 상향식- 하향식 접근법(Top-down): 상위의 해답을 구하기 위해 아래로 내려가며 하위의 해답을 구하는 방식 (재귀 활용), 큰 문제를 해결하기 위해 작은 재귀 함수 호출
재귀 함수 호출 시 바로 답이 나오지 않고, 타고 타고 내려가서 바닥(최하위) 찍고 return&return해서 답(최종) 해결을 하니까 하향식
- 사용 조건
- 최적 부분 구조(Optimal Substructure): 부분 문제들의 ‘최적’의 답을 구해서, 이를 바탕으로 기존 문제의 ‘최적’의 답을 구할 수 있는 구조 -> 부분 문제가 전체 문제의 최적해라는 보장이 있는 구조
- 중복되는 부분 문제(Overlapping SubProblem): 동일한 작은 문제를 반복적으로 해결해야 하는 경우
- ex. 피보나치 수열 fibo(5)=fibo(3)+fibo(4)인데, 이 때 fibo(3)=fibo(1)+fibo(2), fibo(4)=fibo(2)+fibo(3)이라 fibo(2)가 여러 번 사용된다. 이런 케이스
-> 이렇게 DP 접근 방식은 특정 제한 사항이나 전제 조건이 있는 문제의 경우에만 적용될 수 있음
-04/04 토론 주제
1. 하노이의 탑은 DP인가 아닌가?
- 이전 값에 의존(활용)해서 해결하는 구조가 아니기 때문에, 즉 재활용하지 않는 구조이기 때문에 DP라고 볼 수 없을 것
- 하위 문제들의 최적의 값이 아닌, 특정 규칙에 의한 유일한 값이기 때문에 DP라고 볼 수 없는 것
- Memoization이 불필요한 계산을 하지 않는다?
- Memoization은 호출할 때 입력 값에 대해 (이전에 계산되어있지 않다면) 결과를 저장하기 때문에, 불필요한 연산을 하지 않는다
- 그에 비해 Tabulation은 계산에 필요하지 않을 수도 있는, 모든 가능한 경우의 수에 대해 미리 계산에 저장해놓고, 저장한 값을 필요로 할 때 사용한다.
- ex. index[1], [2]…[6]이 있음 -> [6]을 만들기 위해 [3]을 두 개 쓰면 될 때, [4][5]를 굳이 계산하지 않는 느낌?!
