Greedy

greedy

• make the choice that appears best at each moments
• 주어진 문제를 부분 문제로 쪼갰을 때 부분 문제의 상태에서 선택할 수 있는 최선의 선택을 고름
• 그 앞까지의 결과와 앞으로의 결과를 고려하지 않은 선택

개략적인 접근 방법

1. 기준에 따른 Sorting
2. ⇒ 기준을 무엇으로 정할 것인가?
3. 가장 앞의 것을 고름

The Fractional Knapsack Problem

• n개의 item
• 각각의 item은 weight와 profit이 존재
• weight의 합이 W가 넘지 않도록 item을 고를 때, profit의 합이 최대가 되는 item subset?
• 이때 item을 ratio r만큼 “부분” 가져올 수 있다.

greedy approach

1. item들을 “profits per unit weight” $\frac{p_i}{w_i}$ 를 기준으로 정렬한다.
2. 매 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

1. profit 순으로 정렬
2. for job in JOBS
   1. parent($\small{d_{job}}$) 확인 (find($\small{d_{job}}$))
      1. 0이면 $\small{d_{job}}$ 까지의 모든 타임라인이 job보다 profit이 높은 애들로 이미 채워진 것
      2. → reject job
      3. else: parent($\small{d_{job}}$)에 job 스케줄링, union($\small{d_{job}-1}$, $\small{d_{job}}$)
      4. union 함수를 실행하면 parent($\small{d_{job}-1}$)에 parent($\small{d_{job}}$)이 합쳐짐 즉, parent($\small{d_{job}}$)=parent($\small{d_{job}-1}$)가 됨

최종적으로 root가 0인 tree가 완성됨

time complexity

• sorting profit : $\small{O(nlogn)}$
• disjoint set manipulation: $\small{O(nlogm)}$, $\small{m: min?max?(n, d_{max})}$

백준예제

소방서의 고민

2180번: 소방서의 고민

#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$

1. a의 parent 찾음 : a0
2. b의 parent 찾음 : b0
3. rank(a0)와 rank(b0) 비교
   1. rank(a0) > rank(b0)
   2. parent[b0] = a0
   3. else
      1. rank(a) == rank(b)
      2. rank(b)++
   4. parent[a0] = b0

void union_find(int x, int y){
    int x0 = find(x);
    int y0 = find(y);

    if(x0 == y0) return;
    if(rank

서강대학교 임인성 교수님 알고리즘 수업을 기반으로 작성한 문서입니다