Algorithm.Greedy Algorithm

[Visual Studio과 C#으로 구현/최적화문제해결]

Algorithm Greedy Algorithm Coding // Week06

20211014_20615034

[ Greedy Algorithm Coding_Theory ]

Greedy Algorithm은 최적화 문제를 해결하는 알고리즘이다.

• 최적화 (optimization) 문제
- 가능한 해들 중에서 가장 좋은 (최대 또는 최소) 해를 찾는 문제
• 욕심쟁이 방법, 탐욕적 방법, 탐욕 알고리즘 등으로 불림
• 그리디 알고리즘은 (입력) 데이터 간의 관계를 고려하지 않고 수행 과정에서 ‘욕심내어’ 최소값 또는 최대값을 가진 데이터를 선택
- 이러한 선택을 ‘근시안적’인 선택이라고 말하기도 함
• 그리디 알고리즘은 일단 한 번 선택하면, 이를 절대로 번복하지 않는다.
- 즉, 선택한 데이터를 버리고 다른 것을 취하지 않는다.
• 이러한 특성 때문에 대부분의 그리디 알고리즘들은 매우 단순하며, 또한 제한적인 문제들만이 그리디 알고리즘으로 해결된다.

[ 동전 거스름돈 문제 (CoinChange 알고리즘) ]

동전 거스름돈 (Coin Change) 문제를 해결하는 가장 간단하고 효율적인 방법

• 남은 액수를 초과하지 않는 조건하에 ‘욕심내어’ 가장 큰 액면의 동전을 취하는 것
• 동전 거스름돈 문제의 최소 동전 수를 찾는 그리디 알고리즘

- 단, 동전의 액면은 500원, 100원, 50원, 10원, 1원

- CoinChange
입력 : 거스름돈 액수 W

출력 : 거스름돈 액수에 대한 최소 동전 수

예) 동전 거스름돈의 예

• 760원일 경우

- 500 + 2*100 + 50 + 10

• 만일 160원짜리 동전이 있을 때, 거스름돈이 200원이라면?

- 160 + 4*10 >> 5개의 동전

- 2*100 >> 2개의 동전

• CoinChange 알고리즘은 항상 최적의 답을 주지 못함
- 따라서 실제로는 거스름돈에 대한 그리디 알고리즘이 적용되도록 동전이 발행됨

[ 최소 신장 트리 (Minimum Spanning Tree) ]

주어진 가중치 그래프에서 사이클이 없이 모든 점들을 연결시 킨 트리들 중 선분들의 가중치 합이 최소인 트리
​

• (c)는 가중치의 합이 (b)보다 크고, (d)는 트리가 주어진 그래프의 모든 노드를 포함하고 있지 않다
​
주어진 그래프의 신장 트리를 찾는 방법
: 사이클이 없도록 모든 점을 연결시킨다.
​
그래프의 점의 수가 n
- 신장 트리에는 정확히 (n-1)개의 선분이 있다.
- 트리에 선분을 하나 추가시키면, 반드시 사이클이 만들어진다.

[ 최소 신장 트리 (그리디)알고리즘 ]

- 크러스컬 (Kruskal) 알고리즘
가중치가 가장 작은 선분이 사이클을 만들지 않을 때에만 ‘욕심내어’ 그 선분을 추가시킨다.
​
- 프림 (Prim) 알고리즘
임의의 점 하나를 선택한 후, (n-1)개의 선분을 하나씩 추가시켜 트리를 만든다.
​ •알고리즘의 입력은 1개의 연결요소 (connected component)로 된 가중치 그래프

[ Kruskal’s MST ]

Kruskal 최소신장트리 알고리즘

KruskalMST(G)

입력 : 가중치 그래프 G=(V,E), |V|=n , |E|=m
출력 : 최소 신장 트리

[ Prim’s MST ]

Prim의 최소신장트리 알고리즘

PrimMST(G)

입력: 가중치 그래프 G=(V,E), |V|=n, |E|=m

출력: 최소 신장 트리 T

>> 수행과정

1. a에서 시작한다면, a와 연결된 에지를 찾아서 그 중 가장 작은 값을 갖는 a-d를 선택 이제 a, d가 선택되었고, Dist[] 배열을 업데이트 한다.
2. 그 다음 작은 값인 a-b를 선택 이제 a, b, d가 선택되었고 Dist[] 배열을 업데이트 한다.

=> 1, 2 과정을 버텍스 갯수만큼 반복

이미 선택된 버텍스는 다시 선택되지 않으므로 사이클이 생기지 않는다.

[ Prim의 MST 실행 예 ]

[ Prim의 MST 실행 ]

교수님 너무 어렵습니다...

저 아직 저어기 앞쪽에 있어요,,,, 흐엉 ㅠㅠ