이 글은 반성적 그리디(Repentant Greedy) 알고리즘에 대한 학습 내용을 정리한 것입니다. 필자가 Div.3 대회에서 이 유형의 문제를 만난 후 깊이 공부하게 되었습니다.

반성적 그리디란?

일반적인 그리디 알고리즘은 선택을 되돌리지 않고 매 순간 최선이라고 판단되는 선택을 합니다. 하지만 이러한 방식은 지역 최적해(Local Optimum)에 빠져 전역 최적해(Global Optimum)를 놓칠 위험이 있습니다.

반성적 그리디는 이런 한계를 극복하기 위해, 현재 선택이 전역적으로 최적이 아님을 발견했을 때 이전 선택을 취소하고 더 나은 선택으로 대체하는 메커니즘입니다.

반성적 그리디는 크게 두 가지 방식으로 구현됩니다:

1. 반성 힙(Repentance Heap): 힙 자료구조를 사용하여 현재까지 선택한 값들을 관리하고, 더 좋은 선택이 나타나면 힙에서 가장 나쁜 선택을 제거하고 새로운 선택을 추가합니다.
2. 반성 오토마톤(Repentance Automaton): 차분값(Difference)을 활용하여 반성 과정을 자동화합니다. 선택의 여파를 새로운 노드나 값으로 변환하여 재사용합니다.

반성 힙 예제

시간 제약 모델: 작업 스케줄링

각 작업이 마감 기한 D_i와 이익 P_i를 가질 때, 최대 이익을 구하는 문제입니다. 모든 작업은 1단위 시간이 소요됩니다.

해결 방법:

• 작업을 마감 기한 기준으로 오름차순 정렬합니다.
• 현재 시각을 now라고 할 때, 마감 기한이 현재 시각보다 크면 작업을 수행하고 이익을 최소 힙에 추가합니다.
• 마감 기한이 현재 시각 이하인 경우, 최소 힙의 최상단(가장 작은 이익)과 현재 작업의 이익을 비교합니다. 현재 작업의 이익이 더 크다면 힙에서 가장 작은 이익을 제거하고 현재 작업을 추가하여 전체 이익을 증가시킵니다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<pair<int,int>> tasks(n);
    for (int i = 0; i < n; i++) {
        cin >> tasks[i].first >> tasks[i].second;
    }
    
    sort(tasks.begin(), tasks.end());
    priority_queue<int, vector<int>, greater<int>> pq;
    ll total = 0;
    int time = 0;
    
    for (auto &[deadline, profit] : tasks) {
        if (deadline > time) {
            pq.push(profit);
            total += profit;
            time++;
        } else if (!pq.empty() && profit > pq.top()) {
            total += profit - pq.top();
            pq.pop();
            pq.push(profit);
        }
    }
    
    cout << total << '\n';
    return 0;
}

가치 일정 모델: 건물 복구

모든 작업의 가치가 동일할 때, 최대한 많은 작업을 완료하는 문제입니다. 각 작업은 소요 시간 T1과 마감 기한 T2를 가집니다.

해결 방법:

• 마감 기한 기준으로 정렬한 후, 각 작업을 순회하며 현재 시간에 작업을 추가할 수 있으면 수행합니다.
• 추가할 수 없는 경우, 현재까지 선택한 작업 중 가장 오래 걸리는 작업(최대 힙의 최상단)과 현재 작업의 소요 시간을 비교합니다. 현재 작업이 더 짧다면 대체하여 더 많은 여유 시간을 확보합니다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<pair<int,int>> tasks(n);
    for (int i = 0; i < n; i++) {
        cin >> tasks[i].first >> tasks[i].second;
    }
    
    sort(tasks.begin(), tasks.end(), 
         [](auto &a, auto &b) { return a.second < b.second; });
    
    priority_queue<int> pq;
    ll time = 0;
    int count = 0;
    
    for (auto &[duration, deadline] : tasks) {
        if (time + duration <= deadline) {
            time += duration;
            pq.push(duration);
            count++;
        } else if (!pq.empty() && duration < pq.top()) {
            time -= pq.top() - duration;
            pq.pop();
            pq.push(duration);
        }
    }
    
    cout << count << '\n';
    return 0;
}

반성 오토마톤 예제

주식 매매: CF865D

주식 가격 배열이 주어질 때, 최대 이익을 얻는 문제입니다. 하루에 한 번 매수 또는 매도만 가능합니다.

핵심 아이디어: 중간 가격 C_i를 이용하여 C_sell - C_buy = (C_sell - C_i) + (C_i - C_buy) 형태로 차분값을 누적합니다. 이는 반성 오토마톤의 전형적인 예시입니다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> prices(n);
    for (int i = 0; i < n; i++) cin >> prices[i];
    
    priority_queue<int, vector<int>, greater<int>> pq;
    ll profit = 0;
    
    for (int price : prices) {
        pq.push(price);
        if (!pq.empty() && pq.top() < price) {
            profit += price - pq.top();
            pq.pop();
            pq.push(price);
        }
    }
    
    cout << profit << '\n';
    return 0;
}

이중 연결 리스트 반성: 나무 심기

일렬로 늘어선 n개의 위치에 m그루의 나무를 심되, 인접한 위치에는 심을 수 없을 때 최대 가치를 구하는 문제입니다.

해결 방법:

• 먼저 m > n/2이면 불가능하므로 에러를 출력합니다.
• 이중 연결 리스트와 최대 힙을 사용합니다. 각 노드는 자신의 가치와 양옆 노드를 가리킵니다.
• 가장 큰 가치를 선택하면 양옆 노드는 선택 불가능하므로 제거합니다.
• 반성을 위해 새 노드를 생성합니다: 새 가치 = 왼쪽 가치 + 오른쪽 가치 - 현재 가치. 이 노드를 선택하면 원래 선택을 취소하고 양옆을 선택한 효과가 납니다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 200005;

struct Node {
    ll val;
    int idx;
    bool operator<(const Node& other) const {
        return val < other.val;
    }
};

ll value[MAX];
bool removed[MAX];
int left_list[MAX], right_list[MAX];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    if (m > n / 2) {
        cout << "Error!" << '\n';
        return 0;
    }
    
    for (int i = 1; i <= n; i++) cin >> value[i];
    
    priority_queue<Node> pq;
    for (int i = 1; i <= n; i++) {
        pq.push({value[i], i});
    }
    
    for (int i = 1; i <= n; i++) {
        left_list[i] = i - 1;
        right_list[i] = i + 1;
    }
    left_list[1] = right_list[n] = 0;
    
    ll answer = 0;
    while (m--) {
        Node current = pq.top(); pq.pop();
        
        while (removed[current.idx]) {
            current = pq.top(); pq.pop();
        }
        
        if (current.val < 0) break;
        
        answer += current.val;
        int l = left_list[current.idx];
        int r = right_list[current.idx];
        
        if (l) removed[l] = true;
        if (r) removed[r] = true;
        
        if (l && r) {
            value[current.idx] = value[l] + value[r] - current.val;
            right_list[left_list[l]] = current.idx;
            left_list[current.idx] = left_list[l];
            left_list[right_list[r]] = current.idx;
            right_list[current.idx] = right_list[r];
            pq.push({value[current.idx], current.idx});
        } else if (l) {
            right_list[left_list[l]] = 0;
        } else {
            left_list[right_list[r]] = 0;
        }
    }
    
    cout << answer << '\n';
    return 0;
}