✔ 그리디 알고리즘이란?
영어단어 greedy의 사전 풀이를 찾아보면 다음과 같다.
'탐욕스러운, 욕심 많은'
단어 뜻처럼 눈앞의 이득만 우선 추구하는 알고리즘을 그리디 알고리즘이라고 한다.
while 해가 구성되기 전 {
가장 좋아 보이는 선택
} 하지만 매 순간 가장 좋아보이는 선택을 해서 결과를 도출했을 때, 항상 최적해를 보장하지 않는다. (거의 대부분 보장하지 않는다고 한다) 최적해를 보장하는 경우와 아닌 경우를 예시와 함께 살펴보자.
❌그리디 알고리즘이 최적해를 보장하지 않는 경우
👉이진 트리 최적합 경로 찾기
가장 직관적으로 최적해가 보장되지 않음을 알 수 있는 예시다. 예를 들어 루트에서 시작해 정점의 값들을 합했을 때 최대값을 가지는 경로를 찾는 문제라고 해보자. 여기서 매 순간 가장 좋아보이는 선택은 왼쪽과 오른쪽 정점 중 큰 값을 가진 정점을 선택하는 것 이다. 하지만 아래 그림을 보면 바로 알 수 있듯, 최적해를 보장하지 않는다. 이 문제는 DFS, BFS 등으로 모든 정점을 확인해야 최적해를 얻을 수 있다.
👉특정 금액을 이룰 수 있는 최소한의 동전 갯수 구하기
어떤 금액과 몇 종류의 동전들이 주어졌을 때, 이 금액을 이루는 동전의 갯수 최솟값을 구하는 문제이다. 예를 들어 1300원이라는 금액을 500원, 400원, 100원, 75원, 50원 짜리 동전으로 만들 때, 가장 적은 동전 갯수를 구한다고 해보자. 가장 큰 금액의 동전부터 최대한 금액을 채우는 것이 Greedy한 방식이라고 할 수 있다. 하지만 이 문제는 이러한 방식으로 최적해를 구할 수 없다.
그리디한 방법 : 500원 X 2, 100원 X 3 -> 5개를 사용
최적해 : 500원 X 1, 400원 X 2개 -> 3개
탐욕적으로 가장 큰 금액인 500원 짜리를 최대한 사용한 경우보다 오히려 1개 적게 사용한 경우가 전체적으로 최적해임을 보였다.
최적해를 보장하는 경우!
주어진 동전들이, 큰 액수의 동전이 이보다 한 단계 작은 액수의 동전의 배수일 경우 그리디 알고리즘은 최적해를 보장한다. 예를 들어 주어진 동전이 500원, 100원, 50원, 10원 일 때 이다.
👉보따리(가방) 문제
일정 부피를 담을 수 있는 보따리와, 각기 다른 부피와 가격를 지닌 물건들을 보따리에 넣어야 한다. 보따리가 꽉 찼을 때 보따리 속 물건 가격의 합이 가장 비싼 경우를 구하는 문제이다. 이를 Greedy하게 접근해본다면 다음과 같다. 우선 물건들을 부피 대비 가격이 비싼 순으로 나열한 뒤, 순서대로 채워 넣는 것 이다. 하지만 이런 방식은 최적해를 보장하지 못하고 NP-Hard에 속하는 문제이다.
최적해를 보장하는 경우!
만약 물건을 칼로 잘라 가방에 넣을 수 있다면 그리디 알고리즘으로 최적해를 구할 수 있다.
⭕그리디 알고리즘이 최적해를 보장하는 경우
👉최소신장트리를 구하는 프림 알고리즘, 크루스칼 알고리즘
어떤 n개의 정점이 있는 그래프에서 신장 트리는 n개의 정점은 그대로 두고, 간선을 n-1개만 남겨 트리가 되도록 만든 것 이다. 이때 간선들의 가중치 합이 최소인 경우 최소신장트리라고 한다. 최소신장트리를 구할 수 있는 프림, 크루스칼 알고리즘이 바로 그리디 알고리즘이다. 그래프에서 신장트리를 만들어 나갈 때, 매 순간 가장 작은 가중치를 가진 간선을 선택하여 연결하기 때문이다.
👉회의실 시간 배정하기
여러 팀들이 사용하는 공용 회의실이 있다. 각 팀들은 자신들이 사용할 시간을 제출하는데 (Ex, 2시 ~ 3시) 이때 가장 많은 팀들이 회의실을 사용할 수 있도록 배정하는 경우이다. 이 문제를 그리디한 방법으로 처음 접근하게 되면 회의 시간이 적은 팀들을 우선적으로 배정할 수 있다. (회의 시간이 1시간인 팀 먼저, 이후 2시간인 팀..) 하지만 이 방식은 최적해를 보장하지 않는다.
이 문제를 그리디 알고리즘으로 해결하기 위해선 회의가 일찍 끝나는 팀을 매순간 우선적으로 배정해야 한다.
👉어떤 문제의 공간이 메트로이드(Matroid)를 이룰 때
메트로이드(Matroid)는 독립성이라는 성질을 만족하는 수학적 공간이다.(게임 시리즈는 Metriod) 어떤 문제의 공간이 메트로이드를 이루면 이 문제를 위한 최적해를 보장하는 그리디 알고리즘이 존재한다.
마무리
머릿속에 알고있는 것과 이를 글로 설명하는 건 정말 다르다느 것을.. 다시 한번 더 느낄 수 있었다..(문제 풀러 가야겟다)
