그리디(Greedy)

Greedy 알고리즘

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 이용하는 알고리즘으로 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
• 따라서 그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다. (그리디 알고리즘의 정당성)
• 보통 코딩 테스트에서 출제되는 그리디 알고리즘 유형의 문제는 창의력, 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.
• 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘 이므로, 그 기준을 알게 모르게 제시해준다. EX) ‘가장 큰 순서대로', ‘가장 작은 순서대로' 와 같은 기준 → 자주 정렬 알고리즘과 짝을 이뤄 출제된다.
• 다익스트라 최단경로 알고리즘, 크루스칼 알고리즘 모두 그리디 알고리즘에 속한다. (뒤에 설명)

 

(계속 추가 중)