What is it
- 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해 보다 큰 크기의 부분 문제를 해결. 최종적으로 전체 문제를 해결하는 알고리즘
- 상향식 접근법으로, 가장 최하위 해답을 구한 후 이를 저장. 해당 결과값을 이용해 상위 문제를 풀어가는 방식
- Memoization 방식을 사용함
- Memoizaion? 프로그램 실행 시 이전에 계산한 값을 어딘가에 메모해놓고 다시 계산하지 않도록해 전체 실행 속도를 빠르게 하는 기술
- 문제를 잘게 쪼갤 때 부분 문제는 중복되어 재활용된다(피보나치 수열 등)
분할 정복(Divide and Conquer)과의 차이점
분할 정복은 큰 문제를 해결하기 어려워 단지 작게 쪼개어 푸는 방법.(Memoization 기법 사용 X)
작은 문제에서 반복이 일어나지 않는다.
반면 DP는 작은 부분 문제들이 반복(중복)되어 값이 재활용된다
Dynamic Programming의 조건
- 작은 문제의 반복이 일어나는 경우
- 같은 문제는 구할때마다 같은 정답
How to works it
- 구하고자 하는 큰 문제를 작은 부분 문제로 나눈다
- 가장 작은 부분 문제(종료 조건, 주로 0또는 1일때)부터 푼 뒤 값을 저장한다 -> Memoization
- Memoization 된 부분 문제들의 해를 이용해, 차례로 더 큰 상위 문제의 답을 구한다
- 3과정을 가장 큰문제(최종 얻으려는 값)에 도달할때까지 반복한다
Let's Make it Code
피보나치 수열을 재귀호출과 DP를 이용해서 각각 구현해보자
재귀호출로 구현
func fiboRecursive(_ num: Int) -> Int {
if num <= 1 { return num }
return fiboRecursive(num - 1) + fiboRecursive(num - 2)
}
fiboRecursive(10) //55먼저 재귀호출을 이용해서 피보나치 수열을 만드는 함수를 구현해보았다.
들어오는 값이 작으면 여러번 반복되어도 공간복잡도 면에서 크게 상관 없겠지만, 아주 큰 숫자가 들어온다고 했을 때 재귀호출을 이용하는 것은 이전에 계산했던 값을 재활용 하지 않고 또 계산하므로 비효율적이다.
그럼 이번엔 DP를 이용한 코드를 함께 보자
DP로 구현
func fiboDP(_ num: Int) -> Int {
var memo: [Int] = []
for index in 0..< num + 1 { memo.append(0) } //#1
memo[0] = 0
memo[1] = 1 //#2
for index in 2..< num + 1 {
memo[index] = memo[index - 1] + memo[index - 2] //#3
}
return memo[num]
}
fiboDP(10) //55- 입력된
num만큼 0으로 채워진 배열을 생성한다 - 가장 작은 부분 문제의 값을 저장한다(피보나치 수열의 시작값 지정)
- 얻고자 하는 값까지 반복해서 수행한다
이전에 계산했던 값을 memo라는 배열에 저장해두고, 그것을 필요할 때 다시 이용하므로 재귀 방법보다 함수 호출을 줄일 수 있다.
Dynamic Programming 방법은 퀵 정렬, 병합 정렬 등 보다 복잡한 알고리즘에 자주 사용되므로 꼭 알아둬야 할 개념이었다
References
🌐Code makes world better