[Algorithm] 그리디 알고리즘 정리 + 백준 추천 문제

 

그리디 알고리즘(Greedy Algorithm)은 '탐욕(Greedy)'이라는 이름에 알맞게

지금 당장 가질 수 있는 최고의 이익을 따라가는 알고리즘을 의미한다.

 

모든 경우 최적해를 보장하지는 못하지만,

드물게 최적해를 결과로 내는 경우도 있다.

합리적인 시간 내로 최적에 가까운 해답을 찾을 수 있다는 점에서 유용한 알고리즘이다.

 

그리디 알고리즘이 잘 작동하는 문제들은

이전의 선택이 이후의 선택에 영향을 주지 않는 문제들이 많다.

물론 꼭 그렇지 않더라도 괜찮은 정답을 찾을 수 있는 알고리즘이다.

 

다이나믹 프로그래밍(DP)과는 최적 부분 구조 문제를 푼다는 점에서 약간 다른데,

DP가 하위 문제에 대한 최적의 솔루션을 찾은 다음, 이를 이용한 전역 최적 솔루션을 찾는 것이라면

그리디는 각 단계마다 지역 최적해를 찾는 문제로, 문제를 더 작게 줄여나가는 형태다.

 

코딩테스트에서 어느정도 인기 있는 유형이고,

문제의 난이도가 좀 높아지면 스택, 우선순위 큐 등의 자료구조와 엮어서 푸는 문제들도 종종 보인다.

 

---

 

그리디 알고리즘으로 풀 수 없는 문제도 존재한다.

대표적인 예로 트리 구조에서 가장 큰 합을 구하는 문제가 있다.

 

그리디로 접근한 가장 큰 합 찾기

 

루트 노드인 2부터 시작해서 탐색하는 자식 노드의 숫자들을 더하고

결과적으로 가장 큰 합을 만들기 위해서 그리디 알고리즘으로 접근한다고 가정하자.

그렇다면 위 그림처럼 각 level에서 큰 값을 취해 2 -> 9 -> 14를 결과로 내게 될 것이다.

 

하지만 2 -> 3 -> 50을 따라가면 훨씬 큰 값을 output으로 낼 수 있지만

그리디 알고리즘으로는 50 노드를 찾아갈 수 없다.

루트 노드에서 3과 9중 그리디 알고리즘 방식을 택한다면 3을 택하지 않을 것이기 때문이다.

해당 문제는 이진트리를 정렬한다든지 작업을 해주지 않는 이상 그리디로 풀 수 없다.

 

---

 

그리디 알고리즘 백준 추천 문제

 

14916 - 거스름돈 (실버 5)

20300 - 서강근육맨 (실버 3)

20365 - 블로그2 (실버 3)

11501 - 주식 (실버 2)

11000 - 강의실 배정(골드 5)

2212 - 센서 (골드 5)

2141 - 우체국 (골드 4)

2812 - 크게 만들기 (골드 3)