그리디 알고리즘 (Greedy Algorithm)

그리디 알고리즘 (탐욕 알고리즘) 이란?

• Greedy는 '탐욕스러운, 욕심 많은' 이라는 뜻이다.
• 그리디 알고리즘은 선택하는 순간마다 당장 최적의 상황만을 선택해 최종적인 해답에 도달하는 방법이다.
• 그리디 알고리즘은 최적의 해를 구하는 데에 사용되는 근사적인 방법이다.
• 순간마다 선택하는 답은 그 순간에서는 지역적으로 최적의 답일 순 있지만, 그 선택들을 계속 수집하여 나온 최종적인 답은 최적이 아닐 수 있다.
• 시간적으로 매우 효율적임.
• 수학적 증명이 요구되는 사항이 많음. 
• 코딩 테스트의 경우 비슷한 문제나 직관에 의해 판단 할 수 있도록 문제가 주어짐. 그렇기에 많은 문제를 풀어서 감을 익힐 수 있도록 해야함.

---

예시

1. 루트 노드 7에서 시작해서 10과 12의 대소관계를 파악한다.
2. 더 큰 12를 택한 후 다음 16과 30에 대한 대소관계를 파악한다.
3. 더 큰 30을 택한다. 다음 루트가 Greedy Algorithm을 사용한 최적해 루트이다.

---

그리디 알고리즘을 쓰는 경우

• 주로 O(n) 시간 복잡도를 갖기에 입력범위가 큰 경우가 많다. (1,000,000 이상인 경우)
• 순간의 최적해가 전체 문제의 최적해가 될 수 있도록 해야함.
• 그렇기 때문에, 정렬 후 접근하는 문제가 굉장히 많음.

---

그리디 알고리즘 풀이 순서

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

---

연관 문제

문제 - 1 페이지