[알고리즘] 탐욕 알고리즘 · 탐욕법 · 그리디(Greedy)

탐욕법
Greedy Method

 

각 단계마다 최적의 방법을 찾는 알고리즘. 여러 조각으로 나누고, 단계마다 답의 한 부분을 만들어가는 방법.

 

탐욕이라는 이름대로 그리디 알고리즘은 다음 단계를 고려하지 않고, 현재 단계에서 최적해를 찾아낸다.
이 때문에 지역적으로 최적인 답을 찾을 때는 매우 유용하게 사용되는 알고리즘이다.
하지만 지역적 최적이 최종적으로 최적이라는 보장은 없다.

 

---

 

1. 문제 해결 방법

1) 선택 절차 Selection Procedure

현재 상태에서 최적인 답을 선택한다.

 

2) 적절성 검사 Feasibility Check

조건을 벗어나지 않는지 검사한다.

 

3) 해답 검사 Solution Check

문제가 해결되었는지 검사한다. 아닐 시 선택 절차로 돌아가 반복한다.

 

 

2. 정당성 증명

1) 탐욕적 선택 속성 Greedy Choice Property

탐욕법은 동적계획법보다 수행시간이 빠르다.

탐욕법으로 최적해를 구할 수 있다는 것은 한 번의 선택만으로 최종 최적해가 나온다는 것이다.
만약 탐욕법으로 최적해를 구할 수 있는 문제가 있으면, DP대신 속도가 더 빠른 탐욕법이 더 유용하다.

DP는 무조건 최종 최적해를 구할 수 있어 탐욕법으로 풀이가 가능한 문제는 모두 DP로도 풀이가 가능하다.

 

2) 최적 부분 구조 Optimal Substructure

최적해를 찾기 어려운 문제가 있으면 근사해를 찾아내는 방법을 선택할 수 있다.
부분에 대한 최적해를 찾아 가장 근사한 값을 찾아낸다.

 

 

---

 

백준 1715번 문제는 Greedy알고리즘을 이용한 문제이다.

 

 

문제

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

 

 

 

1. 카드 묶음의 개수대로 순서대로 정렬하여 묶음의 수가 적은 것부터 더해준다.
2. 두 묶음이 합해진 개수의 한 묶음이 생기면, 해당 묶음으로 다른 묶음과 더해주어야 한다.

오름차순으로 정렬하여 적은 것부터 합치면 최소 비교를 구할 수 있어 탐욕법으로 구할 수 있는 문제이다.

 

문제에 대한 풀이는 아래 BOJ 1715 글에서 확인할 수 있다.

[백준] 1715번 카드 정렬하기