알고리즘(Swift) - 그리디 알고리즘(탐욕 알고리즘)

 

그리디 알고리즘 (탐욕 알고리즘)

• 현재 시점에서 가장 최선의 선택을 반복하여 문제를 해결하는 알고리즘
• 매 단계에서 현재 최적이라고 판단되는 선택을 함으로써 전체적인 최적 해에 도달하려고 함

 

특징

1. 지역 최적화(Local Optimal): 매 순간마다 최적의 선택을 함
2. 전역 최적화(Global Optimal): 여러 단계의 최적화 결과가 모여 전체 문제에 대한 최적 해를 보장
3. 빠른 계산 속도: 복잡한 계산 과정을 거치지 않고 매 순간 최적의 선택을 하기 때문에 계산량이 적음
4. 최적 해 보장 조건: 항상 최적의 해를 보장하는 것이 아님, 아래의 조건을 만족해야 최적의 해를 구함
   • 탐욕적 선택 속성(Greedy Choice Property): 현재의 선택이 나머지 선택에 영향을 주지 않음
   • 최적 부분 구조(Optimal Substructure): 부분 문제의 최적 해를 이용해 전체 문제를 해결할 수 있음

 

과정

1. 문제를 분할하여 각 단계에서 선택할 수 있는 옵션을 나열
2. 각 단계에서 가장 최적인 선택을 수행
3. 최종적으로 해답을 구함

 

적용 가능한 문제

1. 최소 동전 개수 문제
   • 예: 거스름돈을 가장 적은 동전 수로 주는 문제
   • 각 단계에서 가장 큰 단위의 동전을 선택
2. 활동 선택 문제(Activity Selection Problem)
   • 예: 가장 많은 회의를 진행 할 수 있도록 회의 스케줄을 선택
   • 종료 시간이 빠른 순으로 선택
3. 최소 신장 트리(MST)
   • 크루스칼, 프림 알고리즘을 통해 구현 가능
4. 최단 경로 문제
   • 다익스트라 알고리즘에서 사용

 

장점

• 구현이 간단하고 계산 속도가 빠름
• 적은 메모리 사용

단점

• 모든 문제에 대해 항상 최적의 해를 보장하지 않음
• 탐욕적 선택이 잘못되면 전체 해답이 틀릴 수 있음

 

예제 문제

 

1. 최소 동전 개수 문제

let coins = [500, 100, 50, 10] // 동전 단위
let amount = 1260              // 거스름돈
var count = 0

var remaining = amount
for coin in coins {
    count += remaining / coin  // 각 동전으로 거슬러 줄 수 있는 개수
    remaining %= coin          // 남은 금액
}

print("필요한 동전의 최소 개수: \(count)")

• 가장 큰 단위의 동전을 우선적으로 사용하여 거스름돈을 줄임

 

2. 활동 선택 문제

let activities = [(start: 1, end: 4), (start: 3, end: 5), (start: 0, end: 6), (start: 5, end: 7), (start: 8, end: 9)]
let sortedActivities = activities.sorted { $0.end < $1.end }

var selected = [sortedActivities[0]]
var lastEndTime = sortedActivities[0].end

for activity in sortedActivities[1...] {
    if activity.start >= lastEndTime {
        selected.append(activity)
        lastEndTime = activity.end
    }
}

print("선택된 활동: \(selected)")

• 종료 시간이 빠른 활동을 우선적으로 선택하여 최대 활동을 선택

 

그리디 알고리즘을 쓸 수 없는 문제

 

배낭 문제(Knapsack Problem)

문제: 무게 제한이 있는 배낭에 물건들을 담아, 가치의 합을 최대화하라.

조건: 물건은 각각의 가치와 무게가 다르며, 물건은 쪼갤 수 없습니다.

• 배낭 무게 제한: 50
• 물건 A: 가치 60, 무게 10
• 물건 B: 가치 70, 무게 15
• 물건 C: 가치 110, 무게 25
• 물건 D: 가치 100, 무게 20
• 물건 E: 가치 120, 무게 30

그리디 방식: 가치가 높은 물건 순서대로 선택.

• 물건 E(120) 선택 → 배낭에 담기 남은 용량: 20
• 물건 D(100) 선택 → 배낭에 담기 남은 용량: 0

→ 가치: 120 + 100 = 220

 

정답

• 물건 A(60) 선택 → 남은 용량: 40
• 물건 B(70) 선택 → 남은 용량: 25
• 물건 C(110) 선택 → 남은 용량: 0

→ 가치: 60 + 70 + 110 = 240

 

그리디 알고리즘은 항상 가장 가치가 높은 물건부터 선택해 최적 해를 보장하지 못함.

→ 동적 계획법(DP)이 필요

 

 

문제의 상황을 다양하게 재해석해보고

그 재해석한 상황에서 매 순간에서의 최선의 선택 = 문제의 최적해 인지를 확인해봅시다.

만약, 재해석을 해봐도 그리디 알고리즘을 사용할 수 없다면 다른 풀이를 떠올려야 합니다. → DP

 

 

https://gliver.tistory.com/18