프로그래밍 대회에서 배우는

알고리즘
문제 해결 전략

19.7절 다시 쓰기

입력의 크기

이 문제를 풀 때 까다로운 것은 입력의 크기입니다. 일단 처리는 그렇다 치고 5천만 개의 32비트 정수를 저장하는 데만도 190MB의 메모리가 필요하기 때문에, 문제의 메모리 제한인 64MB에는 모든 정수를 저장할 수조차 없습니다. 모든 키들이 [1, 10000] 구간의 자연수라는 점을 이용해 16비트 정수로 표현하더라도 64MB를 넘어가게 됩니다. 따라서 우리는 모든 키를 메모리에 생성해 올려놓지 않고 이 중 일부만을 사용하는 온라인 알고리즘(online algorithm)을 작성해야 합니다. 온라인 알고리즘이란 전체 입력이 한꺼번에 주어지지 않아도 계산을 시작할 수 있는 알고리즘을 말합니다. 알고리즘 수행 중 새 입력을 받아 계산을 계속하기 때문에, 입력 전체가 메모리에 올라와 있지 않아도 계산을 시작할 수 있습니다. 반대로 오프라인 알고리즘이란 입력 전체를 이미 가지고 있다고 가정하고 동작하는 알고리즘을 말하지요. 예를 들어 삽입 정렬은 새 원소를 이전의 정렬된 목록에 끼워넣는 방식으로 동작하므로, 처음에 모든 원소가 없더라도 정렬을 시작할 수 있습니다. 반면 선택 정렬은 남아 있는 모든 원소 중에서 최소의 원소를 찾아서 맨 앞에 옮기는 방식으로 동작하므로, 모든 원소를 알고 있어야만 동작을 시작할 수 있습니다. 따라서 삽입 정렬은 온라인 알고리즘, 선택 정렬은 오프라인 알고리즘이라고 할 수 있지요.

오프라인 알고리즘 만들기

우선 메모리에 모든 숫자를 저장할 수 없다는 제약 조건을 무시하고 알고리즘을 설계한 뒤 이것을 점진적으로 최적화해 봅시다. 이 문제를 푸는 가장 단순한 방법은 모든 부분 구간을 검사하면서 합이 $K$인 것을 찾는 것입니다. 

// 코드 19.3 외계 신호 분석 문제를 해결하는 가장 단순한 알고리즘
int simple(const vector<int>& signals, int k) {
  int ret = 0;
  for(int head = 0; head < signals.size(); ++head) {
    int sum = 0;
    for(int tail = head; tail < signals.size(); ++tail) {
      // sum은 [head, tail] 구간의 합이다
      sum += signals[tail];  
      if(sum == k) ret++;
      if(sum >= k) break;
    }   
  }
  return ret;
}

이런 단순한 알고리즘의 구현을 코드 19.3에서 볼 수 있습니다. 이 코드는 구간의 왼쪽 끝 $head$와 오른쪽 끝 $tail$에 대해 2중 for문을 수행하면서 모든 구간의 합을 검사합니다. 이 알고리즘의 시간 복잡도는 얼마일까요? $head$에 대한 for문은 물론 $N$번 수행되며, $tail$에 대한 for문은 최대 $min(N, K)$번 수행될 수 있습니다. 대부분의 경우 $K \le N$이라고 가정하면 전체 시간 복잡도는 $O(NK)$가 됩니다. 이대로는 절대로 시간 안에 문제를 해결할 수 없겠죠. 하지만 이 알고리즘이 하는 일을 정확히 이해하고 최적화하면 이것을 선형 시간 알고리즘으로 바꿀 수 있습니다.

그를 위해 이 알고리즘이 수행하는 간단한 최적화에 주목합시다. $head$에 대한 for문의 내부는 $head$에서 시작하는 구간들을 길이 순서대로 검사하는데, 구간합이 이미 $K$ 이상이 되었을 경우 더 이상 구간의 길이를 늘리지 않고 종료합니다. 모든 신호는 양수이므로 구간의 길이를 더 이상 늘려봐야 답을 찾을 수 없으니, 이 최적화의 정당성은 아주 자명하지요. 이 때 주목할 것은 종료하기 전에 마지막으로 검사한 구간입니다. 이 구간은 $head$에 시작하는 구간 중 합이 $K$ 이상인 가장 짧은 구간입니다. 중요한 것은 $head$가 정해져 있을 때 이 구간 외의 구간은 답이 될 수 없다는 것입니다. 이 구간보다 짧으면 합이 반드시 $K$ 미만일테고, 이보다 길면 $K$를 반드시 초과하기 때문입니다. 이 구간들만이 답이 될 가능성이 있다는 의미에서, 이 구간들을 후보 구간들이라고 부릅시다.

그림 19.4: 각 위치에서 시작하는 후보 구간들

문제에 주어진 예제 입력에서 각 위치마다 시작하는 후보 구간들을 그림 19.4에서 볼 수 있습니다. 후보 구간의 합이 실제 $K$와 같은 경우 짙은 색으로 표시했습니다. 이 그림을 볼 때 눈치챌 수 있는 점은 $head$가 늘어났을 때 $tail$이 줄어드는 일이 없다는 것입니다. 우연일까요? $head$가 증가했는데 $tail$이 감소했다면 이 후보 구간은 이전 후보 구간의 부분 구간이 됩니다. 이 구간의 합이 이미 $K$ 이상이라면 이전 후보 구간은 더 일찍 끝났어야 하므로, 이런 경우는 있을 수 없습니다.

여기에서 이 문제를 풀기 위한 핵심적인 통찰이 등장합니다. $head$가 증가했을 때 $tail$이 전보다 줄어드는 일이 없다면, 후보 구간의 $tail$을 찾을 때 $head$에서부터 시작하는 것이 아니라 마지막에 찾았던 $tail$에서부터 시작해도 되지 않을까요? 

// 코드 19.4 외계 신호 분석 문제를 해결하는 최적화된 알고리즘
int optimized(const vector<int>& signals, int k) {
  int ret = 0, tail = 0, rangeSum = signals[0];
  for(int head = 0; head < signals.size(); ++head) {
    // rangeSum이 k 이상인 최초의 구간을 만날 때까지 tail을 옮긴다.
    while(rangeSum < k && tail + 1 < signals.size()) 
      rangeSum += signals[++tail];

    if(rangeSum == k) ret++;

    // signals[head]는 이제 구간에서 빠진다.
    rangeSum -= signals[head];
  }
  return ret;
}

코드 19.4는 이 아이디어를 이용한 최적화를 보여줍니다. $tail$과 구간합을 나타내는 $rangeSum$ 변수가 이제 $head$에 대한 for문 밖에 선언되어 있지요. 또한 $head$가 증가하기 직전에 마지막에 계산했던 후보 구간의 합에서 $signals[head]$를 빼 주는 점을 눈여겨 봅시다. 이렇게 하면 $head$가 증가한 후에 구간합을 새로 계산할 필요가 없지요.

이 알고리즘의 시간 복잡도는 얼마일까요? 여전히 중첩 반복문이 있기 때문에 시간 복잡도가 다르지 않다고 생각할 수도 있지만, while문의 내부가 실행될 때마다 $tail$이 증가한다는 점에 주목합시다. $tail$은 0에서 시작해 $N$까지 증가하므로, while문의 내부는 최대 $N$번 수행됩니다. 분할 상환 분석을 이용하면 코드 19.4의 시간 복잡도는 $O(N)$이라는 것을 쉽게 알 수 있지요.

온라인 알고리즘 만들기

시간 제한 안에 충분히 돌아가는 알고리즘을 만들었으니, 이것을 온라인 알고리즘으로 바꿔 봅시다. 모든 데이터를 미리 생성하는 대신, 구간에 새 숫자를 포함시켜야 할 때마다 해당 숫자를 하나씩 생성합니다. 그리고 필요 없게 된 숫자는 메모리에 저장해 둘 필요 없이 지워버리면 됩니다. $head$가 증가하고 나면 우리가 지나쳐온 숫자들은 더 이상 고려할 필요가 없으므로, 저장할 필요가 없지요. 따라서 우리가 메모리에 저장해야 하는 것은 우리가 유지하는 후보 구간에 포함된 숫자들 뿐이라는 것을 알 수 있습니다.

// 코드 19.5 외계 신호 분석 문제를 해결하는 온라인 알고리즘
int countRanges(int k, int n) {
  RNG rng; // 신호값을 생성하는 난수 생성기
  queue<int> range; // 현재 구간에 들어 있는 숫자들을 저장하는 큐                                                                               
  int ret = 0, rangeSum = 0;
  for(int i = 0; i < n; i++) {
    // 구간에 숫자를 추가한다.
    int newSignal = rng.next();
    rangeSum += newSignal;
    range.push(newSignal);

    // 구간의 합이 k를 초과하는 동안 구간에서 숫자를 뺀다
    while(rangeSum > k) {
      rangeSum -= range.front();
      range.pop();
    }

    if(rangeSum == k) ret++;
  }
  return ret;
}

이 숫자들을 어떻게 저장하면 좋을까요? 숫자들은 항상 구간의 맨 뒤에서 추가되고, 맨 앞에서 제외되므로 큐를 사용하면 간단하겠지요. 현재 구간에 들어 있는 숫자들을 큐에 저장하는 알고리즘의 구현을 코드 19.5에서 볼 수 있습니다. 단 구현을 좀더 간단히 하기 위해, 원소를 넣는 순서와 빼는 순서를 바꿨습니다. 구간에 원소를 먼저 넣은 뒤, 구간 합이 $K$ 이하가 될 때까지 원소를 빼지요. 결과적으로 우리는 각 $tail$에 대해 합이 $K$ 이하가 되는 가장 긴 구간을 찾는 셈입니다.

이 문제에서 모든 신호는 양수이므로 큐의 크기는 항상 $K$ 이하이고, 결과적으로 적은 양의 메모리만을 쓰고 이 문제를 해결할 수 있습니다.

신호의 생성

이 문제에서 신호를 생성하는 방법은 사실 가장 간단한 형태의 난수 생성기 중 하나인 선형 합동 난수 생성기(linear congruential random number generator)입니다. 입력의 크기가 너무 큰 경우 이렇게 입력을 직접 생성해야 하는 경우도 종종 볼 수 있으니 참고합시다. 이런 코드를 작성할 때 유의할 점은 계산 과정에서 오버플로우가 발생하는 경우를 잘 처리하는 것입니다. $countRanges()$에서 사용한 $RNG$ 클래스의 구현을 코드 19.6에서 볼 수 있습니다. 내부적으로 unsigned 자료형을 사용함으로써 $2^{32}$로 나눈 나머지를 취하는 연산을 할 필요가 없다는 것을 눈여겨봅시다.

// 코드 19.6 외계 신호 분석 문제에서 사용하는 선형 합동 난수 생성기의 구현
struct RNG {
  unsigned seed;
  RNG() : seed(1983) {}
  unsigned next() {
    unsigned ret = seed;
    seed = ((seed * 214013u) + 2531011u);
    return ret % 10000 + 1;
  }
};