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;
}

Algorithmic Problem Solving Strategies - Chapter 04

• vector operation

const double PI = 2.0 *acos(0.0);

struct vector2 {
    double x, y;

    // 생성자를 explicit 으로 저장하면 vector2 를 넣을 곳에 잘못해
    // 실수가 들어가는 일을 방지해준다.
    explicit vector2(double x_ = 0, double y_ = 0) : x(x_), y(y_)
    {}

    // 두 벡터의 비교
    bool operator == (const vector2 &rhs) const {
        return x == rhs.x && y == rhs.y;
    }

    bool operator < (const vector2 &rhs) const {
        return x != rhs.x ? x < rhs.x : y < rhs.y;
    }

    // 벡터의 덧셈과 뺄셈
    vector2 operator + (const vector2 &rhs) const {
        return vector2(x + rhs.x, y + rhs.y);
    }

    vector2 operator - (const vector2 &rhs) const {
        return vector2(x - rhs.x, y - rhs.y);
    }

    // 실수로 곱셈
    vector2 operator * (double rhs) const {
        return vector2(x * rhs, y * rhs);
    }

    // 벡터의 길이를 반환
    double norm() const { return hypot(x, y); }

    // 방향이 같은 단위 벡터(unit vector)를 반환한다.
    // 영벡터에 대해 호출한 경우 반환 값은 정의되지 않는다.
    vector2 normalize() const {
        return vector2(x / norm(), y / norm());
    }

    // x축의 양의 방향으로부터 이 벡터까지 반시계 방향으로 잰 각도
    double polar() const {
        return fmod(atan2(y,x) + 2*PI, 2*PI);
    }

    // 내적
    double dot(const vector2 &rhs) const {
        return x * rhs.x + y * rhs.y;
    }

    // 외적
    double cross(const vector2 &rhs) const {
        return x * rhs.y - y * rhs.x;
    }

    // 이 벡터를 rhs 에 사영한 결과
    vector2 project(const vector2 &rhs) const {
        vector2 r = rhs.normalize();
        return r * r.dot(*this);
    }
};

// 점 p,a,b 가 주어졌을 때 a 가 b 보다 p 에 얼마나 더 가까운가.
double howMuchCloser(vector2 p, vector2 a, vector2 b) {
    return (b - p).norm() - (a - p).norm();
}

// 두 벡터의 방향성을 판단하는 함수
// 원점에서 벡터 b가 벡터 a의 반시계 방향이면 양수, 시계 방향이면 음수,
// 평행이면 0을 반환
double ccw(vector2 a, vector2 b) {
    return a.cross(b);
}

// 점 p를 기준으로 벡터 b가 벡터 a의 반시계 방향이면 양수,
// 시계 방향이면 음수, 평행이면 0을 반환한다.
double ccw(vector2 p, vector2 a, vector2 b) {
    return ccw(a - p, b - p);
}


// 두 직선의 교차점을 계산하는 함수
// (a,b) 를 포함하는 선과 (c,d)를 포함하는 선의 교점을 x 에 반환
// 두 선이 평행이면 (겹치는 경우를 포함) 거짓을, 아니면 참을 반환
bool lineIntersection(vector2 a, vector2 b,
                      vector2 c, vector2 d,
                      vector2 &x)
{
    // a + pb = c + qd 방정식을 이용해서
    // x값과 y값 각각에 해당되는 연립 방정식을 얻으면
    // 분모가 0 인 경우를 제외하고 아래의 식대로 p를 얻는다.
    // p = ((c-a)*d)/(b*d)
    // 여기서 구한 p를 a + pb 에 대입해 원하는 점을 구한다.
    double det = (b - a).cross(d - c); // 행렬식
    // 두 선이 평행한 경우: 행렬식 = 0
    if (fabs(det) < EPSILON) return false;
    double p = ((c - a).cross(d - c) / det);
    x = a + (b-a) * p;
    return true;
}


// 선분과 선분의 교차점을 계산하는 함수
// (a,b)와 (c,d)가 평행한 두 선분일 때 이들이 한 점에서 겹치는지 확인한다.
bool parallelSegments(vector2 a, vector2 b,
                      vector2 c, vector2 d,
                      vector2 &p)
{
    // 평행일 때 가능한 경우의 수
    // 1. 두 선분이 서로 겹치지 않음
    // 2. 두 선분이 한 점에서 닿음
    // 3. 두 선분이 겹쳐짐
    // 4. 한 선분이 다른 선분 안에 포함됨
    if (b < a) swap(a, b);
    if (d < c) swap(c, d);
    // 한 직선 위에 없거나 두 선분이 겹치지 않는 경우를 우선 걸러낸다.
    if (ccw(a,b,c) != 0 || b < c || d < a) return false;
    // 두 선분이 확실히 겹치므로, 교차점을 찾는다.
    if (a < c) p = c; // a와 b 사이에 c가 있는 경우
    else p = a; // c와 d 사이에 a가 있는 경우
    return true;
}

// p가 (a,b)를 감싸면서 각 변이 x, y축에 평행한 최소 사각형 내부에 있는지 확인
// a, b, p 는 일직선 상에 있다고 가정한다.
bool inBoundingRectangle(vector2 p, vector2 a, vector2 b) {
    if (b < a) swap(a, b);
    return p == a || p == b || (a < p && p < b);
}

// (a,b) 선분과 (c,d) 선분의 교점을 p에 반환한다.
// 교점이 여러 개일 경우 아무 점이나 반환한다.
// 두 선분이 교차하지 않을 경우 false를 반환한다.
bool segmentIntersection(vector2 a, vector2 b,
                         vector2 c, vector2 d,
                         vector2 &p)
{
    // 두 직선이 평행인 경우를 우선 예외로 처리한다.
    if (!lineIntersection(a,b,c,d,p))
        return parallelSegments(a,b,c,d,p);
    // p가 두 선분에 포함되어 있는 경우에만 참을 반환한다.
    return inBoundingRectangle(p,a,b) &&
           inBoundingRectangle(p,c,d);
}


// 선분과 선분의 교차점을 계산하는 함수 (교차점이 필요 없을 때)
bool segmentIntersects(vector2 a, vector2 b,
                       vector2 c, vector2 d)
{
    // 교차한다면, a를 기준으로 b는 c와 d 사이에 있어야 한다.
    // 즉, c가 b에서 떨어진 방향과 d가 떨어진 방향은 곱했을 때 음수어야 한다.
    double ab = ccw(a,b,c) * ccw(a,b,d);
    double cd = ccw(c,d,a)  * ccw(c,d,b);
    // 두 선분이 한 직선 위에 있거나 끝점이 겹치는 경우
    if (ab == 0 && cd == 0) {
        if (b < a) swap(a,b);
        if (d < c) swap(c,d);
        return !(b < c || d < a);
    }
    return ab <= 0 && cd <= 0;
}


// 점과 선분 사이의 거리를 계산하는 함수
// 점 p에서 (a,b) 직선에 내린 수선의 발을 구한다.
vector2 prependicularFoot(vector2 p, vector2 a, vector2 b) {
    return a + (p - a).project(b - a);
}

// 점 p와 (a,b) 직선 사이의 거리를 구한다.
double pointToLine(vector2 p, vector2 a, vector2 b) {
    return (p - prependicularFoot(p,a,b)).norm();
}

• polygon operation using vector

typedef vector<vector2> polygon;

// 단순 다각형의 넓이를 구하는 함수
// 주어진 단순 다각형 p의 넓이를 구한다.
// p는 각 꼭지점의 위치 벡터의 집합으로 주어진다.
double area(const polygon &p) {
    double result = 0;
    for (int i=0; i<p.size(); i++) {
        int j = (i+1) % p.size();
        result += p[i].x * p[j].y - p[j].x * p[i].y;
    }
    return fabs(result) / 2.0; // 오목 다각형을 고려하여 절댓값으로 반환
}

// 주어진 점이 단순 다각형 내부에 포함되어 있는지 확인하는 함수
// 점 q가 다각형 p 안에 포함되어 있을 경우 참, 아닌 경우 거짓을 반환
// q가 다각형의 경계 위에 있는 경우의 반환 값은 정의되어 있지 않다.
bool isInside(vector2 q, const polygon &p) {
  int crosses = 0;
  for (int i=0; i<p.size(); i++) {
    int j = (i + 1) % p.size();
    // (p[i], p[j])가 반직선을 세로로 가로지르는가?
    if ((p[i].y > q.y) != (p[j].y > q.y)) {
      // 가로지르는 경우: x 좌표를 계산 (직선의 방정식 이용)
      double atX = (p[j].x - p[i].x) * (q.y - p[i].y) / (p[j].y - p[i].y) + p[i].x;
      if (q.x < atX) {
        crosses++;
      }
    }
  }
  return crosses % 2 > 0; // 홀수 개면 안에, 짝수 개면 밖에 있음.
}

// 반평면과 단순 다각형의 교집합을 구한다.
// (a,b)를 포함하는 직선으로 다각형 p를 자른 뒤, (a,b)의 왼쪽에 있는 부분들을 반환
polygon cutPoly(const polygon &p,
                const vector2 &a, const vector2 &b)
{
    int n = p.size();
    // 각 점이 반평면 내에 있는지 여부를 우선 확인
    vector<bool> inside(n);
    for (int i=0; i<n; i++)
      inside[i] = ccw(a,b,p[i]) >= 0;
    polygon ret;
    // 다각형의 각 변을 순회하면서 결과 다각형의 각 점을 발견
    for (int i=0; i<n; i++) {
      int j = (i+1) % n;
      // 반평면 내에 있는 점 p[i]는 항상 결과 다각형에 포함
      if(inside[i]) ret.push_back(p[i]);
      // 변 p[i] - p[j] 가 직선과 교차하면 교차점을 결과 다각형에 포함
      if (inside[i] != inside[j]) {
        vector2 cross;
        assert(lineIntersection(p[i], p[j], a, b, cross));
        ret.push_back(cross);
      }
    }
    return ret;
}


// 서덜랜드-호지맨 (Sutherland-Hodgman) 알고리즘을 이용한 다각형 클리핑
polygon intersection(const polygon &p, double x1, double y1,
                     double x2, double y2)
{
    vector2 a(x1, y1), b(x2, y1), c(x2, y2), d(x1, y2);
    polygon ret = cutPoly(p, a, b);
    ret = cutPoly(ret, b, c);
    ret = cutPoly(ret, c, d);
    ret = cutPoly(ret, d, a);
    return ret;
}

// 두 볼록 다각형의 교차 여부를 확인하는 함수
// 두 다각형이 서로 닿거나 겹치는지 여부를 반환한다.
// 한 점이라도 겹친다면 true를 반환
bool polygonIntersects(const polygon &p, const polygon &q) {
  int n = p.size(), m = q.size();
  // 우선 한 다각형이 다른 다각형에 포함되어 있는 경우를 확인하자.
  if (isInside(p[0], q) || isInside(q[0], p)) return true;
  // 이 외의 경우, 두 다각형이 서로 겹친다면 서로 닿는 두 변이 반드시 존재한다.
  for (int i=0; i<n; i++)
      for (int j=0; j<m; j++)
        if (segmentIntersects(p[i], p[(i+1)%n], q[j], q[(j+1)%m]))
          return true;
  return false;
}

소수: 1과 자기자신을 약수로 갖는 숫자

소인수분해: 어떤 정수 N 을 소수의 곱으로만 표현한 것

단순히 배수 판정법으로 문제를 해결할 수 있으나 숫자가 커질수록 시간복잡도가 너무 커져 비효율적이다.

위키에 따르면, 다음과 같은 정리가 성립한다고 한다.

3개 이상의 소수로 구성된  합성수는 그 수의 제곱근보다 작거나 같은 약수를 갖는다.

이에 대한 증명은 다음과 같다.

n 을 합성수라 하자. 그러면  n=ab 로 표현할 때, 1<a,b<n 이다.
만약  a,b 가 둘 다  n의 제곱근보다 크다면 [ a, b > sqrt(n) ]
ab > n 가 되어 n = ab 와 모순이다. 따라서  a,b 중 적어도 하나는 n의 제곱근보다 작거나 같다.

위의 증명때문에 1~N 사이의 숫자로 모두 나눠보지 않아도 N의 제곱근보다 작은 숫자만으로 소인수분해가 가능하다는 걸 알 수 있다.

해당 알고리즘은 for문을 2~sqrt(n) 번 돌리면서 나오는 약수의 소수를 찾아서 배열에 저장한다.

에라토스테네스의 체: 숫자 2부터 N까지 있으면, 각 숫자의 소수임을 판별할 때 배수가 되는 숫자들을 지워나가는 방법으로 속도가 빠르네 메모리 공간을 많이 차지하므로 비트마스크 등 별도의 최적화를 수행하기도 한다.

int n;
bool isPrime[MAX_N+1]; // 숫자 i의 소수 유무

void eratosthenes() {
	memset(isPrime, 1, sizeof(isPrime));
	// 1은 항상 예외 처리
	isPrime[0] = isPrime[1] = false;
	int sqrtn = int(sqrt(n)); // 어떤 약수도 sqrt(n) 을 넘기지 않음
	for (int i=2; i<=sqrtn; i++)
		if (isPrime(i)) // 이 수가 아직 지워지지 않았다면
			for (int j=i*i; j<=n; j+=i)
				isPrime[j] = false;
	// i의 배수 j에 대해 isPrime[j] = false;
	// i*i 미만의 배수들은 이미 처리됨. (2*i, 3*i 등 j=2,3일 때)
}

에라토스테네스의 체를 이용한 빠른 소인수 분해

// minFactor[i]: i의 가장 작은 소인수 저장 (i가 소수인 경우 자기 자신)
int minFactor[MAX_N];
// 에라토스테네스의 체를 수행하면서 소인수분해를 위한 정보도 저장
void eratosthenes2() {
	// 1은 항상 예외 처리
	minFactor[0] = minFactor[1] = -1;
	// 모든 숫자를 처음에는 소수로 표시
	for (int i=2; i<=n; i++)
		minFactor[i] = i;
	// 에라토스테네스의 체를 수행
	int sqrtn = int(sqrt(n));
	for (int i=2; i<=sqrtn; i++) {
		if (minFactor[i] == i)
			for (int j=i*i; j<=n; j+=i)
				if (minFactor[j] == j)
					minFactor[j] = i; // 아직 약수를 본 적 없는 숫자인 경우
	}
}

// 2이상의 자연수 n을 소인수분해한 결과를 반환
vector<int> factor(int n) {
	vector<int> ret;
	// n이 1이 될 때까지 가장 작은 소인수(minFactor)로 나누기를 반복한다.
	while (n > 1) {
		ret.push_back(minFactor[n]);
		n /= minFactor[n];
	}
	return ret;
}