[C++] 그리디 알고리즘(1) - 동전 문제와 주의 사항

본 게시글은 "Competitive Programmer's Handbook"을 보며 임의로 해석하며 공부한 내용입니다.

 

Greedy algorithms

그리디 알고리즘은 항상 그 순간에 가장 좋아보이는 선택을 함으로서 문제에 대한 해결책을 만든다.

 

그리디 알고리즘은 선택을 되돌리지 않고, 최종 솔루션을 직접 구성한다.

그러므로 그리디 알고리즘은 매우 효율적이다.

 

하지만, 설계 시 어려운 점은 문제에 대한 최적의 해결책을 제시하는 전략을 찾는 것이다.

 

 

[대표 문제] Coin 문제

동전의 종류가 주어졌을 때, 동전을 사용하여 돈의 합계를 만드는 것이다. 동전의 가치는 coins = {c1, c2, c3, ...} 와 같이 주어지며, 동전 한 개당 원하는 횟수만큼 사용할 수 있다. 이때 필요한 최소 동전의 수는 몇 개 인가?

 

Q. 동전 종류는 {1, 2, 5, 10, 20, 50, 100, 200}, n=520 일때, 동전의 합이 n이 되기 위한 최소 동전의 수는 몇 개인가?

A. 최적의 선택은 200+200+100+20 이다.

 

화폐 가치가 가장 큰 동전부터 선택하여 합계를 만드는 것이 가장 효율적이다. 왜 그럴까?

 

1. {1, 5, 10, 50, 100} appears at most once in an optimal solution

    - 5 + 5 = 10

    - 50 + 50 = 100

 

2. {2, 20} appear at most twice in an optimal solution

    - 2 + 2 + 2 = 5 + 1

    - 20 + 20 +20 = 50 +10 

 

3. optimal solution cannot contain this.

    - 2 + 2 +1 = 5 

    - 20 + 20 + 10 = 50

 

결과적으로 각 코인 x에 대해 x보다 작은 코인 만을 사용하여 최적의 합계를 만드는 것은 불가능하다.

따라서 항상 가장 큰 코인을 선택하는 그리디 알고리즘이 최적의 솔루션을 만들어 낸다.

 

주의 사항

 

동전 종류는 어떠한 동전도 포함 가능하기 때문에, 그리디 알고리즘이 무조건 최적의 솔루션을 만들어낼 수는 없다.

 

Q2. 예를 들어, 동전 종류 {1,3,4}이고, 목표 합계가 6인 경우를 살펴보자.

 

앞선, 그리디 알고리즘과 같이 큰 동전을 우선 선택한다면, "4+1+1"이 나온다.

하지만 최적의 솔루션은 "3+3" 이다.

 

이와 같이 그리디 알고리즘이 무조건 동전 문제에 대해 해결하진 않는다.

때론, 동적프로그래밍 알고리즘이 효과적일 수 있다.