그리디 알고리즘(Greedy Algorithm)

1. 그리디(Greedy) 알고리즘이란

1.1 왜 탐욕 알고리즘이라고 부를까?

매 순간 가장 유리해보이는 선택을 하기 때문이다.

 

Greedy 알고리즘은 매 단 계마다 지금 당장 가장 좋아 보이는 선택을 하는 방식의 알고리즘이다.

이런 선택을 계속 반복하면서 최종적으로는 최적의 해를 찾을 수 있기를 기대한다.

---

1.2 동작 방식

1️⃣ 목표 정하기

먼저 문제에서 무엇을 최적화할 것인지를 결정한다.

예를 들어 가치의 합을 최대화하거나 비용을 최소화하는 것이 목표가 될 수 있다.

 

2️⃣ 현재 상황에서 가장 좋아 보이는 선택하기

지금 당장 가장 유리하다고 판단되는 선택지를 고른다

 

3️⃣ 해당 선택이 가능한 지 확인

선택한 항목이 문제의 조건이나 제약 사항을 만족하는 지 체크한다. 조건을 만족하지 못하면 다른 선택지를 고려한다.

 

4️⃣ 선택한 항목을 최종 결과에 포함

조건을 만족한다면 해당 선택을 결과에 반영하고 다음 단계로 넘어간다

 

5️⃣ 더 이상 선택할 수 없을 때까지 반복

모든 조건을 만족했거나 더 이상 선택할 수 있는 항목이 없을 때까지 위 과정을 반복한다.

 

 

---

1.3  그리디 알고리즘의 특징

• Greedy 알고리즘은 구현이 쉽고 동작 방식이 단순한 편이다.
• 시간 복잡도 측면에서 효율적인 경우가 많으며, 빠르게 해를 구할 수 있다.
• 매 순간 현재 상황에서 가장 좋아 보이는 선택을 한다. 따라서 이미 내린 선택을 다시 되돌아보지 않으며, 미래의 상황까지 고려하지 않는다.

---

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

2.1 👍 장점

구현이 비교적 쉽고 이해하기가 쉽다

Greedy 알고리즘은 동작 방식이 단순한 편이라 구현이 쉽고, 동작 방식의 이해가 어렵지 않은 편이다.

특정 문제의 경우 최적의 해를 구할 수 있다

모든 문제에 해당하는 것은 아니지만, 일부 문제에서는 실제로 최적의 해를 찾을 수 있다. (음수 가중치가 없는 그래프의 최단 경로 구하기)

실행 속도가 빠른 편이다

현재 상황에서 가장 좋은 선택만 하면 되기 때문에, 다른 알고리즘에 비해 시간 복잡도가 낮고 실행 속도가 빠른 편이다.

---

2.2 👎 단점

항상 최적의 해를 보장하지는 않다.

이 알고리즘은 현재 상황에서 가장 좋아 보이는 선택을 우선하기 때문에, 전체적으로 봤을 때 최적의 해가 아닌 결과를 얻을 수도 있다.

입력 데이터의 순서에 영향을 받을 수 있다

입력된 데이터의 순서에 따라 선택 과정이 달라질 수 있고, 경우에 따라 결과에도 영향을 줄 수 있다.

모든 문제에 적용할 수 있지는 않다

Greedy 알고리즘은 특정 문제에서는 효과적일 수 있지만, 복잡한 조건이 많거나 여러 경우를 고려해야 하는 경우에는 적합하지 않을 수 있다.

---

3. 그리디 알고리즘 적용해보기

3.1 거스름돈 문제

💡 아이디어

동전의 개수를 최소화하기 위해 먼저 5원짜리 동전을 최대한 많이 사용하는 방향으로 생각했다.

 

현재 금액이 5로 나누어 떨어지면, 남은 금액은 모두 5원짜리 동전으로 거슬러 줄 수 있다. 따라서 지금까지 사용한 동전의 개수와 남은 금액을 5로 나눈 값을 더해 바로 반환한다.

 

만약, 5로 나누어 떨어지지 않는다면,  2원짜리 동전을 하나 사용하고 남은 금액에서 2를 뺀다. 이후 다시 5로 나누어 떨어지는 지 확인하는 과정을 반복한다.

 

이 과정을 반복하다가 남은 금액이 음수가 된다면, 더 이상 2원짜리 동전을 사용할 수없는 상태가 된 것이다. 즉, 해당 금액을 5원과 2원만으로는 만들 수 없다는 의미로 -1를 return한다.

구현

def change_money(n):
  total =n  # 현재 남은 돈 
  count=0 # 동전 개수 

  while total != 0:
    if total % 5 == 0: # total이 5로 나누어지면 
      return (total //5 ) + count  # 지금 까지 쓴 동전 개수 
    else : # 5로 나누어지지 않을 때
      count+=1 # 2원짜리 동전 하나 사용
      total-=2 # 남은 돈에서 2를 뺀다 

  if total < 0: # 남은 돈이 음수가 되면 5와 2로 거스름돈을 표현할 수 없음
    return -1  # -1 반환 




print('===== 거스름돈 문제 =====')
print(change_money(13))
print()

실행 결과

===== 거스름돈 문제 =====
5

---

3.2 회의실 배정 문제

💡 아이디어

먼저 회의 스케줄들을 끝나는 시간 기준으로 오름차순으로 정렬한다.
가장 먼저 끝나는 회의를 우선 선택한 뒤, 그 다음 회의들 중에서 이전에 선택한 회의가 끝나는 시간 이후에 시작하는 회의를 선택한다.

 

선택할 수 있는 회의를 찾을 때마다 count를 1 증가시킨다.

이 과정을 모든 스케줄에 대해 반복하여 배정할 수 있는 회의의 최대 개수를 구할 수 있게 한다.

구현

def schedule(meetings):
  count = 0 # 가능한 회의의 개수 0으로 초기화

  # 끝나는 시간이 빠른 순으로 정렬(끝나는 시간이 같으면 시작 시간이 빠른 것이 먼저)
  meetings.sort(key=lambda meeting: (meeting[1], meeting[0]))

  count+=1    # 첫번째 회의 선택 

  before= meetings[0] # 직전에 선택한 회의

  for i in range(1,len(meetings)): # 두 번째 회의부터 확인 
    current =meetings[i]
    if current[0] >= before[1]: # 현재 회의의 시작 시간이 직전 회의 의 종료 시간 이상이면 회의실을 이어 서 ㅏ용할 수 있게 함 
      count+=1
      before= meetings[i]

    else: # 시간이 겹치면 넘어가기 
      continue 

  return count 

print('===== 회의실 문제 =====')

n = int(input())

meetings = []

for i in range(n):
    start, end = map(int, input().split())
    meetings.append([start, end])

print('결과:', schedule(meetings))

실행결과

---

3.3 배낭 문제

💡 아이디어

이 문제에서 가장 먼저 떠올린 방법은 가치가 높은 물건부터 배낭에 넣는 그리디(Greedy) 방식이었다.

먼저 입력받은 물건들을 가치 기준으로 내림차순 정렬한 뒤, 현재 남은 무게 안에 들어갈 수 있는 물건이라면 배낭에 넣는다. 이후 남은 무게를 갱신하고, 다시 가장 가치가 높은 물건부터 같은 과정을 반복한다.

즉,

• 가치가 가장 높은 물건을 먼저 선택
• 현재 배낭에 넣을 수 있으면 넣기
• 남은 무게를 갱신하고 다음 물건을 확인

👉 매 순간 가장 좋아 보이는 선택을 하는 방식이 바로 그리디 알고리즘이다.
하지만 실제 예제를 적용해 보니 정답과 다른 결과가 나왔다.

그리디 알고리즘으로 구현

def backpack(items, weight):
  left = weight
  totalV= 0
  items.sort(key=lambda item: item[1], reverse =True )
  # 가치를 기준으로 내림차순한다 

  for item in items:
    currentW = item[0]
    if currentW <= left:
      totalV+=item[1]
      left -= currentW
    else : continue

  return totalV



print('==== 배낭 문제 그리디 알고리즘으로 ====')

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

items = []

for i in range(n):
    weight, value = map(int, input().split())
    items.append([weight, value])

print('결과:',backpack(items,k))

실행 결과

 

하지만 실제 최적의 해는 4kg 가치 8과 3kg 가치 6을 함께 선택한 14이다.
위 결과를 통해 현재 기준 가장 좋아 보이는 선택을 하는 그리디 알고리즘이 항상 최적의 해를 보장하지 않는다는 것을 확인할 수 있었다.