1주차 - 그리디 이론

정의

• ‘탐욕스러운’ 혹은 ‘욕심 많은’을 뜻하는 알고리즘으로 선택의 순간마다 바로 눈앞에 보이는 이익만을 좇는 알고리즘을 뜻합니다.
• 즉, 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법을 말합니다.
• 결정을 내리는 순간마다 가장 최선의 선택을 통해 전체적인 최적의 해결책을 찾아내고자 하는 노력에서 비롯되었습니다. 각 단계에서의 최선의 선택이 결국 전체적인 최적의 해결책을 제공해주는 경우가 많습니다.
• 동적 프로그래밍을 사용하게 되면 중복되는 하위 문제를 다루게 되는데 이것이 많은 연산량과 계산 복잡도가 커지게 한다는 한계점을 가지고 있습니다. 이러한 점에 착안하여 고안된 알고리즘입니다. (동적 프로그래밍을 대체하는 것이 아닌 서로 보완하는 개념입니다)

특징

대부분의 경우 계산 속도가 빠르므로 매우 실용적인 편입니다.

어떤 경우에 사용할 수 있을까?

• 최적화 문제를 대상으로 합니다.
• 즉, 정해진 시간 내에 최적에 가까운 답을 찾는 방법으로 정답에 근사하는 정답을 찾는 방법

대표적인 알고리즘

• 다익스트라 알고리즘
• 압축 알고리즘: 허프만 코딩
• 의사결정트리

그리디 알고리즘을 적용하기 위한 조건

탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건을 만족해야 그리디 알고리즘으로 해결할 수 있습니다.

• 최적 부분 구조: 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것 (다시 고려할 필요가 없음)
• 탐욕스런 선택 조건: 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것

탐욕 알고리즘 문제를 해결하는 방법

• 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다.
• 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다.
• 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

그리디 알고리즘 vs 다이나믹 알고리즘

• 다이나믹 프로그래밍은 하위 문제에 대한 최적의 솔루션을 찾은 다음, 이 결과들을 결합한 정보에 기반하여 전역(global)의 최적인 해결책에 대한 선택을 하는 것인 반면, 그리디 알고리즘은 각 단계마다 로컬 최적해를 찾는 문제로 접근해 문제를 더 작게 줄여나가는 형태입니다 → 서로 반대 방향으로 접근하는 구조입니다.