그리디 알고리즘(Greedy Algorithm)

그리디와 이분탐색

왜 이분 탐색 다음에 그리디 알고리즘이 나왔느냐-

둘다 분할 정복, 재귀함수를 사용한다는 공통점이 있어 결이 비슷하기 때문이다.

 

그리디란?

그리디 알고리즘의 경우, 가장 좋은 해부터 찾아내고 나머지는 쪼개는 방식으로 진행한다. 밥먹을 때 제일 맛있는 반찬부터 먹는 욕심쟁이를 닮은 알고리즘 이랄까. 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법으로, 이것이 전체로 봤을 때도 최선이길 바라는 알고리즘이다. 따라서 적용할 수 있는 문제의 조건이 조금 까다로운 편이다.

 

비슷해 보여도 그리디를 쓸 수 있는 문제가 있고, 아닌 게 있다. 예를 들어, 동전을 사용해 어떤 금액을 표현하는 문제는 그리디로 풀리는데, 동전의 단위가 배수-약수관계가 아니면 그리디 알고리즘을 쓸 수 없다.

 

그리디 대표 유형

그리디가 적용될 수 있는 대표적인 문제들에는 '도시락 문제', '회의실 배정 문제' 등이 있다.

(백준 그리디 번호 - 11047, 2875, 10610, 1783, 1931, 11399, 2873, 1744)