알고리즘/DP
2020. 4. 24.
동적 계획법 (Dynamic Programming)
동적 계획법 (이하 DP)은 큰 문제를 분할하여 부분 문제들로 만든 다음, 각 부분 문제의 답으로부터 전체 문제의 답을 이끌어내는 방식의 알고리즘입니다. 그런데 이 정의 어디에서 본 적이 있는 것 같습니다. 그렇습니다. DP도 일종의 분할 정복 알고리즘이라고 할 수 있습니다. 다만 일반적인 분할 정복 알고리즘과는 다른 점이 있습니다. 그것은 바로 DP는 부분 문제들이 독립적이지 않다는 점입니다. 다시 말하면, DP는 서로 겹치는 부분 문제가 존재할 때 쓸 수 있는 알고리즘입니다. 문제를 나눠서 푸는데 어떻게 부분 문제들이 겹칠 수 있을까요? 가장 쉬운 예를 살펴봅시다. https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 문제 피보나치 수는 0과 1로 시작한다. ..
