그리디 알고리즘은 언제 사용해야할까? (백준)

그리디 알고리즘은 언제 사용할까?

 

백준의 대표적인 그리드 알고리즘 문제

11047 - 동전0

 

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

 

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

---

✅ 1. 해당 문제(11047 - 동전 0)가 그리디로 최적해를 보장하는 이유

🔸 문제 요약:

• 주어진 동전 종류 A1, A2, ..., AN (오름차순 정렬됨)
• 각 동전은 무한히 존재
• 목표 금액 K를 가장 적은 동전 개수로 만들기

🔸 핵심 조건:

• 동전 단위가 배수 관계임
• 즉, 어떤 동전 단위는 항상 더 큰 동전의 배수 (예: 1, 5, 10, 50, 100, 500)

🔸 그리디가 최적해를 보장하는 이유:

• 큰 동전부터 최대한 사용하는 것이 항상 최적임
• 작은 동전 여러 개를 쓰는 것보다, 큰 동전 하나를 쓰는 게 효율적임
• 이 성질이 성립하는 이유는:
• "동전 단위가 배수 관계를 만족하면 greedy choice property가 보장됨"

✅ 이걸 Greedy Choice Property라고 해.
(현재 단계에서 가장 최선의 선택이 전체적으로도 최선이라는 성질)

---

✅ 2. 이 문제가 왜 '그리디 문제'인지 판단하는 기준

🔍 문제를 보고 그리디인지 유추하는 3가지 힌트:

힌트설명

최적화(최소/최대)	"가장 적은 수의 동전", "가장 큰 수익", "최소 시간" 같은 키워드
국소 최적이 전체 최적이 되는 구조	어떤 선택이 다른 선택에 영향을 덜 주거나, 영향이 독립적일 때
순차적, 선택적 구성	매 순간 하나씩 선택해서 누적해가는 방식 (ex. 선택/거절/대체)

 

예시로 적용:

• "동전 개수를 최소로" → 최적화 문제
• "큰 동전부터 최대한 쓴다" → 지금 최선이 전체에서도 최선
• "동전 하나씩 선택해간다" → 순차적 구조

✔ 이런 요소들이 있다면 그리디일 가능성이 매우 높음

✅ 3. 다른 유형의 그리디 문제에서도 어떻게 유추할까?

📌 주요 그리디 유형과 특징

유형	예시	아이디어
동전/자원 최소화	동전 0, 거스름돈	큰 단위부터 최대 사용
활동 선택 문제	회의실 배정, 강의실 배정	빨리 끝나는 순서대로 선택
정렬 후 선택	배낭 문제 (1차원)	가치/무게 비율 기준
우선순위 큐	최소 힙, 작업 스케줄	현재 가장 작은/큰 값 우선 처리
스케줄링/스위핑	CPU 스케줄링, 공항 문제	선형 시간 동안 최선 선택 유지

✅ 실전에서 유추하는 팁

• 문제에서 "한 번 결정하면 되돌릴 수 없다" → 그리디 가능성 ↑
• 매 순간 가장 좋은 선택을 고르면 정답일까? 라는 질문을 던져보자
• 선택의 결과가 다음 선택에 큰 영향을 주지 않는가? → 그리디 가능성 ↑
• 다르게 선택했다고 해도 전체 결과는 비슷한가? → 그리디 가능성 ↑

✅ 결론 요약

항목	설명
이 문제는 왜 그리디인가?	동전 단위가 배수 관계라, 큰 단위부터 쓰는 게 항상 최선
그리디가 최적해 보장 이유	Greedy Choice Property + Optimal Substructure 성립
다른 문제에서 유추 방법	최적화 + 순차 선택 + 선택이 다음에 큰 영향을 안 준다면 그리디 가능성 ↑

---

그리이 알고리즘을 선택하지 않아야할 경우는?

✅ 1. 그리디 선택이 전체 최적해를 보장하지 않는 경우

❌ [반례가 존재]하는 유형

🔹 예시 1: 배낭 문제 (Knapsack Problem) - 0/1 Knapsack

• 문제 요약: 무게 제한이 있는 배낭에 물건을 넣을 때, 최대 가치를 얻도록 물건을 선택
• 그리디 전략 오답 예시: 가치/무게 비율이 높은 것부터 넣기
• 실제 정답: DP (부분집합 조합 고려해야 함)
• 왜 틀림?
  • 어떤 물건을 한 번 넣으면, 이후 선택에 영향을 미치기 때문
  • 전체 조합 중 최적해가 있을 수 있음

✅ 2. 국소 최적이 전체 최적이 아닌 경우

🔹 예시 2: 문자열 압축/변환 문제

• 어떤 변환 과정에서 현재 문자열을 짧게 만드는 것이,
  이후 전체 문자열을 더 길게 만들 수도 있음

✔ 이럴 땐 BFS, DFS 또는 DP가 적합

 

✅ 3. 다음 선택에 영향을 주는 구조

🔹 예시 3: ATM 인출 시간 (백준 11399)

• 각 사람이 걸리는 시간이 다를 때, 줄을 어떻게 세워야 전체 대기 시간이 최소?
• 정답 전략: 인출 시간이 적은 순서대로 정렬 → 그리디
• 그런데 만약 "누군가를 먼저 보내는 데 페널티가 있다면", 그리디가 깨짐

✅ 4. 탐욕적 선택이 되돌릴 수 없는 구조

🔹 예시 4: 최소 스패닝 트리 - 크루스칼 vs 프림

• 크루스칼은 그리디지만, 사이클을 피해야 하므로 항상 가능한 간선을 선택할 수 없음 → 유니온 파인드 필요

✅ 그리디 오답 패턴 요약

오답 유형	설명	적절한 알고리즘
전체 조합 고려 필요	조합이 달라지면 결과가 달라지는 문제	DP, 완전탐색
선택이 미래에 영향 줌	한 번의 선택이 이후 상황 제한	DFS, BFS
가중치/조건 변화	선택 기준이 상황에 따라 달라짐	우선순위큐, DP
되돌릴 수 없음	국소 최적이 전체 최적 아님	백트래킹

✅ 정리: 그리디 사용 전 체크리스트

1. 선택이 다음 선택에 영향을 주는가? → 영향 크면 ❌
2. 지금의 최선이 전체에서 항상 최선인가? → 아니면 ❌
3. 문제에서 "최적해"를 구하라고 할 때, 조합을 고려해야 할 가능성은? → 그러면 DP나 탐색 필요
4. 문제에서 입력 조건이 다양하게 꼬여 있는가? → 그리디 단독으론 위험