spicykong   2년 전

'최적 부분 구조'와 '탐욕적 선택 속성'이 성립할 때 그리디 알고리즘을 사용해 최적해를 얻을 수 있다고 배웠는데요. 

연습 삼아 이 문제로 해당 두 조건이 성립함을 보이려다가 '최적 부분 구조'가 성립함을 어떻게 보여야 할 지 모르겠어서 질문 드립니다. 추가적으로 아래 '탐욕적 선택 속성'이 성립함을 저런 식으로 보여도 되는지 여쭈어 보고 싶습니다.

우선 탐욕적 선택 속성이 성립함은 다음과 같이 보였습니다.

가능한 높은 가치의 동전을 선택하지 않는 경우, (각 동전들의 가치는 배수 관계에 있으므로) 항상 높은 가치의 동전을 사용하는 것 보다 많은 개수의 동전을 사용하게 됩니다. 따라서 가능한 높은 가치의 동전을 선택하는 것이 최적해에 포함됨을 알 수 있습니다.

최적 부분 구조는 f(x): x원을 표현할 때 드는 최소 동전의 개수라 정의할 때, f(2700) = f(500) + f(2200)이 성립함은 너무 당연해 보이는데, 직관을 어떻게 논리로 서술할 수 있을지 잘 모르겠습니다..ㅎㅎ

댓글을 작성하려면 로그인해야 합니다.