동적 계획법

[Algorithm] DP(Dynamic Programming), 동적 계획법

다이나믹 프로그래밍(Dynamic Programming)은 동적 계획법이라고도 불린다. 이 알고리즘은 똑같은 연산을 계속 반복하지 않고, 한 번의 풀이만으로 해결하고자 하는 알고리즘이다. 큰 문제 하나를 여러 개의 작은 문제로 나누어서 해결하고자 하는 방법이다. ❗ 분할 정복 vs. 다이나믹 프로그래밍 둘의 공통점은 큰 문제 하나를 여러 개의 작은 문제로 나누어서 해결한다는 것이다. 분할 정복과 다이나믹 프로그래밍의 차이점은 DP의 경우, 나누어진 부분 문제가 중복되기 때문에, 재활용할 수 있다는 것이다. 분할 정복의 경우, 나누어진 부분 문제가 중복되지 않는다. ❗ 탑다운(Top-Down) vs. 바텀업(Bottom-Up) 탑다운 방식은 큰 문제를 해결하기 위해서 작은 문제를 호출하며 풀어나가는 방식 ..