4장. 탐욕적인 접근방법(Greedy Algorithm) (2)

CS/알고릴라

4장. 탐욕적인 접근방법(Greedy Algorithm) (2)

seeyoun 2023. 5. 1. 22:17

◆ Dijkstra 알고리즘

하나의 출발 지점으로부터 다른 모든 도착 지점들로 가는 각 최단 경로들을 모두 계산할 때 쓰는 방법

< 방법 >

F (최종 결과 엣지 집합)를 공집합으로 초기화
Y (최단 경로가 확정된 노드들 집합)는 출발 노드로 초기화.(예시에서는 v1에서 출발하는 걸로 가정)
V-Y집합(최단 경로가 확정된 노드들을 제외한 노드들)에 속한 노드 중에서, v1(출발 노드)에서 Y에 속한 정점만을 거쳐서(무조건 거쳐야 하는 것은 아님) 최단 경로가 되는 정점 v를 선정한다.
그 정점 v를 Y에 추가한다.
v에서 Y로 이어지는 엣지('v와 Y를 잇기 위해 Y내에서 최종 경유하는 노드'와 'v노드'간의 엣지)를 F에 추가한다.
Y = V가 되면(전체 노드 다 돌음), T = (V, F)가 최단 경로를 나타내는 그래프(vertices, edges)

[pseudo code]

void dijkstra(int n, const number W[][],set_of_edges& F) {	//노드 수, 가중치 배열, 반환할 F
    index i, vnear;	
    edge e; 
    index touch[2..n];	// v1에서 시작해서, (V-Y에 속하는)vi까지 최단 거리로 갈 때, 	
                	// Y내에서 최종적으로 경유하는 노드의 index
                        // 시작노드가 v1이라 가정했으므로 2부터 시작
    number length[2..n]; // v1에서 시작해서, (V-Y에 속하는)vi까지의 최단 거리
    
    // 초기화
    F = ϕ;
    for(i=2; i <= n; i++) { // 첫 노드를 v1으로 잡고, touch[]와 length[] 초기화
        touch[i] = 1; // 처음엔 Y에 v1밖에 없으므로, 모든 노드에 대한 touch[i] = 1로 초기화
        length[i] = W[1][i]; // 처음엔 Y에 v1밖에 없으므로, v1과 vi를 직접 잇는 엣지의 가중치로 초기화
    }
    
    repeat(n-1 times) { // 처음 Y에 추가한 1을 제외하고 n-1번 반복(반복시마다 한 노드확정)
    			// Y에 속한 노드와 가장 가까운 V-Y의 노드인 vnear 찾기
        min = ∞;
        for(i=2; i <= n; i++)	// 각 정점들에 대해서
            if (0 <= length[i] < min) { // 출발 노드 v1과, (V-Y에 속한) vi 사이의 가중치가 min보다 작은 경우
            				// 이때, 이미 Y에 속하는 노드(length[i] > 0인 경우)는 제외
                min = length[i]; // min 업데이트
        		vnear = i; // 그 노드의 index로 vnear을 업데이트
    		}
            
        e = (touch[vnear], vnear); // vnear과 touch[vnear]을 잇는 엣지
        e를 F에 추가;
        
        // 업데이트된 Y에서, v1과 (V-Y에 속한) vi사이의 length가 감소할 수 있는지 확인
        for(i=2; i <= n; i++)
            if (length[vnear]+ W[vnear][i] < length[i]) { // v1~vnear + vnear~vi의 거리가 기존 v1~vi의 거리보다 작다면
            						// 이때, 이미 Y에 속하는 노드까지의 length는 -1이므로 여기 안들어감
                length[i] = length[vnear] + W[vnear][i]; // length[i]를 갱신한다
                touch[i] = vnear; // 이에 따른 touch[i]도 갱신
            }
        length[vnear]=-1;	// 찾은 노드를 Y에 추가한다.
    }
}

◇ Dijkstra 알고리즘 - 시간 복잡도 분석

(n-1) 반복 안에, 두번의 (n-1) 반복문이 있으므로 (n-1) * 2(n-1) = 2(n-1)²

따라서 T(n) = 2(n-1)² ∈ Θ(n²)

근데.. heap으로 구현하면 Θ(m lg n)까지 줄일 수 있다고 한다!

◆ Dijkstra 알고리즘 - heap으로 구현

start부터 node까지의 length가 현재보다 작은 node에 관한 정보를 최소 heap에 담아두고 작은거부터 꺼냄

빨간 화살표로 확인한 엣지는, 한번 확인하고 다시는 확인 안해도 되는 엣지임.

< Heap(pq)으로 구현 >

방문하지 않은 노드 중에서, length가 현재보다 작은 node에 관한 정보를 pq에 담아둠
위에서부터 하나씩 꺼내서 갖고옴. 이때, 그 노드 차례가 되기 전(아직 방문하기 전)까지는 그 노드 정보가 추가로 pq에 저장될 수도 있음. 그러다가 만약 그 노드를 이미 처리했으면, 그 다음에 다시 나오는 해당 노드 정보는 안봐도 됨.
length와 touch 업데이트 확인 시, 굳이 다 반복하며 확인하지 않고 필요한 횟수만큼만 확인하는 것.=> 우선순위 큐

< 시간 복잡도 >

O(n lg n) : root에서 min을 갖고 오고(n번), Heap을 재정렬하는 시간(log n 시간)
m : 총 엣지수 - v1에 연결된 엣지 수
length와 touch 업데이트 확인 시, 한번 안 고른 엣지는 다음에 다시 확인 안해도 됨. (이미 한번 안고를 때, 걔보다는 좋은 경로가 있는 것이 확정된 셈이니까).
=> 즉, 전체 알고리즘에서 하나의 엣지는 한번만 확인해주면 되는 것! 따라서 애초부터 v1에 연결되어 있던 애들(length 초기화시 미리 넣어둠)을 제외한 엣지들을 확인해주면 된다.
=> m번 만큼 heap operation을 해주면 되는데, 데이터 개수가 n개인 heap operation은 log n 시간이 소요되므로 Θ(m lg n)

따라서 총 시간복잡도는 O(n lg n) + Θ(m lg n)인데, m ≥ n이므로 Θ(m lg n)

참고) Heap 연산에서의 시간 복잡도

루트를 찾는 것 : O(1)
루트 찾고 재정렬 : O(lg n)
추가, 삭제, 수정 : O(lg n)

(최적여부 검증은 생략)

◆ Huffman Code

허프만 코드 자체가 아닌, greedy 알고리즘을 어떻게 적용해서 허프만 코드를 만들 수 있는지를 살펴볼 것임

허프만코드는 주어진 문자로 전치코드이자 최적 이진 코드를 만듦

Fixed-length binary code
코드 길이가 고정.. but, 코드 빈도가 높더라도 같은 길이를 써야하므로 낭비가 생길 수 있음
Variable-length binary code
코드의 길이가 변함.. but, 코드 길이가 다르므로 어디까지가 한 코든지 구분하기 힘들 수 있음(구분자 필요)
최적 이진 코드: Optimal binary code
주어진 파일에 있는 문자들을 이진코드로 표현하는데 필요한 비트의 개수(총 비트수)가 최소가 되는 코드
전치코드: prefix code
한 문자의 코드워드가 다른 문자의 코드워드의 앞부분이 될 수 없도록 한 것(구분자 없어도 됨)

예시)

총 비트수

Σ(vi가 나타날 빈도수 * 트리에서 vi의 depth)

트리 구조상, vi의 depth가 vi의 코드 길이가 됨 ㅇㅇ

근데 같은 prefix 코드여도 최적이 될 수도 있고 아닐 수도 있기 때문에, 최적을 찾아야함 => greedy 적용해보자!

◇ 허프만 코드 구축 과정 - Greedy 알고리즘 사용

(0) 빈도수를 데이터로 갖는 n개의 노드를 생성
(1)~(5) 빈도수의 합이 최소가 되는 두 노드를 merge 시켜 이진트리로 구축(merge된 노드도 하나의 노드로 취급)
- 모든 노드가 하나의 이진트리가 될 때까지 반복

◇ 허프만 코드 구축과정 - 구현

PQ(min heap)에서 루트 빼서 p에 넣고, 루트 빼서 q에 넣음. 둘이 합친 r 만들어서 다시 PQ에 넣음. n-1번 반복!

< 준비물 >

우선순위 큐 - Heap (MinHeap)

노드타입 자료구조는 다음과 같이 설계할 수 있다.

struct nodetype {
    char symbol;   //문자
    int frequency; //빈도수
    nodetype* left;
    nodetype* right;
};

[허프만 코드 생성 알고리즘]

for (i=1;i <= n-1; i++) {	// 반복할 때마다 두개의 트리가 합쳐서 한 트리가 만들어지므로 n-1번
    remove(PQ,p);	// PQ에서 빈도가 제일 낮은 애를 빼서 p로 받음
    remove(PQ,q);	// 그 다음으로 빈도가 낮은 애를 빼서 q로 받음
    
    // p,q를 합친 트리 r을 만듦
    r = new nodetype;
    r->left = p;	
    r->right = q;
    r->frequency = p->frequency + q->frequency;	// r의 빈도는 p빈도 + q빈도
    
    // PQ에다 p와 q를 합친 r을 집어넣음
    insert(PQ,r);
}
remove(PQ,r);	//PQ에서 최종으로 합쳐진 하나를 빼서 r로 받아서 리턴
return r;

빈도수가 작을수록 우선순위가 높다 (<= min heap은 빈도수가 작은 것부터 빼냄. 따라서 먼저 합치게 돼서, 최종적으로 아래쪽에 위치하게 됨)

실습해보기.

한번 조작할 때마다 lg n 만큼의 시간(heap operation)이 필요하기 때문에, 이를 n번 반복하면

Θ(n lg n) 이다.

◆ 0-1 Knapsack Problem (zero-one 배낭 문제)

어떤 물건을 넣느냐(1)/안 넣느냐(0)의 문제 (나눠서 넣을 수는 없음)

탐욕적 방법으로는 풀 수 없다

가장 가치가 크면서, 최대 무게를 초과하지 않도록 하는 것

S = item들의 집합
w_i = item_i의 무게
p_i = item_i의 가치
W = 배낭에 넣을 수 있는 최대 무게

라고 할 때,

한정된 무게 W 안에서 최대한의 가치를 갖도록 item을 넣는 방법

◇ 0-1 Knapsack Problem - 무작정 알고리즘

하나하나 다 고려해보자!

물건 개수가 n개일 때, 가능한 멱집합의 가짓수는 2ⁿ개이다. 넘 많음 ㅡ.ㅡ

◇ 0-1 Knapsack Problem - 탐욕적 알고리즘

우선 결론 : Greedy를 적용할 수 없는 문제다

가장 가치가 큰 물건부터 채워도 최적이 아니고, 가장 가벼운 물건부터 채워도 최적이 아니기 때문.

또, 무게당 가치가 가장 높은 물건부터 채워도 최적이 아님.

참고※ 배낭 빈틈없이 채우기 문제 (fractional kanpack problem)에서는 사용 가능함

문제를 잘라서 담을 수 있다는 가정 하에, 무게 한도 내에서 가장 큰 가치를 담을 수 있도록 하는 것!

→ 단위 무게당 가치가 큰 것부터 넣고, 더이상 넣을 수 없으면 배낭에 남은 무게만큼 잘라서 넣으면 됨.

◇ 0-1 Knapsack Problem - 동적 계획법

P[i][w] 배열을 채워넣으며, 최종적으로 P[n][W]의 값을 구하는 것이 목표.

P[i][w] = i번째 아이템까지 고려했을 때, 전체 무게가 w가 넘지 않는 한에서 최고의 이익

i번째 아이템이 w보다 크다면, 아예 넣을수가 없는 것이므로 이번 턴 패스.
i번째 아이템이 w보다 작거나 같다면, 최대 가치는 저번 턴(i-1 턴)의 최대 가치 또는 i번째 아이템을 포함했을 때의 가치 중 최댓값이다.(i번째를 포함하는 경우, i번째 아이템의 가치인 p_i를 더하고, 이번 턴 한도 무게에서 i번째 아이템의 무게인 w_i를 뺐을 때의 무게가 한도 무게였 때의 최대 가치를 더한 값이다.)

※ P[0][w] = 0이고, P[w][0] = 0 이다.

(0번째 아이템까지의 최고 이익은 0이고, 총 무게가 0을 넘지 않는 한에서 최고 이익도 0이다.)

P[n][W] = 모든 아이템(n개)까지 고려했을 때, 전체 무게가 한도 무게(W)를 넘지 않는 한에서 최고의 이익

이게 바로 우리가 최종적으로 구해야 할 것!!

[pseudo code]

knapsack(p,w,n,W) { #p[], w[], n, W[][]
    for(w=0 to W) P[0,w]=0	# 0번째 아이템까지의 가치는 0
    for(i=0 to n) P[i,0]=0	# 총 무게가 0일때 까지의 가치는 0
    
    for(i=1 to n)	# 첫번째 부터 마지막 아이템까지
        for(w=0 to W)	# 무게가 0일때부터 최대 한도 무게까지 설정
            if(w_i ≤ w)	# i번째 아이템의 무게가 이번 루프에 설정한 최대 무게 이하일때
                P[i,w] = max { P[i-1, w], p_i+P[i-1, w- wi]}	# 넣/말 결정
            else	# 이번 루프에 설정한 최대 무게보다 크면
                P[i,w] = P[i-1, w];	# 못 넣음
	
    return P[n,W]
}

1행 1열은 다 0으로 초기화하고, 가로로 한줄씩 채움.

시간 복잡도는 Θ(nW)

근데 사실.. 만약 W가 n! 정도의 값을 가진다면, 무작정 알고리즘에 비해 하나도 나은 게 없음! ㅠㅠ

◇ 0-1 Knapsack Problem - 개선된 동적 계획법

아이디어 : 모든 n-1 번째 행을 계산할 필요는 없다!
P[n-1][W]와 P[n-1][W-w_n] 식에 포함된 애들만 계산하면 됨

P[n-1][W]와 P[n-1][W-w_n] 식에 포함된 애들만 계산하면 됨.(재귀적으로 ㅇㅇ)

◇ 0-1 Knapsack Problem - 개선된 동적 계획법 시간복잡도

다음 두가지 경우 중 최악의 경우를 선정할 수 있다.

1) 한 턴을 계산하기 위해 2개의 이전 턴이 필요함.

n번째 턴을 계산하기 위해서는 2ⁿ-1개의 항을 계산해야 함!(등비급수 1+2+2²+...+2^(n-1)의 합)

따라서 Θ(2ⁿ)이다.

2) n=W+1이라고 하자. 모든 w_i가 1이라 하면(모든 아이템의 무게가 1), 한 턴을 계산할 때 고작 바로 붙어있는 대각선에서 갖고 오기 때문에, W 길이만큼 다 계산해봐야함. 따라서 1+2+3+...+n = n(n+1)/2 = (W+1)(n+1)/2 ∈ Θ(nW) 이다.

따라서, 최악의 경우 수행시간은

O(min(2ⁿ, nW))이다.

◆ 상호 배타적(Disjoint; 교집합이 공집합인.) 집합의 처리

상호 배타적: 서로 겹치는 원소가 없는.
프로그램 내에서 집합을 어떻게 표현하는 것이 좋은가? 표현 방법에 따라서 집합에 대한 연산 시간이 얼마나 걸릴것인가?

집합을 나타내는 세 가지 방법!

linked list
array
tree
- 단순 방법
- 무게(weight) 고려 방법
- path compression(경로 압축) 방법

▶ 우리의 목표 : find(원소 찾기), union(집합 합치기)의 명령어가 다수 있을 때 효율적인 처리가 가능한 자료구조와 알고리즘을 찾는다.

1) linked list 사용

Operation

✓ make_set(v): v를 원소로 하는 집합을 만듦
✓ find(v): v가 속해있는 집합 이름(최초 원소값) 반환
✓ union(u,v): 원소 u와 원소 v를 갖고 있는 집합을 하나로 합친다. (u가 속해있는 집합 이름을 가리키는 포인터들을 v가 속해있는 집합 이름을 가리키도록 바꿔준다) 이미같은 집합에 속해 있을 수 있다.