개요
아래 내용은 Greedy(탐욕법)의 핵심 개념을 먼저 정리한 뒤, A4greedy 패키지에 있는 실습 코드(최소 동전 개수)를 통해 “정렬 기준 → 매 선택의 규칙 → Greedy가 성립하는 조건(언제 맞고 언제 틀리는지)”를 한 흐름으로 정리한 글이다.
Greedy(탐욕법)란?
Greedy는 “매 순간 가장 좋아 보이는 선택”을 반복해서 답을 만들어내는 방식이다. 즉, 각 단계에서의 지역 최적(local optimum)을 선택해 전역 최적(global optimum)을 노린다
다만 모든 문제에서 정답을 보장하진 않고, “이 문제는 Greedy 규칙이 항상 맞다”는 성질이 성립할 때만 안전하게 사용할 수 있다.
Greedy의 핵심 특징
Greedy 문제는 전형적인 DP처럼 “항상 같은 형태의 점화식”이 있는 게 아니라, 문제에 맞는 규칙(rule) 을 찾아야 한다.
규칙이 맞는지 확인할 때는 보통 다음을 점검한다.
- 지금 선택이 이후 선택을 망치지 않는가? (선택의 안정성)
- 부분 문제로 쪼갰을 때, “부분 최적해 + 선택”이 전체 최적해를 구성하는가? (구조적 성질)
대표 예시: 최소 동전 문제
최소 동전 문제는 “현재 남은 금액에서 가장 큰 동전을 최대한 많이 쓰는 선택”이 전체 동전 개수도 줄여준다는 규칙이 성립할 때 Greedy로 풀 수 있다.
단, 모든 동전 체계에서 이 규칙이 성립하는 건 아니고(예: 특정 동전 구성에서는 반례 존재), 문제에서 주어진 동전 체계가 Greedy를 허용하는 형태인지가 중요하다.
실습 코드 해설 (A01GreedyBasic)
1) 정렬: “큰 동전부터” 쓰기 위한 준비
int[] arr = {10, 5, 1, 20};
Arrays.sort(arr);정렬을 해두면 뒤에서부터 순회하면서 큰 동전 → 작은 동전 순으로 처리할 수 있다.
Greedy는 “매 순간의 선택 규칙”이 핵심이라서, 이 문제에서는 “가장 큰 동전부터 최대한 사용”이 그 규칙이 된다.
2) 현재 동전으로 최대한 사용
int b = target / a; // 몫
total += b;
target -= b * a;현재 금액(target)에서 동전 a를 몇 개 쓸 수 있는지 몫으로 구하고, 그 개수를 누적(total)한 뒤 남은 금액으로 target을 갱신한다.
이 흐름 자체가 “현재 시점 최선(가장 큰 동전 사용)”을 선택하는 Greedy의 전형적인 구현이다.
3) 전체 흐름 요약
- 동전을 정렬한다.
- 큰 동전부터, 가능한 만큼 최대한 사용한다.
- 남은 금액에 대해 같은 규칙을 반복한다.
Greedy를 쓸 때 주의할 점
Greedy는 빠르고 구현이 간단하지만, “항상 맞는 규칙인지” 검증 없이 적용하면 오답이 나올 수 있다.
그래서 코딩테스트에서는 보통 아래 방식으로 안전성을 확보한다.
- 문제 조건에서 Greedy가 성립한다고 암시되는지 확인
- 작은 반례를 직접 만들어 규칙이 깨지는지 테스트
- Greedy가 의심되면 DP/최단거리/이분탐색 등 다른 접근과 비교
