DP 정복 - 2.1 최적의 하위 구조

앞 장에서 재귀 호출의 개념과 효율성에 대해 살펴봤는데

재귀 호출은 실행 시간 및 메모리 관점에서 좋은 풀이법이 아니라는 사실을 설명했다.

 

이번장에서는 재귀 접근 방식이 가지는 두 특징인 '최적의 하위 구조'와 '하위 문제의 반복 계산'에 대해 알아본다.

또한 재귀 호출 과정에서 하위 문제를 반복 계산함으로써 생기는 비효율을 줄이기 위한 '메모 전략'도 소개한다.

 

최적의 하위 구조

- n개의 원소를 가지는 문제가 있을 때(크기가 n인 문제)

- 이 문제를 풀 때 형태는 같지만 n 미만의 원소를 가지는 더 작은 크기의 문제의 풀이법을 사용한다면

- 이를 최적의 하위 구조 특성을 갖는 문제라고 함.

예를 들어 1부터 10까지의 합을 구하는 경우(10이 n)

1부터 9까지의 합을 더한 값에 10을 더하는 문제(sum(1, n-1) + n)

1부터 8까지의 합을 더한 값에 9를 더한 값에 10을 더하는 문제(sum(1, n-2) + n-1 + n)

...으로 최적의 하위 구조 특성을 갖는 문제라고 볼 수 있다.

(* 책에서는 다른 예제를 듦)

 

- 최적의 하위 구조 특성은 DP로 풀어야 할 조건 중 하나. 나머지 하나는 '하위 문제의 반복 계산' (다음 절에 설명)

- 플로이드-워셜, 벨먼-포드 알고리즘 같은 전체 쌍 최적 경로 찾기에 대한 표준 알고리즘은 DP의 전형적인 예

 

DP의 첫 번째 단계 : 어떤 문제의 점화식을 작성하거나 최적의 하위 구조를 정의하는 것

DP와 관련된 문제가 주어지면 : 점화식 또는 재귀 접근 방식을 사용해 문제를 푼 다음, 같은 로직을 사용해 DP의 관점인 상향식으로 접근하는 것을 추천.