최적 부분 구조(Optimal Substructure)

최적 부분 구조

 

- 각 부분 문제의 최적해만 있으면 전체 문제의 최적해를 쉽게 얻어낼 수 있을 경우 최적 부분 구조 조건을 성립한다고 한다. 

 

(예시)

- 서울에서 부산을 가는 최단 경로의 경우 이 최단 경로가 대전을 지난다고 가정한다. 이 때, 최단 경로는 (서울, 대전)의 최단경로, (대전, 부산)의 최단 경로를 찾아서 이으면 구할 수 있다. 즉 부분문제를 통해 전체의 최적해를 구할 수 있으므로 이는 최적 부분 구조라고 할 수 있다.

 

 

 

최적 부분 구조가 존재하지 않을 경우

 

-  서울에서 부산으로 향하는데 고속도로의 통행료 합이 3만원을 초과하지 않는 최단경로를 찾을 때, 대전에서 부산으로 가는 경로가 2가지 있다. 

 

	통행 시간	통행료
경로 A	2 시간	1만원
경로 B	1 시간	2만원

 

 - 이 두 경로 중 어느 쪽을 택해야 할지는 서울-대전 구간의 통행료에 따라 결정된다. 이 경우, 부분 문제의 최적해가 전체 문제의 최적해로 연결되지 않을 수 있으며, 따라서 최적 부분 구조가 존재하지 않는다. 

 

 

 

 

예시

 

- 최대 증가 부분 수열(LIS, Longest Increasing Subsequence)

 

j	0	1	2	3	4	5	6	7
A[j]	3	2	1	7	5	4	2	6

 

Sol 1. 만약 특정한 A[j]를 첫 숫자로 골랐다고 하면 A[j]에서 시작하는 증가 수열 중 가장 긴 증가 수열을 찾기 위해 A[j+1]부터 시작하는 부분 수열에서 A[j]보다 큰 숫자들만 고른 부분 수열 B를 만들고 B의 LIS를 재귀 호출로 계산한다.

 

-> 이중 for문을 이용한 완전탐색으로 메모이제이션을 적용하기 어렵다.

 

 

 

 

 

 

 

출처 : 프로그래밍 대회에서 배우는 알고리즘 문제해결전략