그리디 알고리즘(탐욕법)

그리디 알고리즘 (Greedy Algorithm)

그리디 알고리즘은 눈앞의 가장 좋은 것을 매 순간 선택해서 결국 전체적으로도 좋은 결과를 얻기를 기대하는 알고리즘. 

핵심 아이디어:

• 매 순간의 최적 선택: 현재 상황에서 가장 최선이라고 생각되는 선택을 한다.
• 전체 최적 해 보장 X: 각 단계의 최적 선택이 최종적인 최적 해를 보장하지는 않는다. 하지만 많은 경우에 꽤 괜찮은 해답을 빠르게 찾을 수 있다.

쉬운 예시: 거스름돈 문제

만약 700원을 거슬러 줘야 하고, 동전 종류가 500원, 100원, 50원, 10원이 있다고 생각해 보자. 그리디 알고리즘 방식대로라면 아래와 같이 계산한다.

1. 가장 큰 동전인 500원짜리를 최대한 많이 (1개) 준다. 남은 돈은 200원.
2. 다음으로 큰 동전인 100원짜리를 최대한 많이 (2개) 준다. 남은 돈은 0원.

결과적으로 500원 1개, 100원 2개, 총 3개의 동전으로 거스름돈을 준 셈이다. 이 경우에는 최소 개수의 동전으로 거스름돈을 주는 최적의 해답과 같다.

하지만 항상 최적은 아니다

만약 동전 종류가 500원, 400원, 100원이라고 하고, 800원을 거슬러 줘야 한다고 가정한다.

• 그리디 알고리즘: 500원 1개 선택 (남은 300원) -> 100원 3개 선택. 총 4개의 동전.
• 최적 해답: 400원 2개 선택. 총 2개의 동전.

이처럼 그리디 알고리즘은 매 순간 최적의 선택을 하지만, 전체적으로 봤을 때는 최적의 해답이 아닐 수도 있다.

그리디 알고리즘이 유용한 경우:

• 단순하고 빠른 해답: 복잡한 계산 없이 빠르게 결과를 얻고 싶을 때.
• 근사적인 해답: 최적 해가 아니어도 괜찮고, 어느 정도 만족스러운 해답을 찾는 것이 중요할 때.
• 특정한 문제 유형: 거스름돈 문제처럼 탐욕적인 선택이 항상 최적 해를 보장하는 특정 유형의 문제.

정리하자면:

그리디 알고리즘은 매 순간 가장 탐욕스러운 선택을 해서 문제를 해결하는 방법. 이해하기 쉽고 구현도 간단하지만, 항상 최고의 결과를 보장하지는 않는다.