그리디 알고리즘이라고도 불리는, 매 순간 최선의 선택을 하는 탐욕법에 대해 알아봅시다.

탐욕법

• 매 순간 현재 상황에서 가장 좋아 보이는 선택 (탐욕적 선택)을 반복하는 알고리즘
• 탐욕법으로 문제의 정답(최적해)이 보장되는 경우도 있고, 보장되지 않는 경우도 있음
• 따라서 문제에 탐욕법을 적용할 수 있는지 판단하는 것이 중요함
  • 단순히 빠른 선택을 하는 만큼 시간 복잡도가 낮은 편이지만
  • 엉뚱한 답을 낼 수도 있음
• 특히 비슷한 문제 같아 보여도, 약간의 조건 차이 때문에 탐욕법을 쓸 수 있는 / 없는 경우가 나뉠 수 있음에 유의할 것

거스름돈 문제

탐욕법을 사용할 수 있는 경우

• 500원, 100원, 50원, 10원짜리 동전이 무한히 존재함
• 위 동전으로 $N$원을 만들 때, 필요한 최소한 동전 수를 구하는 문제
• 정답을 구하는 방법: 가장 큰 화폐 단위부터 있는 대로 사용하기

예시

• 1260원을 만들 때 -> 최소 동전 6개 필요

단위	몇 개?	남은 돈
500원	2개	$1260 - 500 \times 2 = 260$
100원	2개	$260 - 100 \times 2 = 60$
50원	1개	$60 - 50 \times 1 = 10$
10원	1개	$10 - 10 \times 1 = 0$
계	6개

• 가장 큰 단위부터 사용하는 것이 최적해를 보장하는 이유
  • 큰 단위가 항상 작은 단위의 배수이므로, 큰 단위를 먼저 쓰는 것이 무조건 이득
    • 500원 = 100원 5개
    • 100원 = 50원 2개
    • 50원 = 10원 5개
  • 500원을 놔두고 굳이 100원 5개를 쓸 이유는 없음

구현

N = 1260
coins = [500, 100, 50, 10]
answer = 0

for c in coins:
    answer += N // c    # 현재 사용한 동전 수를 정답에 추가
    N = N % c           # 동전 다 쓰고 남은 돈

if N <= 0:              # N원을 만드는 데 성공
    print(answer)
else:                   # N원을 만들지 못함
    print("FAIL")

# 결과: 6

• 동전의 종류가 $K$개일 때, 시간 복잡도는 반복문 순회하며 $O(K)$
• 일일이 $N$원을 만드는 모든 경우의 수를 따져보지 않아도 빠르게 풀 수 있음

탐욕법을 사용할 수 없는 경우

• 사용 가능한 동전의 단위가 500원, 400원, 100원일 때 800원 만들기
• 위 예시처럼 탐욕법 사용 시

단위	몇 개?	남은 돈
500원	1개	$800 - 500 \times 1 = 300$원
400원	불가능	$300$원
100원	3개	$300 - 100 \times 3 = 0$원
계	4개

• 하지만, 400원 2개로도 800원을 만들 수 있음
• 동전 단위가 배수를 이루지 않으므로, 탐욕법을 사용할 수 없음
  • 이럴 땐 동적 계획법을 사용해야 함

배낭 문제

• 무게와 금액이 다른 짐들을 배낭에 넣으려고 함
• 단, 배낭엔 일정 무게 이상은 담을 수 없음
• 배낭의 무게를 초과하지 않고서, 담은 금액을 최대로 하는 방법은?
• 본 글에서는 아래와 같은 예제를 사용함

짐 번호	무게	금액
A	10kg	1900원
B	7kg	1000원
C	6kg	1000원
배낭 최대 무게	15kg

탐욕법을 사용할 수 있는 경우

• 짐을 쪼갤 수 있는 경우
  • 예: 짐 A가 10kg에 1900원일 때, 5kg만 쪼개 넣을 수 있음
  • 쪼갤 수 있는 최소 단위는 1kg라고 가정
  • 이 경우 총 금액은 950원

• 1단계 짐별로 무게당 금액을 구하기
• 2단계 무게당 금액이 가장 높은 짐부터 넣기
  • 배낭의 남은 무게가 짐보다 크면, 넣을 수 있는 부분만 쪼개 넣기
• 3단계 배낭이 다 찰 때까지 반복

위 예제에 적용하면

번호	무게	금액	1kg당 금액
A	10kg	1,900원	$1900 \div 10 = 190$원
B	7kg	1,000원	$1000 \div 7 =$ 약 $142$원
C	6kg	1,000원	$1000 \div 6 =$ 약 $166$원
배낭 최대 무게	15kg

• 1kg당 금액이 높은 A(190) -> C(약 166) -> B(약 142) 순으로 넣기

넣을 짐	넣은 무게	넣은 금액	배낭의 남은 무게
A (10kg, 1900원)	10kg	1900원	$15 - 10 = 5$ kg
C (6kg, 1000원)	5kg	약 833원	$5 - 5 = 0$ kg
B (7kg, 1000원)	불가능		$0$ kg
총 금액	약 2,733원

• 무게당 금액이 가장 높은 짐부터 선택하면, 항상 최적해가 보장됨
  • 굳이 무게당 금액이 더 낮은 짐을 선택할 이유가 없음

코드

things = [(10, 1900), (6, 1000), (7, 1000)]
max_weight = 15
total_value = 0

# 무게당 금액이 높은 순으로 정렬
things.sort(key=lambda x: x[1] / x[0], reverse=True)

for weight, value in things:
    # 배낭에 공간이 남지 않은 경우
    if max_weight == 0:
        break

    # 안 쪼개고 다 넣을 수 있는 경우
    if weight <= max_weight:
        taken_weight = weight
        taken_value = value
    # 쪼개서 넣어야 하는 경우
    else:
        taken_weight = max_weight
        taken_value = value * (max_weight / weight)

    print(f"무게 {weight}kg, 금액 {value}원인 짐 중 {taken_weight}kg을 넣었습니다.")
    max_weight -= taken_weight
    total_value += taken_value
    print(f"남은 배낭 무게: {max_weight}")

print(f"총 금액: {total_value:.2f}원")

# 무게 10kg, 금액 1900원인 짐 중 10kg을 넣었습니다.
# 남은 배낭 무게: 5
# 무게 6kg, 금액 1000원인 짐 중 5kg을 넣었습니다.
# 남은 배낭 무게: 0
# 총 금액: 2733.33원

• 시간 복잡도: 짐의 개수가 $K$개일 때, 정렬에 $O(K \log K)$ 반복문을 돌며 $O(K)$
• 최종 $O(K \log K)$

탐욕법을 사용할 수 없는 경우

• 짐을 쪼갤 수 없는 경우
  • e.g., 짐 A가 10kg에 1900원일 때, 무조건 10kg를 다 넣거나, 아예 넣지 말아야 함

• 매번 무게당 금액이 높은 짐을 먼저 선택하는 경우 (탐욕적 선택)

넣을 짐	넣은 무게	넣은 금액	배낭의 남은 무게
A (10kg, 1900원)	10kg	1900원	$15 - 10 = 5$ kg
C (6kg, 1000원)	불가능		$5$ kg
B (7kg, 1000원)	불가능		$5$ kg
총 금액	1,900원

• 하지만 실제로는 B 7kg, C 6kg을 넣으면 2,000원
  • 즉 탐욕법으로 구한 해 1,900원은 최적해가 아님
• 이럴 땐 동적 계획법을 사용해야 함

탐욕법의 예시

• 사실 지금까지 배운 다양한 알고리즘도 탐욕법을 사용함
• 매번 탐욕적 선택을 반복하면, 최적해를 구할 수 있음

알고리즘	탐욕적 선택	설명 링크
크루스칼 알고리즘	최소신장트리에 포함되는 간선을 고를 때, 가중치가 가장 낮은 간선부터 확인	링크
다익스트라 알고리즘	매번 시작 노드로부터 거리가 가장 짧은 노드를 선택	링크

(참고) 탐욕법의 사용 가능 조건

• 어려운 표현을 사용하자면, 탐욕법은 탐욕 선택 속성과 최적 부분 구조 두 조건을 만족해야 사용할 수 있음
• 직관적으로 파악하기 어려우니, 이런 게 있다 정도만 알아둘 것

탐욕 선택 속성

• 현재 탐욕적 선택을 해도, 나중에 문제를 최적으로 해결하는 데 방해가 되지 않아야 함
• e.g., 1260원을 500원, 100원, 50원, 10원으로 만들기
  • 500원 2개를 먼저 쓰고, 남은 260원도 계속 큰 단위 동전을 선택하면 최적해를 만들 수 있음
• e.g., 800원을 500원, 400원, 100원으로 만들기
  • 500원 1개를 먼저 써 버리면, 400원 2개로 800원을 만들 수 없음

최적 부분 구조

• 문제를 부분 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음
• e.g., 1260원을 700원 / 560원으로 나눠서 500원, 100원, 50원, 10원으로 만들기
  • 700원 = 500원 x 1 + 100원 x 2 -> 동전 3개
  • 560원 = 500원 x 1 + 50원 x 1 + 10원 x 1 -> 동전 3개
  • 합쳐서 총 6개의 동전이 필요한데, 이는 1260원을 만드는 문제의 최적해와 동일

문제풀이

11047. 동전

백준 / 실버 4 / 11047. 동전

• 앞선 거스름돈 문제와 동일. 하지만 높은 단위부터 확인해야 하니 정렬을 잊지 맙시다.
• 시간복잡도는 동전 수가 $N$개일 때 $O(N \log N)$ (정렬 과정에서)

N, K = map(int, input().split())
coins = []
answer = 0

for _ in range(N):
    coins.append(int(input()))

# 단위 내림차순으로 정렬
coins.sort(reverse=True)

# 필요한 동전의 수 계산
for c in coins:
    answer += K // c
    K = K % c
    
print(answer)

1541. 잃어버린 괄호

백준 / 실버 2 / 1541. 잃어버린 괄호

• 일단 눈에 보이는 덧셈 연산을 모두 처리하고, 그 다음에 뺄셈 연산을 처리하기
• $A - B$에서 $B$가 클수록 결과가 작아짐
  • 즉 뺄셈 기호 뒤에 나오는 수들은, 전부 더해서 크게 만든 뒤 한꺼번에 빼면 최소값이 됨
• 이것이 현재 가장 최적인 선택이므로 탐욕법

# 뺄셈 기호를 기준으로 나누기
plus_list = list(input().split("-"))

minus_list = []
# 모든 더하기 연산 처리
for p in plus_list:
    minus_list.append(sum(map(int, p.split("+"))))
    
# 모든 빼기 연산 처리
answer = minus_list[0]
for i in range(1, len(minus_list)):
    answer -= minus_list[i]
print(answer)