DP 정복 - 3.1 다이내믹 프로그래밍이란?

다이내믹 프로그래밍 : 문제를 푸는 전략 중 하나. 위키피디아에서는 '복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법'이라고 정의

 

메모 전략도 일종의 다이내믹 프로그래밍. 그러나 이번에 소개할 다이내믹 프로그래밍은 '상향식'이다.

 

내가 예전에 다른 책을 봤을 때 완전 탐색(재귀 호출을 이용한) 후에 메모 전략을 소개했어서 DP도 같은 '하향식' 형태인지 알았는데 이 책의 소개를 보고 다른 것임을 깨달음.

 

다이내믹 프로그래밍의 주 적용 대상

- 최적의 하위 구조 특성을 갖고 있으며

- 하위 문제를 반복해서 계산하는 복잡한 문제들

 

그러나 다이내믹 프로그래밍 방법은 직관적인 접근 방법이 아니기에 매우 복잡한 문제를 적용하기 쉽지 않음.

때로는 하위 문제의 반복 계산 여부가 명확지 않아서 재귀적인 풀이법이 없는 것처럼 보일 때도 있음.

 

다음으로 가장 긴 부분 문자열 구하기의 예를 소개하며 다음과 같은 사실을 알려준다.

1. 가장 직관적인 해결 방법이 반드시 재귀 호출을 사용해야 하는 것은 아님.

2. 가장 직관적인 해결 방법이 반드시 지수 시간의 시간 복잡도인 것은 아님.

 

O(N^3)의 시간 복잡도를 갖는 직관적인 해결 방법을,

DP를 통해 O(N^2)의 시간 복잡도와 O(N^2)의 추가 메모리를 사용하도록 개선하는 예를 보여줌.

 

간단한 예였지만 역시 이해하기는 어려운 DP ㅠㅠ