[알고리즘] 23. 그리드 알고리즘

1. 그리디 알고리즘 개요

정의:

• 그리디(Greedy) 알고리즘은 최적화(optimization) 문제를 해결하는 알고리즘으로, 매 순간 가장 좋아 보이는 선택(최소 또는 최대)을 하는 방식이다.

 

특징:

• "욕심쟁이", "탐욕적 방법"이라고도 불린다.

• 데이터 간의 관계나 전체 구조는 고려하지 않으며, 그 순간 가장 좋은 선택만 고려한다.

• 이러한 선택을 **‘근시안적 선택(myopic choice)’**이라 한다.

• 선택한 해를 번복하지 않는다.

• 간단하고 빠르지만, 일부 문제에만 적용 가능하다.

• 부분적으로 최적해를 선택하고, 이들을 모아 전체 문제의 해답을 만든다.

 

 

2. 배낭 채우기(Knapsack) 문제

개념:

• 물건이 n개 있으며 각각 무게와 가치가 있음

• 배낭의 허용 무게는 W

• 가치의 합이 최대가 되도록 배낭에 물건을 선택하여 담는 문제

 

유형:

부분 배낭 문제 (Fractional Knapsack)
· 물건을 나누어 담을 수 있음
· 그리디 알고리즘으로 해결 가능

 

0-1 배낭 문제 (0-1 Knapsack)
· 물건을 나눌 수 없음 (모두 담거나 버려야 함)
· 동적 계획법, 백트래킹, 분기한정 기법 등으로 해결

 

1) 부분 배낭 채우기 문제

• 단위 무게당 가치가 높은 물건부터 순차적으로 선택

• 배낭이 가득 찰 때까지 물건을 담고, 남은 공간에는 해당 물건의 일부만 쪼개어 담을 수 있음

• 그리디 알고리즘으로 최적해 가능

 

2) 0-1 배낭 채우기 문제

예시 상황:

• 도둑이 보석상에 침입

• 각 보석의 무게와 가치를 알고 있음

• 배낭의 최대 무게 W를 초과하면 안 됨

• 총 가치를 최대화하도록 보석을 선택해야 함

 

문제 정의 (형식적 표현):

입력:
· 보석 수 n, 보석 집합 S = {item₁, item₂, ..., itemₙ}
· 각 보석의 무게: wi, 가치: pi
· 배낭 허용 무게: W

 

목표:
· ∑wi ≤ W를 만족하면서
· ∑pi가 최대가 되도록
· A ⊆ S를 선택

 

단점:

• 부분 집합의 수 = 2ⁿ → 완전탐색 시 계산량이 급증

• 그리디 알고리즘은 적용 불가
→ 동적 계획법 등 다른 방법 필요

 

 

3. 그리디 알고리즘의 적용 예

1) 동전 거스름돈 문제

설명:

• 잔돈을 가장 적은 동전 수로 거슬러주는 문제

• 가장 큰 액면가부터 차례로 선택하면서, 남은 금액을 줄여나감

• 예: 500원, 100원, 50원, 10원, 1원 등

 

한계:

• 동전 단위가 불규칙하면 최적해를 보장하지 못함
• 예: 160원이 추가되면, 200원을 160+10×4 = 5개의 동전으로 거슬러줌 (사실은 100×2 = 2개가 최적)

 

2) 최소 신장 트리 (Minimum Spanning Tree)

목적:

• 주어진 그래프에서 모든 정점을 연결하는 간선들의 집합 중, 가중치의 합이 최소가 되는 트리를 찾는 문제

 

대표 알고리즘:

크루스칼(Kruskal) 알고리즘
· 가중치가 가장 작은 간선부터 선택
· 사이클이 생기지 않도록 간선을 추가
· 그리디한 방식으로 트리 구성

 

프림(Prim) 알고리즘
· 임의의 정점에서 시작
· 인접한 간선 중 가장 가중치가 작은 간선을 선택
· 정점들을 하나씩 연결하며 트리를 확장

 

공통점:

• 둘 다 그리디 알고리즘 기반

• 가중치 그래프가 연결되어 있어야 함

---

이 내용은 휴넷사회복지평생교육원의 알고리즘 강의를 듣고 정리한 것입니다.