[이론] 그리디(Greedy)

그리디 알고리즘은 각 단계에서 그 순간이 최선이라고 생각하며 선택하는 방식이다.

겉보기엔 간단하고 직관적이지만 항상 최적의 해를 보장하지는 않는다.

이번 포스터에선 그리디 알고리즘의 개념과 특징, 그리고 예시를 통해 알아보도록 하겠다.

 

 

---

그리디 알고리즘이란 무엇인가

 

그리디(Greedy): 문제를 해결할 때 각 단계에서 가장 최선이라고 생각되는 선택을 함으로써 전체 해를 구하는 방식

 

 

그리디를 사용하는 이유

 

그리디 알고리즘을 사용하면 많은 이점이 있습니다.

완전 탐색이 아닌, 최적의 해를 구하는 성질에 의한 경우만 탐색하면 되기 때문입니다.

 

 

구현이 간단하고 빠름

그리디 알고리즘은 성질에 따라 로직을 구현하면 되기 때문에 다른 알고리즘보다 구현하기 쉽다. 

 

계산 속도가 빠름

전체 경우가 아닌, 이미 성질에 의해 정해진 경우만 처리하기 때문에 계산 속도가 매우 빠르다.

DP 혹은 백트래킹보다 빠르며, 주로 O(n *log n) 혹은 O(n) 시간 복잡도를 가진다.

 

메모리 사용량이 낮음

이 역시 필요한 경우에 대해서만 메모리를 사용하기 때문에 메모리 사용량을 크게 낮출 수 있다.

 

 

 

---

그리디가 동작하는 원리

 

그리디를 사용하기 전에, 해당 문제가 탐욕적 선택 속성(Greedy Choice Property)과 최적 부분 구조(Optional Substructure)을 보유하고 있는지 확인해야 한다.

 

탐욕적 선택 속성: 각 단계에서 최선의 선택이 전체 문제의 최적해로 이어질 수 있는 속성

최적 부분 구조: 전체 문제의 최적해가 부분 문제들의 최적해로 구성될 수 있음

 

주로 수학적 귀납법을 통해 증명하여 그리디 알고리즘의 사용 여부를 결정한다.

하지만 코딩 테스트라면 시간이 촉박하니 다른 알고리즘을 먼저 생각하거나 반례를 통해 사용 여부를 결정하자.

 

 

 

---

그리디는 언제 사용하면 좋은가

 

아까 말한 대로 수학적 귀납법을 통해 탐욕적 선택 속성과 최적 부분 구조를 충족하면 사용하면 된다.

그리디를 사용하는 대표적인 문제는 다음과 같다.

• 활동 선택 문제(Activity Selection Problem)
• 최소 신장 트리(MST)
• 다익스트라 알고리즘(Dijkstra's Algorithm)
• 허프만 코딩(Huffman Coding)

코딩 테스트에서는 주로 정렬(sort) 혹은 우선 순위 큐(prioirty_queue)를 사용한다.

즉, 최적의 해를 구하기 위해선 문제의 요구를 파악하고 위 방식으로 자료구조를 정리해야 한다.

 

 

 

주로 다음과 같은 알고리즘이 가장 대표적이다.

 

라인 스위핑 (Line Sweeping)

 

마치 빗자루를 쓸듯이 탐색한다고 하여 붙여진 이름이다.

배열을 정렬하여 왼쪽 혹은 오른쪽부터 천천히 탐색하는 방식이다.

주로 최대 구간 및 횟수를 찾을 때 많이 사용한다.

 

예시 문제: 백준 2170번

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

 

투포인터 (Two Pointer)

 

두 개의 포인터를 사용하여 정렬된 배열에서 특정 조건을 만족하는 경우를 찾는다.

주로 두 수의 합 찾기, 연속된 부분의 배열의 합 찾기 등에 사용된다.

 

예시 문제: 백준 3273번

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

 

 

 

---

정리

사실 문제를 봤을 때 그리디라고 생각하기 어렵다. 왜냐하면 정말 그리디 문제라면 귀납법 증명을 통해 증명해야 하기 때문이다. (혹은 이미 풀어본 유형의 문제라서 기억하고 있거나) 그래서 주로 코딩 테스트에선 다른 알고리즘으로 접근했다가 최후의 방법으로 그리디를 선택하는게 일반적이다.