[알고리즘] 그리디 알고리즘 (greedy algorithm)

그리디 알고리즘 - 최적화 문제

데이터 간의 관계를 고려하지 않고 수행 과정에서 욕심내서 최소 또는 최댓값을 가진 데이터를 선택한다. (근시안적 선택)

 

동전 거스름돈 알고리즘

#의사코드

change=W, n500=n100=n50=n10=n1=0 // n500, n100, n50, n10, n1은 각각의 동전 카운트
while ( change ≥ 500 )       change = change-500, n500++      // 500원짜리 동전 수를 1 증가
while ( change ≥ 100 )       change = change-100, n100++      // 100원짜리 동전 수를 1 증가
while ( change ≥ 50 )       change = change-50, n50++          // 50원짜리 동전 수를 1 증가
while ( change ≥ 10 )       change = change-10, n10++          // 10원짜리 동전 수를 1 증가
while ( change ≥ 1 )       change = change-1, n1++              // 1원짜리 동전 수를 1 증가
return (n500+n100+n50+n10+n1)        // 총 동전 수를 리턴한다.

수도 코드. 한 line마다 최적의 해를 결정하고(이때 다음 줄에서 일어날 일은 고려하지 않음) 다음 줄로 넘어간다.

그러나 이는 위 동전이 항상 최적해가 나오도록(그리디 알고리즘에 맞게) 설계되었기 때문

만약 400원짜리 동전이 존재하고, 800원을 거슬러야 한다면 500원 1개 + 100원 3개가 아닌 400원 2개가 최적해이다.

따라서 그리디 알고리즘은 항상 최적해를 보장하지 않음.

import sys

n = int(sys.stdin.readline())

def coin(n):
    five_available = n // 5
    for i in range(five_available + 1):
        five = five_available - i
        a = n - five * 5
        if a == 0:
            return five
        elif a % 2 == 0:
            b = a // 2
            return five + b
        else: continue

    return -1

print(coin(n))

특정 상황까지 고려한 최적해 알고리즘이다. (동전 종류 2개의 경우)

 

 

최소신장트리 (MST) 알고리즘

그래프 내에서 사이클 없이 모든 vertex가 연결된 트리 중 선분 가중치 합이 가장 작은 트리를 찾는 알고리즘

 

1) kruskal 알고리즘 / 그리디로 가중치가 가장 작은 거(사이클 안만든다는 기준)만 선택해서 선분 추가

- 가중치 오름차순 리스트를 만들고 사이클이 안되는 조건으로 버리고 추가하면서 mst 생성

2) 프림 알고리즘 / 임의 점 하나 선택 후 (n-1)개의 선분을 하나씩 추가해서 트리 생성

- 무조건 이어져서 만들어져야 함. 연결되면서 연결된 점에 대해서 다른 점으로, 무한대였던 가중치 값이 할당됨

	크러스컬 알고리즘	프림 알고리즘
특징	•선분이 1개씩 T에 추가되는데, 이는 마치 n개의 점들이 각각의 트리인 상태에서 선분이 추가되면 2개의 트리가 1개의 트리로 합쳐지는 것과 같다. •크러스컬 알고리즘은 이를 반복하여 1개의 트리인 T를 만든다. •즉, n개의 트리들이 점차 합쳐져서 1개의 신장 트리가 만들어진다.	•T가 점 1개인 트리에서 시작되어 선분을 1개씩 추가시킨다. •즉, 1개의 트리가 자라나서 신장 트리가 된다.
시간복잡도	O(mlogm) m = 선분 수	O(n^2) while loop 찾는데 n-1 * 최소가중치 점 찾는데 n = n^2

 

크러스컬 sudo code (union find 자료구조 사용)

algorithm Kruskal(G)

    // 공집합으로 초기화
    A := ∅
    // 그래프 G의 모든 정점에 대해서
    for each v ∈ G.V do
        // 모든 정점들을 하나의 독립된 트리로 만들어 준다.
        MAKE-SET(v)
    // 그래프 G의 모든 간선들에 대해서 (간선들은 전부 오름차순으로 나열 되어있다.)
    for each (u, v) in G.E ordered by weight(u, v), increasing do
        // u와 v가 속한 집합이 서로 다르면 (서로 다른 집합의 트리라면)
        if FIND-SET(u) ≠ FIND-SET(v) then
           // u, v를 정점으로 하는 간선 (u, v)를 집합 A에 포함 시킨다.
           A := A ∪ {(u, v)}
           // 두 집합 u, v를 하나의 집합으로 합친다.
           UNION(FIND-SET(u), FIND-SET(v))
    return A

 

Prim 알고리즘 의사코드

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

D[p] = 0

for each V in G
    if v == p continue
    else if v connected to p
         D[v] = w(p, v)
    else D[v] = 무한대

T = {p}

while (len(T) < n)
    T.extract(u, v_min)
    for each w not in T
        if weight(v_min, w) < D[w]    //기존 가중치보다 새로 판 길의 가중치가 작은 경우 갱신
            D[w] = weight(v_min, w)

return T

 

최단 경로 찾기  - 다익스트라 알고리즘

ShortestPath(G, s)
입력: 가중치 그래프 G=(V,E), |V|=n , |E|=m
출력: 출발점 s로부터 (n-1)개의 점까지 각각 최단 거리를 저장한 배열 D

1. 배열 D를 ∞로 초기화시킨다. 단, D[s]=0으로 초기화한다.
          // 배열 D[v]에는 출발점 s로부터 점 v까지의 거리가 저장된다.
2. while (s로부터의 최단 거리가 확정되지 않은 점이 있으면) {
3.     현재까지 s로부터 최단 거리가 확정되지 않은 각 점 v에 대해서 최소의 D[v]의 값을 가진 점 vmin을 선택하고, 출발점 s로부터 점 vmin까지의 최단 거리 D[vmin]을 확정한다. 
4.     s로부터 현재보다 짧은 거리로 점 vmin을 통해 우회 가능한 각 점 w에 대해서 D[w]를 갱신한다. }
5. return D

 

 

부분 배낭 문제

FractionalKnapsack
입력: n개의 물건, 각 물건의 무게와 가치, 배낭의 용량 C
출력: 배낭에 담은 물건 리스트 L과 배낭에 담은 물건 가치의 합 v


S = 무게 당 가치 기준으로 내림차순 정렬된 리스트

L = []        #배낭 
w = 0, v = 0  #배낭 내 물건 무게 합, #배낭 내 물건 가치 합

x = S[0]

while w + x <= C
    L.append(x)
    w += x_w
    v += x_v
    S.remove(x)
    x = S[0]

#부분적으로 담기

if C - w > 0   #아직 배낭 내 자리가 있으면
        L.append(x_fraction)
    v += x_v * x_fraction

return L, v

 

FractionalKnapsack(Item *arr, int capacity)
{
  각 물건의 단위 무게당 가치를 계산한다.
  단위 무게당 가치를 기준으로 내림차순 정렬하여 저장한다.
  int weight = 0; // 배낭에 담긴 무게
  int value = 0; // 배낭에 담긴 가치의 총합
  Item highest = 단위 무게당 가치가 가장 큰 물건;
  Item *list; // 배낭에 담긴 물건의 리스트
  while (weight + highest.weight <= capacity)
  {
    highest를 list에 추가한다.
    weight += highest.weight;
    value += highest.value;
    highest를 arr에서 제거한다.
    새로운 highest를 선정한다.
  }
  if (capacity > weight)
  {
    highest를 (capacity - weight)만큼만 list에 추가한다.
    value += capacity - weight;
  }
  return list, value;
}

 

Line 4에서 n개의 물건 단위 무게당 가치를 계산하는 데 O(n) 시간이 걸림.
Line 5에서 물건의 단위 무게당 가치에 대해 정렬하므로 O(nlogn) 시간이 걸림.
Line 8~13의 while-루프의 수행은 n번을 넘지 않으며, 루프 내부의 수행은 O(1) 시간,
Line 14~17, O(1) 시간이 걸림.

 

 

집합 커버

C=∅

while (U≠∅) do {

U의 원소들을 가장 많이 포함하고 있는 집합  Si를 F에서 선택한다.

U=U-Si

Si를 F에서 제거하고, Si를 C에 추가한다.

}

return C

 

1 loop 시간복잡도

•Line 2의 while-루프 조건 (U≠∅)을 검사는 O(1)  (U의 현재 원소 수를 위한 변수를 두고 그 값이 0인지를 검사하면 되기 때문)

•Line 3: U의 원소들을 가장 많이 포함하고 있는 집합 S를 찾으려면, 현재 남아있는 Si들 각각을 U와 비교하여야 한다.

-> 따라서 Si들의 수가 최대 n이라면, 각 Si와 U의 비교는 O(n) 시간이 걸리므로, line 3은 O(n^2) 시간이 걸린다.

•Line 4: 집합 U에서 집합 Si의 원소를 제거하는 것이므로 O(n) 시간이 걸린다.

•Line 5: Si를 F에서 제거하고, Si를 C에 추가하는 것이므로 O(1) 시간이 걸린다.

 

•루프가 수행되는 횟수

•O(n)

 

•루프 1회의 시간복잡도

•O(1)+O(n^2)+O(n)+O(1) = O(n^2)

 

•SetCover 알고리즘의 시간복잡도

•O(n) x O(n^2) = O(n^3)이다.