[자료구조와 알고리즘 | 파이썬] Greedy Algorithms(그리디 알고리즘)

1. Greedy Algorithms

다양한 최적화 문제들 중에서 최선의 선택을 결정하기 위한 방법으로 다이나믹 프로그래밍(동적계획법)을 사용하는 것은 다소 지나친 행동일 수 있습니다.

 

그렇기 때문에 더 단순하고 효율적인 알고리즘을 택해야 하는데, 그러한 관점에서 그리디 알고리즘(Greedy Algorithm)은 항상 그 순간에 최선으로 보이는 선택을 하는 알고리즘으로, 이는 내가 한 선택이 globally optimal solution(결과적으로 최선의 선택)을 이끌기 희망하는 locally optimal choice(당장의 최선의 선택)을 만들어 내는 알고리즘입니다. 

 

그리디 알고리즘에 대해 요약을 한 내용은 다음과 같습니다.

• 현재 상황에서 가장 좋아보이는 선택을 한다.
• local optimum(극댓값)
  • (수학적 관점에서 의미) 전체 그래프가 어떻게 생겼는지는 모르지만 현재 지점을 기점으로 오른쪽에서 올라가고 왼쪽에서는 내려간다.
  • 그렇다면 현 상황에서는 오른쪽으로 가는 것이 최선(positive)의 선택이고 가다가 기울기가 0인 지점이 극댓값, local optimum이라고 한다.
  • 이 local optimum(극댓값)이 global optimum(최댓값)이 되기를 바라고 하는 것이 그리디 알고리즘이다.
• global optimum(최댓값)
  • 전체 그래프 상에서 정해진 구간 내의 최댓값을 global optimum이라고 한다.

 

greedy algorithm을 적용할 수 있는 상황은 local optimum을 찾았을 때 그것이 global optimum이 될 수 있는 경우입니다. (예를 들어, 위로 볼록한 이차 함수의 그래프 y = - x²)

 

그리디 알고리즘이 항상 최선의 결과를 가져다 주는 것은 아니지만 많은 문제에서 그리디 알고리즘으로 최선의 솔루션을 낼 수 있습니다.

 

이제 그리디 알고리즘이 어떤 알고리즘인지 알아보기 위해 가장 먼저 단순하지만 사소하지 않은 문제인 activity-selection problem(활동 선택 문제)에 대해 살펴보도록 하겠습니다.

 

해당 문제는 그리디 알고리즘으로 최적의 솔루션을 효율적이게 계산하는 문제입니다.

 

문제를 살펴보기 전에 그리디 알고리즘에서 다시 한번 상기해야 할 점은 아래 두 가지 입니다.

• 항상 optimal solution을 제공하지는 않는다.
• 하지만 많은 경우에 써 먹을 수 있다.

 

앞서 다이나믹 프로그래밍으로만 풀릴 수 있던 문제를 살펴볼까요?

1-1. 다이나믹 프로그래밍으로만 풀리는 문제

Review: rod-cutting(나무 자르기)

아래는 rod-cutting 문제입니다.

주어진 n인치짜리 길이의 나무 막대와 pi(i=1,2,...n) 가격의 테이블들로 최대 수익 r_n을 결정해야 합니다. 이 때,  수익은 나무 막대를 자르고 토막들을 팔아서도 얻어질 수 있습니다.

 

 

<Greedy approach>

• 길이 당 최고 가격의 순서로 조각들을 취합니다. 
  • 위 정보를 통해 얻을 수 있는 정보는 길이당 얻을 수 있는 최고 가격이 정해져 있다는 점입니다.

 

• 4인치 짜리의 rod가 있는 경우, 이를 2인치 두 개로 나누었을 때 가장 높은 가격을 얻을 수 있는데, greedy 방식으로 생각해 보면 현재 가진 정보를 이용해서 최적의 결과를 내도록 하는 것이기 때문에 3인치와 1인치를 합쳤을 때가 최적의 결과가 됩니다.
  • 하지만 이것은 global optimum이 아니라 local optimum이 되어버립니다.
• 8인치 짜리를 봤을 때는 6인치를 사용했을 때 가장 최적의 선택이 되는데 실제로 봤을 때도 6+2로 나누는 것이 제일 가격이 높으므로 이 상황에는 global optimum이 됩니다.
  • 하지만 local optimum이 나올 수 있다는 경우가 존재하기 때문에 결국 이 문제는 greedy algorithm 을 사용하지 못하는 case의 문제가 됩니다.

그렇지만 이 문제를 dynamic programming으로 풀면 그 속도가 느리더라도 무조건 찾을 수 밖에 없겠죠.

 

Review: 정수삼각형

Greedy approach로 풀면 한 노드에서 바라볼 수 있는 노드 중에서 값이 가장 큰, max(left child, right child)의 노드로 가야합니다. 

• 내가 현재 7에 있고 3이나 8로 갈 수 있다.
• 뒤에 어떻게 될지는 모르지만 현재의 최선의 선택은 8로 가는 것이다.

 

이러한 greedy algorithm을 통한 path는 다음과 같이 될 것입니다.

• 7 8 1 7 5

 

이런 경우에는 합이 28입니다. 하지만 실제 global optimum을 구해보면 값이 30이기 때문에 이 문제 역시 greedy algorithm을 적용하지 못하는 문제가 되겠습니다.

 

따라서 이런 경우도 모든 case를 다 뒤져봐야 하기 때문에 dynamic programming을 사용하면 해결이 가능합니다.

 

 

 

Review: 0-1 knapsack Problem(배낭 문제)

도둑이 배낭을 메고 보석 가게에 들어왔다. 훔친 보석의 총 무게가 배낭의 용량 W를 초과하면 배낭이 찢어진다.

각 보석의 무게와 값어치는 알고 있다. 이때의 딜레마는 훔친 보석의 총무게가 W를 넘지 않으면서도, 보석의 총 값어치가 최대가 되도록 하는 보석을 배낭에 담는 것이다.

• (a)그림에서 무게당 가격을 보면 다 다르다.
• greedy algorithm을 적용하면 다음과 같다.

<Greedy approach>

• 단위 무게당 가격이 높으면 집어 넣는다(현 상황에서 최적의 선택)

 

왼쪽 그림에서 item1부터 item3까지 쭉 보면서 dynamic programming을 적용하면 (b)그림의 첫 번째 경우가 되기 때문에 global optimum을 반드시 찾을 수 있는데,

 

greedy algorithm을 적용하면 (b)그림의 나머지 경우(2,3번째 경우)가 되기 때문에 local optimum이 구해지는 쪽으로 결과가 흘러갑니다. 결과적으로 이 문제 또한 그리디로는 풀 수 없는 문제가 됩니다.

 

Fractional knapsack problem (분수 배낭 문제)

그렇다면 이 문제는 어떨까요? 

 

fractional knapsack problem에서 기본적인 설정은 앞의 일반 배낭 문제와 같습니다. 하지만, 도둑이 각 아이템을 가져갈지 말지에 대한 단순히 이분법적인 선택만을 하는 것이 아니라, 아이템을 쪼개서도 가져갈 수 있다는 점이 추가됩니다.

결론을 말하면, fractional knapsack problem에서 그리디 알고리즘은 optimal solution(global solution)을 얻을 수 있습니다.

 

fractional knapsack problem의 경우는 item을 쪼갤 수 있기 때문에 무조건 단위무게당 가격이 높은 애들을 집어 넣는 식으로 진행 한다는 점이 그리디 알고리즘이기 때문에 이 경우에는 global optimum을 찾을 수 있게 되고 또한 DP와 비교했을 때, 더 빠른 속도로 해결할 수 있게됩니다.

 

 

1-2. 그리디 전략의 요소(Element of the greedy strategy)

그리디 알고리즘은 선택지들의 순서를 만들어냄으로써 문제에 대한 최선의 솔루션(optimal solution)을 얻어냅니다.

각각의 결정 지점에서, 이 알고리즘은 그 순간에 가장 최선인 것처럼 보이는 선택을 합니다.

 

이러한 휴리스틱적(heuristic) 전략은 항상 최적의 솔루션을 만들어내지는 못하지만 우리가 행동 선택 문제(activity-selection problem)에서 봤듯 때때로 이것이 먹힐 때는 분명히 존재합니다.

• 휴리스틱(heuristic) 또는 발견법이란 불충분한 시간이나 정보로 인하여 합리적인 판단을 할 수 없거나, 체계적이면서 합리적인 판단이 굳이 필요하지 않은 상황에서, 사람들이 빠르게 사용할 수 있도록 보다 쉽게 구성된 간편추론의 방법입니다.

 

바로 이것이 그리디 알고리즘의 존재 이유이자 가치입니다.

 

그렇다면 그리디 알고리즘이 주어진 최적화 문제를 풀어 낼 것인지 아닌지 어떻게 말할 수 있을까요?

 

항상 정답을 맞추는 방법은 없지만 ①greedy-choice property(그리디 선택 속성) 와 ②optimal substructure(최적의 하위구조) 이 두 가지가 핵심 요소를 생각하면 됩니다.

 

만약 우리가 어떤 문제에서 이러한 속성이 있다는 것을 증명할 수만 있다면, 그리디 알고리즘을 수행할 수 있을 것입니다.

 

 

① Greedy-choice property

첫번째 핵심 구성요소는 greedy-choice property입니다. (단어 그대로를 받아들이는 것이 좋을 것 같아 굳이 번역하지 않겠습니다.)

 

우리는 locally optimal(그 상황에서의 최선의 선택)을 선택함으로써 globally optimal solution으로 정답에 근접할 수 있습니다. 다시 말해, 우리가 어느 선택을 할 지 고민하는 중일 때, 하위 문제의 결과를 고려하지 않고 가장 최근 문제에서 가장 최선으로 보이는 선택을 내리는 것입니다. 

 

즉, 이전의 선택이 이후의 선택에 영향을 주지 않는 경우입니다.

 

② Optimal substructure

전체 문제에 대한 optimal solution이 하위 문제들에 대한 optimal solution을 포함하는 경우, 전체 문제는 optimal substructure를 갖게 됩니다. 이는 그리디 알고리즘뿐만 아니라 동적 프로그래밍(DP)의 적용 가능성을 평가할 수도 있는 핵심 요소입니다.

 

 

정리하면, 위 두 조건이 만족되는 경우에만 greedy algorithm을 적용할 수 있는 것입니다.

 

1-3.  An activity-selection problem(행동 선택 문제)

그렇다면 이제 대표적인 그리디 문제인 activity-selection 문제에 대해 살펴봅시다.

 

회의실을 사용하려고 하는데, n번의 회의 시간이 등록되어 있습니다. 이 때, 그러한 회의 시간의 집합 S = {a1, a2, ... , an}를 가정해 보겠습니다. 그런데 회의는 한 번에 회의 딱 한 번만을 진행할 수 있습니다.(연속 진행 불가능)

 

각각의 회의 ai는 시작 시간 si를 갖고 종료 시간 fi를 갖습니다.( 0 <= si <= fi < ∞ )

 

선택된 회의에 대해 ai는 반열린 구간 [si, fi)동안 이루어집니다. 현재 회의 ai와 다음 회의 aj는 [si, fi) 와 [sj, fj)에서 구간이 겹치지만 않는다면 회의가 마치자마자 동시에 시작하는 것은 가능하다고 합니다. (fi와 sj가 같은 경우 두 회의 붙여서 진행 가능)

 

정리하면 다음과 같을 것입니다.

• n개의 회의 시간이 존재.
• i번째 회의는 각각 시작시간과 종료 시간이 존재.
• 회의실은 하나를 사용하기 때문에 배치를 잘해서 가능한 많은 회의를 할 수 있도록 해야하고, 최대 회의 횟수가 이 경우의 global optimum 값이 된다.

 

activity-selection 문제에서 우리는 최대 크기의 상호베타적으로 양립가능(mutally compatible)한 활동의 부분집합을 골라내기를 원합니다.

(여기서 상호배타적으로 양립가능이란, 위에서 설명했듯 서로 겹치지 않고 진행할 수 있는 회의와 같은 관계를 말합니다.)

 

우리는 그 회의들의 종료 시간의 순서가 단조롭게 증가하도록 정렬되었다고 가정합니다.

2번 회의는 3시에 시작해서 5시에 끝나는데 우리가 실제로 정해진 시간 내에 회의를 할 때에는 사실상 5시보다 조금 전에 끝나기 때문에 구간의 범위를 아래와 같이 왼쪽은 닫힌 구간, 오른쪽은 열린 구간으로 설정되었습니다.

• [s_i, f_i)

 

그렇기 때문에 2번 회의가 끝난 다음에 4번 회의를 배치하는 것이 가능한 것이고, 이러한 선택이 잘 되기 위해선 그 기저에 끝나는 시간을 기준으로 회의가 정렬되어 있다는 점이 존재해야만 합니다. 

 

그렇다면 이제 회의 순서를 결정해 보겠습니다

 

• 제일 일찍 끝나는 회의인 1번 회의를 집어 넣는다.
• 그러면 2번, 3번은 겹치기 때문에 집어 넣을 수 없다.
• 그러면 1번 회의가 끝나고 나서 시작하는 회의 중에서 가장 빨리 시작할 수 있는 회의를 골라야 한다.
  • 4번 가능
• 4번을 선택하여 계속 진행해 보면, 4번은 7시에 끝나기 때문에 7시 이후에 시작하는 회의 중에서 가장 빨리 시작하는 회의인 8번 회의가 가능하고, 또한 8번 회의가 끝나는 11시 이후에 시작하는 회의 중에서 가장 빨리 시작하는 회의는 11이다.

따라서 가장 많은 회의를 하려면 1, 4, 8, 11 번 순서대로 회의를 진행하면 되겠습니다.

 

 

물론 이 문제도 모든 경우를 다 뒤져서 최댓값을 찾는 dynamic programming으로도 풀 수 있지만 greedy algorithm으로도 풀 수 있기 때문에 속도 측면에서는 그리디로 푸는 것이 훨씬 이득일 것입니다.

• greedy: 현재 available한 resource에 대해서 회의 시간이 빨리 끝나는 애부터 집어 넣으면 최대한 많이 넣을 수 있을 것이다. (회의 시간이 적은 회의 부터)
  • 이것을 greedy의 직감이라고 합니다.

 

 

1-4. 그리디 선택을 하기 (Making the greedy choice)

activity-selection 문제에서 그리디 선택은 무엇을 의미할까요? 그리디의 직감은 우리가 가능한 많은 활동에 사용할 수 있도록 회의실을 남길 수 있는 활동을 선택해야 한다고 제시합니다.

 

우리가 선택한 활동 중에서 그 중 하나가 가장 먼저 완료되어야 합니다. 따라서 직감은 집합 S에서 가능한 많은 활동에 자원을 사용할 수 있게 할 것이기 때문에 가장 빨리 다가오는 종료 시간을 선택해야 함을 제시합니다.

 

게다가, 우리는 이미 activity-selection 문제가 최적의 하위구조를 나타낸다는 걸 이미 확인했었습니다.

 

위처럼 집합 S를 활동 ak가 끝난 후 시작되는 활동의 집합이라고 합시다.

 

만약 우리가 활동 a1의 그리디 선택을 했다면 S1은 해결해야 할 유일한 하위 문제로 남아있게됩니다.

 

• S0: 0번 activity가 끝난 후에 시작되는 모든 회의의 집합(전체 집합)
  • S0 = a1 + S1
  • -> S0 중에서 가장 빨리 시작하는 1번 회의 선택
• S1: 1번 회의가 끝난 후에 시작되는 모든 회의에 대한 집합

 

1-5. Activity-selector

아직 하나의 중요한 질문이 남아있습니다:

 

우리의 직감이 올바른 것일까요?

 

첫 번째 활동을 선택하는 그리디 선택이 항상 최적의 솔루션의 일부에 해당할까요? 아래 Theorem 16.1은 그 말이 맞다는 것을 보여줍니다.

 

 

Theorem 16.1

Consider any non-empty subproblem S_k, and let a_m be an activity in S_k with the earliest finish time. Then am is included in some maximum-size subset of mutually compatible activities of S_k.

Thus, we see that although we might be able to solve the activity-selection problem with dynamic programming, we don't need to.

Greedy algorithms typically have his top-down design: make a choice and then solve a subproblem, rather than the bottom-up technique of solving subproblems before making a choice.

 

번역의 오해가 생길 수 있어 원문을 그대로 가져와 봤습니다.

 

해당 정리의 의미는 다음과 같습니다.

• non-empty인 하위 문제 Sk를 고려하고, am이 가장 빠른 종료 시간을 갖는 Sk 안의 활동이 되도록 합니다. am은 Sk의 상호 배타적으로 양립 가능한 활동들로 이루어진 최대 크기의 부분집합에 포함됩니다.
• 따라서 동적 프로그래밍(DP)으로 활동 선택 문제를 해결할 수 있지만, 그럴 필요는 없다는 것을 알 수 있습니다.
• 그리디 알고리즘은 전형적으로 이런 하향식 설계 방식(Top-down)을 가지고 있습니다.

• 하위 문제에 대한 선택을 하기 전에 하위 문제를 해결하는 상향식 기술(Bottom-up)과 다르게, 하위 문제를 선택한 후에 해결하는 방식인 것입니다.

 

 

그러니 greedy를 써도 될 지 말지가 고민 된다면 그냥 dynamic programming으로라도 해야 합니다.

(그러나 간혹가다 DP로 풀면 시간 초과가 걸리도록 설정된 문제도 있으니 제대로 이해하는 것이 중요할 것입니다.)

 

 

---

위에서 Theorem을 봤는데 왜 다른 용어가 아니라 Theorem을 썼는지 궁금하여 다른 Lemma와 Corollary가 용어적으로 무엇이 다른지 정리해 보았습니다.

Theorem: 정리 공리

Lemma: 보조 정리

Corollary: 따름 정리

• Lemma에 의해서 어떠한 성질이 있음을 유추함. -> 그래서 증명이 없음 (theorem에서 결론이 났기 때문)

---

 

 

1-6. An iterative implementation (반복문 구현)

def selector(s: list, f: list): # 1
    selected_act = 1        # currently selected activity
    ans = [selected_act]

    for act in range(2, len(s)): # 5
        if s[act] >= f[selected_act]:
            selected_act = act
            ans.append(selected_act)

    return ans # 10


# s[0] and f[0] are dummis
_s = [0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12] # 14
_f = [0, 4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16]

print(selector(_s, _f))

• def selector(s: list, f: list)
  • 이 함수를 호출을 할 때 두 개의 parameter를 전달해야 하는데 두 값이 지정된 형식대로 받아야 한다는 것을 의미.
• 1번 act는 무조건 선택
  • ans = [1]
  • (ans는 answer의 약자입니다.)
• for문을 통해 2번 act부터 11번 act까지 돌면서
  • 시작시간과 종료시간을 잘 맞물리게 하여(si >= fk 인 경우 -> 그 act를 answer list에 집어 넣음)
• 실행 결과

[1, 4, 8, 11]

 

 

2. 관련된 문제

1931번: 회의실 배정

def selector(a_list):
    selected_act = 0
    result = [selected_act]

    for act in range(1, len(acts)):
        if a_list[act][0] >= a_list[selected_act][1]:
            selected_act = act
            result.append(selected_act)

    return len(result)


sys.stdin = open('bj1931_in.txt', 'r')
input = sys.stdin.readline

n = int(input())
acts = []
for _ in range(n):
    a, b = map(int, sys.stdin.readline().split())
    acts.append((a,b))

print(acts)
print(selector(acts))

위 코드를 제출하면 틀렸다고 나옵니다.

 

[함정]

예제 입력이 주어지는데 입력 데이터가 끝나는 시간으로 sorting이 되어있다는 조건이 문제에 붙지 않았기 때문에 저대로 돌리면 틀리게 되는 것입니다.

 

그러면?

sort() 와 lambda를 이용해서 끝나는 시간을 기준으로 sorting을 먼저 진행한 후에! 앞의 greedy 코드와 같이 돌리면 됩니다.

 

 

[또 하나의 함정]

앞선 activity selection 구조를 잘 살펴보면, i번째의 회의 경우에 시작시간과 끝나는 시간의 크기가 명시되어 있습니다.

하지만 이 문제에서는 그런게 없기 때문에 시작하자마자 끝나는 경우가 있을 수도 있는 것입니다.

 

sort()를 할 때 먼저 끝나는 시간을 기준으로 sorting을 하고 끝나는 시간이 같은 경우에는 시작 시간을 기준으로 다시 sorting해야 합니다. 이런 경우 lambda 함수로 굉장히 쉽게 구현할 수 있습니다.

• sort(acts, lambda x: (x[1], x[0])

 

그래서 백준의 예제 입력 2의 경우 답이 [1,2,3] -> 3 입니다.

 

[정답 코드]

import sys


def selector(a_list):
    selected_act = 0
    result = [selected_act]

    for act in range(1, len(acts)):
        if a_list[act][0] >= a_list[selected_act][1]:
            selected_act = act
            result.append(selected_act)

    return len(result)


sys.stdin = open('bj1931_in.txt', 'r')
input = sys.stdin.readline

n = int(input())
acts = []

for _ in range(n):
    a, b = map(int, input().split())
    acts.append((a, b))

acts.sort(key=lambda x: (x[1], x[0]))
print(acts)
print(selector(acts))

---

 

5585번: 거스름돈

문제 조건

 

 

• 손님이 380원을 샀고 1000을 냈으면 거스름 돈을 620원을 주어야 하는데 이 때 동전의 갯수를 최소한으로 주는 경우 몇 개의 동전을 줄 수 있는가? 를 찾아내는 문제
• dynamic programming으로 모든 경우를 다 뒤져서 가장 작은 경우를 찾을 수 있겠지만 greedy로 하면 더 빠르게 찾을 수 있다.
• 쓸 수 있는 동전 중에서 큰 단위의 동전을 최우선으로 줄 수 있는 만큼 주면 된다.
  • 500원으로 줄 수 있는만큼 다 주고
  • 100원으로 줄 수 있는 만큼 다 주고
  • 10원짜리로 다 채우면
  • 그 때의 동전을 count 한 것이 답.

cost = 1000 - int(input())

coin = [500, 100, 50, 10, 5, 1]

count = 0
for i in coin:
    count += cost // i
    cost %= i

print(count)

4