poArlim poArlim

1. 탐욕적 기법(Greedy Algorithm)이란? 탐욕적 기법, 혹은 욕심쟁이 기법이라고 불리는 이 알고리즘은 말 그대로 욕심쟁이처럼 항상 눈앞의 가장 큰 이익만을 좇는 방법이다. 대부분의 알고리즘은 큰 문제를 작은 문제로 쪼개어 해결하는 과정을 거치는데, 탐욕적 기법은 작은 문제들을 해결하는 과정에서 전체 결과를 생각하지 않고 당장 작은 문제의 최적해를 찾고 이를 모두 더하여 최종 결과를 도출하게 된다. 이러한 기법은 생각보다 잘 통하는 경우가 많지 않다. 아래 그림을 보자. 서울에서 부산까지 최단거리로 가는 방법은 서울->대전->부산의 경로로 4.5km 이지만, 이 상황에 탐욕적 기법을 적용하면 알고리즘은 각 단계에서 최적해, 즉 가장 가까이 있는 도시로 이동하여 서울->인천->대전->부산의 경..