[알고리즘] 최적 부분 구조

최적 부분 구조란, 

" 부분 문제의 답을 이용해서 기존 문제의 답을 구할 수 있는 구조"를 가진 구조이다. 

 

예를 들어, 총 5개의 새콤달콤을 팔려는 영희가, 1개에는 100원, 2개에는 400원, 3개에는 800원, 4개에는 900원 , 5개에는 1000원에 팔고자 하고, 이 수익을 최대화 하는 전략을 고민하는 문제가 있다고 하면, 

 

5개를 갖고 최대 수익을 내는 방법
1. 4개를 갖고 최대 수익을 내는 방법 + 1개를 갖고 최대 수익을 내는 방법
2. 3개를 갖고 최대 수익을 내는 방법 + 2개를 갖고 최대 수익을 내는 방법
3. 5개를 한명에게 팔았을 때의 수익 

과 같이 구분 지을 수 있다. 

 

3번의 경우에는 심플하지만 1, 2번의 경우 결국 4개를 갖고 최대 수익을 내는 방법은 2개, 2개씩 혹은 3개, 1개씩 등으로 쪼개어서도 생각할 수 있고 이런 경우에는 결국 1개부터, 2개, 3개 쭉쭉 부분문제부터 생각해보면서 답을 구하는 문제이다.