[Algorithm] Greedy

[Greedy Algorithm]

 

• 문제 해결 과정에서 매 순간 가장 좋아 보이는 선택을 하는 방식이다.
• 각 단계에서의 선택은 국소적으로 최적 (locally optimal) 이지만, 전체적으로도 최적인지는 보장되지 않음.
• 한 번 선택한 것은 되돌리지 않으며, 항상 최종 해답에 포함된다.
• 일부 문제에서는 Greedy 방식이 전역 최적해 (globally optimal solution) 를 보장하기도 하지만, 항상 그런 것은 아니다.

ex) 거스름돈 문제

[General Greedy Approach]

1. 초기 상태

• 빈 집합(또는 빈 상태)에서 시작

2. 반복 과정

• 문제를 해결할 때까지 다음의 세 가지 단계 반복:

1. Selection Procedure (선택 절차)

• 탐욕 기준(greedy criterion)을 바탕으로, 현재 상태에서 가장 좋아 보이는 요소를 선택
  (예: 최소 비용, 최대 가치 등)

2. Feasibility Check (적합성 검사)

• 선택한 요소를 집합에 추가했을 때 제약 조건을 위반하지 않는지 확인
  (즉, 해당 선택이 부분해로서 유효한지 판단)

3. Solution Check (해결 조건 검사)

• 현재까지의 선택 집합이 문제의 해답 조건을 만족하는지 검사
  (예: 모든 작업이 배정되었는가, 필요한 용량이 채워졌는가 등)