[cs준비] 그리디 알고리즘이란?

그리디 알고리즘이란 여러 경우 중 매 순간 최적이라고 생각되는 선택지를 선택하는 방식으로 진행해서 최종적으로 값을 구하는 방식이다

 

따라서 특정 문제를 만났을 때 단순히 현재 상황에서 최적이라고 생각하는 답만 골랐을 때에도 문제를 정상적으로 풀 수 있는지를 고려하는 것이 가장 중요하다.

 

대표적인 예시로는 동전문제, 회의실 문제 등이 있다.

 

동전 문제는 거스름돈을 거슬러 줄 때 가장 적은 수의 동전을 가지고 거슬러 주는 문제인데 이 때에는 동전들을 내림차순 정렬한 뒤 가장 큰 동전부터 비교해가면서 거슬러 주면 된다.

- 현재 기준에서 가장 큰 동전 말고 더 좋은 선택지가 없기 때문에 이런식으로 구하다 보면 거스름돈을 위한 최소한의 동전 개수를 고를 수 있다.

- 하지만 배수가 되지않는 금액 [ex)100, 400, 500] 이런식으로 동전이 주어지게 된다면 그리디 알고리즘으로는 풀 수 없다.

 

그리디 알고리즘의 장점으로는 계산속도가 빠르다는 것이다.

하지만 단점으로는 현재의 선택이 다음 선택에는 전혀 무관한 값이여야 함을 증명해야 한다.