알고리즘

[알고리즘] Greedy algorithm

래모 2022. 7. 1. 20:12

Greedy 알고리즘

: 목적을 달성하기 위해 현재의 정보만으로 각 단계에서 가장 좋은 선택을 반복해서 답을 구성하는 방법

 

  • 탐욕 선택 속성
  • 최적 부분 구조

위의 특성을 가지는 문제들을 해결하는데 강점이 있음

즉, 한 번의 선택이 다음 선택에는 전혀 무관한 값이어야 하며 매 수간의 최적해가 문제에 대한 최적해여야 한다는 의미

 

예시 1️⃣ : 최소 개수의 동전

Q. 1원, 10원, 50원, 100원 동전이 있을 때,
최소 개수의 동전으로 371원을 거슬러 주고 싶다. 어떤 동전들을 몇 개씩 사용해야 할까?

이 질문의 답으로 우리는

100 * 3 + 50 * 1 + 10 * 2 + 1 * 1 = 371

위와 같은 계산으로 3 + 1 + 2 + 1 = 7 개의 동전들로 최소 개수가 이루어짐을 알았을 것이다.

 

이는 어떤 방식으로 생각된거냐면!

  1. 371원을 거슬러 줄 수 있는 최대 금액의 동전으로 최대한 많이 거슬러야 최소가 될 거 같다. 즉, 100 * 3 = 300원을 먼저 거슬러 주자
  2. 남은 71원을 100원 다음으로 큰 50원으로 거슬러준다. 50 * 1 = 50원을 거슬러 주자
  3. 남은 21원에 대해선 10원 * 2개 + 1원 * 2개 로 거슬러 준다 

만약 1원, 5원, 7원이 동전 단위인 경우 10원을 거슬러 주고 싶다면?

앞의 방식대로 해결하면 7 * 1 + 1 * 3 으로 총 4개의 동전으로 거슬러 줄 수 있다.

하지만 5 * 2 = 10 이므로 2 개의 동전으로 거슬러 주는 것이 최소이다.

이 문제에 대해선 앞의 방식이 최고의 방법이 아니다.

왜냐하면 1원이 10원이 될 순 있지만 5원이 7원이 될 수는 없기 때문이다.

즉, 작은 단위의 배수가 큰 단위와 일치하지 않아서 이런 방식에 대해선 greedy 알고리즘을 사용하는 것이 옳지는 않다.

 

예시 2️⃣ : 강의실 배정

Q. 강의실이 하나 뿐인데, 이 강의실에서 쓰고 싶은 강의가 많다.
강의가 서로 겹치지 않게 최대한 많은 강의를 배정하라.
입력 : n 개의 강의가 주어진다. 강의 i 번은 S[i]에 시작해서 F[i]에 끝난다.
출력: 강의실의 개수

 

greedy 기준을 생각해보자 ( 각 그림은 반례를 표현한 것 )

수업시간이 가장 짧은 강의부터 선택
가장 적게 겹치는 강의부터 선택  
가장 빨리 시작하는 강의부터 선택
가장 빨리 끝나는 강의부터 선택  요게 정답임ㅎ.ㅎ

 

정답인 기준에 의해 수업을 배정해보면 다음과 같은 과정을 따른다!

  1. F의 값을 기준으로 S와 F 모두 오름차순으로 정렬( O(nlogn)의 시간복잡도를 가짐 )
  2. L 이라는 배열을 만듬, 이 배열에는 뽑힌 강의의 번호(i)가 들어갈 거임. 이미 F를 오름차순으로 정렬했으므로 S[0]으로 시작하고 F[0]으로 끝나는 강의가 가장 빨리 끝나는 강의 즉 0번 강의는 무조건 들어감
  3. for문을 돌면서 강의가 겹치지 않도록 L 배열에 넣고 가장 최근에 뽑힌 강의의 번호를 k 에 저장

Pseudo 코드

L = [0]
k = 0
for i in range(n):
    if S[i] >= F[k] :
        L.append(i)
        k = i

 

관련 문제

https://www.acmicpc.net/problem/11000

 

11000번: 강의실 배정

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

www.acmicpc.net

 

예시 3️⃣: Huffman Coding 문제

허프만 코드란?

데이터를 효율적으로 압축하는데 사용하는 방법으로 허므만 알고리즘에 의해 생성된 최적 이진코드를 말한다.

 

압축하고자 하는 문자열에서 자주 등장하는 문자는 짧은 비트로 표현하고 거의 등장하니 않는 문자는 긴 비트로 표현한다(가변 길이 코드)

즉, 문자의 빈도수를 이용함!

 

예를들어

문자 빈도수 고정길이코드 가변길이코드
a 43 000 0
b 13 001 101
c 12 010 100
d 16 011 111
e 9 100 1101
f 7 101 1100

여기서 고정길이 코드는 6개의 문자를 구분하기 위해 3bit를 필요로 한다.

(2^2 < 6 < 2^3)

 

총 빈도수가 100이므로 고정길이 코드로 암호화 한 경우엔 100 * 3 = 300bit가 필요하고 

가변길이 코드로 암호화 한 경우엔 1* 43 + 3 * (13 + 12 + 16) + 4 * (9 + 7) = 230bit가 필요하다

가변길이코드가 훨씬 적은 메모리를 사용함을 알 수 있음

 

모호성이 없는 코드 체계는 항상 prefix-free 코드여야 한다.

prefix-free 코드란?
한 코드가 다른 코드의 prefix에나타나지 않는 코드 체계를 말한다
예를 들어 'a' = 0  / 'b' = 11  / 'c' = 011 라고 하자
그럼 011이란 이진코드가 주어질 때 이것이 'ab'인지 'c'인지 알 수 없다
그래서 주어진 문자열을위한 최적 이진트리를 구축하기 위해서는 prefix code로 구현되어야 한다.

greedy 기준

  1. 빈도수가 낮은 문자를 먼저 짝을 지어 트리를 점진적으로 구성
  2. 먼저 짝을 지어 구성하므로 빈도수가 낮은 문자가 루트노드에서 멀어지게 되는 효과가 있다

위의 표를 예시로 이진트리를 구성하면 다음과 같다.

이는 heap의 자료구조를 통해 코드를 작성할 수 있다

 

Pseudo code

H = []
for x in range(n):
    heappush(H, (f[x], 'x'))

while len(H) > 1:
    a = heappop(H) # 가장 작은 빈도수 item
    b = heappop(H) # 두 번째로 작은 빈도수 item
    heappush(H, a.f + b.f, '(a.x b.x')

tree_string = heappop(H)[1]