[개념] Greedy Algorithm(탐욕적인 알고리즘)

탐욕적 알고리즘(Greedy Algorithm)의 개념과 다양한 응용 사례를 설명합니다. 매 순간 최적의 선택을 통해 해답에 도달하는 방식의 한계점, 최소 신장 트리(MST)를 구하는 프림과 크루스칼 알고리즘, 다익스트라 최단 경로 알고리즘, 분할 가능한 배낭 문제, 허프만 코드 등 다양한 그리디 알고리즘의 원리와 구현 방법을 예제와 함께 상세히 다루고 있습니다.

DP 방법 말고도 다양한 기법들이 존재한다.
그 중에서 탐욕적인(Greedy) 기법을 소개하겠다.

탐욕적인 알고리즘(Greedy alogrithm)

매 순간의 선택을 최적의 선택을 함으로써 최종적인 해답에 도달하는 형식

최적의 해를 얻지 못하는 경우

그리디로 최적의 해를 얻지 못하는 경우들이 존재한다.
그 순간의 선택이 최적의 선택이 아니여야 최종적인 해답에 도달하는 경우도 있기 때문

• 카드, 보드 게임 등은 적용 불가
  • 예로 거스름돈 문제에서 16원의 경우??(액면가 1원, 5원, 10원, 12원)
    • 12원 1개, 1원 4개 => 동전개수 5개(그리디 방법)
    • 10원 1개, 5원 1개, 1원 1개 => 동전개수 3개(최적의 해)
  • 또 다른 예로 연쇄행렬곱셈 그리디 2가지 방법 + DP 방법
    • 1번 : 차원 중 p 값이 가장 큰 두 행렬부터 계산
    • 결과 : , 곱셈 수 :996
    • 2번 : n*m 값이 가장 작은 두 행렬부터 계산
    • 결과 : , 곱셈 수 : 990
    • DP 방법 : 곱셈 수 904
  • 또 다른 예로 격자에서 수 선택 이것은 당연히 DP를 써야 최적이 된다.

MST(최소비용 신장트리)

MST(Minimum Spanning Tree)는 최소의 가중치로 만든 신장트리이다.
이를 구하는 알고리즘은 그리디 방식인 Prim, Kruskal이 있다.

• 신장트리(Spanning Tree) : Connected Acyclic Graph (Acyclic : 사이클X)

• 완전그래프(Complete Graph) : 모든 정점이 연결 (K1,K2,K3…)

• MST 특징 : 같은 비용인데 다른 모양은 여러 개 나올 수도 있음
• 응용 : 도로건설, 통신, 배관(파이프) 등에 적용
• 노드 수 : N, 에지 수 : N-1

Prim

시작정점 아무거나 선택해서 시작하며 동일 비용의 노드들은 아무거나 택하고,
젤 최소 비용인 노드들을 우선 선택해 나가는 방식의 알고리즘이다.

• 사이클 신경 안써도 됨
• 인접 행렬, nearest 배열, distance 배열 사용(최소비용 노드 선택 후 이 배열들 계속 갱신 해줘야함)

• 시작노드 0로 시작 한 상태의 모습

• 다음 가중치가 젤 작은 노드1을 선택하고 배열도 갱신한 모습

• 다음 같은 가중치인 2번과 7번 노드중에서 아무거나(2번) 선택한 후 배열 갱신한 모습
  • 여기까지 이해 되었다면, 전체 노드 선택할때까지 반복해서 최종 답을 구할 수 있다.

• 참고용 Prim 알고리즘의 코드 구조
  • 구현한 Prim 코드

Kruskal

에지들의 가중치로 비내림차순 정렬을 먼저 한 후 작은 것들을 순서대로 선택해 나가는 알고리즘이다.

• 사이클이 생성되는 경우가 있기 때문에 사이클 구분이 매우 중요
  • 서로소 집합 추상 데이터 타입(disjoint set abstract data type) 형태를 사용 - Union Find??
    • 이를 직접 만들어 사용하거나 이미 지원해주는 언어는 바로 사용하면 됨
    • 예로 C++은 지원하며, C는 지원하지 않음

• 먼저 에지들 정렬하고 젤 작은 에지부터 선택해 나가는 모습

• 위 상황처럼 파란색 6 (6,8)은 사이클을 생성시키므로 pass한다.
  • 이처럼 사이클을 구분하게끔 알고리즘을 만들어야함.

• Kruskal 알고리즘의 코드 구조
  • initial(n)은 전체를 자기자신을 루트로 가지게 9개의 트리가 독립적으로 만들어진 상태
  • find(i)는 자신이 속한 트리의 루트가 누구인지 찾음
  • equal(p,q)는 동일한지 확인
  • merge(p,q)는 p집합, q집합을 합병(q의 root가 p의 root를 가리키게 바꾸는것)

• 기본 동작 구조 : find(root) -> equal(p,q) -> merge(q->p) 흐름

• 사이클을 감지하는 순간의 모습(핵심)
  • 구현한 Kruskal 코드

두 알고리즘 복잡도 관련

• sparse graph : Prim( ), Kruskal( )

• dense graph : Prim( ), Kruskal( )

• Heap : Prim+sparse – , Prim+dense -

• Fibonacci heap : Prim+sparse – , Prim+dense -

Prim도 자료구조가 다르면 이렇게 복잡도가 까지 가능

Dijkstra(다익스트라)

SSSP(Single Source Shortest Path Dijkstra Algorithm) : 단일출발점 최단경로 문제(다익스트라)

• 각 정점에 최단경로 길이를 레이블에 기억 후 젤 작은 레이블 값부터 색칠해가는 형태

• Label correctioin 알고리즘이라고도 부름
• distance(=label), from(=nearest) 배열 사용
  • 이 두 배열은 앞서 위에서 봤듯이 Prim 알고리즘에서 사용한 배열과 매우 유사하다
  • 심지어 알고리즘 방식도 조금 유사하지만 차이점이 있다.
  • 최단경로 길이를 기억해나가는 것이고, 이 길이는 만약 다른 노드 경유를 한 경우거나 하면 그 경유한 길이도 꼭 다 합산한 총 길이를 기록해나가야한다.
  • 자세한건 아래 그림을보고 이해하자

• Prim알고리즘과 유사하게 배열들 초기값이 형성되는 모습이다.

• 시작을 1노드로 하고 배열들 갱신한 모습이다.

• 현재 다음으로 작은 가중치인 5번노드를 택한 경우이고, 6번 노드 길이가 22가 된것을 보자.
  • Prim과 차이점이 여기선 v1->v5->v6 길이로 22를 기록한것이고
  • Prim의 경우 그저 v5->v6으로 가는 가중치 15를 기록했을것이다.
  • 이처럼 출발지점인 v1노드 기준으로 각각 노드들의 길이들을 판단하게 된다는것이 중요하다.

Dijkstra vs Floyd

• Dijkstra( ) - 단일 출발점, 임의의 도착점(Greedy)
• Floyd( ) - 임의의(복수가능) 출발점, 임의의 도착점(DP)

물론 Dijkstra도 임의의 출발점을 위해 n번 사용하면 으로 가능

다익스트라와 플로이드 구현 코드

Heap(힙)

힙은 “완전 이진 트리” 이며 “위 아래 관계” 를 가진다. 힙의 응용으로는 “우선순위 큐”가 있다.

여러 예시 중에 힙 정렬을 참고하자.

• 힙 정렬

Fractional Knapsack(Greedy)

Fractional Knapsack란 배낭을 빈틈없이 채우는 알고리즘이다.
여러 품목(item)들 중에서 정해진 무게(W)만큼 채워서 최대한 많은 이득을 취할 수 있는 문제를 다룬다.

무게 큰거부터 차례로 넣어가고, 남은건 쪼개서 담으면 되기때문에 탐욕(그리디)방법으로 풀 수 있다.
하지만 물건을 쪼갤수 없는 상태면?? 0-1 Knapsack의 문제가 되는것이다.
Fractional Knapsack과 0-1 Knapsack을 구별할 것

• Greedy는 Fractional Knapsack 가능, 0-1 Knapsack 불가
• 따라서 0-1 Knapsack은 DP로 구현

• 그리디 방식으로 풀면 되고, 값어치를 구해서 젤큰 품목(item)부터 차례로 넣으면 된다.
• 220만원이 최적이며 간단하므로 더이상 설명은 생략하겠다.

Huffman Code(그리디 방법으로 가능)

메시지를 직접 전송하는 대신 이진 code를 전송할건데 빈도수 높은 메시지는 이진 code를 짧게해서 총 전송 비용을 최소로 하는것이 목표인 알고리즘

• 빈도 수 정렬 후 이진트리 생성 및 이진 code로 읽는 방식으로 진행

• f는 문자들 빈도수를 적어둔 것
• 그리고 이진트리를 구해줌
• 다음으로 이 이진트리를 차례대로 읽어줘서 이진 코드로 변경
• 이후 총 전송 비용을 계산(아래그림)