다이나믹 프로그래밍
-
2. 다이나믹 프로그래밍(DP)PS 입문 2023. 6. 22. 16:01
다이나믹 프로그래밍을 간단히 말하면, 주어진 문제보다 작은 문제를 풀어놓고 그것을 통해서 큰 문제를 풀어내는 방식의 알고리즘이다. 간단한 예시로는 점화식이 주어진 수열의 특정 항의 값을 구하는 문제가 있다. 잘 알려진 수열 중 피보나치 수열을 생각해보자. 피보나치 수열의 점화식은 다음과 같다. $F_0=F_1=1, F_n=F_{n-1} +F_{n-2} (n \geq 2)$ 이때 "피보나치 수열의 10번째 항($F_{10}$)을 구하시오"라는 질문에 대답하기 위해서는 종이에 "1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89"를 적게 된다. 구현 방식은 사람마다, 상황마다 다를 수 있지만 DP로 문제를 풀 때는 기본적으로 위와 같은 알고리즘을 작성하게 된다고 생각하면 편하다.실제 문제를 보..