Greedy Algorithm(그리디 알고리즘)

Greedy Algorithm

• optimization problem을 풀 때 사용
• dynamic programming이 너무 과도할 때(복잡할 때) greedy로 더 쉽게 풀 수 있다. 
• 현재 상황에서 최선의 답을 선택. 현재 상황의 최선이 전체의 최선이길 바라면서 푼다. 
• Greedy choice property(앞의 선택이 이후의 선택에 영향을 주지 않는 조건)를 만족할 때 사용한다. 
• 현재 상황에서는 최선이지만 전체에서 최선이라는 보장은 없다. 
• greedy로 풀 수 있는 문제는 모두 dynamic programming으로 풀 수 있다. 
• top-down 구조 (dynamic은 bottom up)
• ex) 가방채우기 문제, 허프만 코드, 크루스컬 MST, 프림 MST, SSSP

 

 

 

Counting money

6.39$를 만든다고 하자. 

1. $5 bill
2. $1 bill, to make $6
3. 25¢ coin, to make $6.25
4. 10¢ coin, to make $6.35
5. four 1¢ coins, to make $6.39

US 달러에 대해서는 greedy algorithm으로 optimum solution을 풀 수 있다. 

 

그런데 만약 krons라는 화폐가 있다면? (a faliure of the greedy algorithm)

이 화폐는 1kron, 7kron, 10kron의 동전으로 이루어져있다. 

그리디 알고리즘으로 15krons를 만든다면

• 10 kron bill, to make 10kron
• five 1kron, to make 15kron

총 6개의 동전이 필요하다. 

 

하지만 7kron 2개, 1kron 1개를 내면 3개의 동전으로 더 적다. 이렇게 그리디 알고리즘은 모든 케이스에 맞는 답을 내지는 않는다. 

즉, 이 경우에 Greedy Algorithm은 답을 냈지만 최적해는 아니다. 

 

 

Activity-selection Problem(활동 선택 문제)

여러개의 activity가 있을 때, 각 activity의 시작시간, 종료시간을 보고 최대 몇개의 활동을 할 수 있을까?

Input : activity 집합의 시작시간: Si, 종료 시간Fi

Output : 최대 할 수 있는 활동의 집합

예시)

 

그림의 경우 {1, 4, 7}의 활동이 한번에 가능하다. 

 

만약 이걸 Dynamic Programming으로 푼다면? 

복잡하다.

-> Greedy로 훨씬 간단하게 풀 수 있다. 

 

1. 종료시간은 오름차순 정렬
2. 첫번째 활동을 넣고 시작
3. 이전 활동이 끝나는 시간 이후에 시작하는 activity를 넣는다.
4. 더이상의 활동이 없을 때 까지 반복한다. 

증명

현재 상황에서 선택할수 있는 가장 빠른 활동을 선택하지 않는 경우가 있다해도, 그것은 빠른 활동을 선택한 경우로 대체가 가능하다.

 

 

Greedy Algorithms vs. Dynamic Programming

• 표에서 볼 수 있듯 Greedy로 풀 수 있는 문제는 무조건 DP로 풀 수 있지만(DP가 더 Powerfull 하다. ) DP를 무조건 Greedy로 풀 수 있지는 않다.
• 그리디와 DP 모두 Optimization 문제를 풀 때 사용한다.  
• DP는 하위 문제에 의존하지만 Greedy는 순간의 최선의 선택을 하며 이 선택은 하위문제에 의존하지 않는다. 
• greedy를 언제 써야 하는지 알아차리기 어렵다. -> DP로 먼저 풀어보고 선택을 이해한 후 눈앞의 선택이 다른 선택보다 나은지 확인한 후 문제를 푼다. 

 

 

The Knapsack Problem(가방 채우기 문제)

• 가방에 담을 수 있는 무게가 정해져있을 때, 가방에 담은 물건들의 가치가 최고가 되도록 선택하는 문제 
• 가방 최대 용량 W
• set S는 n개의 물건으로 구성
• wi : 아이템 i의 무게
• bi : 아이템 i의 가치

 

방법1. 0-1 knapsack problem

• item을 넣거나 안넣거나

0-1 knapsack

 

• brute-force approach로 푼다면?

        -> O(2^n)

 

• Dynamic problem으로 푼다면?

    Sk={items labeled 1,2,...,k}

    물건을 빼고 다른걸 넣을 수 있기 때문에 Sn이 Sk의 부분의 일부분이 아닐 수 있다. -> 오류!! 다시 생각해야한다.

    -> 2차원 배열로 정의한다. 

 

 

case1 : wk>w이면 item k는 너무 무거워서  배낭에 넣을 수 없다. 

ex) 처음에 배낭이 20kg이고 w1=2kg이므로 배낭에 넣을 수 있다. item1을 넣는다는 선택을 하면 최대 가격은 3+18kg에 넣을 수 있는 최대 가격이 된다. 즉, 18kg에 남은 물건을 넣는 부분 문제가 된다.

 

case2 : wk≤w이면 item k를 넣지 않았을때와 넣었을때의 가격중 최대를 택한다.

ex) 만약 item1을 넣지 않는 선택을 하면 최대가격은 0+20kg에 남은 물건을 넣을 수 있는 최대 가격이 된다. 즉, 20kg에 남은 물건을 넣는 부분문제가 된다. 

 

Running time : O(n*W)

 

• Greedy로는 풀 수 없다. 

 

 

방법2. fracional knapsack problem (아이템을 잘라서 가져갈 수 있다.)

fractional

 

• Greedy로 풀 수 있다. 

각각의 단위 무게당 값어치를 따진 후 높은것부터 집어넣는다. 

Runnung tima : item이 정렬되어있을 경우 : O(n), 아니면 O(nlogn)

 

 

Huffman Code Problem

• 한글이 포함된 문자는 16bit유니코드를 사용한다. 영어만 포함된 문자는 8bit ASCII코드를 사용한다. 영어로 1,000자를 작성했다면 8 X 1,000 bit 를 차지하게 된다.
• 이 파일 크기를 줄이기 위해 허프만코드를 이용해 데이터를 압축한다. 
• 빈도수가 많은 문자에 적은 비트를 할당하여 데이터를 압축하는 방식이다. 
• 허프만 코드는 prefix 코드인다. 

        * prefix-free : 어떤 코드도 다른 코드의 접두사로 나오지 않는다. -> decoding과정이 명확해진다. 

          20%~90%로 사이즈를 줄일 수 있다. 

• 단어 출현 빈도가 균일하면 허프만 코드(Variable-length codeword)는 ASCII(fixed-length codeword)에비해 이점이 없다. 
• 허프만 압축 알고리즘 과정

1. 발생 빈도수가 가장 낮은 두 문자를 선택해서 하나로 합친다. 
2. 왼쪽은 빈도수가 낮고 오른쪽은 높다.
3. 빈도수가 같은 것 중에서는 작은 집합을 우선적으로 연결한다.
4. 트리가 생성되면 차례대로 0,1 값을 부여한다. (왼쪽 0, 오른쪽 1)

예를 들어 a: 45, b: 13, c:12, d: 16, e: 9, f: 5 라면 

그림처럼 트리로 나타낸 후 해당 문자까지 타고 내려간다.

a: 0, c: 100, b: 101, d: 111, f: 1100, e: 1101

그렇다면 압축률은?

허프만 사용 : 45*1bit + (13+12+16)*3bit + (9+5)*4bit = 224bit

원래는 100개의 문자가 있었기 때문에 8bit X 100 = 800bit 였다. 

즉 224/8000 = 28%로 원래의 28%로 압축되었다. 

 

• Running time : O(nlogn)
• mp3, jpg format에 사용된다. 

 

	Divide & Conquer	Dynamic Programming	Greedy Algorithm
하위 문제	O	O	O
recursive	O	O	O
하위 문제의 독립성	O	X 연관이 있다.	O
하위 문제의 갯수	어떻게 쪼개는지에 따라 달라짐	typically small	순서에 의존
전처리 할 때Runnung time	typically logn	하위 문제의 수와 난이도에 달렸다.	nlogn 정렬 주로 사용
주로 optimization문제를 푼다.		O	O
optimal substructure		O	O
Greedy choice property			O
Heuristic, 경험적인 법칙에 이용			O