9주차-Greedy Algorithms

3-1/Algorithm

9주차-Greedy Algorithms

Donghun Kang 2024. 6. 8. 15:34

Greedy algorithm

지역 최적화를 위한 탐욕적인 접근 방식으, 전체적으로 최적의 해답을 찾는 것이 목표이다.
항상 최적의 해답을 보장하지는 않지만, 많은 상황에서 효과적으로 작동한다.

Feasible(실현가능성)

문제의 제약 조건을 만족해야 한다.

Locally optimal(지역최적성)

각 단계에서 가능한 모든 선택 중 가장 좋은 선택을 해야한다.

이러한 지역적인 선택이 전체적으로 최적의 해답을 제공하는 경우 문제는 최적의 부분 구조를 갖는다.

Irrevocable(돌이킬 수 없음)

한 번 선택한 것은 알고리즘의 이후 단계에서 되돌리 수 없다.

단순하고 매력적이지만 최적의 해답을 제공하지는 않는다.

EX)

0-1 배낭 문제

- 도둑이 n개의 아이템이 있는 상점을 털려고 합니다.
- 각 아이템은 v[i] 달러의 가치와 w[i] 파운드의 무게를 가집니다.도둑은 가능한 많은 가치를 얻고자 하지만, 그의 배낭은 최대 W 파운드의 무게만을 담을 수 있습니다.도둑은 어떤 아이템을 선택해야 할까요?

그리디 알고리즘
=> 가장 가치 있는 아이템을 최대한 많이 선택합니다.그러나 이 방법은 반드시 최적의 가치를 보장하지 않습니다.

각 item의 무게당 가치를 계산한다.
A: 60/2 = 30
B: 75/3 = 25
C: 90/4 = 22.5
=> 먼저 A를 선택(무게 2, 가치 60, 남은 용량 3), B를 선택(무게3, 가치 75, 남은 용량 0)
총가치는 60+75 = 135

아이템 A: 60 / 2 = 30
아이템 B: 100 / 4 = 25
아이템 C: 90 / 4 = 22.5
=> 먼저 A를 모두 선택(무게 2, 남은 용량 3), 다음으로 아이템 B를 부분적으로 선택: 무게 3, 남은 용량 0

Greedy VS D.P

Greedy	Dynamic Prgramming
문제에 따라 최적의 해답을 제공할 때도 있고 그렇지 않을때 있다.	적용 가능한 경우 일반적으로 최적의 해답을 제공한다. 그러나 동적 프로그래밍 알고리즘은 일반적으로 고안하고 구현하기 더 어렵다.

EX)

Activity selection problem

활동 j는 sj에 시작하고 fj에 종료됩니다.
두 활동이 겹치지 않으면 호환 가능 (compatible) 합니다.
목표: 서로 호환 가능한 활동의 최대 부분 집합을 찾는 것입니다.

1. 가장 빠른 시작 시간 (Earliest start time): 시작 시간 sj을 오름차순으로 정렬합니다.
2. 가장 빠른 종료 시간 (Earliest finish time): 종료 시간 fj을 오름차순으로 정렬합니다.
3. 가장 짧은 활동 (Shortest activity): 활동 길이 fj - sj를 오름차순으로 정렬합니다.
4. 가장 적은 충돌 (Fewest conflicts): 각 활동에 대해 충돌하는 활동의 수 cj를 계산하고, 충돌이 적은 순서대로 정렬합니다.

가장 빨리 시작하는 활동/ 가장 짧은 시간을 소요하는 활동/ 충돌이 가장 적은 활동을 먼저 선택한다.

- 전체 알고리즘의 시간 복잡도는 O(nlog⁡n).
- 마지막으로 추가된 활동 i의 종료 시간 fi를 기억합니다.
- 활동 j는 sj≥fi이면 호환 가능합니다.

EX)

Optimal offline caching

- 캐시 용량 (k): 캐시가 저장할 수 있는 아이템의 최대 개수.
- 아이템 요청 시퀀스 (d1, d2, ..., dm): m개의 아이템 요청이 순서대로 주어짐.
- 캐시 히트 (Cache hit): 요청된 아이템이 캐시에 이미 존재하는 경우.
- 캐시 미스 (Cache miss): 요청된 아이템이 캐시에 없는 경우. 이때 새로운 아이템을 캐시에 추가하고, 필요 시 기존 아이템을 교체해야 함.

=> 목표: 전체 요청 시퀀스에서 캐시 미스를 최소화하는 교체 스케줄을 찾는 것.