greedy
- make the choice that appears best at each moments
- 주어진 문제를 부분 문제로 쪼갰을 때 부분 문제의 상태에서 선택할 수 있는 최선의 선택을 고름
- 그 앞까지의 결과와 앞으로의 결과를 고려하지 않은 선택
개략적인 접근 방법
- 기준에 따른 Sorting
- ⇒ 기준을 무엇으로 정할 것인가?
- 가장 앞의 것을 고름
The Fractional Knapsack Problem
- n개의 item
- 각각의 item은 weight와 profit이 존재
- weight의 합이 W가 넘지 않도록 item을 고를 때, profit의 합이 최대가 되는 item subset?
- 이때 item을 ratio r만큼 “부분” 가져올 수 있다.
greedy approach
- item들을 “profits per unit weight” $\frac{p_i}{w_i}$ 를 기준으로 정렬한다.
- 매 iteration마다 현재 남아있는 item들 중 “profits per unit weight”가 가장 큰 item을 W가 넘지 않을 만큼 가져온다.
예제
implement
sorting한 item들은 heap sort로 정렬한다. → O(nlogn)
Huffman Coding
prefix codes
- 가장 적은 수의 bit를 사용하되, 서로 모호한 일이 없도록
- 빈도수를 기준으로 tree를 구성해 prefix codes 할당
Scheduling with deadline
disjoint set
- profit 순으로 정렬
- for job in JOBS
- parent($\small{d_{job}}$) 확인 (find($\small{d_{job}}$))
- 0이면 $\small{d_{job}}$ 까지의 모든 타임라인이 job보다 profit이 높은 애들로 이미 채워진 것
- → reject job
- else: parent($\small{d_{job}}$)에 job 스케줄링, union($\small{d_{job}-1}$, $\small{d_{job}}$)
- union 함수를 실행하면 parent($\small{d_{job}-1}$)에 parent($\small{d_{job}}$)이 합쳐짐 즉, parent($\small{d_{job}}$)=parent($\small{d_{job}-1}$)가 됨
- parent($\small{d_{job}}$) 확인 (find($\small{d_{job}}$))
최종적으로 root가 0인 tree가 완성됨
time complexity
- sorting profit : $\small{O(nlogn)}$
- disjoint set manipulation: $\small{O(nlogm)}$, $\small{m: min?max?(n, d_{max})}$
백준예제
소방서의 고민
#include <stdio.h>
#include <stdlib.h>
#define MAX 40001
#define GETKEY(a, b) a==0?MAX:(float)b/(float)a
void adjust(int *sorted_idx, int *a, int *b, int i, int n){
int rootidx = sorted_idx[i];
float rootkey = GETKEY(a[rootidx], b[rootidx]);
// left child
int child = i*2;
while(child <= n){
int childidx = sorted_idx[child];
float childkey = GETKEY(a[childidx], b[childidx]);
if(child+1 <= n){
int rchildidx = sorted_idx[child+1];
float rchildkey = GETKEY(a[rchildidx], b[rchildidx]);
if(rchildkey > childkey){
childkey = rchildkey;
childidx = rchildidx;
child += 1;
}
}
if(rootkey > childkey) break;
else{
sorted_idx[child/2] = childidx;
child *= 2;
}
}
sorted_idx[child/2] = rootidx;
}
int main(){
int n, T=0;
int *a, *b, i, *sorted_idx;
scanf("%d", &n);
a = (int*)malloc(sizeof(int)*(n+1));
b = (int*)malloc(sizeof(int)*(n+1));
sorted_idx = (int*)malloc(sizeof(int)*(n+1));
for(i=1; i<=n; i++){
scanf("%d %d", &a[i], &b[i]);
sorted_idx[i] = i;
}
for(i=n/2; i>=1; i--){
adjust(sorted_idx, a, b, i, n);
}
for(i=n-1; i>=1; i--){
int tmp = sorted_idx[i+1];
sorted_idx[i+1] = sorted_idx[1];
sorted_idx[1] = tmp;
adjust(sorted_idx, a, b, 1, i);
}
for(i=1; i<=n; i++){
int idx = sorted_idx[i];
T += (a[idx]*T+b[idx]);
T %= 40000;
}
printf("%d\n", T);
free(a);
free(b);
free(sorted_idx);
return 0;
}
sorting 기준 찾기
greedy 알고리즘의 경우 input data들을 어떤식으로 정렬할지 기준을 정해야 한다.
선정한 기준으로 정렬해 문제를 해결하면 그 값이 최적의 값이 되는데 정렬 결과 $i$ 번째에 소방서가 진압할 화재를 $P_i$ , $i+1$ 번째에 소방서가 진압해야할 화재를 $P_{i+1}$ 이라고 하자.
이때 소방서가 $P_{i+1}$ 을 먼저 진압하고 $P_{i}$ 를 진압할 경우 최적의 해가 아니게 되므로 $P_i \rightarrow P_{i+1}$ 순서로 진압했을 때보다 진압에 걸리는 시간이 길어지게 된다.
$i$ 번째 화재를 진압하기 전까지 걸린 시간을 $t$라고 하고 $i$번째와 $i+1$번째에 진압한 화재가 각각 $P_i \rightarrow P_{i+1}$인 경우와 $P_{i+1} \rightarrow P_{i}$ 인 경우에 대해 $i+1$ 번째 화재 진압까지 걸린 시간을 계산해보면 아래와 같다.
$P_i \rightarrow P_{i+1}$
$i$번째 진압 $i+1$번째 진압 화재 $P_i$ $P_{i+1}$ 진압 전 시간 $t$ $(a_i+1)t+b_i$ 진압에 걸리는 시간 $a_i{t}+b_i$ $a_{i+1}{(a_i+1)t+b_i}+b_{i+1}$ 진압 후 시간 $t+(a_i{t}+b_i) = (a_i+1)t+b_i$ ${(a_i+1)t+b_i}+a_{i+1}{(a_i+1)t+b_i}+b_{i+1}\ = (a_{i+1}+1){(a_i+1)t+b_i}+b_{i+1}$ $P_{i+1} \rightarrow P_{i}$
$i+1$번째 진압 $i$번째 진압 화재 $P_{i+1}$ $P_i$ 진압 전 시간 $t$ $(a_{i+1}+1)t+b_{i+1}$ 진압에 걸리는 시간 $a_{i+1}{t}+b_{i+1}$ $a_{i}{(a_{i+1}+1)t+b_{i+1}}+b_{i}$ 진압 후 시간 $t+(a_{i+1}{t}+b_{i+1}) = (a_{i+1}+1)t+b_{i+1}$ ${(a_{i+1}+1)t+b_{i+1}}+a_{i}{(a_{i+1}+1)t+b_{i+1}}+b_{i}\ = (a_{i}+1){(a_{i+1}+1)t+b_{i+1}}+b_{i}$
우리는 $P_i \rightarrow P_{i+1}$ 의 순서로 진압이 진행될 때가 최적의 해임을 가정했기 때문에 두 $i+1$ 번째 진압이 완료되고 난 뒤의 시간은 아래와 같은 관계를 가진다.
$$
(a_{i+1}+1){(a_i+1)t+b_i}+b_{i+1} \le (a_{i}+1){(a_{i+1}+1)t+b_{i+1}}+b_{i} \
a_{i+1}b_i \le a_{i}b_{i+1} \
\cfrac{b_i}{a_i} \le \cfrac{b_{i+1}}{a_{i+1}}
$$
Disjoint Set DataStructure
find
⇒ $O(logd)$ , $\small{d: \text{the depth of tree}}$
int find(int x){
while(x != parent(x))
x = parent(x);
return x;
}
union by rank
⇒ $2\text{find operation}+1$
- a의 parent 찾음 : a0
- b의 parent 찾음 : b0
- rank(a0)와 rank(b0) 비교
- rank(a0) > rank(b0)
- parent[b0] = a0
- else
- rank(a) == rank(b)
- rank(b)++
- parent[a0] = b0
void union_find(int x, int y){
int x0 = find(x);
int y0 = find(y);
if(x0 == y0) return;
if(rank
서강대학교 임인성 교수님 알고리즘 수업을 기반으로 작성한 문서입니다
'알고리즘' 카테고리의 다른 글
Divide and Conquer (0) | 2022.12.09 |
---|---|
Dynamic Programming (0) | 2022.12.09 |
댓글