그리디(Greedy)

Greedy Alg.

경우의 수가 존재할 경우, 경우를 선택해야할 때 최선이라고 생각하는 경우를 선택하는 알고리즘이다.

§해를 구하는 일련의 선택 과정마다

§그 단계에서 ‘가장 최선’이라고 여겨지는 국부적인 최적해를 선택해 나가면

§결과적으로 전체적인 최적해를 구할 수 있을 것이라고 희망적인 전략을 취하는 방법

–희망적 à 각 단계마다 선택한 최적해가 전체 최적해를 만들어 내지 못할 수 있음을 의미

§동작 과정

1.해 선택: 현재 상태에서 부분 문제의 최적해를 구한 뒤, 이를 부분해 집합(solution set)에 추가

2.실행 가능성 검사: 새로운 부분해 집합이 실행 가능한지 확인, 문제의 제약 조건을 위반하지 않는지 검사

3.해 검사: 새로운 부분해 집합이 문제의 해가 되는지 확인; 아직 전체 문제의 해가 완성되지 않았다면 (1)의 과정부터 다시 시작

§최소 개수 거스름돈 만들기

§예) 물건 가격이 1200원, 손님이 2000원을 지불한 경우

–거스름돈 800원

•100원 * 8개

•500원 * 1개  + 100원 * 3개

1.해 선택: 단위가 가장 큰 단위 동전 선택; 거스름돈에 추가

2.실행 가능성 검사: 선택한 동전이 거스름돈 총액을 초과하는지 검사

3.해 검사: 여태까지 선택한 동전이 최종 거스름돈 총액과 동일한지 검사; 모자라면 다시 1)을 수행

§Knapsack problem

§최대 용량 M인 하나의 배낭과 각각 무게 wi와 이익 bi가 부여되어 있는 n개의 물체가 있다고 가정

§Knapsack Problem

–배낭의 용량을 초과하지 않는 범위에서 배낭에 들어있는 물체의 이익의 합이 최대가 되도록 물체를 집어넣는 방법을 찾아내는 것 

1.해 선택: 단위 무게당 이익이 가장 큰 물건 넣기

2.실행 가능성 검사: 선택한 물건의 무게가 배낭 총량을 넘지 않는지 검사

3.해 검사: 더 넣을 수 있다면 다시 (1) 수행

§Minimum Spanning Tree

–Kruskal

§Kruskal’s Alg.

(1) Graph 내의 모든 edge을 weight에 따라 increasing order로 sorting

(2) (1)의 edge를 차례대로 MST에 추가;

(3) 단 cycle이 형성되면 안됨

1.해 선택:

  (1) Graph 내의 모든 edge을 weight에 따라 increasing order로 sorting

  (2) (1)의 edge를 차례대로 MST에 추가;

2.실행 가능성 검사:

(3) 단 cycle이 형성되면 안됨

3.해 검사:

  Graph 내의 모든 vertex 연결? 아니면 다시 1로

–Prim

1.Graph와 MST= { }

2.Graph에서 임의의 vertex를 MST의 root node로 설정

3.MST에 삽입되어있는 vertex들과 이 vertex의 인접 vertex사이의 edge의 가중치 중에서 가장 작은 vertex을 MST에 추가

4.단 cycle은 없어야 함

5.MST가 Graph이 모든 vertex을 연결할 때까지 반복 (3/4) 반복

§해 선택:

3. MST에 삽입되어있는 vertex들과 이 vertex의 인접 vertex사이의 edge의 가중치 중에서 가장 작은 vertex을 MST에 추가

§실행 가능성 검사:

4. 단 cycle은 없어야 함

§해 검사:

5. MST가 Graph이 모든 vertex을 연결할 때까지 반복 (3/4) 반복

§Shortest Path

–Dijkstra’s Alg.

1.각 vertex까지의 경로 길이를 무한대로 초기화

2.시작 vertex의 경로 길이를 0으로 초기화

3.아직 포함되지 않은 vertex 중 최소인 것 선택하여 최단경로에 추가

4.최단경로에 새로 추가된 vertex의 인접 vertex들에 대해 경로 길이를 갱신; 만약

5.모든 vertex이 최단경로에 소속될 때까지 (3/4)번 과정 반복

§해 선택:

     3. 아직 포함되지 않은 vertex 중 최소인 것 선택하여 최단경로에 추가

     4. 최단경로에 새로 추가된 vertex의 인접 vertex들에 대해 경로 길이를 갱신; 만약

§실행 가능성 검사:

§해 검사:

    5. Graph내의 모든 vertex이 최단 경로에 소속될 때까지 (3/4)번 과정 반복

§Huffman Coding