그리디(Greedy)

그리디 알고리즘은 문제를 해결할 때 현 시점에서 가장 최선이라고 판단되는 선택(local optimum)을 반복적으로 수행하여 전체 문제를 해결하는 알고리즘 설계 기법으로, 이는 '근시안적' 인 선택을 통해 부분 최적해를 찾고, 이를 모아 전체 문제에 대한 최적해를 얻고자 하는 방식이다.

이러한 선택은 항상 전체 문제의 최적해(global optimum)를 보장하지 않기 때문에, 그리디 알고리즘이 항상 최적해를 찾을 수 있는 것은 아니다. 하지만, 특정 조건을 만족하는 문제에서 그리디 알고리즘은 적은 계산량으로 빠르고 효율적으로 최적해를 구할 수 있다.

그리디, 동적 계획법(DP), 분할 정복 간의 비교링크를 제목에 복사

그리디 알고리즘이 최적해를 보장하는 경우링크를 제목에 복사

• 최소 신장 트리(Minimum Spanning Tree, MST)를 구하는 알고리즘
  • 프림(Prim) 알고리즘
  • 크루스칼(Kruskal) 알고리즘
• 메트로이드(Matroid) 구조를 만족할 때
• 허프만 코딩(Huffman Coding)

그리디 알고리즘의 적용 대상링크를 제목에 복사

• 최적 부분 구조(Optimal Substructure)
• 탐욕 선택 속성(Greedy Choice Property)

최적 부분 구조(Optimal Substructure)링크를 제목에 복사

문제에 대한 최적해가 그 하위 문제(subproblem)들의 최적해를 통해 구성될 수 있는 성질

예시: 피보나치 수열, 최단거리

탐욕 선택 속성(Greedy Choice Property)링크를 제목에 복사

각 단계에서 최적의 선택을 했을 때 최종적으로 최적의 해답을 구할 수 있는 경우

예시: 동전 거스름돈 문제, 활동 선택 문제

그리디 알고리즘의 절차링크를 제목에 복사

1. 선택 절차(Selection Procedure)

2. 적절성 검사(Feasibility Check)

   • 만족한다면 다음 단계로 넘어간다.
   • 만족하지 않으면 새로운 탐욕적 선택을 시도한다.

3. 해답 검사(Solution Check)

   • 해결되었다면 종료한다.
   • 해결되지 않았다면 새로운 탐욕적 선택을 시도한다.

더 이상 가능한 탐욕적 선택이 없거나, 문제를 해결할 수 없다고 판단되면 종료한다. 이 경우, 그리디 알고리즘으로는 문제를 해결할 수 없으므로 다른 알고리즘을 고려해야 한다.