[Baekjoon] 1700 – 멀티탭 스케줄링

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

📖 문제 이해하기

이 문제는 한정된 개수의 멀티탭 구멍으로 여러 전기용품을 사용해야 하는 상황에서, 플러그를 빼는 횟수를 최소화하는 문제입니다.

구체적으로 살펴보면, N개의 구멍이 있는 멀티탭과 K번의 전기용품 사용 순서가 주어집니다. 어떤 전기용품을 사용하려는데 이미 멀티탭이 가득 차 있다면, 기존에 꽂혀 있는 플러그 중 하나를 뽑아야 합니다. 이때 어떤 플러그를 뽑을지 전략적으로 선택하여 총 제거 횟수를 최소화하는 것이 목표입니다.

예시를 보면 3구 멀티탭에서 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기, 키보드, 헤어드라이기 순서로 사용할 때, 디지털 카메라 충전기를 사용하기 전에 핸드폰 충전기를 제거하는 것이 최적입니다. 왜냐하면 핸드폰 충전기는 더 이상 사용되지 않는 반면, 키보드와 헤어드라이기는 나중에 다시 사용되기 때문입니다.

🧠 첫 번째 시도와 한계점

이 문제를 처음 접하면 가장 직관적으로 떠올릴 수 있는 방법은 “가장 오래 전에 사용된 것을 제거하는” LRU(Least Recently Used) 전략입니다. 즉, 현재 멀티탭에 꽂혀 있는 플러그들 중에서 가장 최근에 사용되지 않은 것을 뽑는 방식입니다. 이는 운영체제의 캐시 교체 알고리즘에서도 널리 사용되는 합리적인 접근법처럼 보입니다.

하지만 이 접근법은 심각한 한계를 가지고 있습니다. 과거의 사용 패턴만 고려할 뿐, 미래에 언제 다시 사용될지는 전혀 고려하지 않기 때문입니다. 위의 예시에서 LRU 방식을 적용하면, 디지털 카메라 충전기를 사용할 때 키보드를 제거할 수도 있습니다. 키보드가 가장 먼저 사용되었기 때문입니다. 하지만 키보드는 곧바로 다시 사용되므로, 이는 명백히 비효율적인 선택입니다.

또 다른 단순한 접근법으로는 “사용 빈도가 가장 낮은 것을 제거”하는 전략을 생각해볼 수 있습니다. 하지만 이 역시 문제가 있습니다. 전체 사용 패턴에서는 빈도가 낮더라도, 현재 시점에서 곧바로 다시 사용될 수 있기 때문입니다. 게다가 사용 빈도를 계산하려면 전체 입력을 미리 분석해야 하므로, 실시간으로 결정을 내려야 하는 상황에서는 적합하지 않습니다.

💡 그리디 알고리즘의 핵심 통찰

이 문제를 해결하는 핵심은 그리디 알고리즘의 관점에서 접근하는 것입니다. 그리디 알고리즘은 각 단계에서 그 순간에 가장 최적으로 보이는 선택을 하는 알고리즘입니다. 하지만 여기서 중요한 것은 “그 순간에 가장 최적”이라는 기준을 어떻게 정의하느냐입니다.

멀티탭이 가득 찬 상황에서 새로운 전기용품을 사용해야 할 때, 우리는 현재 꽂혀 있는 플러그들 중 하나를 제거해야 합니다. 이때 그리디한 선택 기준은 “가장 나중에 사용될 것(또는 아예 사용되지 않을 것)을 제거한다”입니다. 이는 직관적으로도 매우 합리적입니다. 가장 늦게 사용될 것을 제거함으로써 가능한 한 오랫동안 해당 슬롯을 다른 용도로 활용할 수 있기 때문입니다.

📘 그리디 알고리즘에 대하여
그리디 알고리즘은 매 순간 지역적으로 최적인 선택을 하여 전역적 최적해를 구하는 알고리즘입니다. 모든 문제에서 그리디 접근법이 최적해를 보장하지는 않지만, 특정 조건을 만족하는 문제들에서는 매우 효율적이고 직관적인 해법을 제공합니다. 이 문제의 경우, “교환 논증(exchange argument)”을 통해 그리디 선택이 최적임을 증명할 수 있습니다.

이 그리디 전략이 최적인 이유를 좀 더 자세히 살펴보겠습니다. 만약 어떤 시점에서 우리가 “더 빨리 사용될 것”을 제거하고 “더 늦게 사용될 것”을 남겨둔다고 가정해봅시다. 그러면 제거한 것을 다시 사용할 때 다시 꽂아야 하는데, 이때 “더 늦게 사용될 것”을 제거하게 됩니다. 결과적으로 같은 제거 작업을 하면서도 더 일찍 수행하게 되므로, 원래 전략과 비교해 손해를 보지 않습니다. 이런 식으로 모든 경우에 대해 그리디 선택이 다른 선택보다 나쁘지 않음을 보일 수 있습니다.

그리디 알고리즘이 이 문제에서 성공하는 또 다른 이유는 미래 정보의 활용 때문입니다. 일반적으로 그리디 알고리즘은 현재 상황만 고려하여 결정을 내리지만, 이 문제에서는 전체 사용 순서가 미리 주어져 있습니다. 따라서 각 시점에서 “미래에 언제 사용될지”라는 정보를 활용하여 그리디한 결정을 내릴 수 있습니다.

🔍 알고리즘 동작 과정 살펴보기

구체적인 예시를 통해 그리디 알고리즘이 어떻게 작동하는지 살펴보겠습니다. 3구 멀티탭에서 전기용품 사용 순서가 [1, 2, 3, 4, 1, 2]로 주어진다고 가정해보겠습니다.

먼저 전처리 단계에서 각 전기용품이 언제 사용될지 미리 계산합니다. 이는 그리디 결정을 위한 핵심 정보입니다:

  • 전기용품 1: 0번째, 4번째에 사용 (다음: 0→4→∞)
  • 전기용품 2: 1번째, 5번째에 사용 (다음: 1→5→∞)
  • 전기용품 3: 2번째에만 사용 (다음: 2→∞)
  • 전기용품 4: 3번째에만 사용 (다음: 3→∞)

이제 단계별로 그리디 결정 과정을 살펴보겠습니다.

  • 0번째 단계 (전기용품 1 사용)
    • 멀티탭 상태: 비어있음
    • 그리디 결정: 자리가 있으므로 그냥 꽂습니다
    • 현재 멀티탭: [1], 제거 횟수: 0
  • 1번째 단계 (전기용품 2 사용)
    • 멀티탭 상태: [1]
    • 그리디 결정: 자리가 있으므로 그냥 꽂습니다
    • 현재 멀티탭: [1, 2], 제거 횟수: 0
  • 2번째 단계 (전기용품 3 사용)
    • 멀티탭 상태: [1, 2]
    • 그리디 결정: 자리가 있으므로 그냥 꽂습니다
    • 현재 멀티탭: [1, 2, 3], 제거 횟수: 0
  • 3번째 단계 (전기용품 4 사용)
    • 멀티탭 상태: [1, 2, 3] (가득 참)
    • 그리디 결정 필요: 어떤 것을 제거할까?
    • 다음 사용 시점 비교
      • 전기용품 1: 4번째에 다시 사용
      • 전기용품 2: 5번째에 다시 사용
      • 전기용품 3: 더 이상 사용되지 않음 (∞)
    • 그리디 선택: 전기용품 3이 가장 늦게(실제로는 전혀) 사용되므로 제거
    • 현재 멀티탭: [1, 2, 4], 제거 횟수: 1
  • 4번째 단계 (전기용품 1 사용)
    • 멀티탭 상태: [1, 2, 4]
    • 그리디 결정: 전기용품 1은 이미 꽂혀 있으므로 아무것도 하지 않음
    • 현재 멀티탭: [1, 2, 4], 제거 횟수: 1
  • 5번째 단계 (전기용품 2 사용)
    • 멀티탭 상태: [1, 2, 4]
    • 그리디 결정: 전기용품 2는 이미 꽂혀 있으므로 아무것도 하지 않음
    • 현재 멀티탭: [1, 2, 4], 제거 횟수: 1

최종 결과는 총 1번의 제거가 필요합니다. 3번째 단계에서의 그리디 선택이 전체 최적해를 달성했습니다.

💻 소스 코드

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, K;
    cin >> N >> K;
    
    <em>// 전기용품 사용 순서를 저장하는 배열</em>
    vector<int> A(K);
    for (int i = 0; i < K; ++i) {
        cin >> A[i];
    }
    
    <em>// 각 전기용품별로 사용될 위치들을 큐에 미리 저장</em>
    <em>// 이는 그리디 결정을 위한 핵심 정보입니다</em>
    vector<queue<int>> pos(K+1);
    for (int i = 0; i < K; ++i) {
        pos[A[i]].push(i);
    }
    
    <em>// 모든 전기용품에 대해 마지막에 무한대 값을 추가</em>
    <em>// 더 이상 사용되지 않는 경우를 처리하기 위함</em>
    <em>// 그리디 비교에서 "가장 늦게 사용됨"으로 판단되도록 함</em>
    for (int i = 1; i <= K; ++i) {
        pos[i].push(1e9);
    }
    
    int ans = 0;      <em>// 플러그를 뺀 횟수 (최소화 목표)</em>
    int tot = 0;      <em>// 현재 멀티탭에 꽂혀있는 전기용품 개수</em>
    vector<bool> included(K+1, false);  <em>// 각 전기용품이 현재 멀티탭에 꽂혀있는지 여부</em>
    
    <em>// 각 사용 단계에서 그리디 결정을 수행</em>
    for (int i = 0; i < K; ++i) {
        int curr = A[i];  <em>// 현재 사용하려는 전기용품</em>
        
        <em>// 현재 위치를 해당 전기용품의 위치 큐에서 제거</em>
        <em>// 다음 사용 시점만 남겨두어 그리디 비교에 활용</em>
        if (!pos[curr].empty()) pos[curr].pop();
        
        <em>// 그리디 결정이 필요한 상황: 멀티탭이 가득 찬 상태에서 새로운 전기용품 사용</em>
        if (tot == N && !included[curr]) {
            int target = -1;   <em>// 제거할 전기용품 번호</em>
            int maxVal = -1;   <em>// 가장 늦게 사용될 시점</em>
            
            <em>// 그리디 선택: 현재 멀티탭에 꽂혀있는 모든 전기용품 중에서</em>
            <em>// 가장 늦게 사용될 것을 찾아 제거 대상으로 선정</em>
            for (int j = 1; j <= K; ++j) {
                if (included[j] && maxVal < pos[j].front()) {
                    maxVal = pos[j].front();
                    target = j; 
                }
            }
            
            <em>// 그리디 선택에 따라 가장 늦게 사용될 전기용품을 멀티탭에서 제거</em>
            included[target] = false;
            tot--;
            ans++;  <em>// 제거 횟수 증가 (최소화하려는 목표 값)</em>
        }
        
        <em>// 현재 전기용품이 멀티탭에 꽂혀있지 않다면 추가</em>
        if (!included[curr]) tot++;
        included[curr] = true;  <em>// 현재 전기용품을 멀티탭에 꽂힌 상태로 표시</em>
    }
    
    cout << ans << "\n";
    return 0;
}

🔁 대안적 접근법: 동적 계획법의 한계

이 문제에 대한 다른 접근법으로는 동적 계획법을 고려해볼 수 있습니다. 각 시점에서 가능한 모든 멀티탭 상태를 유지하면서 최소 제거 횟수를 계산하는 방법입니다. 상태를 dp[i][mask]로 정의하여 i번째 단계에서 멀티탭 상태가 mask일 때의 최소 제거 횟수를 저장할 수 있습니다.

하지만 이 방법은 상태 공간이 지수적으로 증가하여 실용적이지 않습니다. 전기용품 종류가 K개이고 멀티탭 크기가 N일 때, 가능한 상태의 수는 C(K, N)에 비례하므로 계산 복잡도가 매우 높아집니다. 반면 그리디 알고리즘은 O(K × N)의 시간 복잡도로 효율적으로 해결할 수 있습니다.

또한 완전 탐색 방법도 있지만, 각 단계에서 제거할 수 있는 모든 선택지를 탐색해야 하므로 지수 시간이 걸립니다. 이 문제의 경우 그리디 알고리즘이 최적해를 보장하면서도 가장 효율적인 해법입니다.

📚 추가 학습: 벨레이디 알고리즘

이 문제에서 사용한 그리디 전략은 사실 컴퓨터 과학에서 **벨레이디 알고리즘(Belady’s Algorithm)**으로 알려진 이론적 최적 페이지 교체 알고리즘과 동일한 원리입니다. 1966년 라즐로 벨레이디가 제안한 이 알고리즘은 운영체제의 메모리 관리에서 페이지 폴트를 최소화하기 위해 사용됩니다.

벨레이디 알고리즘의 핵심 아이디어는 “가장 오랫동안 사용되지 않을 페이지를 교체한다”는 것으로, 우리 문제의 “가장 늦게 사용될 전기용품을 제거한다”와 정확히 일치합니다. 실제 운영체제에서는 미래를 완벽하게 예측할 수 없어 구현이 불가능하지만, 다른 페이지 교체 알고리즘의 성능을 평가하는 이론적 기준점 역할을 하며, 이 문제처럼 미래 정보가 주어진 경우에는 실제로 구현 가능한 최적 알고리즘이 됩니다.

📌 핵심 교훈과 마무리

이 문제는 그리디 알고리즘의 핵심 특성을 잘 보여주는 훌륭한 예시입니다. 단순히 “현재 상황에서 가장 좋아 보이는 것을 선택”한다는 일반적인 그리디 개념을 넘어서, 미래 정보를 활용한 그리디 선택의 힘을 보여줍니다.

여기서 중요한 통찰은 그리디 알고리즘이 항상 근시안적일 필요는 없다는 것입니다. 사용 가능한 모든 정보를 활용하여 각 순간에 최적의 결정을 내리는 것이 진정한 그리디 정신입니다. 이 문제에서는 전체 사용 패턴이라는 미래 정보를 활용하여 매 순간 최적의 제거 대상을 선택함으로써 전역 최적해를 달성했습니다.

또한 이 문제는 그리디 알고리즘의 정당성을 증명하는 방법론도 잘 보여줍니다. 교환 논증을 통해 다른 어떤 전략도 우리의 그리디 선택보다 나을 수 없음을 논리적으로 증명할 수 있습니다. 이런 엄밀한 증명이 뒷받침되어야만 그리디 알고리즘을 안심하고 사용할 수 있습니다.

Similar Posts