Greedy Algorithm

🍒 Greedy Algorithm

• 어떤 선택을 해야 할 때 그 당시에 가장 최선의 선택을 하여 문제를 해결하는 알고리즘
• 그 당시에 지역적으로 최적인 선택
• 이런 선택을 모은 최종적인 해답이 최적의 해답이라는 보장은 없음
• 따라서 해답을 얻은 후에 이 해답이 최적인지 검사해야 함

🍒 설계 절차

• 선정과정
  • 현재 상태에서 가장 좋다고 생각되는 해답을 찾아서 해답모음 (solution set)에 포함
• 적정성 점검
  • 새로 얻은 해답모음이 적절한지 결정
• 해답 점검
  • 새로 얻은 해답모음이 최적의 해인지 결정

🍒 거스름돈 문제

• 문제: 동전의 개수가 최소가 되도록 거스름돈을 주어야 함
• 탐욕적 알고리즘
  • 1) 주어야 할 거스름돈을 넘지 않는 가장 큰 액수의 동전을 줌
  • 2) 단계 1에서 건네준 동전의 총액이 거스름돈과 정확하게 일치할 때까지 단계 1 반복
• 단계 1: 선정과정
• 동전 선정 후 선정된 동전이 최종 해답에 포함될 수 있는지 (거스름돈을 넘지 않는지) 검사: 적정성 검사
• 적정성 검살르 통과하면, 현재까지 선정된 동전의 총액 (solution set)이 거스름돈과 정확하게 일치하는지 검사: 해답 검사

• 현재 유통되고 있는 동전만을 가지고 탐욕적 알고리즘을 적용하면 이 알고리즘은 최적의 해를 제공함

ex 1) 100원, 50원, 10원인 동전만 있다고 하자.

• 210원에 대한 거스름: 100원, 100원, 10원 -> 3개

ex 2) 위 3개 외에 120원짜리 동전도 있다고 하자.

• 120원, 40원, 10원짜리 4개 -> 6개
• 최적의 해가 아님

거스름돈 문제 알고리즘

• 문제: 동전의 개수가 최소가 되도록 거스름돈 주어야 함
• 입력: changes[]: 액면가가 큰 동전이 큰 순서대로 정렬
          amount: 거스름돈 액수
• 출력: cc[]: 거스름돈에서 필요한 각 동전의 개수 저장

void minChange(int changes[], int amount, int &cc[]) {
    cc[] = {0};
    for(i = 1, i <= r, i++) {     // r: 배열의 크기, 동전 액면가의 가지 수
        while(amount >= changes[i]) {   // 가장 큰 액수의 동전부터 거스름돈에 들어가는 만큼 선택
            cc[i]++;
            amount = amount - changes[i];
        }
    }
}

🍒 최소 비용 신장트리 Minimum Spanning Tree

신장 트리

• 연결된 무방향 그래프에서 모든 정점을 포함하는 트리 형태의 부분 그래프
• 순환경로 (cycle)이 없는 모든 정점을 포함하는 부분 그래프

• n개의 노드가 있을 때 신장 트리들의 공통점: n-1개의 연결선을 가짐

최소 비용 신장 트리

• 연결된 가중치 무방향 그래프의 신장트리 중 트리의 모든 간선의 가중치 합이 최소가 되는 신장트리
• 최소 비용 신장트리를 구하는 무작정 알고리즘의 시간복잡도는 지수 시간보다 나쁨

• G = (V, E)
  • G: 무방향 그래프
  • V: 정점의 유한 집합
  • E: V에 속한 정점의 쌍의 집합
• $(V_i, V_j)$: $V_i, V_j$를 연결하는 간선
• T = (V, F)
  • T: G의 신장 트리
  • F: E의 부분 집합

Greedy Approach

• 문제: 비방향성 그래프 G=(V, E)가 주어졌을 때, F ⊆ E를 만족하면서 (V, F)가 G의 MST가 되는 F를 찾아라.
• 추상적 알고리즘
  • F = ∅
  • 사례가 해결될 때까지 다음을 반복
    • 지역적으로 최적인 간선 선택 : 선정절차
    • 선택한 간선이 순환경로를 만드는지 검사 : 적정성 검사
      • 만들지 않으면 F에 추가
    • T=(V, F)가 신장 트리인지 검사 : 해답 검사

🍒 Prim’s Approach

알고리즘

• 신장 트리 간선 : F = ∅
• 선택한 정점 : Y = {$V_1$}
• 사례가 해결될 때까지 다음을 반복
  • V-Y에서 Y와 가장 가까운 정점 선택 : 선정절차 + 적정성 검사
  • 선택한 정점으로 Y에 추가하고, 해당 간선을 F에 추가
  • Y = V이면 종료, T = (V, F)가 최소 비용 신장 트리 : 해답 검사

자료구조

• 인접행렬 W[i][j]: Floyd 최단경로 알고리즘에서 사용한 행렬과 같은 행렬. 그래프 간선의 거리
• nearest[i]: Y에 속한 정점 중 $V_i$와 가장 가까운 정점의 index. $V_i$는 Y에 포함되지 않은 정점
• distance[i]: $V_i$와 nearest[i]를 잇는 간선의 가중치 값

의사코드

void prim(int n, number W[][], EdgeSet& F) {
    index i, vnear; 
    number min;
    edge e;
    index nearest[2..n]; 
    number distance[2..n];
    F = ∅;
    for(i = 2; i <= n; i++) {    // V1과의 거리로 초기화
        nearest[i] = 1;
        distance[i] = W[1][i];
    }

    for(j = 1; j <= n-1; j++) {
        min = ∞;
        for(i = 2; i <= n; i++) {         // Y와 가장 가까운 정점 검색
            if(0 <= distance[i] < min) {
                min = distance[i];
                vnear = i;
            }
        }
        e = (nearest[vnear], vnear);
        F = F ∪ {e};
        distance[vnear] = -1;
        for(i = 2; i <= n; i++) {
            if(W[i][vnear] < distance[i]) { 
                distance[i] = W[i][vnear];
                nearest[i] = vnear;
            }
        }
    }
}

시간복잡도

• 기본연산: 비교 연산
• 입력 크기: n
• 분석
  • for(j = 1; j <= n-1; j++) 문: (n-1)번 반복 -> 곱
  • 2개의 for(i = 2; i <= n; i++)문: 각 (n-1)번 반복 -> 합 (연달아 발생)
  • 총 T(n) = 2(n-1)(n-1) ∈ Θ(n²)

🍒 분리 (부분)집합 자료구조 (disjoint set)

• 집합의 모든 원소는 수 0, 1, 2, …, n-1 이라고 가정
• 임의의 두 집합은 어던 원소도 공유하지 않음
• 자식에서 부모로 가는 링크로 연결

연산

• 분리 합집합 merge(Si, Sj)
  • $S_i ∪ S_j$ = {x | x는 $S_i$ 또는 $S_j$에 포함되는 모든 원소}
  • 두 집합이 연결 상태가 됨
  • 어느 한 트리가 다른 트리의 서브 트리로 들어감
• 탐색 find(i)
  • 원소 i를 포함하는 집합 탐색
  • root가 같은지 여부로 같은 집합인지 판별 (교집합이 없기 때문에 가능)

S1, S2, S3의 배열 표현

• i번째 원소: 원소 i를 포함하는 트리 노드
• 원소: 대응되는 트리 노드의 부모 포인터
  • 배열을 통해 재귀적으로 부모 노드를 찾을 수 있음
• 루트의 parent는 -1

연산 알고리즘

• initial
  • 모든 노드를 root로 만듦 (서로 다른 분리 부분집합)

    void initial(int n) {
      for(i = 0; i <= n-1; i++)
      parent[i] = -1;
    }
    

• find
  • i의 parent값으로 찾음
  • parent[i]가 0보다 작으면 set_pointer return
    • set_pointer : 루트의 노드 번호

      set_pointer find(index i) {
        for(; parent[i] >= 0; i = parent[i])
        ;
        return i;
      }
      

• equal

  bool equal(set_pointer p, set_pointer q) {
    if(p == q) return true;
    else       return false;
  }
  

• merge
  • 루트 노드가 q인 트리가 p인 트리의 서브트리로 들어감

    void merge(set_pointer p, set_pointer q) {
      parent[q] = p;
    }
    

🍒 Kruskal 알고리즘

• 1) 각 정점을 하나만 포함하는 n개의 집합 생성
  • 어느 노드들도 연결되지 않은 상태
• 2) 모든 간선을 가중치 값을 기준으로 오름차순 정렬
• 3) 가중치가 가장 작은 것부터 검사하여 간선이 서로소(disjoint)인 두 집합을 연결하면 그 간선을 F에 추가, 연결된 두 집합을 하나의 집합으로 결합
  • 연결해도 cycle이 생기지 않는 경우
• 4) F가 MST가 될 때까지 단계 3 반복

의사코드

void kruskal(int n, int m, EdgeSet E, EdgeSet& F) {
    index i, j;
    set_pointer p, q;
    edge e;
    VertexSet V[1..n];
    E에 속한 m개의 간선을 가중치에 따라 오름차순 정렬   // mlg(m)
    F = ∅;
    initial(n);    // n개의 서로소 부분집합 초기화

    while(|F| < n-1) {     // 신장트리의 간선 개수: n-1
        e = 아직 고려하지 않은 가중치가 최소인 간선;
        i, j = e에 의해 연결되는 정점의 index;
        p = find(i);     // Vi가 포함되어 있는 집합, lg(n)
        q = find(j);     // Vj가 포함되어 있는 집합, lg(n)
        if(!equal(p, q)) {    // 비교: 상수 시간
            merge(p, q);      // 할당 1번
            F = F ∪ {e};
        }
    }
}

시간복잡도

• 최악의 경우 분석
• 기본 연산: 비교
• 입력 크기: 정점의 수 n, 간선의 수 m
• 고려사항
  • 정렬에 소요되는 비용: $Θ(mlg^m)$
  • while 루프
    • 최악의 경우 모든 간선을 고려해야 함 -> m번 반복
    • 전체 비용은 $Θ(mlg^m)$
  • V[i] 집합 초기화하는 비용: $Θ(n)$   (할당)
• n < m 이므로 $Θ(mlg^m)$이 전체 비용 지배
• m은 최악의 경우 $\frac{n(n-1)}{2}$ 이므로 전체 비용은 $Θ(n^2lg^n)$

🍒 Prim vs. Kruskal

• m(edge의 수)의 범위
  • $n-1 ≤ m ≤ \frac{n(n-1)}{2}$
• 두 알고리즘의 시간복잡도

	W(m, n)	sparse graph	dense graph
Prim	$Θ(n^2)$	$Θ(n^2)$	$Θ(n^2)$
Kruskal	$Θ(mlg^m)$ and $Θ(n^2 lg^n)$	$Θ(nlg^n)$	$Θ(n^2 lg^n)$

• Kruskal: m에 따라 달라짐

🍒 Dijkstra 단일출발점 최단경로 문제

• Floyd의 최단경로 알고리즘은 가중치 방향 그래프에서 각 정점 간의 최단경로를 구해주며, 시간복잡도는 $Θ(n^3)$ 임
• 어떤 특정한 정점에서 다른 모든 정점까지의 최단경로만 필요한 경우에는 이 알고리즘은 너무 비용이 큼
• Dijkstra의 단일출발점 최단경로 알고리즘의 시간복잡도는 $Θ(n^2)$
  • Prim의 MST 알고리즘과 유사

자료구조

• 인접행렬 W[i][j]
• touch[i]
  • Y에 있는 정점들만을 이용하여 V1에서 Vi로 가는 현재 최단경로 상의 마지막 간선이 (V1, Vi)라고 할 때, Y에 있는 정점 V의 index
  • 경유하는 중간 노드 저장
• length[i]
  • Y에 있는 정점들만을 이용하여 V1에서 Vi로 가는 현재 최단경로의 길이
  • -1로 바뀌기 전

의사코드

void dijkstra(int n, const number W[][], EdgeSet& F) {
    index i, vnear, touch[2..n];
    edge e;
    number length[2..n];
    int min;
    F = ∅;

    for(i = 2; i <= n; i++) {
        touch[i] = 1;
        length[i] = W[1][i];
    }

    for(j = 1; j <= n-1; j++) {
        min = ∞;
        for(i = 2; i <= n; i++) {
            if(0 <= length[i] < min) {
                min = length[i]; 
                vnear = i;
            }
        }
        e = (touch[vnear], vnear);    // vnear: 경유하는 노드
        F = F ∪ {e};
        for(i = 2; i <= n; i++) {
            if(length[vnear] + W[vnear][i] < length[i]) {
                length[i] = length[vnear] + W[vnear][i];
                touch[i] = vnear;
            }
        }
        length[vnear] = -1;
    }
}

시간 복잡도

• 2개의 for 루프에 의해
  T(n) = 2(n-1)(n-1) ∈ $Θ(n^2)$

🍒 탐욕적 방법 vs. 동적 프로그래밍

• 두 방법 모두 최적화 문제를 해결하는 데 사용할 수 있는 기법
• 같은 문제를 두 방법으로 모두 해결할 수 있으면 보통 탐욕적 방법이 더 효율적임
• 탐욕적 방법은 알고리즘의 결과가 최적인지 증명해야 함
• 동적 프로그래밍은 최적화 문제가 최적의 원칙에 적용되는지 검사해야 함
  • 최적의 원칙: 어떤 해의 최적 해가 그 사례를 분할한 부분 사례에 대한 최적해를 항상 포함하고 있으면 그 문제는 최적의 원칙이 적용된다고 표현

🍒 0-1 배낭채우기 문제

• $S$ = {$item1, item2, …, item_n$}
• $W_i$: $item_i$의 무게
• $P_i$: $item_i$의 가치
• $W$: 배낭이 수용할 수 있는 총 무게

• $A$: $S$의 부분집합으로 선택된 item들의 집합

• 목표: $\sum_{item_i ∈ A} w_i ≤ W$ 를 만족하면서 $\sum_{item_i ∈ A} P_i ≤ W$ 가 최대가 되도록 A ⊆ S를 만듦
• 0-1: $item_i$는 A에 포함되거나 포함되지 않음

• 무작정 알고리즘
  • S의 가능한 모든 부분집합을 고려
  • 시간복잡도: $2^n$ = 부분집합의 개수

• ex1) W = 30kg, S = {item1, item2, item3}

item	weight	profit
item1	25kg	10
item2	10kg	9
item3	10kg	9

• 탐욕적 알고리즘1: 가장 비싼 item 순으로 채움
  • 최적이 아님
  • A = {item1}, 10
  • 최적의 해답: A = {item2, item3}, 18

• ex2) W = 30kg, S = {item1, item2, item3}

item	weight	profit
item1	25kg	10
item2	10kg	4
item3	10kg	4

• 탐욕적 알고리즘2: 가장 무게가 적은 item 순으로 채움
  • 역시 최적이 아님
  • A = {item2, item3}, 8
  • 최적의 해답: A = {item1}, 10

• ex3) W = 30kg, S = {item1, item2, item3}

item	weight	profit	profit per weight
item1	5kg	50	50/5 = 10
item2	10kg	60	60/10 = 6
item3	20kg	140	140/20 = 7

• 탐욕적 알고리즘3: 무게당 가치가 가장 높은 물건부터 채움
  • 또한 최적이 아님
  • A = {item1, item3}, 190
  • 최적의 해답: A = {item2, item3}, 200
• 결론: 0-1 배낭채우기 문제는 greedy 알고리즘으로 풀 수 없음

🍒 배낭 빈틈없이 채우기 문제

• 0-1 배낭 채우기 문제와 달리 item을 잘라서 일부만 담을 수 있음

• 0-1 배낭 채우기 문제에 대한 탐욕적 알고리즘3 (무게 당 가치)은 항상 배낭 빈틈없이 채우기 문제의 최적의 해를 구해줌

• ex)

item	weight	profit	profit per weight
item1	5kg	50	50/5 = 10
item2	10kg	60	60/10 = 6
item3	20kg	140	140/20 = 7

• item1 + item3 + item2 * $\frac{1}{2}$ = 220

Greedy 알고리즘

• 문제: 배낭의 용량을 넘지 않으면서 가장 최대의 이득을 얻을 수 있도록 배낭 채우기
• 입력: 배낭의 용량 M, 아이템 개수 n, 각 아이템의 이득과 무게가 저장된 배열 p[1:n], w[1:n] (무게 당 이익이 큰 순으로 정렬 p[i]/w[i] ≥ p[i+1]/w[i+1])
• 출력: 배낭에 들어가는 아이템 리스트 x[1:n]

의사코드

void GreedyKnapsack(float M, int n, int p[], int w[], float& x[]) {
    for(int i = 1; i <= n; i++) x[i] = 0.0;    // initialize x
    float U = M;
    for(i = 1; i <= n; i++) {
        if(w[i] > U) break;
        x[i] = 1.0;
        U -= w[i];
    }
    if(i <= n) x[i] = U/w[i];
}

시간복잡도

• p[1..n], w[1..n] 배열의 정렬: $Θ(n log^n)$ (사전작업)
• GreedyKnapsack: $Θ(n)$
• 따라서, $T(n) = Θ(nlog^n)$

🍒 최적 머지 패턴

• 문제: 두 개 이상의 정렬된 파일이 주어졌을 때, 가장 효율적으로 이 파일들을 하나의 정렬된 파일로 합병하는 방법 찾기
• 효율성: 파일 레코드의 비교나 이동의 횟수 최소화

• 정렬된 2개의 파일(배열)을 합병하기 위해 각 배열의 크기를 더한 만큼의 이동

• 각 배열의 크기만큼 이동해야 하나의 파일을 합칠 수 있음!

• 크기가 작은 배열부터 하나씩 합쳐나가는 것이 가장 이동 횟수가 적음

• ex)

• 결국 리프 노드들로 루트 노드를 만들어가는 과정!
• record moves: 15 + 30 + 50 + 60 + 110 = 265
• 5 * 4 + 10 * 4 + 15 * 3 + 20 * 2 + 30 * 2 + 30 * 2
  • ∑ (주어진 파일 크기 * 레벨)
  • $= \sum_{i=1}^n d_i q_i $
• 보라색 원: 중간 노드 -> 하나의 file이 됨
• 노란색 사각형: 주어진 file들

알고리즘

• 문제: 여러 개의 파일을 최소 비용으로 하나의 파일로 만들기 위한 합병 방법
• 입력: 여러 개의 파일 (n개)
• 출력: 최적 머지 패턴 트리

의사코드

struct treenode {
    struct treenode *lchild, *rchild;
    int #ofrecords;    // file 크기
};
typedef struct treenode Type;

Type *Tree(int n) {
    // list is a global list of n single node (file)

    for(int i = 1; i <= n-1; i++) {
        type *pt = new Type;   // Get a new tree node 중간 노드 생성
        pt -> lchild = Least(list);      // Merge two trees with (가장 작은 크기의 파일)
        pt -> rchild = Least(list);      // smallest lengths (그 다음으로 작은 크기의 파일)
        pt -> #ofrecords = (pt -> lchild) -> #ofrecords + (pt -> rchild) -> #ofrecords;    // 노드의 크기 = 양쪽 child의 크기의 합
        Insert(list, *pt);    // 마지막 -> root만 남게됨
    }
    return (Least(list));   // tree left in list is the merge tree
}

자료구조

• min heap 사용
  • 가장 작은 값이 root인 heap tree
  • 매번 root만 꺼내면 됨
• list에서 가장 작은 것 2개 꺼내서 중간 노드 만듦 -> 다시 list에 넣음

시간복잡도

• for문에서 비교횟수 (n-1), (n-2), …, 0
  • $\frac{(n-1)^2}{2}$
• min heap
  • 구축: n
  • 꺼내는건 root만 꺼내면 되기 때문에 1 (비용X)
  • 꺼낸 후 다시 min heap으로 만들어줘야 함: $log^n$
  • for문 (n-1)번 반복 -> $(n-1)(2log^n) ∈ Θ(nlog^n)$
• 결론
  • $Θ(n^2)$ or $Θ(nlog^n)$
  • 자료구조에 따라 효율성에 차이가 남

🍒 최적 이진 코드 (허프만 코드)

• 문제: 주어진 파일에 있는 문자들을 이진 코드로 표현하는데 필요한 비트의 개수가 최소가 되는 이진 문자의 코드 찾기
• 허프만 코드: 파일을 코드화하는 하나의 방식
• Prefix code: 다른 글자의 앞부분으로 시작하지 않는 코드

• 필요한 비트 수: $bits(T) = \sum_{i=1}^n frequency(v_i) * depth(v_i)$

• ex)

• (a): C2 (문자가 빈번하게 나타날수록 짧게)
  • frequency에 따라 트리 생성
• (b): C3 (허프만 코드)

• Bits(C1) = 163 + 53 + 123 + 173 + 103 + 253 = 255
• Bits(C2) = 163 + 55 + 124 + 172 + 105 + 251 = 230
• Bits(C3) = 162 + 54 + 123 + 172 + 104 + 252 = 212

최적 이진 코드 생성 과정

= 최적 머지 패턴

• 빈도수가 작은 것부터 트리 연결

알고리즘

• 문제: 최적 이진 코드 생성
• 입력: 빈도수를 가진 문자 집합
• 출력: 최적 이진 코드 트리

의사코드

• 우선순위 큐 이용 (min heap)

struct nodetype {
    char symbol;
    int frequency;
    nodetype* left;
    nodetype* right;
};

Nodetype Huffman(struct ndoetype charSet[], int n) {
    for(i = 1; i <= n; i++) {
        Insert(PQ, charSet[i]);
    }
    for(i = 1; i <= n-1; i++) {
        p = remove(PQ);
        q = remove(PQ);
        r = new nodetype;
        r -> left = p;
        r -> right = q;
        r -> frequency = p -> frequency + q -> frequency;
        Insert(PQ, r);
    }
    return remove(PQ);
}

시간복잡도

• 최적 머지 패턴과 동일 = $Θ(nlog^n)$
• 우선순위 큐 (PQ) : min heap으로 구성
  • Insert(PQ, key) : $log^n$
  • Remove(PQ) : 상수 시간