탐욕 알고리즘(Greedy Algorithm)

김소정·2022년 7월 29일

Algorithm

목록 보기

2/3

Greedy Algorithm

그리디 알고리즘은 단순하면서도 강력한 알고리즘이다. 이름과 같이 탐욕적으로 문제를 푸는 알고리즘이다. 여기서 탐욕적이라는 것은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.

매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는 것이 가장 큰 특징이다. 따라서 순간마다 하는 선택은 지역적으로는 최선이자 최적이지만, 최종적인 결과 도출에 대한 최적해를 보장할 수는 없다.

그리디 알고리즘 유형의 문제는 주로 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력, 즉 창의력을 요구한다. 따라서 특정한 문제를 만났을 때 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악할 수 있어야 한다.

조건

그리디 알고리즘을 사용하기 위해 필요한 조건은 2가지이다.

탐욕적 선택 속성(Greedy Choice Property)
앞의 선택이 이후의 선택에 영향을 주지 않는다.
최적 부분 구조(Optimal Substructure)
문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

위 두가지 조건을 만족하면 우리는 그리디 알고리즘을 사용하여 최적해를 도출할 수 있다. 따라서 그리디 알고리즘을 사용하기 이전에, 위 조건들을 만족하는가(그리디 알고리즘을 사용하여 최적해를 도출할 수 있는가)를 확인해야 한다.

문제

1) 거스름돈

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

풀이

동전을 최대한 적게 이용하여 거스름돈을 주기 위해서는 '가장 큰 화폐 단위'부터 돈을 거슬러 줘야 한다. 즉 매 순간 남은 거스름돈보다 크지 않은 단위 중 가장 큰 단위의 동전을 선택하는 것이 지역적으로 최적의 선택인 동시에 전역적으로 최적해를 구할 수 있는 방법이다.

ex. N = 1260

1260보다 크지 않은 500의 배수 중 최댓값은 1000이다. 따라서 500원짜리는 최대 2개 사용할 수 있다.
260보다 크지 않은 100의 배수 중 최댓값은 200이다. 따라서 100원짜리는 최대 2개 사용할 수 있다.
60보다 크지 않은 50의 배수 중 최댓값은 50이다. 따라서 50원짜리는 최대 1개 이용할 수 있다.
10보다 크지 않은 10의 배수 중 최댓값은 10이다. 따라서 10원짜리는 최대 1개 이용할 수 있다.
따라서 N이 1260일 때 손님이 받은 최소 동전 개수는 6개이다.

500 100 50 10
2 2 1 1

500	100	50	10
2	2	1	1

코드

n = 1260
count = 0

# 큰 단위의 화폐부터 차례대로 확인
coin_types = [500, 100, 50, 10]

for coin in coin_types:
  count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전 개수
  n %= coin # 남은 돈

print(count)

화폐의 종류만큼 반복을 수행해야 하기에, 화폐의 종류가 $K$ 개라고 할 때 시간 복잡도는 $O(K)$ 이다.

2) 1이 될 때까지

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려 한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.

N에서 1을 뺀다.
N을 K로 나눈다.

예를 들어 N이 17, K가 4라고 가정하자. 이 때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 된다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 된다. 이는 N을 1로 만드는 최소 횟수이다.

N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(2 ≤ N ≤ 100,000)과 K(2 ≤ K ≤ 100,000)가 공백으로 구분되며 각각 자연수로 주어진다. 이 때 입력으로 주어지는 N은 항상 K보다 크거나 같다.

출력

첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.

풀이

어떠한 수가 있을 때 1을 빼는 방법(1번) 보다는 2 이상의 어떤 수로 나누는 방법(2번)이 훨씬 빨리 1에 도달하게 만들어준다. 따라서 이 문제에서는 '최대한 많이 나누는 것'이 최선의 솔루션이다.

예를 들어 N = 25, K = 3이라면

단계	연산 과정	N의 값
0단계		25
1단계	N에서 1 빼기	24
2단계	N을 K로 나누기	8
3단계	N에서 1 빼기	7
4단계	N에서 1 빼기	6
5단계	N을 K로 나누기	2
6단계	N에서 1 빼기	1

6번의 과정으로 N을 1로 만들 수 있다. 위 예시에서도 알 수 있듯이, 1을 빼는 것 보다 K로 나누는 것이 N이 더 빠른 속도로 1에 가까워지게 만들어준다. 그러므로 K로 최대한 많이 나누는 것이 곧 최적해를 보장하는 방법이다.

코드

# 방법 1

n, k = map(int, input().split())
result = 0

while n >= k:
  while n % k != 0:
    n -= 1
    result += 1
  n //= k
  result += 1
  
while n > 1:
  n -= 1
  result += 1
  
print(result)

문제에서는 N의 범위가 한정되어 있으므로, 위 소스코드와 같이 일일이 1을 빼도 문제를 해결할 수 있다. 하지만, N의 범위가 한정되어 있지 않다면 위 코드 소스는 계산량이 비효율적으로 늘어나며, 결국 시간 초과가 발생할 가능성이 높다.

따라서 N의 값에 관계 없이 코드가 빠르게 동작하려면, N이 K의 배수가 되도록 효율적으로 한 번에 뺴는 방식으로도 코드를 작성할 수 있다.

# 방법 2

n, k = map(int, input().split())
result = 0

while True:
  target = (n // k) * k
  result += (n - target)
  n = target
  if n < k:
    break
  result += 1
  n //= k

result += (n - 1)
print(result)

N이 K로 나누어떨어지는 수가 될 때까지 1씩 빼준다.
K로 나눈다.
N이 K보다 작아지면 더 이상 K로 나눌 수 없으므로 반복문을 탈출한다. (if문)
남은 수에 대하여 1씩 뺀다. (result += (n - 1))

위와 같이 소스코드를 작성하면 1을 반복하여 뺄 필요 없이, 필요한 만큼 한번에 계산해주기 때문에 동작이 빨라지며 효율성 측면에서도 뛰어나다.

정당성

그리디 알고리즘을 모든 알고리즘 문제에 적용할 수 있는 것은 아니다. 앞서 제시한 두가지 조건을 만족하는 문제에서만 직관적이고 효과적인 해결책을 제시할 뿐, 이 외의 문제들에서는 최적해를 찾을 수 없을 가능성이 높다.

따라서 그리디 알고리즘으로 문제를 해결했을 때는 해당 솔루션이 정당한지 검토해봐야 한다. 위의 거스름돈 문제는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문에 그리디 알고리즘을 사용하여 최적해를 도출할 수 있는 것이다.

그리디 알고리즘을 이용하면 다이나믹 프로그래밍보다 수행 시간이 단축되고 직관적이기 때문에 효율적이며, 시간이나 공간적 제약으로 인해 다른 방법으로 최적해를 찾기 어려운 경우 최적해가 아닌 근사해를 찾는 방법으로 사용되기도 한다. 하지만 DP와 달리 모든 선택지를 고려하지 않기 때문에 정당성 증명을 통해 결과 값이 최적임을 증명해야 한다.

앞서 다이나믹 프로그래밍 포스팅에서 다룬 효율적인 화폐 구성 문제 같은 경우는 그리디 알고리즘으로는 해결할 수 없는 문제이다. 따라서 어떠한 문제를 만났을 때는 그리디 알고리즘을 이용하여 해당 문제를 해결할 수 있는지 생각해보고, 해답을 찾기 어렵다면 다이나믹 프로그래밍이나 그래프 알고리즘 등의 여러 방법들을 고민해보는 것이 좋다.