코딩테스트에서 자주 나오는 유형
아래 두 조건을 문제가 만족을 하면, 그리디 알고리즘으로 해결을 한다.(시간상 이득)
그렇지 않은 경우 항상 최선의 해답을 내놓지 못할 수 있음.
문제에서 그리디인지 아닌지를 판단하려면 반례 하나만 들어봐도 알 수 있으니, 예시를 잘 생각하자.
도둑문제에 그리디를 적용할 수 없는 이유는, 이전의 선택이 추후의 선택에 영향을 주기도 하고(물건이 단 1개씩만 있으니까) 부분 문제에 대한 최적 해결 방법이, 최종 해결 방법을 구성하지 못하기 때문이다. 첫번째 단계에서는 그림 선택하는게 최선의 선택이었지만, 사실살 전체적으로 봤을 때 최선의 선택은 반지와 컴퓨터를 선택하는 것이었다. 이러한 반례가 있기 때문에 그리디 알고리즘 적용이 어렵다.
사실상 그리디 알고리즘은 백트래킹과는 다른 개념이다. 왜냐하면 백트래킹의 경우, 앞에서 선택한 요소가 이후의 선택에 큰 영향을 주기 때문이다. 예를 들면 스도쿠가 있겠다.
동적계획법은 그리디 알고리즘과 문제에 접근하는 방식이 굉장히 유사하다. 부분 문제를 최적화하는 기법이, 전체 문제를 최적화하는 기법에 사용된다는 점에서다. 하지만 동적계획법은 그리디 알고리즘과는 달리, 작은 부분 문제를 풀 때 그 안에서 모든 경우의 수를 고려해 이를 조합하여 최적의 해결책을 찾아나간다.
이러한 이유로 그리디를 사용할 수 있는 문제에 동적계획법을 쓰게 되면 시간이 오래 걸리는 경우가 있을 수 있음..
그리디를 사용하게 되면 항상 최적해를 보장할 수는 없지만, 그래도 시간적인 면에서 이득일 수 있다.
예) 거스름돈 문제
거스름돈 문제에 그리디를 적용할 수 있는 이유는, 이전의 선택이 추후의 선택에 영향을 주지 않기 때문. 풀어서 설명해 보면, 500원짜리 동전을 앞에서 썼다고 그 이후에는 500원을 못 쓰는 게 아니기 때문이다. 앞에서 뭘 선택했든, 선택할 수 있는 동전의 종류는 500,100,50,10으로 항상 일정하다. (앞의 선택에 따라 변화하는 것은 남은 거스름돈의 금액)
또한 부분문제에 대한 최선의 선택들을 조합했을 때, 전체 문제에 대한 최선의 선택이 되기 때문이다
비슷한 문제로 활동 선택 문제도 있음.