개발지식/자료구조

[자료구조] 탐욕법(Greedy Algorithm)

thinktank911 2025. 11. 25. 13:55

프로그래밍 문제를 풀다 보면 최적의 선택을 반복해서 문제를 해결해야 할 때가 많다. 이럴 때 유용한 기법이 바로

탐욕법(Greedy Algorithm)이다. 탐욕법은 말 그대로 매 순간 가장 좋아 보이는 선택을 하는 방법을 의미한다.

1. 탐욕법의 개념

탐욕법은 문제를 작은 단위로 나누어 단계별로 최적의 선택을 하는 방식이다.
즉, 전체 문제를 한 번에 고려하지 않고 현재 상황에서 가장 좋은 선택을 하는 것이다.

탐욕법은 다음과 같은 특징을 가진다.

  1. 단계적 선택
    문제를 여러 단계로 나누고, 각 단계마다 선택을 한다.
  2. 현재 최적 선택
    각 단계에서 현재 가장 최적인 선택을 한다.
  3. 결과의 최적성 보장 X
    항상 최적의 결과가 나오는 것은 아니며, 문제에 따라 최적성을 보장하기도 한다.

2. 탐욕법이 잘 맞는 문제 유형

탐욕법은 다음과 같은 문제에서 자주 사용된다.

  • 최적화 문제: 최소, 최대 값을 구하는 문제
    예) 거스름돈 최소 동전 개수, 회의실 배정 문제
  • 부분 문제의 최적 선택이 전체 문제의 최적 선택으로 이어지는 문제
    예) 최소 스패닝 트리(MST), 다익스트라 알고리즘

탐욕법이 적합한 문제는 “현재의 선택이 이후 선택에도 영향을 주지 않는 문제”가 핵심이다.

 

3. 탐욕법 구현 방법

탐욕법은 자료 구조와 함께 사용하면 효율적으로 구현할 수 있다.
대표적인 자료 구조는 다음과 같다.

자료 구조 용도
배열(Array) 값들을 정렬하거나 순회하며 최적 선택 수행
우선순위 큐(Priority Queue, Heap) 최대/최소 값을 빠르게 가져올 때 사용
정렬(Sort) 문제에서 요구하는 기준으로 정렬 후 탐욕 선택 수행
그래프(Graph) MST, 다익스트라 같은 최적 경로 문제에 사용

예를 들어, 회의실 배정 문제에서는 회의 시작 시간을 기준으로 정렬 후 끝나는 시간이 가장 빠른 회의를 선택하는 방식으로 탐욕법을 적용한다.

4. 탐욕법 예제

4-1. 거스름돈 문제

문제: 최소 동전으로 거슬러주기

자료구조 활용: 배열(Array)

const coins = [500, 100, 50, 10]; // 동전 단위
let amount = 1260;
let count = 0;

for (const coin of coins) {
  count += Math.floor(amount / coin);
  amount %= coin;
}

console.log(count); // 6

설명:

  • 큰 단위 동전부터 거슬러주는 것이 현재 최적 선택이다.
  • 배열을 순회하며 몫과 나머지를 계산하면 전체 문제를 최적화할 수 있다.

4-2. 회의실 배정 문제 (Meeting Room Scheduling)

문제: 최대 회의 수를 배정하기

자료구조 활용: 배열 + 정렬

const meetings = [
  [1, 4],
  [2, 3],
  [3, 5],
  [4, 6],
];

// 끝나는 시간 기준 정렬
meetings.sort((a, b) => a[1] - b[1]);

let count = 0;
let endTime = 0;

for (const [start, end] of meetings) {
  if (start >= endTime) {
    count++;
    endTime = end;
  }
}

console.log(count); // 2

 

5. 탐욕법 장단점

장점

  • 구현이 간단하다.
  • 대부분 정렬과 순회만으로 해결 가능하다.
  • 시간 복잡도가 낮은 경우가 많다.

단점

  • 항상 최적 해를 보장하지 않는다.
  • 문제에 따라 탐욕법 적용이 어렵다.

6. 탐욕법 팁

  • 문제를 현재 단계에서 최적 선택을 할 수 있는가? 먼저 확인해야 한다.
  • 정렬이나 우선순위 큐를 적절히 사용하면 구현이 간단해진다.
  • 탐욕법이 안 통하는 경우 동적 계획법(DP)으로 접근할 수 있다.

결론

탐욕법은 “지금 가장 좋은 선택이 전체 문제에서도 최적이 되는 경우” 매우 유용한 기법이다.
문제를 단계별로 쪼개고 현재 최선의 선택을 반복하는 방식으로 접근하면, 많은 최적화 문제를 효율적으로 해결할 수 있다.