7. Greedy (그리디 알고리즘, 탐욕법)

제가 원래 수학 관련 문제를 좀 좋아합니다. 특히 고등학교 때부터 공간도형 문제를 좋아하고 잘 풀기도 했는데요.

Greedy, DP 이런류의 알고리즘도 수학적 지식이 기반되는 데 반해 항상 감으로만 풀게 되더라구요.

따라서, 잘 푸는 문제는 잘 푸는데 못 푸는 문제는 거의 손도 못 대는 경우가 많습니다.

 

어떤 분류에서 문제 해결에 기복이 있다면, 저는 항상 개념부터 다시 공부하곤 했습니다.

정확한 개념이 잡혀 있어야, 어떤 어려운 응용문제도 하나씩 해결해나갈 수 있으니까요.

같은 어려움을 겪는 분들에게 조금이나마 도움이 될 수 있으면 좋겠네요.

물론 공부하고 학습하기 위한 글로 개념이나 증명적인 부족함이 많을 수 있습니다. 다른 자료들도 많이 참고해보시는 게 좋을 듯합니다.

 

 

Greedy '탐욕스러운, 욕심이 많은'의 뜻을 가진 영어 단어입니다.

사실 누구나 들어봤고 대략적인 의미는 알고 계실 것입니다. (저는 의미만 알지 잘 모르긴 합니다 ㅎㅎ)

 

---

Greedy

매 순간 최적의 해를 선택해 나가는 방식으로 최종적으로 가장 최적의 해를 찾는 것이 목표.

 

 

개념은 매우 간단하죠. 공부할 것이 없을 정도...?

하지만 실제로 해당 문제가 그리디를 적용할 수 있는지 알고 문제를 풀어야 하는데, 위의 정의로는 한참 부족해 보입니다.

 

 

그리디는 일반적으로 아래 두 가지 속성을 가지는 문제에서 유용하게 쓰입니다.

 

Greedy choice property, 탐욕적 선택 조건

한 번의 선택이 다음 선택과는 전혀 무관한 값이어야 한다.

현재의 부분 해가 다음의 부분해 선택에 영향을 주어선 안된다.

Optimal substructure, 최적 부분 구조

매 순간의 최적해가 문제에 대한 최적해여야 한다

 

 

두가지 속성이 어떻게 쓰이는지 알아야, 해당 문제가 그리디로 해결이 가능한지 알 수 있겠죠.

우선 대표적인 그리디 알고리즘부터 알아보겠습니다.

 

Greedy

• 활동 선택 문제(Activity selection problem)
• 거스름돈 문제
• 최소 신장 트리 (Minimum spanning tree, Kruskal)
• 다익스트라 알고리즘 (Dijkstra Algorithm)

 

Activity selection problem

예시문제

활동 선택 문제는 강의실 배정 문제가 대표적입니다. 백준에도 똑같은 문제가 있죠.

 

정해진 강의실 배정 가능 시간 내에 최대한 많은 강의를 배치하는 문제입니다.

이 문제의 해결 아이디어는 강의 종료시간이 가장 빠른 수업을 가장 먼저 배정하는 것입니다.

왜냐하면, 종료시간이 빠를수록 그만큼 강의실을 배정할 수 있는 시간이 늘어난다는 뜻이니까요.

그림 1. Activity selection problem

Greedy choice property를 이 문제에서 생각해봅시다.

B라는 최적해를 골랐을 때, 이후 선택에서 최적해 고르는데 영향을 미칠까요?

미치지 않습니다. 예를 들어 볼게요.

 

A는 오후 1시에 끝이 나고, B는 오전 11시에 끝납니다.

B가 가장 일찍 끝나는 강의로 가정했기 때문에 남은 선택 가능한 강의는 아래와 같이 가정하겠습니다.

C: '13 ~ 16시', D: '12 ~ 14시', E: '12 ~ 16시', F: '15 ~ 17시' ..

이러한 경우 A를 포함 총 5가지 강의를 선택할 수 있습니다.

만약 A를 골랐다면, 이후 선택 가능한 강의는 C가 가능합니다.

B의 경우엔 C, D, E, F 모두 가능하죠. 여기 까진 두 경우 모두 2개의 강의를 넣을 수 있으니 상관없습니다.

하지만 다음 선택에서 A -> C로 선택되며 이후엔 다른 어떤 강의도 시간표에 배정할 수 없습니다.

B의 경우엔 B -> D -> F 이렇게 총 3개의 강의를 넣을 수 있습니다.

 

강의 시간표가 A ~ F까지 존재할 때 남은 시간 내에서 배치 가능한 강의수가 최대인 값이 나오게 되죠.

이렇게 그리디한 선택을 했을 때 그다음의 선택에 영향을 주지 않게 되는 것입니다.

 

 

거스름돈 문제

예시문제

이 문제도 위와 같은 경우입니다.

약간 다른 점은 앞의 문제는 정해진 거스름돈에서 최대한 많은 양의 거스름돈을 줄 수 있는 방법이었다면, 이 문제는 최대한 적은 양의 거스름돈을 준다는 것이 일반적인 문제입니다.

물론 이 방법이 적용될 조건은, 모든 거스름돈이 서로의 배수고 약수여야합니다. 즉, 하나의 거스름돈의 다른 거스름돈의 부분 해로 이루어질 수 있는 경우입니다.

 

 

최소신장트리, Kruskal

예시문제

MST 특히 Kruskal 알고리즘은 서로소 집합 알고리즘을 통해 활용되는 문제가 대부분입니다.

최소신장트리 말 그대로, 간선의 합이 최소가 되는 트리를 만드는 것이 해당 알고리즘의 목적이죠.

 

크루스칼의 목적은 아래와 같은 그래프를 트리로 만들되 최소 비용을 사용하는 것이 목적입니다.

(간선은 비용은 각 노드를 연결하는 비용이라 생각하시면 됩니다.)

그림 2. 예시 그래프

그림 3. Kruskal 적용

 

Kruskal을 이용하면 위와 같이 트리를 만들 수 있습니다.

우선순위 큐를 이용해 간선 생성 비용의 오름차순으로 정렬하고 각 노드를 연결하다 트리가 되는 순간 완료됩니다.

해당 알고리즘 또한 현재 최적의 선택이 다음 최적 선택에 영향을 주지 않습니다.

또한 이렇게 묶인 비용이 트리를 생성하는 최적의 비용이 됩니다.

 

주목하실 점은 5번과 10번 노드의 간선과 4번과 8번 노드의 간선입니다.

분명 비용 오름차순으로 연결한다 했는데, 같은 비용임에도 불구하고 어떻게 트리가 완성되었다 판단하고 간선 생성을 멈췄을까요?

그 이유는 서로소 집합 덕분입니다.

 

또한 1-8의 간선이 1-3-4-8보다 짧은데도 불구하고 1-3-4-8가 연결되어있습니다.

그 이유는 최단 경로를 찾는 것이 아닌 가장 적은 비용의 트리를 만들기 위함입니다.

해당 그림에선 12를 연결하고 트리를 만든다면 훨씬 더 많은 비용이 들게 됩니다.

 

 

다익스트라 알고리즘 (Dijkstra, 최단경로)

예시문제

다익스트라는 시작 정점부터 끝 정점까지 가장 빨리 도달할 수 있는 경로를 찾는 알고리즘입니다.

 

다익스트라는 매 순간 최소 비용을 선택해 최종적으로 최단 경로를 찾아냅니다.

부분 경로의 최단 경로의 집합은 전체 경로의 최단 경로(Optimal substructure)라는 정의를 가집니다.

또한, 경로상에 음의 가중치가 존재하면 사용할 수 없습니다.

 

 

허프만 코드 (Huffman's code)

논외로 데이터 압축 기법에 사용되는 허프만 코드 또한 그리디의 일종입니다.

허프만 코드는 약식으로 기재하는 경우 혼란이 가중될 것 같아 포함된다는 점만 이야기드립니다.

 

 

Kruskal, Dijkstra, Huffman's code는 추후에 좀 더 정확한 개념과 함께 소개할 예정이라 여기서는 간단하게 짚었습니다.

 

 

---

다양한 예시를 살펴봤습니다. 우선 공통점이 하나 존재했습니다,

 

특정 값을 기준으로 그리디하게 판단한다.

즉, 가장 빨리 끝나는 수업/가장 적은 비용 등 매 순간 이러한 값을 알기 위해선 일반적으로 정렬이 필요해 보입니다.

 

또한, 적용 가능한지 증명이 가능해야 합니다. 이것이 그리디 문제가 어려운 가장 큰 이유라고 생각합니다.

위에 말씀드린 Greedy choice property, Optimal substructure가 만족하고 적용 가능한지 확인해 보세요.

이러한 증명을 어떻게 하느냐가 결국엔 그리디 포스팅에 가장 중요한 쟁점이라 생각합니다.

 

하지만, 현재 실제로 보여드릴 수 있는 것은 없어 보입니다. 쉬운 문제부터 하나씩 풀어보고 증명해보는 것이 가장 정확할 것 같습니다.

물론 조금 더 어려운 문제도 감으로 풀고 맞힐 수 있습니다만, 하나씩 증명하며 실력을 쌓아가는 것이 중요해 보이네요.

 

관련된 의견, 질문, 피드백 환영합니다.

남겨주시면 같이 고민해보고 보완해보도록 하겠습니다. 감사합니다.