Ch 04. 그리디 알고리즘 (1)

그리디 알고리즘

개념

• 가능한 해 중, 가장 좋은 해를 찾는 문제

특징

• 전체 고려하지 않고 한 시점에서 최솟값/최댓값 데이터를 선택(= 근시안적)
• 한 번 선택하면 절대 번복하지 않는다.

4.1 동전 거스름돈

그리디 알고리즘 아이디어

• 남은 액수 초과하지 않는 조건 하, 욕심내어 가장 큰 액면의 동전부터 취하는 것!
• 최소 동전 수 찾기

구현

• Pseudocode
  입력: 거스름돈 액수 W

	CoinChange(W)
    	change = W;
        c500 = c100 = c50 = c10 = c1 = 0; //동전 개수 담는 변수
        
        while (change>=500) //500원으로 최대한 많이 거슬러 받기
        	{change -= 500; c500++;}
        while (change>=100)
        	{change -= 100; c100++;}
        while (change>=50)
        	{change -= 50; c50++;}
        while (change>=10)
        	{change -= 10; c10++;}
        while (change>=1)
        	{change -= 1; c1++;}
            
        return (c500+c100+c50+c10+c1);

과정

한계

• 거스름돈이 200원이고, 160원인 동전이 있다면?
  • 160원 1개, 10원 4개
  • BUT! 100원 2개가 최적
• 그리디 알고리즘을 적용한 CoinChange 알고리즘이 항상 최적 답을 제공하지 못한다.
• 동적 계획 알고리즘: 어떤 경우에도 최적해 찾는 알고리즘

4.2 최소 신장 트리

4.2.1 신장트리, 최소 신장트리

개념

• 그래프
  • 정점(V)과 간선(E) 집합으로 구성되는 비선형 자료구조
• 신장트리
  • 그래프의 모든 정점 포함
  • 사이클 없음
  • V-1 개의 간선
• 최소신장트리(MST)
  • 신장트리 중, 가중치의 합 최소

어떻게 찾을까?

• 그리디 알고리즘: Kruskal, Prim
  
  

4.2.2 Kruskal MST

개념

• 간선을 가중치 최솟값부터 오름차순 정렬
• 최소 가중치부터 하나씩 꺼내어 신장트리 구성

구현

가중치 그래프 G = (V, E)
정점의 수 |V| = n
간선의 수 |E| = e

• Pseudocode

	KruskalMST(G)
    	L[e] = 가중치 오름차순으로 간선 정렬;
    	T = NULL; //출력 트리(최소신장트리) 초기화
        
        while(T의 간선 수 < n-1){
        	L에서 최소 가중치 간선 m 꺼내기;
            L에서 m 삭제;
            
            if (T에서 사이클 형성 시) //Union & Find
            	m 제외;
            else
            	T에 m 추가;
        }
        
        return T; //MST 리턴

과정(과제 구현)

시간복잡도

• 가중치 정렬: $O(eloge)$ => 최소 힙정렬
• while Loop: $e$번
• Union & Find: $O(a(N))$ => 경로 압축 시 Find 시간 복잡도

$\therefore$ $O(eloge)$

4.2.3 Prim MST

개념

• 임의의 점에서 시작
• 인접 간선 중 최소 가중치 가진 간선 선택
• 신장트리 구성될 때까지 반복

구현

가중치 그래프 G = (V, E)
정점의 수 |V| = n
간선의 수 |E| = e
최소신장트리 T

• Pseudocode 1(힙 사용하지 않는 경우)

	PrimMST1(G)
    /*D[v]는 T에 있는 점 u, v 연결 최소가중치 간선 갱신 배열*/
    	D[p] = 0; //임의의 시작 정점 
        
        for(p 외의 정점 v){ //D[v] 초기화
        	if ((p, v) 존재)
            	D[v] = w[p, v];
            else
            	D[v] = INTMAX;
        }
        T = {p};
        
        while(|T| < n){
        	//최소 가중치 간선 추가
        	if ((u in T) && (v not in T)) && min{D[v]}
            	T = T + {(u, v), v};
            
            // 가중치 재조정(갱신)
            for (w not in T){
            	if (w[u, w] < D[w])
                	D[w] = w[u, w];
            }
        }
        
        return T;

과정(과제 구현)

특징

• T 밖에 있는 점만을 추가하므로 사이클이 만들어지지 않는다.

시간복잡도

• 힙 자료구조 사용하지 않을 경우
  • $O(n^2)$
• 힙 자료구조(피보나치 힙) 사용할 경우
  • $O(nlogn + e)$

4.3 최단 경로 찾기

4.3.1 Dijkstra

개념

• 출발점에서 다른 도착점까지의 최단 경로를 찾는 문제
• Prim vs. Dijkstra
  • Prim
    • 임의의 점에서 시작
    • 현재 상태 트리에서 가장 가까운 점 추가
  • Dijkstra
    • 출발점이 정해짐
    • 출발점으로부터 최단거리 정해지지 않은 점들 중, 출발점에서 가장 가까운 점 추가

구현

가중치 그래프 G = (V, E)
정점의 수 |V| = n
간선의 수 |E| = e

출발 정점 s
s부터 v까지의 최단거리 저장 배열 D

• Pseudocode

  ShortestPath(G, s){
  	  /*D[v] 무한대로 초기화*/
      D[s] = 0; 모든 D[v] = INTMAX;
      
      while(s부터의 최단거리 확정되지 않은 점 있을 때){
          확정 안 된 점 v에 대해 최소 D[v]인 점 v 선택;
          D[v] 확정;

          각 점 w, D[w] 최단거리 값으로 갱신;
      }
      
      return D;
  }

과정(과제 구현)

시간복잡도

• 힙 자료구조 사용하지 않는 경우

  • while Loop: n-1회
    • D[v] 최솟값인 점 v 찾기: O(n)
    • D[w] 갱신: O(n)

  $\therefore (n-1) * {O(n) + O(n)} = O(n^2)$

• 힙(피보나치 힙) 사용하는 경우

  • $O(nlogn + e)$

4.4 부분 배낭 문제

개념

• n 개의 물건(무게/가치)
• 최대의 가치를 갖도록 한정된 용량의 배낭에 넣을 물건들을 정하는 문제
  
  
• 0-1 배낭 문제: 물건을 통째로 넣어야 한다.
  • 그리디로 해결 불가능
  • 동적계획 알고리즘, 백트래킹 기법, 분기한정 기법 활용
• 부분 배낭 문제: 물건을 쪼개서 담기 가능
  
  
• 단위 무게당 가치 구하기
• 단위 무게당 가치가 높은 순으로 배낭에 넣기
• 통째로 넣을 수 없을 때, 넣을 수 있을 만큼만 쪼개서 담기

구현

물건 개수: n
각 물건 무게: w
각 물건 가치: v
배낭 용량: C

배낭에 담은 물건 리스트: L
담은 물건 무게의 합: sum_w
담은 물건 가치의 합: sum_v

• Pseudocode

  FractionalKnapsack(n, w, v, C)
  	S = 각 물건의 단위 무게당 가치 계산;
    S = sorted(S, reverse = True); //내림차순 정렬
    
    L = NULL; sum_w = 0; sum_v = 0; //초기화
    
    x = S에서 단위 무게당 가치 가장 큰 물건;
    
    while(sum_w + w(x) <= C){
    // (무게 합 + x의 무게)가 배낭 총 용량보다 작거나 같을 때
    
    	L = L + {x};
        sum_w += w(x);
        sum_v += v(x);
        
        S = S - {x};
        x = S에서 단위 무게당 가치 가장 큰 물건;
    
    }
    
    if((C - sum_w) > 0){ //배낭에 쪼개서 담을 여유 있으면
    	L = L + {x};
    	sum_w += {(C-sum_w)만큼의 w(x)};
        sum_v += {(C-sum_v)만큼의 w(v)};
    }
    
    return L, v; //담긴 물건 리스트, 가치의 합

시간복잡도

• 단위 무게당 가치 계산: O(n)
• 내림차순 정렬: O(nlogn)
• while Loop: 최대 n 번
  • 담는 작업: O(1)
• 나머지 쪼개서 담기: O(1)

$\therefore O(nlogn)$