문제 해결 전략 중 **완전 탐색(Brute-Force)**과 **탐욕 알고리즘(Greedy Algorithm)**은 가장 대표적이고 기본적인 설계 패러다임입니다.
1. 억지 기법 / 완전 탐색 (Brute-Force)
가능한 모든 입력 경우의 수를 무식하고 직접적으로 계산하여 정답을 찾는 방법입니다.
- 장점: 단순하고 항상 정확한 최적해를 보장함.
- 단점: 문제의 크기 $N$이 커질 경우 실행 시간이 폭발적으로 증가 ($O(2^N)$ 또는 $O(N!)$).
- 예시: 순차 탐색, 모든 조합/순열 생성, 비밀번호 대입.
2. 탐욕 알고리즘 (Greedy Strategy)
전체적인 상황을 고려하지 않고 **매 순간 최적이라고 판단되는 선택(Local Optimum)**을 내려 최종 해답에 도달하는 기법입니다.
탐욕 알고리즘의 성립 조건 2가지
- 탐욕적 선택 속성 (Greedy Choice Property): 현재의 최적 선택이 이후의 선택에 악영향을 주지 않음.
- 최적 부분 구조 (Optimal Substructure): 부분 문제의 최적해들로 전체 문제의 최적해를 구성할 수 있음.
3. 대표적인 탐욕 알고리즘 예시: 동전 거스름돈
def min_coins(amount, coins=[500, 100, 50, 10]):
count = 0
for coin in coins:
count += amount // coin
amount %= coin
return count
print(min_coins(1260)) # 500원 2개, 100원 2개, 50원 1개, 10원 1개 -> 총 6개
주의: 동전 단위가 서로 배수 관계가 아닐 경우 탐욕법은 최적해를 보장하지 못하며, 이 경우 동적 계획법(DP)을 사용해야 합니다.
4. 자주 묻는 질문 (Q&A)
Q. 탐욕 알고리즘이 항시 최적해를 보장하지 못하는데도 사용하는 이유는 무엇인가요? A. 완전 탐색이나 DP로 풀기에는 시간 복잡도가 너무 높은 NP-난제 문제 등에서 빠르게 만족할 만한 근사해(Approximation Solution)를 얻을 수 있기 때문입니다.