Move Fast

이분 탐색(Binary Search) 문제들 중 최적화를 위해 결정 문제로 바꿔서 푸는 매개변수 탐색 문제가 있다. 가끔 나오는 문제다보니 풀 때마다 구간의 정의(lo와 hi) 및 결정 함수를 구현하는데 삽질을 많이해서 정리할 필요성을 느낌.

이 글을 읽기 전 알아야 할 정보

• 이분 탐색 구현 방법
• 매개 변수 탐색의 개념

구글링하면 자료가 많이 나오니 개념에 대한 설명은 여기로 대체하겠다. (굉장히 설명을 잘 해주셨다.)

매개 변수 탐색에서 마주한 문제는 매개변수의 구간을 정의하는 부분과 결정 함수를 구현하는 부분이다.

먼저, 매개변수의 구간을 정의한다는 것은 이분 탐색에서 lo 와 hi 의 의미를 아는 것에서 출발할 필요가 있다.

int binary_search(int lo, int hi, int value) {
    while (lo + 1 < hi) {
        int mid = (lo + hi) >> 1;
        if (A[mid] <= value) lo = mid;
        else hi = mid;
    }
    return A[lo];
}

탐색할 배열 A가 정렬되어 있으며 value 는 항상 A 에 있다고 가정한다.

따라서 lo < hi 에서 이진 탐색을 수행하므로 while 문에 들어가기 전에 A[lo] < A[hi] 가 성립한다.

while 문에 들어갈 때 lo + 1 < hi 라는 조건때문에 반복문 불변식으로 A[lo] < A[hi] 가 항상 성립한다.

• A[mid] <= value 여서 lo = mid 가 되는 경우, mid < hi 이므로 A[lo] < A[hi] 가 성립한다.
• A[mid] > value 여서 hi = mid 가 되는 경우, lo < mid 이므로 A[lo] < A[hi] 가 성립한다.
• lo 와 hi 가 1 씩 차이나면 mid <= hi 또는 lo <= mid 가 되어 불변식이 깨질 수 있는데, 조건은 항상 hi - lo > 1 이기 때문에 그럴 일은 없다.

while 문에서 빠져나왔을 때는 lo + 1 == hi 일 텐데 어쨌든 lo < hi 이므로 A[lo] < A[hi] 가 성립한다.

(이 조건이 깨지는 경우는 lo < hi 와 같이 잘못된 조건식으로 lo > hi 가 된 상태로 반복문을 빠져나올 때이다. lo + 1 < hi 를 기억하자.)

여기서 A[mid] <= value 일 때 lo = mid 이므로 반환하는 A[lo] 는 항상 value 이다. 만약 조건을 A[mid] < value 로 했다면 A[hi] 를 반환해야 할 것이다. 즉, 값을 찾는 조건에 따라 lo 와 hi 중 하나가 정답이 된다.

| 1 | 2 | 3 | 4 | 5 | 6 |
          ↑   ↑
         lo   hi

이분 탐색에서 while (lo + 1 < hi) 조건으로 탐색할 경우 최종 lo 와 hi 는 위와 같은 모습이다.

다시 매개 변수 탐색으로 돌아와서, 일반적으로 문제에서 최종적으로 구해야 하는 최솟값/최댓값이 찾아야 하는 매개변수이다. 이를 param 이라고 하겠다. 그리고 결정 함수를 다음과 같이 정의하겠다.

fn(param) := param 이 어떤 조건을 만족하면 true를 반환하고 아니면 false를 반환

여기서 param 의 범위는 이분 탐색에서 배열 A가 오름차순이라고 했던 것과 유사하게 연속이어야 하는데, param 값이 연속인 것 말고도 fn(param) 의 결과도 연속이어야 한다.

즉, param 가 구간 [lo, hi] 사이의 값일 때, fn(param) 는 [false, false, ..., false, true, ..., true, true] 또는 [true, true, ..., true, false, ..., false, false] 여야 한다. 중간에 false -> true 또는 true -> false 로 바뀌는 부분이 있는데 이 부분은 1번만 존재해야 하며, 만약 여러 개 있다면 이분 탐색이 아니라 삼분 탐색 등 다른 방법으로 문제를 해결해야 할 것이다. 이분 탐색은 실제로 1차 함수 f 를 가정하고 f(x) < 0 에서 f(x) > 0 으로 바뀌는 f(x) = 0 을 만족하는 x 값을 찾는 방법이다. 0은 그냥 예시이다. 정해진 값 y 가 있다면 0이 아니라 y가 될 것이다.

fn(param) 의 결과 중간에 false -> true 또는 true -> false 로 바뀌는 부분이 있는데, 여기서 true 를 반환하는 param 이 찾고자 하는 최솟값/최댓값이다.

어떤 조건을 만족하는 param 의 최솟값(=answer)을 찾는 문제를 생각해보자.

fn(param) 은 연속이라고 했기 때문에 param >= answer 에 대해 fn(param) 은 항상 true 일 것이다. param 은 오름차순이니 fn(param) 의 결과는 param 에 따라 [false, false, ..., false, true, ..., true, true] 이고, 다음이 성립한다.

• fn(answer - 1) = false
• fn(answer) = true
• fn(answer + 1) = true

여기서 param 의 구간을 [lo, hi] 라고 정의할 때 while(lo + 1 < hi) 조건으로 반복문을 돌리면 최종적으로 아래와 같이 lo 와 hi 를 얻게 된다.

| f | ... | f | t | ... | t |
            ↑   ↑
           lo   hi

param 의 구간이 [1, 6] 이라면 위와 아래는 의미가 동일하다. 단지 위의 배열은 fn(param) 의 결과이고 아래의 배열은 param 의 배열이라는 점이 차이이다.

| 1 | 2 | 3 | 4 | 5 | 6 |
          ↑   ↑
         lo   hi

어떤 조건을 만족하는 param 의 최솟값은 lo 가 아니라 hi 임을 알 수 있다. 따라서 이 경우에는 lo 가 아닌 hi 를 반환해야 한다.

bool fn(int param);

int binary_search(int lo, int hi) {
    while (lo + 1 < hi) {
        int mid = (lo + hi) >> 1;
        if (fn(mid)) hi = mid; // 참이면 왼쪽 구간을 탐색
        else lo = mid; // 거짓이면 오른쪽 구간을 탐색
    }
    return hi;
}

구간을 좁히는 조건문을 보면, 조건을 만족할 때마다 왼쪽 구간을 탐색하는데 그 이유는 현재 param 에 대해 fn 이 true 이면 오른쪽 구간은 전부 true 이니 볼 필요가 없기 때문이다. false -> true 는 현재 param 보다 왼쪽에 위치하게 된다.

반대로 조건을 만족하지 않으면 현재 param 에 대해 fn 이 false 이므로 왼쪽 구간은 전부 false 임을 알 수 있다. 따라서 false -> true 는 현재 param 보다 오른쪽에 위치하게 된다.

주의사항: 처음에 lo 와 hi 구간을 정의할 때, lo = 구간의 최솟값 - 1 로, hi = 구간의 최댓값 으로 정의해야 한다. hi 를 반환하기 때문에 lo = 구간의 최솟값이면 hi 는 구간의 최솟값이 될 수 없어서 (lo + 1 < hi 라는 조건에 의해) 구간의 최솟값이 정답일 경우 답을 반환할 수 없게 된다.

어떤 조건을 만족하는 param 의 최댓값(=answer)을 찾는 문제를 생각해보자.

fn(param) 은 연속이라고 했기 때문에 param <= answer 에 대해 fn(param) 은 항상 true 일 것이다. param 은 오름차순이니 fn(param) 의 결과는 param 에 따라 [true, true, ..., true, false, ..., false, false] 이고, 다음이 성립한다.

• fn(answer - 1) = true
• fn(answer) = true
• fn(answer + 1) = false

여기서 param 의 구간을 [lo, hi] 라고 정의할 때 while(lo + 1 < hi) 조건으로 반복문을 돌리면 최종적으로 아래와 같이 lo 와 hi 를 얻게 된다.

| t | ... | t | f | ... | f |
            ↑   ↑
           lo   hi

최솟값 구할 때랑 배열이 반대로 결과가 나온다. 어떤 조건을 만족하는 param 의 최댓값은 lo 임을 알 수 있다. 따라서 이 경우에는 lo를 반환해야 한다.

bool fn(int param);

int binary_search(int lo, int hi) {
    while (lo + 1 < hi) {
        int mid = (lo + hi) >> 1;
        if (fn(mid)) lo = mid; // 참이면 오른쪽 구간을 탐색
        else hi = mid; // 거짓이면 왼쪽 구간을 탐색
    }
    return lo;
}

배열이 반대이기 때문에 탐색하는 방법도 반대라는 것에 주의하자.

구간을 좁히는 조건문을 보면, 조건을 만족할 때마다 오른쪽 구간을 탐색하는데 그 이유는 현재 param 에 대해 fn 이 true 이면 왼쪽 구간은 전부 true 이니 볼 필요가 없기 때문이다. true -> false 는 현재 param 보다 오른쪽에 위치하게 된다.

반대로 조건을 만족하지 않으면 현재 param 에 대해 fn 이 false 이므로 오른쪽 구간은 전부 false 임을 알 수 있다. 따라서 true -> false 는 현재 param 보다 왼쪽에 위치하게 된다.

주의사항: 처음에 lo 와 hi 구간을 정의할 때, lo = 구간의 최솟값 으로, hi = 구간의 최댓값 + 1 로 정의해야 한다. lo 를 반환하기 때문에 hi 가 구간의 최댓값이면 lo 는 구간의 최댓값이 정답이어도 lo + 1 < hi 라는 조건 때문에 반환할 수 없게 된다.

정리하자면,

1. 문제에서 최종적으로 찾고자하는 최솟값/최댓값을 매개변수로 본다.
2. 결정 함수를 정의하고 구현했을 때 결과 배열이 연속인지 확인한다.
3. 최솟값이면 결정 함수의 결과가 [f,f,...,t,t] 에서 f->t 로 바뀌는 부분을 찾는다.
   • 결정 함수가 true 이면, 오른쪽 구간은 전부 true 이니, f->t 가 있는 왼쪽 구간을 탐색한다. hi = mid
   • 결정 함수가 false 이면, 왼쪽 구간은 전부 false 이니, f->t 가 있는 오른쪽 구간을 탐색한다. lo = mid
   • 반복문을 빠져나오면, lo < hi 이므로 fn(lo) = false, fn(hi) = true 이다. 따라서 hi를 반환한다.
4. 최댓값이면 결정 함수의 결과가 [t,t,...,f,f] 에서 t->f 로 바뀌는 부분을 찾는다.
   • 결정 함수가 true 이면, 왼쪽 구간은 전부 true 이니, t->f 가 있는 오른쪽 구간을 탐색한다. lo = mid
   • 결정 함수가 false 이면, 오른쪽 구간은 전부 false 이니, t->f 가 있는 왼쪽 구간을 탐색한다. hi = mid
   • 반복문을 빠져나오면, lo < hi 이므로 fn(lo) = true, fn(hi) = false 이다. 따라서 lo 를 반환한다.

결정 함수의 구현

fn(param) := param 이 어떤 조건을 만족하면 true를 반환하고 아니면 false를 반환

"어떤 조건을 만족" 하는 것은 param 이상/이하일 때 M개의 그룹으로 나눌 수 있는가 또는 M개로 분할할 수 있는가 등을 묻는 것이라고 볼 수 있다. (대개 문제들이 그렇다.) 여기서 fn(param)의 결과 배열에 따라 즉, 최솟값/최댓값인지에 따라 M 에 대한 조건이 달라진다.

두 가지 흔한 예제를 살펴보자.

예제1) BOJ 2110번: 공유기 설치

문제 요약: C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대화

"가장 인접한 두 공유기의 거리를 최대(=answer)화" 하라는 의미는 모든 인접한 두 공유기의 간격이 answer 보다는 크거나 같아야 함을 의미한다. param 을 두 공유기의 간격이라고 하면 결정 함수는 다음과 같이 정의할 수 있다.

param := 두 공유기의 간격

fn(param) := 인접한 두 공유기 사이의 거리 >= param 이 되도록 C 개의 공유기를 설치할 수 있는가

위와 같이 결정 함수를 정의하면 최대 param (=answer) 이하로는 모든 fn(param) = true 가 되므로 이분 탐색으로 문제를 해결할 수 있게 된다. 즉, 거리가 3이상이 되도록 C개를 설치할 수 있으면 당연히 거리가 2이상이 되도록 C개를 설치할 수 있다.

이제 fn(param) 의 결과 배열이 [true, true, ..., true, false, ..., false, false] 인 것을 알았다.

true -> false 를 찾자.

int search() {
    // X는 오름차순 정렬이라 가정
    int lo = 1, hi = X[N-1] + 1;
    while (lo + 1 < hi) {
        int mid = (lo + hi) << 1;
        if (fn(mid)) lo = mid; // 현재 cond 보다 오른쪽 구간에 t->f 가 존재
        else hi = mid; // 현재 cond 보다 왼쪽 구간에 t->f 가 존재
    }
    return lo; // 반복문 불변식: fn(lo) = t, fn(hi) = f.
}

결정 함수를 구현할 때는 설치된 공유기 개수가 C 개 인지 확인하는 조건에 주의해야 한다.

두 집 사이의 거리 >= param 을 만족할 때마다 공유기를 설치한다고 하자.

공유기가 C개 보다 많이 설치된 경우, param 이 작아서 조건을 만족하는 경우가 많다는 의미로, param을 늘려주어야 한다. 따라서 true 를 반환해야 현재 param 보다 오른쪽 구간에서 param 을 탐색할 수 있다.

공유기가 C개 보다 적게 설치된 경우, param 이 커서 조건을 만족하는 경우가 적다는 의미로, param을 줄여야 한다. 따라서 false 를 반환해야 현재 param 보다 왼쪽 구간에서 param 을 탐색할 수 있다.

공유기 개수가 C개이면 조건을 만족하니 true 를 반환한다.

bool fn(int param) {
    int cnt = 1, prev = 0; // 첫번째 집에 공유기를 설치했다고 가정
    for (int i = 1; i < N; i++) {
        if (X[i] - X[prev] >= param) {
            cnt++;
            prev = i;
        }
    }
    return cnt >= C;
}

예제2) BOJ 2613: 숫자구슬

문제 요약: M개의 그룹으로 N개의 숫자구슬을 나눌 때, 그룹의 합의 최댓값을 최소화

param := 그룹의 합

fn(param) := 그룹의 합 <= param 이 되도록 M 개의 그룹으로 나눌 수 있는가

위와 같이 결정 함수를 정의하면 최소 param (=answer) 이상으로는 모든 fn(param) = true 가 되므로 이분 탐색으로 문제를 해결할 수 있다. 예를 들어, 그룹의 합이 4 이하가 되도록 M 개의 그룹으로 나눌 수 있으면, 합이 5 이하가 되도록 M 개의 그룹으로 나눌 수 있다.

이제 fn(param) 의 결과 배열이 [false, false, ..., false, true, ..., true, true] 인 것을 알았다.

false -> true 를 찾자.

int search() {
    int lo = 0, hi = accumulate(A, A + N, 0);
    while (lo + 1 < hi) {
        int mid = (lo + hi) >> 1;
        if (!fn(mid)) lo = mid; // 현재 param 보다 오른쪽 구간에 f -> t 가 존재
        else hi = mid; // 현재 param 보다 왼쪽 구간에 f -> t 가 존재
    }
    return hi;
}

결정 함수를 구현할 때는 그룹의 개수가 M 개인지 확인하는 조건에 주의해야 한다.

숫자 구슬의 합 > param 을 만족할 때마다 그룹을 나눈다고 하자.

그룹이 M 개 보다 많이 나뉘어진 경우, param 이 작아서 조건을 만족하는 경우가 많다는 의미로, param 을 늘려야 한다. 따라서 false 를 반환해야 현재 param보다 오른쪽 구간에서 param 을 탐색한다.

그룹이 M 개 보다 적게 나뉘어진 경우, param 이 커서 조건을 만족하는 경우가 적다는 의미로, param 을 줄여야 한다. 따라서 true 를 반환해야 현재 param보다 왼쪽 구간에서 param 을 탐색한다.

딱 M개인 경우 조건을 만족하므로 true 를 반환한다.

bool fn(int param) {
    int cnt = 1; // 그룹의 개수는 1개부터 시작
    for (int i = 0, psum = 0; i < N; i++) {
        if (A[i] > param) return false; // 숫자구슬 1개가 이미 param 을 넘어서면 false
        if (psum + A[i] > param) {
            psum = A[i];
            cnt++;
        } else psum += A[i];
    }
    return cnt <= M;
}

참고로 A[i] > param 일 때는 무조건 false 를 반환해야 한다. 아니면 계속 반복문이 수행될 수 있어서 결과가 잘못나올 수 있다.

이 문제는 그룹마다 구슬이 몇 개 들어있는지도 출력해야 하는데, 최솟값을 찾고나면 최솟값을 넘지 않도록 그룹 지은 다음 그룹의 개수가 M 보다 작으면 그룹의 합이 최대인 그룹을 제외하고 그룹 내 구슬을 1개씩 다른 그룹으로 나눠주면 된다.

기타 예제)

BOJ 3079 입국심사

BOJ 2805 나무자르기

BOJ 1654 랜선자르기

접미사 배열

• 접미사 배열이란 어떤 문자열의 접미사를 사전식 순서대로 나열한 배열을 말한다. by Wikipedia
• 문자열 "banana" 의 접미사는 다음과 같다.

Suffix Array:
0: banana
1: anana
2: nana
3: ana
4: na
5: a

• 사전순으로 정렬하면 다음과 같다.

Suffix Array:
5: a
3: ana
1: anana
0: banana
4: na
2: nana

Naive Method

• 모든 접미사 문자열에 대해 비교한 경우: 비교할 때 O(N) 이 걸리고, 정렬할 경우 O(N*log(N)) 이 걸린다.
• 다음과 같은 방법으로 접미사 배열을 얻을 경우 O(N^2 * log(N)) 의 시간 복잡도를 갖는다.
• 일반적으로 문자열의 접미사를 모두 저장하기 보다는 접미사의 시작 위치만 저장하여 메모리를 절약한다.

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

struct NaiveComparator {
  const string& s;
  NaiveComparator(const string& s) : s(s) {}
  bool operator() (int i, int j) {
    const char* ptr = s.c_str();
    return strcmp(ptr + i, ptr + j) < 0;
  }
};

// O(N^2 * log(N)), where N is the length of the given string.
vector<int> getSuffixArray(const string& s) {
  vector<int> sfx(s.size());
  generate(sfx.begin(), sfx.end(), [x=0]() mutable { return x++; });
  sort(sfx.begin(), sfx.end(), NaiveComparator(s));
  return sfx;
}

int main() {
  string s = "banana";
  vector<int> sfx = getSuffixArray(s);
  return 0;
}

Manber-Myers Algorithm

• 접미사 배열 생성 시, O(N * log(N)^2) 의 시간복잡도를 갖는다.
• 아이디어는 정렬 시 매 비교마다 각 접미사의 t번째 글자를 기준으로 정렬을 해주는 것이다. 이 때 t는 2배씩 증가한다.
• 정렬을 여러 번 하는데도 빠르게 동작하는 이유는 이전에 비교한 결과를 이용하여 두 문자열의 대소비교를 O(1) 만에 끝낼 수 있기 때문이다. 즉, 정렬할 때 두 문자열의 모든 문자들을 살펴볼 필요가 없다.
• 아래에서 사용된 group[i]은 s[i]부터 시작하는 접미사가 속한 그룹으로, 첫 글자가 같으면 같은 그룹 번호를 가지는 것으로 시작한다. 따라서 초기값은 별도의 번호 없이 s[i]를 그룹 번호로 가진다.
  • 그리고 매 t번째 글자를 기준으로 정렬한 후, t번째 글자가 같은 것끼리 같은 그룹으로 묶는다. 즉, 처음 나뉜 그룹에서 인접한 접미사들이 다음 글자마다 그룹핑되는 것이다.
  • 매 정렬 후, 새 그룹 번호를 할당하는 이유는 t번째 글자마다 그룹핑을 다시하기 때문이다.
  • 비교되는 두 문자열 중 하나가 t보다 짧은 경우를 대비하여 group[n] = -1로 고정시켜놓음으로써 항상 i+t 와 j+t 가 n을 넘기지 않도록 해놓는다. t가 길이를 넘기기 이전에 맨 앞으로 보내지기 때문에 operator() 함수의 if문에서 필터링된다.
• t = 1 일 때 정렬하면, 첫 글자가 같은 접미사들은 sfx 배열 내에서 인접한 위치에 있게 된다.
• t = 2 일 때 정렬하면, 이미 첫 글자가 같은 접미사는 같은 그룹이므로 두번째 글자만 비교하여 순서가 바뀌게 된다.
• 4 < t < n 인 동안 위와 같이 계속 반복한다.

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

struct Comparator {
  vector<int> group;
  int t;
  Comparator(vector<int>& group, int t) : group(group), t(t) {}
  bool operator() (int i, int j) {
    if (group[i] != group[j]) return group[i] < group[j];
    return group[i+t] < group[j+t];
  }
};

// O(N * log(N))
vector<int> getSuffixArray(const string& s) {
  int n = s.size(), t = 1;
  vector<int> group(n+1, -1), sfx(n);
  for (int i = 0; i < n; i++) {
    group[i] = s[i];
    sfx[i] = i;
  }
  
  while (t < n) {
    Comparator comparator(group, t);
    sort(sfx.begin(), sfx.end(), comparator);
    t *= 2;
    vector<int> newGroup(n+1, -1);
    newGroup[sfx[0]] = 0;
    for (int i = 1; i < n; i++) {
      newGroup[sfx[i]] = newGroup[sfx[i-1]];
      // 사전순으로 앞에 위치하면 현재 그룹 번호를 이전 그룹 번호보다 1 증가
      if (comparator(sfx[i-1], sfx[i])) newGroup[sfx[i]]++;
    }
    group = newGroup;
  }
  return sfx;
}

int main() {
  string s = "banana";
  vector<int> sfx = getSuffixArray(s);
  return 0;
}

• 중간 결과를 출력해보면 t 가 증가할 때마다 정렬 결과가 변경되는 것을 알 수 있다.

Initial: 0 1 2 3 4 5 
Suffix Array:
0: banana
1: anana
2: nana
3: ana
4: na
5: a

[t = 1] sfx: 5 1 3 0 2 4 
Suffix Array:
5: a
1: anana
3: ana
0: banana
2: nana
4: na      <--- 아직 첫번째 글자만 비교했기 때문에 na 는 뒤에 있다.
----------------
[t = 2] sfx: 5 3 1 0 4 2 
Suffix Array:
5: a
3: ana
1: anana
0: banana
4: na      <--- 두번째 글자를 비교한 후 na가 앞으로 옮겨졌다.
2: nana
----------------
[t = 4] sfx: 5 3 1 0 4 2 
Suffix Array:
5: a
3: ana
1: anana
0: banana
4: na
2: nana
----------------

• "mississipi" 에서 t번째 글자마다 그룹핑을 다시하여 그룹 번호가 변경된다.

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

struct Comparator {
  vector<int> group;
  int t;
  Comparator(vector<int>& group, int t) : group(group), t(t) {}
  bool operator() (int i, int j) {
    if (group[i] != group[j]) return group[i] < group[j];
    return group[i+t] < group[j+t];
  }
};

vector<int> getSuffixArray(const string& s) {
  int n = s.size(), t = 1;
  vector<int> group(n+1, -1), sfx(n);
  for (int i = 0; i < n; i++) {
    group[i] = s[i]-'a';
    sfx[i] = i;
  }
  
  // DEBUG
  cout << "Initial: ";
  for (int i = 0; i < n; i++) cout << sfx[i] << " ";
  cout << endl << "Suffix Array:" << endl;
  for (auto i : sfx) cout << "Group[" << i << "] = " << group[i] << ": " << s.substr(i) << endl;
  cout << endl;

  while (t < n) {
    Comparator comparator(group, t);
    sort(sfx.begin(), sfx.end(), comparator);
    t *= 2;
    vector<int> newGroup(n+1, -1);
    newGroup[sfx[0]] = 0;
    for (int i = 1; i < n; i++) {
      newGroup[sfx[i]] = newGroup[sfx[i-1]];
      if (comparator(sfx[i-1], sfx[i])) newGroup[sfx[i]]++;
    }
    
    // DEBUG
    cout << "t = " << t << ": ";
    for (int i = 0; i < n; i++) cout << sfx[i] << " ";
    cout << endl << "Suffix Array:" << endl;
    for (auto i : sfx) cout << "Group[" << i << "] = " << group[i] << ": " << s.substr(i) << endl;
    cout << "----------------" << endl;
    
    group = newGroup;
  }
  return sfx;
}

int main() {
  string s = "mississipi";
  vector<int> sfx = getSuffixArray(s);
  return 0;
}

Initial: 0 1 2 3 4 5 6 7 8 9 
Suffix Array:
Group[0] = 12: mississipi
Group[1] = 8: ississipi
Group[2] = 18: ssissipi
Group[3] = 18: sissipi
Group[4] = 8: issipi
Group[5] = 18: ssipi
Group[6] = 18: sipi
Group[7] = 8: ipi
Group[8] = 15: pi
Group[9] = 8: i

t = 2: 9 7 1 4 0 8 3 6 2 5 
Suffix Array:
Group[9] = 8: i
Group[7] = 8: ipi
Group[1] = 8: ississipi
Group[4] = 8: issipi
Group[0] = 12: mississipi
Group[8] = 15: pi
Group[3] = 18: sissipi
Group[6] = 18: sipi
Group[2] = 18: ssissipi
Group[5] = 18: ssipi
----------------
t = 4: 9 7 1 4 0 8 6 3 5 2 
Suffix Array:
Group[9] = 0: i
Group[7] = 1: ipi
Group[1] = 2: ississipi      <---- 같은 그룹 내에서 4번째 글자 기준으로 그룹핑이 다시 된다.
Group[4] = 2: issipi
Group[0] = 3: mississipi
Group[8] = 4: pi
Group[6] = 5: sipi
Group[3] = 5: sissipi
Group[5] = 6: ssipi
Group[2] = 6: ssissipi
----------------
t = 8: 9 7 4 1 0 8 6 3 5 2 
Suffix Array:
Group[9] = 0: i
Group[7] = 1: ipi
Group[4] = 2: issipi
Group[1] = 2: ississipi
Group[0] = 3: mississipi
Group[8] = 4: pi
Group[6] = 5: sipi
Group[3] = 6: sissipi
Group[5] = 7: ssipi
Group[2] = 8: ssissipi
----------------
t = 16: 9 7 4 1 0 8 6 3 5 2 
Suffix Array:
Group[9] = 0: i
Group[7] = 1: ipi
Group[4] = 2: issipi
Group[1] = 3: ississipi
Group[0] = 4: mississipi
Group[8] = 5: pi
Group[6] = 6: sipi
Group[3] = 7: sissipi
Group[5] = 8: ssipi
Group[2] = 9: ssissipi
----------------

최장 공통 접두사 배열

• 접미사 배열에서 이전 접미사와 공통되는 접두사의 길이를 저장한 배열이다. by Wikipedia
• 알고리즘 대회에서는 어떤 문자열이 주어질 때 2번 이상 반복되는 연속되는 부분 문자열의 최대 갈이를 구할 때 주로 사용된다.
  • 해결책은 어떤 부분 문자열은 주어진 문자열의 접미사의 접두사라는 점을 이용하여 인접한 접미사끼리 공통되는 부분 중 가장 긴 것을 찾아내는 것이다.
• LCP 배열의 경우, 문자열의 길이가 길면 접미사를 비교하는데 시간이 오래걸리는 점을 보완하기 위해 인접한 접미사끼리 비교할 때 공통되는 문자들은 건너뛰어 시간을 절약한다. 예를 들면, mississipi 에서 접미사 ipi 와 issipi 를 비교할 때 이전에 i와 ipi 가 비교되었기 때문에 i는 세지 않고 바로 다음 글자인 p와 s부터 길이를 측정하는 것이다.
• 주의할 점은 LCP 배열을 만들 때, 문자열 비교 시간을 절약하기 위해 첫번째 위치에서부터 비교해야 하므로 prevSfx 처럼 접미사 배열에서 이전 접미사의 위치를 저장할 필요가 있다. 0번째 접미사는 이전 접미사가 없으므로 -1을 저장한다.

// 위와 동일

vector<int> getLongestCommonPrefix(const string& s, const vector<int>& sfx) {
    int n = s.size();
    vector<int> plcp(n), prevSfx(n), lcp(n);
    prevSfx[sfx[0]] = -1;
    for (int i = 1; i < n; i++) prevSfx[sfx[i]] = sfx[i-1];
    for (int i = 0, common = 0; i < n; i++) {
        if (prevSfx[i] == -1) plcp[i] = 0;
        else {
            while (s[i+common] == s[prevSfx[i]+common]) common++;
            plcp[i] = common;
            if (common > 0) common--;
        }
    }
    for (int i = 0; i < n; i++) lcp[i] = plcp[sfx[i]];
    return lcp;
}

int main() {
    string s = "mississipi";
    vector<int> sfx = getSuffixArray(s);
    for (int x : sfx) cout << s.substr(x) << endl;
    vector<int> lcp = getLongestCommonPrefix(s, sfx);
    int maxLen = 0, start = 0;
    for (int i = 0; i < lcp.size(); i++) {
        if (maxLen < lcp[i]) {
            maxLen = lcp[i];
            start = i;
        }
    }
    cout << "LongestCommonPrefix: " << s.substr(start, maxLen) << endl;
    return 0;
}

/*
i
ipi
issipi
ississipi
mississipi
pi
sipi
sissipi
ssipi
ssissipi
LongestCommonPrefix: issi
*/

• 소스 코드: 익명 함수 사용 시, 훨씬 빠르다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

vector<int> getSuffixArray(const string& s) {
    int n = s.size();
    vector<int> g(n+1, -1), sfx(n), ng;
    for (int i = 0; i < n; i++) { g[i] = s[i]; sfx[i] = i; }
    
    for (int t = 1; t < n; t <<= 1, g = ng) {
        auto cmp = [&](int i, int j)->bool {
            if (g[i] != g[j]) return g[i] < g[j];
            return g[i+t] < g[j+t];
        };
        sort(sfx.begin(), sfx.end(), cmp);
        ng.clear(); ng.resize(n+1, -1); ng[sfx[0]] = 0;
        for (int i = 1; i < n; i++) {
            ng[sfx[i]] = ng[sfx[i-1]];
            if (cmp(sfx[i-1], sfx[i])) ng[sfx[i]]++;
        }
    }
    
    return sfx;
}

vector<int> getLongestCommonPrefix(const string& s, const vector<int>& sfx) {
    int n = s.size();
    vector<int> plcp(n), prevSfx(n), lcp(n);
    prevSfx[sfx[0]] = -1;
    for (int i = 1; i < n; i++) prevSfx[sfx[i]] = sfx[i-1];
    for (int i = 0, common = 0; i < n; i++) {
        if (prevSfx[i] == -1) plcp[i] = 0;
        else {
            while (s[i+common] == s[prevSfx[i]+common]) common++;
            plcp[i] = common;
            if (common > 0) common--;
        }
    }
    for (int i = 0; i < n; i++) lcp[i] = plcp[sfx[i]];
    return lcp;
}

int main() {
    string s; cin >> s;
    vector<int> sfx = getSuffixArray(s);
    vector<int> lcp = getLongestCommonPrefix(s, sfx);
    for (int x : sfx) cout << x+1 << " ";
    cout << endl << "x" << " ";
    for (int i = 1; i < lcp.size(); i++) cout << lcp[i] << " ";
    cout << endl;
    return 0;
}

이미지 출처: https://book.algospot.com

책을 처음 샀을 때는 2018년 1월 10일. (대략 3년 동안 가지고 있을 줄은 몰랐다)

당시 대학교 3학년이었는데, 친구 추천으로 정말 생각없이 샀었다. (이렇게 어려운 줄 몰랐지)

오늘 오후에 이 책을 완독(2020년 11월 28일)했는데, 여러모로 많은 생각이 들어 경험을 글로 공유하고자 한다. 게다가 실제로 책을 산 사람들은 많은데 후기글은 거의 못 본 것 같다.

책을 사기 전에는 알고리즘에 대한 지식은 거의 없었다. (백준 문제 30개 풀었나..? 학교수업은 just trash)

아무튼 알고리즘 지식은 무다 없을 무 ;;

* 참고로 필자는 내년에 졸업을 앞둔 대학교 4년제 컴공과 학생이다.

기억을 더듬어보면, 책을 받자마자  "나도 이제 알고리즘의 왕이 될 수 있겠지?!" 뭐 그런 생각을 하면서 읽기 시작했던 것 같다. 마치 나는 해적왕이 될거야;

그리고 변수의 이해부터 점점 졸리더니 ㅋㅋㅋ 동적 계획법(Dynamic Programming)의 어딘가에서 멈춰버렸다

물론 어려운 것도 있었지만 사실 알고리즘이 급하지 않아서 언젠가는 하겠지하고 책을 고이 모셔둔(쳐박아둔) 것이었따

그리고 2년 정도 흘렀나,,, (백준 문제 한 150개 풀었을 무렵) 고이 모셔둔(쳐박아둔) 종만북이 생각나서 다시 공부나 해볼까? 했는데 책을 덮고 펼치고 덮고 펼치고 를 반복했었다. (나레기 ..;)

아무튼 막학기에 캡스톤을 해야 해서 이전 겨울 방학때 1부라도 끝내자 해서 울며 겨자먹기로 1부를 읽기 시작했고, 그마저도 다 못해서 (매일 몇 시간씩 했는데도 너무 어렵더라;) 학기 중에 주말에 짬내서 봤다.

그리고 인턴하면서 2부를 시작했는데 진짜 ㅋㅋㅋ 웰컴투더헬 ..

집에ㅅ ㅓ창문에 대고 혼자 소리지르고 싶은거 굉장히 많이 참았다. 그리고 벽에 대고 머리 계속 쥐어박고 ㅠㅠ

책을 보면서 답답한 마음도 있었는데 설명이 이해가 되지 않아서 앞쪽으로 넘어가 다시 읽고를 무한 반복하다보니 시간이 오래 걸렸다. (정말 ㄹㅇ무한재생) 그리고 종만 님의 은혜로운 설명을 보면서 무릎을 탁 치고 (코드 보고 내 이마를 탁 치고;;) 를 여러 번하면서 확실히 실력 향상이 느껴지긴 하지만, 다음 장에 어려운거 또나오면 까먹는 문제가 발생했다.

한 5문제 있으면,

(와 이걸 이렇게?)

(와 이걸 이렇게?)

(와 이걸 이렇게?)

(와 이걸 이렇게?)

(와 이걸 이렇게?)

마지막 것만 기억남 ㅋㅋㅋㅋㅋㅋㅋㅋ

수록된 알고리즘은 각각 설명하고나서 문제를 살펴보는데 "문제 -> 접근 -> 풀이 -> 해설" 순서로 내용을 다룬다.

필자의 경우는 <문제> 읽고 혼자 고민하다가 안되면, <접근> 읽고 고민하고 그러다 안되면, 바로 풀이랑 해설을 보고 공부를 했는데 공부하는 방식은 개인의 스타일대로 하면 되는거고 나는 좀.. 오기(?) 자존심(?)이 좀 있어서 "그래도 이거는 풀 수 있겠지^^.."라는 마음으로 희망하나 버리지 않고 도전했었다.

물론 난이도 높은 문제들은 바로 풀이를 보는 것이 나았다 ㅎ;

책에는 문제별로 (하, 중, 상 이런 식으로) 난이도가 있어서 난이도가 "상"이면 30분 고민하고 안되면 바로 풀이로 넘어갔다.

왜 꼭 그런 문제들 있지 않나,, 30분 고민해도 감이 안오고 점점 딥슬립하게 되는 ㅋㅋ

실제로 그런 경우는 정말 <경험이 없어 아이디어가 생각조차 나지 않는 상황>인 경우가 대부분이었고 (난 멍청하지 않아..)

한 번 그런 풀이를 보고 나면 아래의 두 상황 중 하나가 되게 된다.

유사한 문제가 나왔을 때는 풀 수 있거나 vs 아이디어는 떠올랐는데 구현을 못하거나

구현을 못하는 건 필자의 경우 언어를 제대로 활용하지 못했던 게 큰 이유(뒤늦게 C++ 라이브러리를 정리했다지^^7)였고, 정석대로 구현하는 방법이 있는데 마찬가지로 경험이 없던 것이 문제가 되는 거였다. **이론만 안다고 되는게 아니더라..**

가끔은 내용을 이해하고 직접 짜보고 문제 풀어(무한 디버깅)보고 했는데 6시간이 지나기도 했다.

근데 넘어간 페이지는 3페이지 ㅋㅋ

그러면 자연스레 속에서 깊은 한숨이 나오면서 쓰레빠신고 동네 한바퀴 돌아준다. 안그러면 me쳐버림;

그리고 자기 전에 "ㅅㅂ 한 건했다" 이러고 ;

물론 가끔 일어난 일 ^^,,

뒤로 갈수록 자주 일어나는 일

체감상 느끼는 어려움은 난이도 "상" 문제들을 기준으로 했을 때 인공지능 수업시간에 C++로 다층퍼셉트론 구현한 거와 비슷하거나 그 이상이다. 역전파법(backpropagation)도 이론은 들으면 고개 끄덕끄덕하는데 실제 구현하라하면 'ㅁ'..

난이도 "중" 문제들은 60% 는 어렵다. 정말 어렵다. 비슷한 문제조차 못풀어봤다면 3시간 줘도 못 푼다.

라는 생각이 들만큼 입문자가 풀 수 있는 난이도는 아니라고 생각한다. BUT 종만 님의 알고리즘 설명이 있다면 몇 시간 걸리긴해도 풀 수는 있을 듯하다. 나머지 40%는 알고리즘 문제 좀 풀어봤다? 싶으면 도전해볼 가치는 있다. 대신 알고리즘이 뭔지에 따라 걸리는 시간은 확연히 차이가 난다.

책이 굉장히 두꺼운데 생각보다 알고리즘별로 문제가 많이 수록되어 있지는 않다. 있어봤자 5개가 최대인데 (아마?) 고작 5개 문제 풀어보고 감잡았쓰 - 완전 접쑤 - 라고 할 수는 없지 않나... 그래서 필자의 경우 leetcode에 비슷한 문제가 있는지 찾아보고 다음 챕터로 넘어가기 전에 머리도 식힐 겸 해당 문제들을 풀어봤다. 비슷한 문제니 푸는데 시간이 많이 걸리지는 않았음. leetcode 에 없으면 백준으로~

아무튼,, 주절주절 어렵다어렵다어렵다.. 디퓌컬ㅌ~ 라고 글을 썼지만, 그럼에도 이 책을 많은 사람들이 찾는 건 다 그럴만한 이유가 있지 않겠나..

확실히 읽기 전과 후는 다르다.

아래는 필자 입장(알고리즘 경험 zero)에서 이 책을 읽고 얻어간 것들을 정리한 것.

** 참고로 알고리즘과 자료구조는 다른 이론이기 때문에 알고리즘은 모르더라도 자료구조는 알고 읽기를 바람.

** 최소한 본인이 자주 사용할 언어(혹은 사용중인 언어)에서 전통적인 자료구조(스택, 큐, 우선순위 큐 등)가 어떻게 제공되는지도 무조건 알고 시작해야 함.

• 알고리즘 문제들은 보통 현실 상황을 반영하려 하므로, 대놓고 큐에 뭐 넣어라, 스택에 뭐 넣어라 그러지 않음. 따라서 주어진 문제 상황을 이해하고 이를 어떻게 자료(Data)로 표현할 지가 문제 해결의 핵심인데 (시작이 반이라고) 종만북은 자료구조를 설계하는 방법을 A-to-Z 방식으로 설명함.

• 문제의 해결책마다 시간 복잡도를 왜 그렇게 계산했는지 알려줌. 이게 진짜.. 종만의 미덕이 아닐까? 실제로 재귀 탐색만 하더라도 모든 노드가 아니라 부분 노드만 탐색한다던지 하면 계산하기 복잡한데, 참 수학을 잘하시는 종만 쓰앵님은 계산을 하셔서 알려주심.

• 정당성의 증명. 사실 이 부분은 너무 어려워서 포기한 것들이 손가락으로 셀 정도로 있음. (참새가 어찌 봉황의 뜻을 알겠소) 아니면 그 당시에 이해해도 지금 봐도 모르는 부분은 당연히 존재함 ㅋㅋ. 이 부분은 귀류법이나 귀납법으로 소개한 알고리즘이 반드시 해를 찾는다라는 사실을 증명함. --> 만약 직관이 아니라 증명하는 걸 습관처럼 한다면 그때는 종만북이 필요없을 듯 싶음..

• leetcode 의 난이도 hard 나, 백준의 정답률 20-30% 정도의 문제들을 해결할 수 있는 능력이 생김 (모든 문제 X)

• 다양한 알고리즘 지식, 문제 풀이 경험, 등등 (+ 내가 멍청하다는 사실 ㅠㅠ && 항상 겸손히 배워갈 의지 ^^)

참고: 이 책은 심장과 정신건강에 해롭기 때문에, 본인이 굳건한 멘탈과 이를 갈고 도전할 의지가 있다면 꼭 사길 바람. 뭐든지 쉬워지기전에는 모든게 어렵다고.. 나는 몰라서 못푼거지 멍청하지 않아..

만약 대회 경험도 다수 있고, (SCPC 수상자는 안봐도 될듯..) 큰 대회에 자주 출전해 본 사람이라면, 책을 살 필요가 있나 싶음.

정 읽다가 힘들면 아침부터 "나는 유노윤호다"라고 생각하자.

내일부터는 종만북을 다시 읽을 듯함. 나중에 시간만 되면 추가 후기를 써보던가 해야겠음..

원래 진리를 담은 책은 매번 읽을 때마다 얻어가는게 다르다고 하지않던가..