[자료구조] 동적계획법

동적계획법 (Dynamic Programming, DP)

동적 계획법은 처음 진행되는 연산을 기록해두고, 이미 진행했던 연산이라면 다시 연산하는 것이 아니라 기록되어 있는 값을 가져오는 것을 의미한다.

 

제일 쉽게 예로 들수 있는 것이 피보나치 수열 구하기 이다.

피보나치 수열을 구할 때 제일 쉽게 떠올릴 수 있는 것은 재귀함수로 푸는 것이다.

 

하지만 재귀로 풀게되면, 이전 숫자를 더하는 계산부가 중복으로 작동하기 때문에, 시간적 손실이 크다.

따라서 이전 계산 결과를 저장해두고 사용하는 동적계획법이 훨씬 시간 복잡도를 낮추는 것에 도움이 된다.

 

보통 동적 계획법을 사용하는 문제는, 공통된 계산 과정을 찾아내서 진행하는 편으로,

예전 수학을 배웠을 때 기억을 떠올려보면, 점화식으로 문제를 푸는 것과 비슷하다.

---

동적 계획법은 모든 방법을 일일히 검토해서 최적의 해를 찾아내는 방식의 알고리즘이다.

모든 방법을 검토해보고 결과적으로 효율적인 값을 택하기 때문에, 항상 최적의 해를 구할 수 있는 방법이다.

 

이와 대조되는 것이 그리디 알고리즘(탐욕법)인데, 순간 순간의 최적만 고려하기 때문에 동적계획법에 비해 시간이 빠를 수는 있으나, 항상 최적의 해가 보장되지는 않는다.

 

---

다음의 문제들을 통해 동적 계획법을 연습해볼 수 있다.

 

https://programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기