[알고리즘 Deep Dive #1] 그리디(Greedy): 현재 최적의 선택이 전체 최적을 보장하는 경우
알고리즘 Deep Dive #1 – 그리디: 매 순간 최선의 선택이 전체 최적을 보장하는 조건과 실패하는 경우
들어가며
많은 알고리즘 문제는 여러 선택을 순차적으로 내려야 하는 상황으로 구성된다. 예를 들어 작업을 어떤 순서로 수행할지, 제한된 자원을 어디에 먼저 사용할지와 같은 문제들이다.
이러한 문제에서 사용할 수 있는 한 가지 접근 방식이 Greedy Algorithm이다.
그리디란?
매 순간 현재 상황에서 가장 좋은 선택을 하는 알고리즘
전체를 미리 고려하지 않고, 각 단계에서 로컬 최적(local optimum)을 선택한다. 이 선택들이 쌓여 글로벌 최적(global optimum)이 되길 바라는 방식이다.
이 접근 방식의 특징은 다음과 같다.
- 문제를 여러 단계의 선택으로 나누고, 매 단계에서 현재 기준으로 가장 좋은 선택을 한다.
- 한 번 선택한 결정은 이후에 변경하지 않는다.
- 이러한 선택들이 쌓여 전체 문제의 해가 만들어진다.
Greedy 알고리즘은 구현이 단순하고 계산 비용이 낮다는 장점이 있다. 하지만 이러한 전략이 항상 올바른 결과를 보장하는 것은 아니다. 따라서 Greedy 알고리즘을 적용하기 위해서는 특정한 조건이 만족되는지를 먼저 확인해야 한다.
그리디 문제를 식별하는 방법
실제 알고리즘 문제를 풀 때 가장 어려운 점은 이 문제가 그리디로 풀리는지 판단하는 것이다. 이론적으로는 조건을 증명할 수 있어야 하지만, 실전에서는 몇 가지 패턴을 통해 빠르게 판단하는 경우가 많다.
1. 정렬 기준이 명확하다
많은 그리디 문제는 특정 기준으로 정렬한 뒤 순서대로 선택하는 형태로 나타난다.
예를 들어 다음과 같은 기준이 자주 등장한다.
- 종료 시간이 빠른 순서
- 비용이 작은 순서
- 가치/무게 비율이 큰 순서
- 시작 시간이 빠른 순서
정렬 기준이 자연스럽게 떠오른다면 그리디일 가능성이 높다.
2. 선택이 이후 결정에 영향을 크게 주지 않는다
그리디 문제에서는 현재 선택이 이후 선택의 구조를 크게 바꾸지 않는다.
예를 들어 활동 선택 문제에서는 하나의 활동을 선택하면 단순히 이후 시작 가능한 활동만 남는다.
즉 문제 구조가 다음과 같이 단순해진다.
1
2
3
현재 선택
↓
남은 문제 = 동일한 형태의 작은 문제
이런 형태가 보이면 그리디가 성립할 가능성이 높다.
3. 반례가 쉽게 만들어지지 않는다
그리디 접근을 떠올렸다면 작은 입력에서 반례를 직접 만들어보는 것이 중요하다.
예를 들어 다음 질문을 던져볼 수 있다.
- 더 작은 선택을 먼저 하면 더 좋은 결과가 나오지 않는가?
- 특정 조합을 선택하면 전체 결과가 더 좋아지지 않는가?
만약 이런 반례가 존재한다면 그리디는 실패하고, 다른 접근 방식이 필요할 가능성이 높다.
4. 문제에서 자주 등장하는 표현
문제 설명에서 다음과 같은 표현이 등장하면 그리디일 가능성이 있다.
- 가능한 한 많이 선택하라
- 최소 개수로 구성하라
- 가장 빨리 끝나는 작업
- 비용이 가장 작은 선택
이런 문제들은 대부분 각 단계에서 가장 좋은 선택을 반복하는 구조를 갖는다.
정리
그리디 문제는 다음 특징을 보이는 경우가 많다.
- 정렬 기준이 명확하다.
- 선택이 이후 결정에 큰 영향을 주지 않는다.
- 반례를 만들기 어렵다.
하지만 이러한 특징이 있다고 해서 항상 그리디가 가능한 것은 아니다. 따라서 실제 문제에서는 조건을 확인하고 반례를 검증하는 과정이 중요하다.
대표적인 그리디 문제 유형
그리디 알고리즘은 특정 유형의 문제에서 반복적으로 등장한다. 여러 문제를 풀다 보면 유사한 패턴이 보이기 시작한다. 대표적으로 다음과 같은 유형들이 있다.
1. 정렬 후 순차 선택
가장 흔한 형태의 그리디 패턴이다. 문제를 해결하기 위해 특정 기준으로 정렬한 뒤, 앞에서부터 선택을 진행한다.
대표적인 예가 Activity Selection Problem**이다. 활동을 **종료 시간 기준으로 정렬한 뒤, 겹치지 않는 활동을 순서대로 선택하면 최대 개수를 구할 수 있다.
이 유형의 특징은 다음과 같다.
- 정렬 기준이 문제의 핵심이다.
- 한 번 선택하면 해당 선택과 충돌하는 요소들을 제거한다.
- 이후 동일한 방식으로 문제를 반복한다.
많은 스케줄링 문제가 이 패턴을 따른다.
2. 가장 큰(또는 작은) 값부터 선택
매 단계에서 가장 큰 값 또는 가장 작은 값을 선택하는 방식이다.
대표적인 예는 Fractional Knapsack Problem**이다. 물건을 쪼갤 수 있는 경우에는 **가치/무게 비율이 가장 높은 물건부터 선택하는 것이 항상 최적이다.
이 유형의 특징은 다음과 같다.
- 어떤 우선순위 기준이 존재한다.
- 그 기준이 항상 최선의 선택을 보장한다.
- 우선순위 큐나 정렬이 자주 사용된다.
3. 가능한 한 많이 선택
문제의 목표가 조건을 만족하면서 최대 개수를 선택하는 것일 때 자주 등장한다.
예를 들어 다음과 같은 문제들이 있다.
- 겹치지 않는 구간을 최대한 많이 선택
- 제한된 시간 안에 수행 가능한 작업 최대화
- 회의를 가장 많이 배치하기
이 경우 보통 선택이 이후 선택 가능성을 줄이지 않는 방향으로 전략을 세운다.
4. 비용을 최소화하는 선택 반복
각 단계에서 가장 비용이 작은 선택을 반복하는 방식이다.
대표적인 예로는 *Huffman Coding*이 있다. 가장 빈도가 낮은 두 문자를 먼저 합치는 전략을 반복하면 전체 인코딩 길이가 최소가 된다.
이 유형의 특징은 다음과 같다.
- 매 단계에서 가장 작은 비용을 선택
- 선택 결과로 새로운 요소가 생성될 수 있음
- 우선순위 큐가 자주 사용됨
패턴 요약
그리디 문제는 보통 다음 네 가지 패턴 중 하나로 나타난다.
| 유형 | 핵심 아이디어 |
|---|---|
| 정렬 후 선택 | 특정 기준으로 정렬 후 순차 선택 |
| 최대/최소 선택 | 가장 큰 값 또는 작은 값 선택 |
| 최대 개수 선택 | 조건을 만족하는 요소 최대화 |
| 비용 최소화 | 매 단계에서 최소 비용 선택 |
이 패턴들을 익혀 두면 새로운 문제를 만났을 때 그리디 접근이 가능한지 빠르게 판단할 수 있다.
코딩 테스트에서 자주 등장하는 그리디 문제
그리디 알고리즘은 코딩 테스트에서도 매우 자주 등장한다. 문제의 형태는 다양하지만, 실제로는 몇 가지 대표적인 문제 패턴이 반복적으로 출제되는 경우가 많다.
여기서는 실전에서 자주 등장하는 대표적인 문제들을 살펴본다.
1. 거스름돈 문제
서로 다른 단위의 동전이 주어질 때, 특정 금액을 만들기 위한 최소 동전 개수를 구하는 문제.
예를 들어 500원, 100원, 50원, 10원 동전이 있을 때는 큰 단위 동전부터 사용하는 전략이 항상 최적이다.
이 문제의 핵심 아이디어는 다음과 같다.
- 큰 단위 동전이 작은 단위 동전의 배수 관계를 가진다.
- 따라서 큰 동전을 먼저 사용하는 것이 항상 유리하다.
- 남은 금액에 대해 같은 전략을 반복한다.
이 패턴은 많은 기본 그리디 문제의 출발점이 된다.
2. 회의실 배정 문제
여러 회의가 있을 때 서로 겹치지 않도록 최대한 많은 회의를 선택하는 문제.
이 문제는 *Activity Selection Problem*으로 알려져 있다.
핵심 전략은 다음과 같다.
- 회의를 종료 시간 기준으로 정렬
- 가장 먼저 끝나는 회의부터 선택
- 이후 시작 가능한 회의들을 계속 선택
이 전략이 최적인 이유는 일찍 끝나는 회의를 선택할수록 이후에 더 많은 회의를 선택할 수 있기 때문이다.
3. 분할 배낭 문제
물건을 쪼갤 수 있을 때 배낭의 용량을 넘지 않도록 물건을 담아 총 가치를 최대화하는 문제.
이 문제는 *Fractional Knapsack Problem*으로 알려져 있다.
핵심 전략은 다음과 같다.
- 각 물건의 가치/무게 비율 계산
- 비율이 높은 순서대로 정렬
- 가능한 만큼 배낭에 담기
물건을 쪼갤 수 있기 때문에 가치 밀도가 높은 것부터 선택하는 전략이 항상 최적이 된다.
4. 최소 신장 트리
그래프에서 모든 정점을 연결하면서 간선 가중치의 합을 최소화하는 문제이다.
대표적인 알고리즘은 다음 두 가지가 있다.
- Kruskal’s Algorithm
- Prim’s Algorithm
두 알고리즘 모두 가중치가 가장 작은 간선을 선택하는 전략을 반복한다는 점에서 그리디 알고리즘에 속한다.
정리
코딩 테스트에서 등장하는 그리디 문제는 대부분 다음 형태로 나타난다.
- 정렬 후 순차 선택
- 가장 큰/작은 값 선택
- 최대 개수 선택
- 최소 비용 선택
이러한 패턴을 익혀 두면 문제를 처음 보더라도 그리디 접근이 가능한지 빠르게 판단할 수 있다.
그리디가 실패하는 경우
그리디 알고리즘은 강력하고 구현도 단순하지만, 모든 문제에서 최적해를 보장하지는 않는다. 특히 현재 선택이 이후 선택에 큰 영향을 주는 경우에는 그리디 전략이 실패할 가능성이 높다.
다음은 그리디가 실패하는 대표적인 사례들이다.
1. 조합이 중요한 문제
그리디는 매 단계에서 하나의 선택만 고려하지만, 어떤 문제는 여러 선택의 조합이 결과에 큰 영향을 미친다.
대표적인 예가 *0/1 Knapsack Problem*이다.
예를 들어 다음과 같은 상황을 생각해 보자.
1
2
3
4
5
6
배낭 용량: 50
물건 무게 가치
A 10 60
B 20 100
C 30 120
가치/무게 비율을 기준으로 그리디를 적용하면
1
A (6) → B (5) → C (4)
순서로 선택하게 된다.
1
A + B = 가치 160
하지만 실제 최적해는
1
B + C = 가치 220
이다.
이 문제에서는 개별 선택보다 물건의 조합이 더 중요하기 때문에 단순한 그리디 전략이 실패한다.
2. 미래 선택에 영향을 주는 경우
현재 선택이 이후 가능한 선택의 구조를 크게 바꾸는 문제에서도 그리디는 실패할 수 있다.
예를 들어 다음과 같은 그래프를 생각해 보자.
1
2
3
A → B : 1
B → C : 100
A → C : 50
현재 가장 작은 간선을 선택하는 전략을 사용하면
1
A → B (1)
을 먼저 선택하게 된다.
하지만 전체 경로를 고려하면
1
A → C (50)
가 더 짧을 수 있다.
이처럼 현재 선택이 미래의 더 좋은 선택을 막아버리는 경우에는 단순한 탐욕 전략이 올바른 결과를 보장하지 못한다.
3. 선택 기준이 명확하지 않은 경우
그리디 문제는 보통 명확한 정렬 기준이 존재한다.
예를 들어
- 종료 시간이 빠른 순서
- 비용이 작은 순서
- 가치/무게 비율이 큰 순서
하지만 어떤 문제들은 단일 기준으로 정렬해도 항상 최적이 되지 않는다.
이 경우에는 보통 다음과 같은 접근이 필요하다.
- 상태를 나누어 계산하는 방식
- 여러 경우를 비교하는 방식
즉 단순한 선택 전략이 아니라 문제 전체를 고려하는 알고리즘이 필요하게 된다.
핵심 요약
그리디가 실패하는 대표적인 상황은 다음과 같다.
- 선택의 조합이 중요한 문제
- 현재 선택이 미래 선택을 크게 제한하는 문제
- 명확한 정렬 기준이 존재하지 않는 문제
이러한 특징이 보이면 그리디보다는 다른 알고리즘 설계 방법을 고려해야 한다.
다음 포스트에서는 이러한 문제를 해결하기 위한 대표적인 접근 방식인 *Dynamic Programming*을 살펴보겠다.
Tags: #Algorithm #Greedy #Algorithms #CodingTest #Optimization