그리디 알고리즘

이게 참.. 그리디는 딱히 정형화를 해서 공부할 수 있는 부분이 아닌거 같은데.. 그래서 딱히 뭘 적어야 할지도 모르겠고 해서 항목 자체를 안만들고 있었다.
그러나, 차라리 풀었던 그리디 문제들을 모아놓고, 비슷한 유형끼리 모아보는 식으로 접근해본다면 그래도 도움이 되지 않을까 하는 생각이 들었다.
그래서 이제부터는 그리디 문제를 풀때마다 전부 여기에 일단 모아보기로 하겠다. 그렇게 해서 뭔가 유의미한 결과가 나올지 안나올지는 나도 모르겠다.

대표적인 유형들

Job Scheduling 관련

Interval partitioning

i번 태스크의 시작시간과 종료시간은 (s_i,f_i)로 주어진다. 한 머신에서는 동시에 한개의 태스크만 처리가능할때, 모든 태스크를 처리하기 위해 필요한 최소의 머신 개수는? 그리고 가장 많은 머신이 동시에 작동해야 시간은 언제?
가장 많은 태스크가 겹치는 시간의 태스크 수가, 필요한 최소의 머신 개수가 된다.
결국 Maximum overlapping intervals 문제를 풀면 된다.
관련 문제
- 겹치는 선분, 강의실 배정, 최소 회의실 개수, 유니의 편지 쓰기: 다 비슷한 문제이다..

Interval scheduling

Interval scheduling
i번 태스크의 시작시간과 종료시간이 (s_i,f_i)로 주어진다. 한개의 머신으로 가장 처리할수 있는 가장 많은 태스크의 갯수는? 그리고 그 태스크들의 목록은?
태스크들을 끝나는 시간 순으로 오름차순 정렬해서 하나씩 보면서 겹치지 않으면 작업을 수행하는 방법 (Earliest deadline first scheduling) 이 최적이다

태스크마다 작업 가능한 시간 범위가 주어짐

Minimizing the lateness
- 태스크마다 시작시간, 종료시간, 마감시간이 주어진다. lateness (=종료시간 - 마감시간)의 최댓값을 최소화 시키는 방법은?
- =⇒ Earliest Due Date First rule (EDD): 마감시간이 빠른것부터 처리
Maximizing the throughput
- 태스크마다 릴리즈시간, 마감시간이 주어진다. 처리시간은 모든 과제가 동일하다. 가장 많은 과제를 처리하는 방법?
- pq에 마감시각이 빠른 순으로 태스크들을 관리한다.
- 시간축으로 스위핑하면서 현재 시간부터 작업이 가능한 태스크가 있으면 pq에 추가, 그리고 pq에서 태스크를 꺼내서 처리.
- 만약 모든 과제를 처리할수 있는가? 하는 디시전 문제라면 다른 방식으로 풀수도 있다.
- 관련문제
  - 3430

Page replacement

Page replacement algorithm
운영체제에서 주로 다뤄지는 문제. 캐쉬에 새 데이터를 저장하기 위해 기존에 저장되어 있던 데이터를 지워야 할때, 어떤 것을 지우는 것이 가장 효율적일까?
만약에 미래에 어떤 데이터가 어떤 시점에서 필요하게 될지를 모두 알수 있다면, 그리디한 방법으로 처리할수 있다. 가장 먼 미래에 사용되게 될 데이터를 지우는 전략 (LFD; Longest-Forward-Distance) 이 최적이다. Belady's optimal algorithm 이라고 알려져있는 방법이다.
- 이게 최적이라는것은 그냥 직관적으로 알수 있긴 한데.. 엄밀한 증명은 https://gazelle-and-cs.tistory.com/112 을 참고.
하지만, 일반적인 상황에서는 미래에 어떤 데이터가 필요하게 될지 예측하는것이 불가능하기 때문에 이 알고리즘을 online으로 적용해서 처리할수는 없고, 실제로는 LRU니 LFU니 하는 다양한 전략들로 처리하고, 이 알고리즘은 나중에 다양한 전략들의 성능을 평가하는 기준으로 쓰인다.
관련 문제는 멀티탭 스케줄링

주유소 문제

주유소라는 소재를 갖고 등장하는 문제가 많은데, 여기서 말하는 문제 형태는
- 1차원 도로 위에 주유소들이 있다.
- 각 주유소마다 연료의 가격이 다르다
- 최소 비용으로 도로를 완주하는 방법을 구해라
여기에 다음과 같은 조건들이 붙어서 문제가 달라진다.
- 자동차의 연료통 크기에 제한이 있는가
- 주유소에서 파는 연료의 양에 제한이 있는가? 주유소마다 제한이 각각 다른가?
우선 공통적인 풀이방법을 생각해보면.. 주유소들을 순서대로 거칠때마다, 얼마만큼을 주유할지를 구해야 한다. 그러나 얼마를 주유했을때 그것이 충분할지 부족할지를 알게 되는 것은 이후 주유소들에 도착했을때이다.
주어진 조건들에 따라서는 이후 주유소들을 잘 관리하면, 현재 주유소에서 필요한 주유량을 바로 구할수 있는 경우도 있지만, 그렇기 못한 경우도 있다. 일반적으로 풀 수 있는 접근법중 하나는 DP이다. 주유량에 따라서 다 다른 상태로 관리하는 방식이다. DP[i][j]를 i번 주유소까지 갔을때 연료가 j가 남은 상태에서의 최소 비용으로 저장하는 방식이다.
그러나 이 유형의 대부분의 문제는 그리디로 더 효율적으로 풀수 있다. 기본은, '이전단계의 선택값을 이후에 수정하는 방식'을 사용하는 것이다.

연료통 크기에 제한이 없는 문제

가장 단순한 유형인, 연료통 크기에 제한이 없고, 주유소에서 파는 연료의 양에도 제한이 없는 문제를 생각해보자.
그냥 처음에는 모든 주유소를 스킵하고 (연료를 전혀 사지 않고) 지나간다. 그러다가, 현재 연료가 부족해져서 다음 주유소까지 도착하기가 불가능해지면, 아까 지나왔던 주유소에서 '사실은 아까 연료를 샀던 걸로 하자' 하고 뒤늦게 선택값을 바꿔주는 것이다.
이때는 당연히 지나왔던 주유소들 중에서 가장 저렴했던 곳에서 현재 필요한 양만큼 샀던걸로 처리하면 되니까, 이것을 처리하기 위해서는 주유소를 지날때마다 가장 저렴한 주유소만 갱신해주고 있었다면 O(1)에 해결된다. 전체 시간복잡도는 O(n)이 된다.
간단하게 말하면, '어떤 주유소를 한번 지났다면, 나중에 언제 어디서든지 그 주유소의 판매가격으로 기름을 살수 있다' 라는 조건을 문제에 추가해서 생각하는 것이다. 이래도 답은 바뀌지 않는다
관련 문제:
- 주유소: 위에서 설명한 문제
- 연료 채우기: 가격을 줄이는게 아니라, 주유소 방문 횟수를 줄이는 것이 목표이다. 판매가격이 가장 싼 주유소에서 샀던걸로 처리하는 대신, 판매하는 양이 가장 많은 주유소에서 샀던걸로 처리하면 된다.

연료통 크기에 제한이 있는 문제

연료통 크기에 제한이 있는 경우는 앞의 전략은 안통한다. '이전 주유소에서 연료를 샀던것'으로 처리할때, 그 시점에서 연료통이 얼마나 비어있었는지를 관리하기가 까다롭기 때문이다.
대신 반대 방법으로 접근할수 있다. 모든 주유소에서 연료통을 가득 채울 수 있도록 주유를 하는 것으로 처리하는 것이다. 만약 어떤 주유소에 도착했을때, 연료통에 들어있는 남은 연료중에 지금 주유소 가격보다 비싸게 구입했던 것이 있다면, 그것을 '사실 아까 연료를 안샀던 것'으로 처리하고 지금 주유소에서 그만큼을 다시 사면 된다.
이렇게 비싼 연료를 나중에 취소할수 있다면, 이동할때에는 가장 싼 연료부터 사용해야 한다. 연료통에 들어있는 연료들을 (가격, 양)들로 구분해서 저장해두고 여기에서 가장 싼 연료(이동할때)와 가장 비싼연료(취소할때) 를 찾을 수 있어야 한다.
주유소에서 파는 연료의 양에 제한이 없다면, 주유소를 들를때마다 현재 가격보다 비싸게 샀던 연료들은 다 취소하고 현재 주유소의 연료로 채우게 될것이므로, 연료통의 연료들을 모노톤하게 유지할수 있다. 덱에다가 구현하면 총 시간복잡도는 O(n)이 된다.
주유소에서 파는 연료의 양에 제한이 있다면, 현재 주유소보다 비싼 연료들을 다 취소할수는 없으므로 데이터를 모노토닉하게 유지하는 것은 힘들다. 그래서 그냥 최솟값과 최댓값을 빠르게 추출하기 위해서는 double-ended PQ나 BST를 써서 O(logn)에 처리해줘야 한다. 총 시간복잡도는 O(nlogn)이 된다
간단하게 말하면, '어떤 주유소에서 산 연료는, 나중에 언제 어디서든지 샀을때의 가격 그대로 되팔수 있다.' 라는 조건을 문제에 추가해서 생각하는 것이다. 이래도 답은 바뀌지 않는다
관련 문제
- 16399: 주유소마다 파는 양의 제한은 없다
- 16399: 주유소마다 파는 양의 제한은 없다

Exchange argument

주어진 아이템들을 하나씩 선택해서 처리할때, 그 때의 최적 선택 순서를 찾는 방법에 관한 문제를 풀 때 사용할수 있는 방법이다.
구체적인 문제 예시들로는 이런것들이 있다
- 아이템을 선택할때 조건에 맞는 아이템들만 선택할수 있다 → 모든 아이템을 선택할수 있는 방법이 존재하는가?
- 아이템을 선택할때 조건에 맞는 아이템들만 선택할수 있다 → 가장 많이 선택할수 있는 아이템의 갯수는? 그때의 방법은?
- 아이템을 선택할때마다 점수/페널티를 얻는다 → 점수/페널티의 총합의 최대/최소값은? 그때의 방법은?
이러한 문제에 대해서 어떤 그리디한 풀이가 있다면, '남은 아이템 중에서 가장 XXX 한 것을 먼저 선택한다' 가 될것이다. 전체 순서를 찾아야 하는 문제라면, XXX한 순서대로 아이템들을 모두 정렬한 것이 답이 될것이다.
원래 Exchange argument는 이러한 그리디한 풀이의 정당성(왜 이 풀이가 최적해를 찾아주는지)을 증명하는 방법중의 한가지이다.
- 어떤 그리디한 방식으로 찾은 순서가 최적임을 Exchange arguments 방식으로 증명하는 것은, 어떤 옵티멀한 솔루션이 있다고 가정했을때, 이것을 그리디한 방식으로 도출되는 답으로 변형하더라도 더 나빠지지 않는다는 것을 보이는 방식이다. 옵티멀 솔루션에서 그리디 알고리즘에서 도출된 답으로 답을 변형하는 과정은, 두개의 아이템의 순서를 스왑하는 것을 반복하는 방식으로 이루어지고, 매 스왑마다 답이 더 나빠지지 않으므로, 전체 과정을 다 거쳐도 답이 나빠지지 않고 여전히 옵티멀이라는 것을 증명하게 된다.
하지만 이제 역으로, 특정 순서대로 선택한다는 그리디한 풀이가 먼저 주어져있을때 그 정당성을 증명하는게 아니라, 기준이 뭔지는 모르겠지만 하여튼 그 기준대로 선택하면 답이 되는 그리디한 해답이 존재한다고 가정하면, 그 기준이 과연 무엇일지를 생각해보자. 어떤 기준으로 선택한다면 Exchange arguments 방식으로 정당성이 증명될수 있을지를 생각해 본다는 뜻이다.
사실 말이 복잡한데 방법은 간단하다. 그냥 두개의 아이템만 있는 경우를 생각해보고, 둘중 에서 어느쪽을 먼저 선택해야지 더 좋은 답을 얻을수 있는지를 생각해본다. 구체적으로는 1번을 먼저 처리하고 2번을 처리했을때와, 2번을 먼저 처리하고 1번을 처리했을때의 스코어를 계산해보고, 1번→2번의 스코어가 2번→1번의 스코어보다 높아지는 컨디션을 일반화해서 두 아이템을 비교하는 기준으로 사용하면 된다.
이렇게 해서 찾은 이 비교기준이 total ordering을 만족시키게 된다면, 이제 '모든 아이템을 이 기준으로 정렬해서 그 순서대로 처리한다'는 그리디 해답은 자동적으로 올바른 풀이가 된다.
좀더 자세히는 다음 링크들을 참고
- 원래의 의미 - 어떤 그리디한 풀이의 정당성을 증명하는 방법론으로의 관점
  - https://gazelle-and-cs.tistory.com/59
- 그리디한 풀이를 도출해내는 방법으로써의 관점
  - https://infossm.github.io/blog/2019/11/16/Exchange-argument/
  - https://codeforces.com/blog/entry/63533 - 유튜브 강의 링크가 걸려있고, 설명은 간략하게만 쓰여진 편. 하지만 연습문제가 많이 있다.

유형들

사실 수많은 그리디 알고리즘이 이 방식을 사용해서 도출될 수 있긴 하다. 하지만, 굳이 이 방식으로 생각해보기도 전에 이미 너무 자명하게 떠오르는 문제들도 많다.
예를 들면, 주어진 숫자들을 이어붙여서 가장 큰 수를 만드는 문제. Exchange argument를 굳이 쓰지 않고서도, 큰 숫자부터 앞자리에 붙이면 된다는 것을 당연스럽게 알 수 있다.
비교 기준으로 삼을만한것 자체가 몇가지 없다든가, 아니면 굳이 증명을 안해도 직관적으로 이 순서로 정렬하면 되겠지 하는 느낌이 온다든가 하는 문제들은 exchange argument 없이도 그냥 떠오르는 순서로 정렬해보고 딱히 반례가 안떠오르면 제출 후 proof by AC로 끝내는 경우도 많다
결국 exchange argument가 힘을 받는 문제는 비교 기준으로 삼을만한 후보도 다양하고, 그중에서 정답에 해당하는 비교 기준이 직관적으로는 떠올리기 힘든 것들이다.

기준값에 따른 유형 분류

(a_i/b_i) 를 기준으로 정렬하게 되는 문제들

소방서의 고민
- 현재의 페널티가 t인 상황에서 i번 아이템 (a_i, b_i)를 선택하면, t*a_i+b_i 만큼 페널티가 증가한다.
- f(i)=b_i/a_i 가 작은 순서대로 선택하는 것이 최적이다.
구두 수선공
- 현재의 시간이 t인 상황에서 i번 아이템 (T_i, S_i)를 선택하면, 페널티는 t*S_i만큼 증가, t는 T_i만큼 증가.
- f(i)=T_i/S_i 가 작은 순서대로 선택하는 것이 최적이다.
13448
- 구두 수선공과 조건은 마찬가지. 현재의 시간이 t인 상황에서 i번 아이템 (P_i, R_i)를 선택하면, 페널티는 t*P_i만큼 증가, t는 R_i만큼 증가하므로, f(i)=R_i/P_i 가 작은 순서대로 선택하는 것이 최적이다.
- 다만 모두 선택할수 있는것이 아니고, 시간내에 허용되는 만큼만 선택할수 있는 문제이다. 어떠어떠한 아이템을 선택하기로 했을 경우에 그 아이템들을 어떤 순서로 선택해야 할지는 위에서 구해서 알고 있으므로, '어떠어떠한 아이템을 선택할지' 만 냅색 DP를 통해서 풀어내면 된다.

(a_i - b_i) 에 따라서 두 그룹으로 나눠서 정렬하는 문제

점수가 깎인 뒤 회복

i번째 아이템은 (a_i, b_i) 로 나타내진다. i번째 아이템을 선택하면 총점이 a_i만큼 감소되고, 다시 b_i만큼 증가한다.
총점이 가장 작아졌을 때의 값을 최대화시키는 문제.
우선 정답만 세줄요약하면
- 아이템을 두 종류로 나눈다.
  - 증가아이템: 처리후에 최종적으로 총점이 증가하는 아이템, 즉 a_i ⇐ b_i 인 아이템.
  - 감소아이템: 처리후에 최종적으로 총점이 감소하는 아이템, 즉 a_i > b_i 인 아이템.
- 증가아이템을 모두 먼저 선택하고, 그 뒤에 감소아이템들을 선택해야 한다
- 증가아이템은 a_i가 작은것부터 선택하면 된다
- 감소아이템은 b_i가 큰것부터 선택하는 것이다
좀더 설명하면
- 증가아이템의 순서는 직관적이다. 사용가능한 것부터 선택하면 된다. a_i가 작은것부터 선택하면 그렇게 된다
- 감소아이템을 고르는 기준은 직관적이지는 않다. 직관적으로 생각나는 아이디어들이 있지만 다 오답이다.
  - 처음 선택에 필요한 총점(=a_i)가 작은것부터 사용하면?
    - (실패) 반례: 총점 10, 남은 아이템 (9,7), (5,1)일때, (9,7)을 먼저 선택해야만 한다
  - 선택했을때 총점 감소가 작은것부터 사용하면? 즉, (a_i-b_i)가 작은것부터 사용하면?
    - (실패) 반례: 총점 10, 남은 아이템 (5,3), (9,5)일때, (9,5)을 먼저 선택해야만 한다
- exchange argument로 접근하자. 현재 총점이 x이고, (a1,b1)과 (a2,b2)가 남아있다고 생각하자
  - 1번,2번 순으로 처리가능하려면 x - a1 + b1 >= a2 이어야 한다
    - 바꿔쓰면 b1 >= a1+a2-x
  - 2번,1번 순으로 처리가능하려면 x - a2 + b2 >= a1 이어야 한다
    - 바꿔쓰면 b2 >= a1+a2-x
  - b1>b2이라고 가정하면,
    - 1번2번 순서로 불가능하면 2번1번 순서로도 불가능하다
    - 1번2번 순서로는 가능해도, 2번1번 순서로는 불가능할수도 있다.
    - 그러므로 1번2번 순서로 시도해야 한다.
관련 문제
- 28068: 총점이 최소값을 0이상으로 유지하면서 모든 아이템을 선택할수 있는가
- 12776: 총점의 최소값을 최대화시키면서 모든 아이템을 선택하기

작업시간이 a단계 작업시간과 b단계 작업시간의 합으로 구성되는 문제

각 작업은 a단계 b단계 순으로 이루어져야 한다. 각 단계에서는 동시에 한개의 작업만 처리할수 있다. 모든 작업을 끝내는데 걸리는 시간을 최소화시키는 작업 순서를 찾는 문제.
- a단계를 시작한 작업순서대로 b단계도 시작해야 하는 조건이 들어가는 경우도 있고 아닌 경우도 있는데, 조건 유무에 관계없이 답은 동일하다
i작업, j작업 순으로 진행할때 총 걸리는 시간은 a_i + max(b_i, a_j) + b_j 이다.
하지만 exchange argument 방식으로, 이 식을 비교기준으로 해서 정렬하려하면 strict weak order을 만족하지 않아서 실패한다. Mountain Climbing 참고.
점수가 깎인 뒤 회복 과 동일한 전략으로 해결된다. 세줄요약하면
- 이것도 a_i ⇐ b_i 인 작업과, a_i > b_i인 작업의 두 종류로 나눈다
- a_i ⇐ b_i 인 작업들을 먼저 모두 처리하고, 그 다음 a_i > b_i인 작업들을 처리한다
- a_i ⇐ b_i 인 작업들은 a_i가 작은 순으로 처리한다
- a_i > b_i인 작업들은 b_i가 큰 순으로 처리한다
a단계 작업 큐는 어차피 쉬지않고 돌아가므로, b단계 작업이 멈춰있는 시간을 최소화 해야한다는 관점에서 접근하면 위 방법의 타당성을 알수있다.
관련 문제
- Mountain Climbing, Cakes, The Milk Queue : 모두 똑같은 문제.

선택 순서에 제약이 있는 경우 (트리 형태)

위에서의 기본 유형은, 아이템을 선택하는 순서에는 딱히 제약이 없었다. 그래서 exchange argument로 최적 아이템을 찾으면, 그걸 가장 먼저 선택하면 되었다.
A 아이템은 반드시 B 아이템 보다 나중에 선택해야 한다는 형식의 제약이 주어질 수도 있다. 제너럴하게는 DAG 형태로 표현되겠지만, 그런 문제는 본적이 아직 없고 (어떻게 풀어야할지도 모르고), 트리 형태로 제약이 주어지는 경우는 굉장히 독특한 풀이법이 있다.
- 이 방법으로 풀어야 하는 문제들이 가끔 나오는데, 이 방법 자체에 대한 자세한 튜토리얼은 본적이 없다.. 1763 에 대해서 아이디어 스케치 정도의 요약된 풀이를 써놓은 블로그가 몇개 정도 있었는데, 여기서부터 전체 풀이를 이해하는게 꽤 들었다.
그래서 여기에서 주어지는 문제 유형은 이런것이다. 아이템들이 트리 노드마다 배치되어있다. 자식 노드의 아이템은, 그 부모 노드의 아이템을 이미 선택한 이후에만 선택 가능하다. (첫번째로 선택해야 하는 아이템은 무조건 루트 노드의 아이템이 된다)
관련 문제
- 1763: {총비용}/{크기} 가 큰 순으로선택해야 한다는 것을 exchange argument로 알아낼 수 있다. n이 작아서, 우선순위큐를 사용하지 않고 O(n^2)에 풀어도 돌아간다
- 18595: 점수가 깎인 뒤 회복유형 을 트리 위에 얹은 형태.
- 9539: 점수가 깎인 뒤 회복유형 을 트리 위에 얹은 형태.

목차

그리디 알고리즘

대표적인 유형들

Job Scheduling 관련

Interval partitioning

Interval scheduling

태스크마다 작업 가능한 시간 범위가 주어짐

Page replacement

주유소 문제

연료통 크기에 제한이 없는 문제

연료통 크기에 제한이 있는 문제

Exchange argument

유형들

기준값에 따른 유형 분류

(a_i/b_i) 를 기준으로 정렬하게 되는 문제들

(a_i - b_i) 에 따라서 두 그룹으로 나눠서 정렬하는 문제

점수가 깎인 뒤 회복

작업시간이 a단계 작업시간과 b단계 작업시간의 합으로 구성되는 문제

선택 순서에 제약이 있는 경우 (트리 형태)