[알고리즘] 그리디(탐욕)

그리디(탐욕)

• 각 단계에서 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘
• 항상 최적의 값을 보장하는것이 아니라 최적의 값의 ‘근사한 값’을 목표로
• 최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론
  • 단기적인 목표를 중심으로 한 전략적인 접근 방법

그리디 알고리즘의 성립 조건

• 탐욕 선택 속성
  • 각 단계에서 ‘최선의 선택’을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우
• 최적 부분 구조
  • 전체 문제의 최적해가 ‘부분 문제의 최적해로 구성’될 수 있는 경우

그리디 알고리즘의 단계

1. 문제의 최적해 구조를 결정
2. 문제의 구조에 맞게 선택 절차를 정의
3. 선택 절차에 따라 선택을 수행
4. 선택된 해가 문제의 조건을 만족하는지 검사
5. 조건을 만족하지 않으면 해당 해를 제외
6. 모든 선택이 완료되면 해답을 검사
7. 조건을 만족하지 않으면 해답으로 인정되지 않음

시간 복잡도

• for문으로 전체 탐색하는 경우: O(N)

자료 구조

• 구현에 따라 다름