728x90
다이나믹 프로그래밍은 메모이제이션을 사용해 이전에 사용한 값을 그대로 읽어 사용함으로서 극적으로 줄일 수 있다. 여기서 메모이제이션의 개념을 보면 마치 캐시 와 비슷해보인다. 그래서 혹자는 캐시질이라고도 한다.
Top - Down
큰 숫자에서 작은 숫자까지 내려가면서 솔루션을 구하는 방법이다.
rec(N){
dp[N] = min(rec(N - 1), rec(N - 2))
}
Bottom - Up
작은 숫자부터 시작하며 다음 숫자에서 이전의 값을 사용하는 정석적인 dp 방식이다. 주로 점화식을 찾아서 적용시킬 때 사용된다.
for(int i = 2; i <= 10; i++){
dp[i] = dp[i - 1] + dp[i - 2];
}
'CS > 자료구조,알고리즘' 카테고리의 다른 글
누적합 알고리즘(1차원, 2차원 누적합) (0) | 2024.06.22 |
---|---|
최소 스패닝 트리 (MST) - 크루스칼 알고리즘 (1) | 2024.06.13 |
알고리즘 - 에라토스테네스의 체(C++) (0) | 2024.04.22 |
unordered_map을 이용한 노드 개수 최적화 (0) | 2024.02.07 |
문자열 찾기 - KMP 알고리즘 (0) | 2024.01.26 |