탐욕법 (그리디 알고리즘)의 원리와 한계

By [email protected]

2025-05-05

0

12

💰 탐욕법 (그리디 알고리즘)의 원리와 한계

탐욕법은 각 단계에서 현재 상황에서의 최적해만을 선택하며 문제를 해결하는 알고리즘적 접근 방식이다. 전체 문제에 대한 최적해를 보장하지 않는 경우가 있으나, 특정 조건에서는 효율적인 해법을 제공하였다.

🧠 탐욕법의 핵심 개념

1. 기본 원리

– 탐욕법(그리디 알고리즘)은 매 순간마다 최선의 선택만을 고려하였다
– 다른 경우나 미래의 결과는 고려하지 않는 방식이었다
– 항상 그 순간에만 판단하여 최적이라 생각되는 선택을 하였다

2. 완전 탐색과의 차이점

– 완전 탐색은 모든 가능한 경우를 다 살펴보는 방식이었다
– 탐욕법은 각 단계에서 하나의 최선 경우만 선택하여 진행하였다
– 계산 속도 측면에서 완전 탐색보다 빠른 장점이 있었다

🚫 탐욕법의 한계

1. 반례 존재

– 지금 당장 최선의 선택이 전체적인 최적해가 아닌 경우가 발생하였다
– 현재 최선으로 보이는 B를 선택했으나, 실제로는 D를 선택했을 때 더 좋은 결과가 나오는 경우가 있었다
– 이러한 반례가 존재하는 문제는 탐욕법으로 해결할 수 없었다

💵 동전 문제로 살펴본 탐욕법

1. 첫 번째 케이스: 배수 관계가 성립하는 경우

– 10원, 50원, 100원, 500원 동전이 무한히 있는 상황이었다
– 손님에게 _800원_을 거슬러 주는 최소 동전 개수를 구하는 문제였다
– 큰 단위부터 사용하여 500원 1개, 100원 3개로 총 4개 동전을 사용하였다
– 이는 탐욕법으로 최적해를 얻을 수 있는 경우였다

2. 두 번째 케이스: 배수 관계가 성립하지 않는 경우

– 100원, 400원, 500원 동전이 무한히 있는 상황이었다
– 마찬가지로 손님에게 _800원_을 거슬러 주어야 하였다
– 단순히 큰 단위 동전부터 사용하면 500원 1개, 100원 3개로 총 4개 사용하였다
– 그러나 400원 2개를 사용하면 총 _2개_로 더 적은 동전을 사용할 수 있었다
– 탐욕법이 최적해를 보장하지 않는 경우였다

🔍 탐욕법 적용 가능 조건 분석

1. 배수 관계의 중요성

– 첫 번째 케이스에서 10원, 50원, 100원, _500원_은 모두 배수 관계였다
– _50원_은 _10원_의 배수, _100원_은 _50원_의 배수, _500원_은 _100원_의 배수였다
– 이런 배수 관계에서는 항상 큰 단위 동전을 사용하는 것이 최적이었다

2. 배수 관계가 아닌 경우

– 두 번째 케이스에서 _400원_은 _100원_의 배수이지만, _500원_은 _400원_의 배수가 아니었다
– 배수 관계가 끊어져 있을 때는 탐욕법이 최적해를 보장하지 않았다
– 이런 경우 단순히 큰 단위 동전부터 사용하는 것이 최선이 아니었다

🧩 그리디 문제의 어려움

1. 적용 가능성 판단

– 그리디 알고리즘 문제의 가장 어려운 점은 해당 방법이 적용 가능한지 판단하는 것이었다
– 문제를 보고 그리디로 풀 수 있는지, 반례가 존재하는지 파악해야 하였다
– 알고리즘 선택 자체가 문제 해결의 중요한 부분이었다

2. 규칙성 발견

– 탐욕법 문제는 일정한 규칙성을 발견해야 하는 경우가 많았다
– 그리디 적용 시 어떤 기준으로 ‘최선’을 선택할지 결정하는 것이 중요하였다

🏅 탐욕법(그리디 알고리즘) 적용 대표 문제

1. 💸 거스름돈 문제

1.1. 문제 개요

– 손님에게 거슬러 줄 금액을 가장 적은 동전/지폐 개수로 지급하는 방법을 찾는 문제
– 예시: 10, 50, 100, 500원 동전이 있을 때 800원을 최소 동전 개수로 거슬러 주기

1.2. 탐욕법 적용 이유

– 큰 단위 화폐부터 최대한 사용
– 각 단계의 선택이 이후 선택에 영향을 주지 않음
– 동전 단위가 배수 관계일 때 항상 최적해를 보장

2. 🌳 최소 신장 트리(MST) 문제

2.1. 문제 개요

– 그래프의 모든 정점을 최소 비용으로 연결하는 트리를 찾는 문제
– 대표 알고리즘: 크루스칼(Kruskal), 프림(Prim)

2.2. 탐욕법 적용 이유

– 가장 비용이 낮은 간선부터 선택
– 이미 연결된 부분과 사이클이 생기지 않도록 함
– 각 단계의 선택이 전체 최적해 구성에 기여

3. 🛣️ 다익스트라(Dijkstra) 최단 경로 문제

3.1. 문제 개요

– 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제

3.2. 탐욕법 적용 이유

– 가장 가까운 정점부터 방문
– 이미 방문한 정점은 다시 방문하지 않음
– 각 단계에서의 최선 선택이 전체 최적해로 이어짐

4. 🔤 허프만 코딩(Huffman Coding)

4.1. 문제 개요

– 문자 빈도에 따라 가변 길이의 이진 코드를 할당하여 전체 인코딩 길이를 최소화

4.2. 탐욕법 적용 이유

– 가장 빈도가 낮은 노드부터 합쳐 트리를 구성
– 각 단계의 선택이 전체 최적해에 기여

5. 🏃 활동 선택(Activity Selection) 문제

5.1. 문제 개요

– 겹치지 않는 최대 활동 개수를 선택하는 문제
– 각 활동의 시작/종료 시간이 주어짐

5.2. 탐욕법 적용 이유

– 종료 시간이 가장 빠른 활동부터 선택
– 선택된 활동과 겹치지 않는 다음 활동을 반복적으로 선택

6. 🔢 가장 큰 수 만들기

6.1. 문제 개요

– 주어진 숫자 배열로 만들 수 있는 가장 큰 수를 만드는 문제

6.2. 탐욕법 적용 이유

– 가장 큰 숫자부터 차례로 선택하여 조합

7. 📦 Fractional Knapsack (분할 배낭) 문제

7.1. 문제 개요

– 무게 제한이 있는 배낭에 가치/무게 비율이 가장 높은 물건부터 담아 최대 가치를 구하는 문제

7.2. 탐욕법 적용 이유

– 가치/무게 비율이 높은 순서대로 물건을 담음

📝 정리 표

문제 유형	대표 예시/알고리즘	탐욕적 선택 기준
거스름돈 문제	동전 최소 개수	큰 단위 화폐부터 선택
최소 신장 트리	크루스칼, 프림	비용이 가장 낮은 간선 선택
최단 경로	다익스트라	가장 가까운 정점부터 방문
허프만 코딩	허프만 트리	빈도 낮은 노드부터 합침
활동 선택	Activity Selection	종료 시간 빠른 활동 선택
가장 큰 수 만들기	배열 정렬	큰 숫자부터 조합
Fractional Knapsack	배낭 문제(분할 가능)	가치/무게 비율 높은 것부터

🧩 추가 설명

– 탐욕법은 탐욕적 선택 속성과 최적 부분 구조 조건이 성립할 때 최적해를 보장
– 적용 전 항상 반례가 없는지, 문제 조건이 탐욕법에 적합한지 검토 필요1 2 3 6

Citations:

https://www.money-writing.com/%eb%b8%8c%eb%a3%a8%ed%8a%b8-%ed%8f%ac%ec%8a%a4-%ec%95%8c%ea%b3%a0%eb%a6%ac%ec%a6%98-%ec%99%84%ec%a0%84-%ed%83%90%ec%83%89%ea%b3%bc-%ec%b5%9c%ec%a0%81%ed%99%94-%ec%a0%84%eb%9e%b5/

🔍 브루트 포스 알고리즘 완전 탐색과 최적화 전략