알고리즘/시작하기
2020. 4. 16.
탐욕법 (Greedy)
탐욕법은 각 단계마다 지역적으로 최적인 선택을 하면서, 결국 전역 최적해를 찾는 방식의 알고리즘입니다. 조금 더 쉽게 말하자면, 각 단계에서 지금 "가장 좋아보이는" 선택을 하는 것을 반복해서, 결국 전체적으로 가장 좋은 선택이 되도록 하는 알고리즘을 말합니다. 하지만 이 방식을 모든 문제에서 쓸 수 있는 것은 아닙니다. 간단한 예를 들어봅시다. 다음과 같은 그래프가 있습니다. 우리는 1번 정점에 있고, 4번 정점까지 최단거리를 구하려고 합니다. 그리디하게 접근해봅시다. 현재 1번 정점에서 거리 5인 2번정점으로 가는 것 보다는, 거리가 2인 3번 정점으로 가는 것이, 현재 "가장 좋아보이는 선택"입니다. 하지만 실제 최단 거리는 그렇지 않음을 쉽게 알 수 있습니다. 따라서 탐욕법을 이용해 문제를 풀고자..