[알고리즘] DP 다이내믹 프로그래밍 Dynamic Programming

동적 프로그래밍

DP(Dynamic Programming) 는 예전에 학교 알고리즘 시간에도 배웠지만, 잘 이해가 가지않아서 따로 다시 공부를 하려고 알고리즘 강의를 보게되었다.

이 글은

을 보면서 혼자 정리한 글이다.

문제 해결 방법

• Brute-Force Approach
• Divide And Conquer Approach
• Dynamic Programming Approach
• Greedy Approach

=> 특별히 어떤 알고리즘이 좋다고 할 수는 없다. 상황에 맞는 접근 방법을 사용하자!

DP 특징

• 주어진 문제를 하위로 나누어서 해결

• 문제를 작은 단위로 쪼개어서 생각한다는 것은 Divide and Conquer랑 비슷하지만 문제간의 관계가 다름.

  (하위 문제 끼리 종속성을 가지면 DP를 사용하는 것이 좋다.)

흐름

1. 모든 하위 문제를 푼다.
2. 이러한 결과를 저장한다.
3. 저장된 결과를 다음 단계의 문제를 해결하는데 사용한다.

이러한 흐름 때문에 최적화 문제를 풀 때 사용된다.

최적화 문제란?

가능한 해답이 무수히 존재하며, 각각의 해답은 숫자 등의 크기가 있는 값을 가짐.
가장 크거나 가장 작은 최적의 값을 가지는 해답을 찾을 수 있고, 그런 해답을 최적화 문제의 "최적해" 라고 부른다.

즉, 최적화 문제란 문제의 답이 서로 비교 가능해야하고, 목적에 따라 가장 좋은 결과를 찾아야 하는 문제.

예) 최단경로 문제, 가방에 물건을 담는 문제 등등

동적 계획법을 사용하면 보통 가중치를 많이 구하는 문제가 나오는 데, 이러한 답안이 나오게된 경로를 알아내야하는 문제에서는 보통, 맨 뒤의 결과값부터 역으로 하나씩 추적해나가면 경로를 구할 수 있다.