그리디 (Greedy)

BrokenFinger98·2024년 8월 20일

Problem Solving greedy

Problem Solving

목록 보기

10/29

그리디 (Greedy)

탐욕 알고리즘은 최적 해를 구하는 데 사용되는 근시안적인 방법
최적화 문제(optimization)란 가능한 해들 중에서 가장 좋은(최대 또는 최소) 해를 찾는 문제이다.
일반적으로, 머리 속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 된다.
여러 경우 중 하나를 선택 할 때마다 그 순간의 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
각 선택 시점에서 이루어지는 결정은 지역적으로 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없다.
일단, 한번 선택된 것은 번복하지 않는다. 이런 특성 때문에 대부분의 탐욕 알고리즘들은 단순하며, 또한 제한적인 문제들에 적용된다.

최적 해를 반드시 구한다는 보장이 없다.

화폐 단위 큰 것 → 작은 것 사용
500 1개가 100 : 3, 50 : 10, 10 : 50개를 대체할 수 있다.
100 1개가 50 : 2, 10 : 10개를 대체할 수 있다.
50 1개가 10: 5개를 대체할 수 있다.
각각의 동전이 서로 배수이기 때문에 최적해 임을 만족한다.

배낭 짐싸기(Knapsack)

도둑은 부자들의 값진 물건들을 훔치기 위해 보관 창고에 침입하였다.
도둑은 훔친 물건을 배낭에 담아 올 계획이다. 배낭은 담을 수 있는 물건의 총 무게(W)가 정해져 있다.
창고에는 여러 개(n개)의 물건들이 있고 각각의 물건에는 무게와 값이 정해져 있다.
경비원들에 발각되기 전에 배낭이 수용할 수 있는 무게를 초과하지 않으면서, 값이 최대가 되는 물건들을 담아야 한다.

Knapsack 문제의 정형적 정의

S = {item1, item2, item3, …, itemn}, 물건들의 집합
wi: itemi 의 무게. Pi = itemi의 값
W: 배낭이 수용 가능한 총 무게
문제 정의
선택한 물건의 무게의 합이 배낭이 수용 가능한 총 무게를 넘지 않으면서, 선택한 물건의 가격의 합이 최대가 되도록 물건을 선택하는 문제

Knapsack 문제 유형

0-1 Knapsack
- 배낭에 물건을 통째로 담아야 하는 문제
- 물건을 쪼갤 수 없는 경우
Fractional Knapsack
- 물건을 부분적으로 담는 것이 허용되는 문제
- 물건을 쪼갤 수 있는 경우

0-1 Knapsack에 대한 완전 탐색 방법

완전 탐색으로 물건들의 집합 S에 대한 모든 부분 집합을 구한다.
부분 집합의 총 무게가 W를 초과하는 집합들은 버리고, 나머지 집합에서 총 값이 가장 큰 집합을 선택할 수 있다.
물건의 개수가 증가하면 시간 복잡도가 지수적으로 증가한다.
- 크기 n인 부분 집합의 수 2^n

0-1 Knapsack에 대한 탐욕적 방법 1

	무게	값
물건1	25kg	10만원
물건2	10kg	9만원
물건3	10kg	5만원

값이 비싼 물건부터 채운다.
W = 30kg
탐욕적 방법의 결과
- 물건1 → 25kg, 10만원
최적해
- 물건2, 물건3 → 20kg, 14만원
최적이 아니다.

0-1 Knapsack에 대한 탐욕적 방법 2

	무게	값
물건1	25kg	15만원
물건2	10kg	9만원
물건3	10kg	5만원

무게가 가벼운 물건부터 채운다.
W = 30kg
탐욕적 방법의 결과
- 물건2 + 물건3 → 14만원
최적해
- 물건1 → 15만원
역시 최적 해를 구할 수 없다.

0-1 Knapsack에 대한 탐욕적 방법 3

	무게	값	값/kg
물건1	5kg	50만원	10만원/kg
물건2	10kg	60만원	6만원/kg
물건3	20kg	140만원	7만원/kg

무게 당 (예> kg당) 값이 높은 순서로 물건을 채운다.
W = 30kg
탐욕적 방법의 결과
- 물건1, 물건3 → 190만원
최적해
- 물건2, 물건3 → 200만원
역시, 탐욕적 방법으로 최적 해를 구하기 어렵다.

Fractional Knapsack 문제

	무게	값	값/kg
물건1	5kg	50만원	10만원/kg
물건2	10kg	60만원	6만원/kg
물건3	20kg	140만원	7만원/kg

물건의 일부를 잘라서 담을 수 있다.
탐욕적 방법의 결과
물건1 5kg, 물건 3 20kg, 물건2의 절반 5kg → 30kg, (50 + 140 + 30 → 220만원)

문제 제시

김대리는 소프트웨어 개발팀들의 회의실 사용 신청을 처리하는 업무를 한다. 이번 주 금요일에 사용 가능한 회의실은 하나만 존재하고 다수의 회의가 신청된 상태이다.
회의는 시작 시간과 종료 시간이 있으며, 회의 시간이 겹치는 회의들은 동시에 열릴 수 없다.
가능한 많은 회의가 열리기 위해서는 회의들을 어떻게 배정해야 할까?
입력 예
- 회의 개수
- 시작 시간 종료 시간의 한 쌍의 정보가 공백으로 구분되어 회의 개수 만큼 입련
```
10
1 4 1 6 6 10 5 7 3 8 5 9 3 5 8 11 2 13 12 14
```

활동 선택 문제(Activity-selection problem)

시작 시간과 종료 시간(si, fi)이 있는 n개의 활동들의 집합 A = {A1, A2, …, An}, 1 ≤ i ≤ n 에서 서로 겹치지 않는(non-overlapping) 최대갯수의 활동들의 집합 S를 구하는 문제
양립 가능한 활동들의 크기가 최대가 되는 S0,n+1의 부분집합을 선택하는 문제
- 종료 시간 순으로 활동들을 정렬한다.
- S0,n+1 는 a0의 종료 시간부터 an+1의 시작 시간 사이에 포함된 활동들
- S0,11 = {a1, a2, …, a9, a10} = S
탐욕 기법의 적용
Sij를 풀기 위해
1. ai 종료 시간부터 시작 가능한 활동 중 종료 시간이 가장 빠른 am 선택
2. Sij = {am} U Smj 의 해집합
  
  Sij 는 ai의 종료 시간부터 aj의 시작 시간 사이에 포함된 활동들

탐욕 기법을 적용한 반복 알고리즘

A: 활동들의 집합, S: 선택된 활동(회의)들 집합
Si: i활동의 시작 시간, fi: i활동의 종료 시간, 1 <= i <= n

Sort A by finish time
S = {Ai}
j <- 1 
for(i in 2) -> 2
	if(fj <= si)
		S <- S U {Ai}
		j <- i