목록9095번 (1)

john8538 님의 블로그

백준-9095번 1,2,3 더하기

https://www.acmicpc.net/problem/9095DP란?Divide-And-Conquer : Top-down approach나누어진 부분들 사이에 서로 상관관계가 없는 문제를 해결하는데 적합피보나치 알고리즘의 경우에는 나눈어진 부분들이 서로 연관이 있다.즉, 분할정복식 방법을 적용하여 알고리즘을 설계하게 되면 같은 항을 한 번 이상 계산하는 결과를 초래하게 되므로 효율적이지 않다. 따라서 이 경우에는 분할정복식 방법은 적합하지 않다. Dynamic programming: bottom-up approach큰 문제를 작은 문제로 나눈 다는 점은 Divde-And-Conquer와 동일하다.그러나 작은 문제를 먼저 해결하고, 그 결과를 저장한 다음, 후에 그 결과가 필요할 때마다 다시 계산하는 ..
백준 & 알고리즘 2024. 8. 16. 02:40
이전 Prev 1 Next 다음