[알고리즘] Greedy Algorithm (2)

이전 내용

---

• Greedy Algorithm
• 거스름돈 문제
• 최소비용 신장트리(MST, Minimum Spanning Tree)
  • Prim 알고리즘
  • Kruskal 알고리즘

 

 

Greedy Algorithm (탐욕 알고리즘)

---

• 어떤 선택을 할 때 그 당시 가장 최선의 선택을 하여 문제를 해결하는 알고리즘
• 순간의 선택은 지역적으로 최적이나, 이런 선택을 모아 얻은 해답이 최적인 보장이 없다.
  • 따라서 얻은 해답이 최적인지 검사하는 절차 필요

 

 

Greedy Algorithm 설계

---

1. 선정 과정 (selection procedure)

• 현재 상태에서 가장 좋을 것이라 생각되는(greedy) 해답 찾아서 solution set에 포함

2. 적정성 점검 (feasibility check)

• 새로 얻은 solution set이 적절한지 결정

3. 해답 점검 (solution check)

• 새로 얻은 solution set이 최적의 해인지 결정

 

 

Dijkstra 의 단일출발점 최단경로 알고리즘

---

1) Dijkstra 의 단일출발점 최단경로 문제

• 어떤 특정 정점에서 다른 모든 정점까지 최단 경로만 필요한 경우 사용하는 알고리즘
• Dijkstra 단일출발점 최단경로 알고리즘 시간복잡도: Θ(n^2)
• Prim 알고리즘 MST와 유사

 

2) Dijkstra 알고리즘 자료구조

• 인접 행렬 W[i][j]
• touch[i]: Y에 있는 정점에서 V1에서 Vi로 가는 현재 최단 경로 상 마지막 간선이 (V, Vi)일 때, Y에 있는 정점 V의 색인
• length[i]: Y에 있는 정점에서 V1에서 Vi로 가는 현재 최단경로 길이

 

3) Dijkstra 의 단일출발점 최단경로 알고리즘

1. Y = {V1}

touch

2	3	4	5
1	1	1	1

length

2	3	4	5
7	4	6	1

 

2. Y = {V1, V5}

• V1에서 V5 경유해서 V2~V4 갈 수 있으면, V5 경유했을 때 더 짧아지면 touch 배열 값에 5로 갱신(경유할 수 없으면 놔둠), length 갱신

touch

2	3	4	5
1	1	5	1

length

2	3	4	5
7	4	2	-1

 

3. Y = {V1, V5, V4}

• V4 경유해서 V2~V3 갔을 때 더 짧아지면 해당 경로를 length 배열에 갱신, touch 배열에 4로 값 갱신
• 1에서 5 경유해서 4로 갈때(2) + 4에서 2로 갈 때 값(3)이 기존의 length[2] = 7보다 작으므로 length[2] = 5, touch[2] = 4로 갱신 

touch

2	3	4	5
4	1	5	1

length

2	3	4	5
5	4	-1	-1

 

4. Y = {V1, V5, V4, V3}

• V3을 경유해서 2를 갔을 때(7)보다 length[2]가 더 작으므로 업데이트 X 

touch

2	3	4	5
4	1	5	1

length

2	3	4	5
5	-1	-1	-1

 

4. Y = {V1, V5, V4, V3, V2}

touch

2	3	4	5
4	1	5	1

length

2	3	4	5
-1	-1	-1	-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[1] = 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);
        F = F ∪ {e};
        for(i=2; i<=n; i++){
        	if(length[vnear]+W[vnear][i] < length[i]){ // vnear 경유할 때 더 최단경로이면
            	length[i] = length[vnear] + W[vnear][i];
                touch[i] = vnear; // 경유해서 가는 정점
            }
            length[vnear] = -1 // 방문한 정점은 -1로 표시
        }
    }
}

• 시간복잡도
  • T(n) = 2(n-1)(n-1) ∈ Θ(n^2)

 

 

Greedy Algorithm vs. Dynamic Programming

---

• 최적화 문제 해결에 사용할 수 있는 알고리즘
  • 탐욕 알고리즘은 알고리즘 결과가 최적인지 증명 필요
  • 동적 프로그래밍은 최적의 원칙이 적용되었는지 검사 필요
• 같은 문제를 탐욕 알고리즘, 동적 프로그래밍으로 모두 해결할 수 있으면 보통 탐욕 알고리즘이 더 효율적

 

 

Knapsack Problem (배낭 문제)

---

1) 0-1 배낭 채우기 문제 (0-1 knapsack problem)

• 전체 무게가 배낭이 수용 가능한 총 무게(W)를 넘지 않으면서 item 가치 합이 최대가 되도록 하는 item set을 만든다.
• item이 solution set에 포함되거나 포함되지 않기 때문에 0-1
• 무작정 알고리즘의 경우: 시간복잡도 2^n
• Greedy Algorithm
  • 방법 1. 가장 비싼 item 순으로 채운다.  -> 최적 X
  • 방법 2. 가장 무게 적은 item 순으로 채운다. -> 최적 X
  • 방법 3. 무게당 가치 가장 높은 물건부터 채운다. -> 최적 X

 

 2) Fractional Knapsack Problem (배낭 빈틈없이 채우기 문제)

• item을 잘라서(fractionally) 일부만 담을 수 있는 문제로, 1)에서 Greedy Algorithm 방법 3로 Fractional Knapsack Problem의 최적의 해 구할 수 있다.
• 예) W = 30kg, S= {item1, item2, item3}

  

  Greedy Algorithm 방법3: item1 + item3 + item2 x 1/2일때 이윤 = 50 + 140 + 30 = 220
• 알고리즘
  • 문제: 배낭의 용량 넘지 않으면서 가장 최대의 이득 얻을 수 있도록 배낭 채우기
  • 입력: 배낭 용량 M, 아이템 개수 n, 아이템 이득 저장된 배열 p[1:n], 무게 저장된 배열 w[1:n] (무게 당 이익이 큰 순서로 정렬 p[i]/w[i] >= p[i+1]/w[i+1])
  • 출력: 배낭에 들어가는 아이템 리스트 x[1:n]

int GreedyKnapsack(float M, int n, int p[], int w[], int& x[]){
	for(int i=1; i<=n; i++) x[i] = 0.0;
    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]; // 아이템 남았으면 쪼개서 넣는다.
}

 

3) 배낭 (빈틈업이) 채우기-Greedy 알고리즘 분석

• 시간복잡도
  • p[1..n], w[1..n] 배열 정렬: Θ(nlogn)
  • GreedyKnapsack: Θ(n)
  • T(n) = Θ(nlogn)

 

 

Optimal Merge Patterns (최적 머지 패턴)

---

1) Optimal Merge Patterns (최적 머지 패턴)

• 문제: 두 개 이상의 정렬된 파일이 주어졌을 때, 가장 효율적으로 파일들을 하나의 정렬된 파일로 합병하는 방법 찾기
• 효율성: 파일의 레코드 비교나 이동 횟수 최소화 -> 이동 횟수를 효율성 기준으로 보고 분석
• 정렬된 2개 파일(배열) 합병에는 각 배열의 크기 더한 만큼 이동
• 정렬 -> 최적화 필요
  • internal 정렬: 메모리 상에 정렬할 모든 데이터를 올려서 처리할 수 있는 경우
  • external 정렬: 많은 데이터를 정렬하기 위해 메모리에 모두 데이터를 올릴 수 없어서 swap이 필요한 경우 (파일을 올렸다가 처리 후 다른 파일과 swap해서 다른 파일 처리하는 방식)  
• 예) 작은 파일 우선 merge하는 방법
  • F = (20, 30, 10, 15, 5, 30)
  • (5, 10, 15, 20, 30, 30) sort
  • (15, 15, 20, 30, 30) merge 2 smallest files
  • (20, 30, 30, 30) sort & merge 2 smallest files
  • (30, 30, 50) sort & merge 2 smallest files
  • (50, 60) sort & merge 2 smallest files
  • (110)
  • 파일 이동 횟수: 15+30+50+60+110 = 265 (최적 merge 패턴)
  • 트리 사용

• 트리 구성 후 레코드 이동 총 횟수
  • 각 파일이 몇 번 포함되는지는 파일의 트리에서의 depth와 동일 
  • 레코드 이동 횟수 = 5*4 + 10*4 + 15*3 + 20*2 + 30*2 + 30*2 = 15+30+50+60+110 = 265

total # of record moves

 

2) 알고리즘

struct treenode{
	struct treenode *lchild, *rchild;
    int weight;
};
typedef struct treenode Type;

Type *Tree(int n){
	for(int i=1; i<=n-1; i++){
    	Type *pt = new Type;
        // Get a new tree node
        pt->lchild = Least(list);
        pt->rchild = Least(list);
        // merge two trees with smallest lengths
        pt->weight = (pt->lchild)->weight + (pt->rchild)->weight;
        Insert(list, *pt);
    }
    return (Least(list)); // 루트 노드 반환
}

 

3) 최적 머지 패턴 알고리즘 분석

• 반복문: (n-1)번 -> 비교횟수 (n-1), (n-2), ... => n(n-1)/2 
• heap tree 유지: logn
• 시간복잡도 T(n) = Θ(n^2) 또는 Θ(nlogn)

 

 

Huffman Code (최적이진코드 찾는 문제)

---

1) Huffman Code (최적이진코드 찾는 문제)

• 문제: 주어진 파일 내 문자들을 이진코드로 표현할 때 필요한 비트의 개수가 최소가 되는 이진문자 코드 찾기
• Huffman Code(허프만 코드): 파일을 코드화하는 방식 중 하나
• Prefix code로 구성하여 비트 수를 다르게 줘서 빈도가 높은 문자에 길이가 짧은 비트를 준다. (height가 짧도록)
  • 주의: b의 코드가 0일 때 01 같은 코드는 주지 않는다.

 

2) 허프만 코드 알고리즘

struct nodetype{
	char symbol; // value of character
    int frequency; // 파일에서 숫자 빈도
    nodetype* left;
    nodetype* right;
}

nodetype Huffman(struct nodetype 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);
}

 

3) 허프만 코드 알고리즘 분석

• Optimal Merge Patterns와 동일
• heap 트리 구성: nlogn -> logn
• 시간복잡도 T(n) = Θ(n^2) 또는 Θ(nlogn)