알고리즘 - 동적계획법(Dynamic Programming)

동적 계획법

동적 계획법(Dynamic Programming)이란 하나의 큰 문제를 여러 개의 작은 문제로 나누고, 그 작은 문제의 결과를 큰 문제의 해결을 위해 사용하는 방법을 말한다.

사용 이유

DP는 재귀와 유사한 방법이다. 하지만 단순히 재귀를 사용하면 똑같은 문제들이 반복되어 비효율적인 계산이 이루어지게 된다. 동적 계획법은 이전 계산을 결과를 저장하여 사용하기 때문에 시간복잡도를 크게 개선할 수 있다.

사용 조건

DP는 두 가지 조건을 만족할 때 사용할 수 있다.

1) Overlapping Subproblems(겹치는 부분 문제)
2) Optimal Substructure(최적 부분 구조)

1) 겹치는 부분 문제

동적 계획법에서는 작은 문제를 해결한 값을 저장하여 사용하는 방식이다. 따라서 겹치는 작은 문제가 존재하지 않는다면 사용할 수 없다.

2) 최적 부분 구조

부분 문제의 최적 결과 값을 통해서 큰 문제의 최적 결과를 낼 수 있는 경우를 의미한다. 가령 최단 경로 문제를 생각해볼 때,
A-B-C의 루드에서 A-C의 최단 경로는 A-B의 최단 경로 + B-C의 최단경로이다. 이처럼 부분 문제의 최적 결과값이 큰 문제의 최적 결과 값을 위해 사용되어도 문제가 없어야 한다.