[알고리즘] 그리디(Greedy) 탐욕 알고리즘 - 거스름돈, 회의실, 배낭

그리디(Greedy) 알고리즘은 문제를 해결할 때 
현재 시점 기준으로 가장 최선의 선택을 반복적으로 수행하며 결과에 도달하는 알고리즘으로
탐욕적인 선택을 한다해서 탐욕 알고리즘이라고도 불린다.
 
그리디 알고리즘은 각 단계에서 가능한 최선의 선택을 하지만,
그 선택이 전체 문제에 대해서 최적해를 보장하는지는 문제별로 다르게 나타난다.
 
쉽게 말해, 나무만 보고 숲은 보지 못하는 당장의 이익에만 얽매이는 모습이라 생각하면 된다.

---

1. 그리디 알고리즘 동작 흐름

그리디 알고리즘은 현재 상황에서 선택할 수 있는 후보들을 확인한 후,
후보들 중 가장 좋아보이는 최선의 선택을 한다.
선택한 결과를 문제에 반영하여 문제가 해결될 때 까지 반복하는 동작을 한다.
 
이때 특이한점은
한 번 선택한 결과를 다시 되돌아가지 않는다는 점이다.
 
즉, 선택을 반복했을 때
전체 결과도 최적의 답이 되는 문제에서만 사용이 가능한 알고리즘이라 볼 수 있다.

---

2. 그리디 알고리즘의 조건

그리디 알고리즘은 매 순간 눈앞의 이익만 쫒는 탐욕 알고리즘이기 때문에
아무 문제에나 막 쓰게 되면 오답이 나온다.
그렇기 때문에 그리디 알고리즘을 사용할때는 두가지 조건을 꼭 만족해야한다.
 

2_1) 탐욕 선택 속성 (Greedy Choice Property)

현재 단계에서 가장 좋다고 생각해서 내린 결정이 다음 단계 선택에 나쁜 영향을 주지 않아야 한다.
즉, 앞에서 내린 선택을 나중에 후회하거나 번복하는 일이 없는 구조여야한다는 것이다.
 
예를 들어 미로찾기를 할 때,
갈림길에서 우회전을 하고나서 나중에 막다른길을 마주했을 때
아,, 아까 좌회전할껄 하고 되돌아가는 일이 없어야하는것이다.
 

2_ 2) 최적 부분 구조 (Optimal Substructure)

큰 문제 안에 작은 문제들이 쪼개져 있고,
그 작은 문제들의 최적해(최적의 답)을 구해서 다 합치면 결국 전체 문제에 대한 최적의 답이 되는 구조여야한다.
 
예를 들어 서울에서 부산까지 가는 가장 빠른 경로를 찾을 때,
서울 → 대전, 대전 → 부산에 대한 최단 경로를 각각 구해서 붙이면
결국 서울 → 부산 전체에 대한 최단 경로가 되어야 하는것이다.
 

💡 그리디의 함정: 최적 부분 구조가 있다고 무조건 그리디가 될까?

최적 부분 구조가 있다고 해서 무조건 그리디가 되는것은 아니다.
 
큰 문제를 작은 문제로 쪼갤 수 있는 최적 부분 구조를 가졌더라도,
그리디 알고리즘을 쓰면 오히려 비효율적인 현재의 선택이 미래의 선택지를 제한하는 경우가 있다.
 
예를 들어 아래 트리 구조에서 루트노드에서 아래로 이동하며 가장 큰 합을 찾는 문제가 있을 때,
5에서 시작해서 현재위치에서 선택할 수 있는 값들중 가장 큰 값인 10을 선택하게 된다.
 
이렇게 현재 위치에서 가장 큰 값만 선택하는 그리디 방식으로 값을 찾다보면
결과는 17이 나오게 된다. (5 → 10 → 2)
 
하지만 전체 경로를 확인해보면 실제로 가장 큰 합은 다른 경로에 존재한다. (5 → 1 → 99 = 105)
처음엔 10을 선택하는것이 가장 좋아보였지만
해당 선택으로 인해 99라는 더 큰 값을 선택할 수 있는 기회를 잃게된것이다.
 
즉, 그리디 알고리즘은 단순히 문제를 작은 단위로 나눌 수 있다고 막 사용하는것이 아니라,
현재의 최선의 선택이 전체 결과에서도 최선이 되어야 사용할 수 있다.

# 예시 트리 구조
       [5]
      /   \
   [10]   [1]
   / \     / \
 [1] [2] [99][4]
 
 # 함정 : 5 → 10 → 2 = 17
 # 실제 큰 합 경로 : 5 → 1 → 99 = 105

---

3. 그리디 알고리즘의 장단점

👍 그리디 알고리즘의 장점

• 구현이 간단하다.
• 계산 속도가 빠르다.

👎 그리디 알고리즘의 단점

• 항상 최적해를 보장하는것은 아니다.
• 적용 가능한 문제인지 파악 후 사용해야한다.

---

그리디 사용 예시1) 거스름돈 문제

거스름돈 문제는 주어진 금액을 거슬러 줄 때, 가장 적은 개수의 동전을 사용하는 문제이다.
예를 들어 1260원을 거슬러줘야할 때 500원, 100원, 50원, 10원 동전이 있는 경우
가장 큰 금액의 동전부터 최대한 사용하면 필요한 동전의 개수를 줄일 수 있다.
 

📌 동작 과정

거스름돈: 1260원

# 큰 동전부터 차례대로 선택
500원: 2개 선택
	↓
100원: 2개 선택
	↓
50원: 1개 선택
	↓
10원: 1개 선택

결과: 총 6개 사용

 

✅ 기능 1) 사용 가능한 동전 개수 구하기

현재 금액에서 동전을 몇 개 사용할 수 있는지 계산해야한다.
이를 구하기 위해 나누기의 몫을 구하는 // 연산자를 사용하여 구한다.

money // coin

✅ 기능 2) 동전 사용 후 남은 금액 구하기

동전을 사용하고 난 뒤, 다음 동전을 확인하기 위해 남은 금액을 계산한다.
이때 나머지를 구하는 % 연산자를 사용하여 구한다.

money %= coin

 

💡거스름돈 문제 최종 코드

def greedy_change(money):
    # 사용할 수 있는 동전 종류
    coins = [500, 100, 50, 10]

    # 사용한 동전 개수
    use = 0

    # 큰 동전부터 하나씩 확인 (반복문)
    for coin in coins:
        # 기능1: 현재 동전 사용할 수 있는 개수
        use += money // coin
        # 기능2: 동전 사용 후 남은 금액
        money %= coin

    return use

money = 1260
print(f"필요한 동전 개수: {greedy_change(money)}개")

실행결과 ▶

---

그리디 사용 예시2) 회의실 배정 문제

회의실 배정 문제는 하나의 회의실에서 최대한 많은 회의를 진행할 수 있도록 선택하는 문제이다.
각 회의는 시작 시간과 종료 시간이 있고, 시간이 겹치는 회의는 같은 회의실을 사용할 수 없다.
 
회의가 빨리 끝날수록 뒤에 다른 회의를 배정할 수 있는 시간이 많아지기 때문에
가장 빨리 끝나는 회의를 선택하는 방식으로 진행해야한다.
 

📌 동작 과정

# 회의 목록
(1,4) (3,5) (0,6)
(5,7) (8,11) (12,14)


# 종료 시간이 빠른 회의부터 선택
(1,4)
  ↓
(5,7)
  ↓
(8,11)
  ↓
(12,14)

결과: 총 4개의 회의 선택

 

✅ 기능 1) 종료 시간 기준으로 정렬하기

회의를 최대한 많이 선택하기 위해선 가장 빨리 끝나는 회의를 먼저 확인해야한다.
회의 데이터는 (시작시간, 종료시간)형태이기 때문에 종료시간인 x[1]을 기준으로 정렬한다.

meetings.sort(key=lambda x: (x[1], x[0]))

✅ 기능 2) 시간이 겹치지 않는 회의 선택하기

이 전 회의가 끝난 시간 이후에 시작하는 회의만 선택해야한다.
현재 회의 시작 시간이 마지막으로 선택한 회의 종료 시간 보다 크거나 같은경우만 선택해야한다.

if start >= end_time:

그리고 회의를 선택한 뒤엔 마지막으로 종료 시간을 현재 회의의 종료시간으로 바꿔주면 된다.

end_time = end

 

💡회의실 배정 문제 최종 코드

def meeting_room(meetings):
    # 기능1: 종료 시간 빠른순으로 정렬
    meetings.sort(key=lambda x: (x[1], x[0]))

    # 선택한 회의 개수
    use = 0

    # 마지막으로 선택한 회의 종료 시간
    end_time = 0

    # 회의 하나씩 확인(반복문)
    for start, end in meetings:
        # 기능2: 시작 시간이 이전 종료 시간 이후라면 선택
        if start >= end_time:
            use += 1
            # 기능2: 선택한 회의의 종료 시간 저장
            end_time = end

    return use

meetings = [(1,4), (3,5), (0,6), (5,7), (8,11), (12,14)]
print(f"가능한 회의 개수: {meeting_room(meetings)}개")

실행결과 ▶

---

그리디 사용 예시3) 배낭 문제

배낭 문제는 제한된 무게 안에서 최대 가치를 가지도록 물건을 넣는 문제이다.
무게에 비해 가치가 높은 물건부터 담으면 된다.
 
단, 이 방식은 물건을 나눠 담을 수 있는 경우에만 사용할 수 있다.
물건을 통째로만 담아야 하는 경우에는 그리디로 항상 정답을 구할 수 없다.
 

📌 동작 과정

가방 최대 무게: 50kg

# 1kg당 가치 계산
A : 60 / 10 = 6
B : 100 / 20 = 5
C : 120 / 30 = 4

# 가치 높은 순서
A → B → C


# 담는 순서
A 전체 선택
    ↓
B 전체 선택
    ↓
C 일부 선택

결과 : 최대 가치 240

 

✅ 기능 1) 1kg당 가치 계산하기

물건마다 다른 무게와 가치를 각각 비교하여 계산하기 위해 1kg당 가치를 계산해준다.

value / weight

✅ 기능 2) 1kg당 가치가 높은 순서로 정렬

가치가 높은 순서대로 배낭에 넣어야하기 때문에
1kg당 가치 계산을 마친 값들을 가치가 높은 순서대로 정렬해준다.

items.sort(key=lambda item: item[2] / item[1], reverse=True)

# ("A", 10, 60)
# item[0] = 물건 이름 A
# item[1] = 무게 10kg
# item[2] = 가치 60

✅ 기능 3) 가방에 최대한 담기

물건 전체를 담을 수 있다면 모두 담고

if bag_weight >= weight:

만약 물건 전체를 담을 수 없을 땐 남은 무게만큼만 가방에 담는다.

total_value += value * (bag_weight / weight)

 

💡배낭 문제 최종 코드

def knapsack(items, bag_weight):

    # 기능1: 1kg당 가치 계산
    for item in items:
        item.append(item[2] / item[1])

    # 기능2: 1kg당 가치 높은 순서로 정렬
    items.sort(key=lambda x: x[3], reverse=True)

    # 가방에 담은 총 가치
    total_value = 0

    # 기능3: 가치가 높은 물건부터 담기
    for name, weight, value, ratio in items:
        # 물건 전체를 담을 수 있는 경우
        if bag_weight >= weight:
            # 남은 무게 감소
            bag_weight -= weight
            # 가치 추가
            total_value += value

        # 물건 전체를 담을 수 없는 경우
        else:
            # 남은 공간만큼 일부 선택
            total_value += value * (bag_weight / weight)
            break

    return total_value

items = [
    ["A", 10, 60],
    ["B", 20, 100],
    ["C", 30, 120]
]
print(f"최대 가치: {knapsack(items, 50)}")

실행결과 ▶