[Algorithm] 그리디 알고리즘(Greedy Algorithm)

Greedy Algorithm이란?

Greedy 알고리즘이란 동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘이다. 동적  프로그래밍을 대체하는 것은 아니고 같이 쓰이며 서로 보완하는 개념이다.

Greedy 알고리즘은 탐욕 알고리즘 또는 욕심쟁이 알고리즘이라고 불리기도 하는데, 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법이다. 이렇게 각 단계에서 최선의 선택을 하는 것이 전체적으로도 최선이길 바라는 알고리즘이다.

물론 모든 경우에서 Greedy 알고리즘이 통하지는 않는다. 당장 최선의 방법을 선택해도 시간이 조금 지난 후에 더 나은 선택지가 있을 수 있기 때문이다.

하지만 Greedy 알고리즘이 통하는 몇몇 케이스가 존재하기 때문에 해당 케이스의 유형을 파악하는 것이 중요하다.

 

가장 기본적인 예로 '활동 선택 문제'와 '분할 가능 배낭 문제'를 들 수 있다.

 

[작성 중]