탐욕 알고리즘(greedy algorithm)

탐욕 알고리즘이란?

탐욕법이란 이름 그대로 ‘눈 앞에 보이는 최선’을 탐욕적으로 선택하는 것을 반복하는 알고리즘 설계 패러다임 중 하나입니다. 탐욕법을 이용한 일고리즘을 탐욕 알고리즘, 그리디 알고리즘이라고 합니다. 전체를 여러 조각으로 나눠서 각 단계마다 답의 일부를 만들어 간다는 점에서 완전 탐색과 비슷하지만, 모든 선택지를 보는 완전 탐색과 달리 탐욕 알고리즘은 지금 당장 가장 좋은 해답을 선택합니다. 탐욕 알고리즘의 대표적인 문제로는 각 물건의 무게와 가치가 주어졌을 때, 가방에 가치가 높은 물건을 최대한 많이 담는 경우를 찾는 배낭 문제(Knapsack problem)이 있습니다.

 

 

탐욕 알고리즘의 한계

탐욕 알고리즘은 매 순간 가장 좋은 선택지만 고르기 때문에 전체적으로 봤을 때 더 좋은 선택지가 있어도 발견하지 못합니다. 지금의 선택이 이후에 어떤 영향을 끼칠지를 고려하지 않죠. 그러면 최적인 해답을 찾지 못하는데 왜 사용할까요? 탐욕 알고리즘을 사용하는 경우는 크게 두 가지입니다.

 

1. 탐욕 알고리즘으로 최적의 해답을 찾아도 되는 경우

2. 학문적으로써의 알고리즘 분야에서 인간이 아직 풀지 못한 문제를 풀 때 정확한 최적의 해답을 찾기보다는 근사해를 구하는 경우. 더 적은 시간과 비용으로 비슷한 해답을 찾아낼 수 있습니다.

 

프로그래밍 대회에서는 대부분 1번의 이유로 탐욕 알고리즘을 사용합니다. 2번처럼 근사해를 찾는 경우는 거의 없다고 봐도 될 것 같습니다. 당장은 그런 문제를 만날 일도 없을테니까, 탐욕 알고리즘은 상황과 문제에 따라 사용하시면 되겠습니다.

 

---

 

https://www.acmicpc.net/problem/11399

예시 문제를 풀어보겠습니다. ATM을 쓰기 위해서 사람들이 줄을 서 있습니다. 각 사람 별로 돈을 인출하는데 걸리는 시간이 주어졌을 때, 가장 빨리 모든 사람들이 돈을 뽑는 경우의 시간을 구하는 문제입니다.

 

 

완전 탐색으로 풀 수 있을까?

무식하고 가장 간단하게 풀고자 하면 줄 세우는 모든 경우의 수를 전부 돌면서 가장 적은 시간을 찾아내면 되겠네요. 그런데 이 경우, 최대 사람의 수는 1000이고 1000가지를 나열하는 모든 경우의 수는 1000!이니까 딱 보기에도 시간 제한 1초 안에 풀기는 힘들어집니다. 차라리 다른 은행 가는 게 더 빠르겠습니다.

 

 

탐욕 알고리즘

더 효율적인 탐색 방법을 생각해봅시다. 모든 사람이 가장 빠르게 돈을 뽑기 위해서는 뒷사람들이 기다리는 시간을 줄이면 되겠네요. 빠른 사람부터 뽑으면 뒷사람들이 기다리는 시간이 줄어드니까, 최종적으로는 전체 시간이 줄게 됩니다. 빠른 사람 순으로 오름차순 정렬을 한 뒤에 계산을 하면 답이 나옵니다.

#include <stdio.h>
#include <algorithm>
int n, p[1005], res = 0;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &p[i]);
 
    std::sort(p, p + n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            res += p[j];
        }
    }
    printf("%d", res);
}

 

탐욕 알고리즘을 쓰는 문제는 뭔가를 가장 빨리~, 가장 큰~ 이라는 단어가 많이 들어갑니다. 정렬을 잘 알아두면 문제를 푸는 데에 도움이 될 듯합니다. 문제를 보고 완전탐색으로 풀기에는 경우의 수가 큰데, 뒷일은 생각하지 않고 각 단계에서 최선을 택해도 정답을 구할 수 있을 것 같을 때 탐욕 알고리즘을 사용하면 됩니다.

 

 

추천문제

https://www.acmicpc.net/problem/11399

11399번: ATM

https://www.acmicpc.net/problem/11047

11047번: 동전 0

https://www.acmicpc.net/problem/5585

5585번: 거스름돈

https://www.acmicpc.net/problem/2217

2217번: 로프

https://www.acmicpc.net/problem/1202

1202번: 보석 도둑