요세푸스 문제¶

문제 설명¶

자연수 $n$과 $k$가 주어집니다. $1$부터 $n$까지의 모든 자연수가 원형으로 적혀 있습니다. 먼저 첫 번째 수부터 세어 $k$번째 수를 삭제합니다. 그다음 바로 다음 수부터 다시 $k$개의 수를 세어 $k$번째 수를 또 제거하며, 이 과정을 계속 반복합니다. 수가 하나만 남으면 과정이 끝납니다. 마지막으로 남는 수를 구해야 합니다.

이 문제는 1세기에 플라비우스 요세푸스가 제시했습니다(다만 $k = 2$인 경우로 다소 좁혀진 형태였습니다).

이 문제는 과정을 그대로 시뮬레이션하여 풀 수 있습니다. 브루트 포스 시뮬레이션은 $O(n^{2})$에 동작합니다. 세그먼트 트리를 사용하면 이를 $O(n \log n)$으로 개선할 수 있습니다. 하지만 이보다 더 나은 방법을 찾고자 합니다.

$O(n)$ 풀이 시뮬레이션¶

문제 $J_{n, k}$의 답을 이전 문제들의 해를 통해 나타내는 패턴을 찾아보겠습니다.

브루트 포스 시뮬레이션을 사용하면 예를 들어 다음과 같은 값의 표를 만들 수 있습니다.

$$\begin{array}{ccccccccccc} n\setminus k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 2 & 1 & 2 & 1 & 2 & 1 & 2 & 1 & 2 & 1 \\ 3 & 3 & 3 & 2 & 2 & 1 & 1 & 3 & 3 & 2 & 2 \\ 4 & 4 & 1 & 1 & 2 & 2 & 3 & 2 & 3 & 3 & 4 \\ 5 & 5 & 3 & 4 & 1 & 2 & 4 & 4 & 1 & 2 & 4 \\ 6 & 6 & 5 & 1 & 5 & 1 & 4 & 5 & 3 & 5 & 2 \\ 7 & 7 & 7 & 4 & 2 & 6 & 3 & 5 & 4 & 7 & 5 \\ 8 & 8 & 1 & 7 & 6 & 3 & 1 & 4 & 4 & 8 & 7 \\ 9 & 9 & 3 & 1 & 1 & 8 & 7 & 2 & 3 & 8 & 8 \\ 10 & 10 & 5 & 4 & 5 & 3 & 3 & 9 & 1 & 7 & 8 \\ \end{array}$$

여기에서 다음과 같은 패턴을 분명히 확인할 수 있습니다.

$$J_{n,k} = \left( (J_{n-1,k} + k - 1) \bmod n \right) + 1$$

$$J_{1,k} = 1$$

여기서는 1-인덱싱 때문에 식이 다소 지저분해집니다. 대신 위치에 0부터 번호를 매기면 매우 깔끔한 식을 얻을 수 있습니다.

$$J_{n,k} = (J_{n-1,k} + k) \bmod n$$

이렇게 하여 $O(n)$번의 연산으로 동작하는 요세푸스 문제의 풀이를 찾았습니다.

구현¶

간단한 재귀 구현 (1-인덱싱 기준)

int josephus(int n, int k) {
    return n > 1 ? (josephus(n-1, k) + k - 1) % n + 1 : 1;
}

비재귀 형태 :

int josephus(int n, int k) {
    int res = 0;
    for (int i = 1; i <= n; ++i)
      res = (res + k) % i;
    return res + 1;
}

이 식은 해석적으로도 유도할 수 있습니다. 여기서도 0-인덱싱을 가정합니다. 첫 번째 수를 삭제하고 나면 $n-1$개의 수가 남습니다. 과정을 반복할 때는 원래 인덱스가 $k \bmod n$이었던 수부터 시작하게 됩니다. $0$부터 세기 시작한다면 $J_{n-1, k}$가 남은 원에 대한 답이 되지만, 실제로는 $k$부터 시작하므로 $J_{n, k} = (J_{n-1,k} + k) \ \bmod n$이 성립합니다.

$O(k \log n)$ 풀이 시뮬레이션¶

비교적 작은 $k$에 대해서는 위의 $O(n)$ 재귀 풀이보다 더 나은 풀이를 고안할 수 있습니다. $k$가 $n$보다 훨씬 작다면, 한 번의 순회에서 일일이 반복하지 않고 여러 개의 수($\lfloor \frac{n}{k} \rfloor$개)를 한꺼번에 삭제할 수 있습니다. 그러고 나면 $n - \lfloor \frac{n}{k} \rfloor$개의 수가 남고, $(\lfloor \frac{n}{k} \rfloor \cdot k)$번째 수부터 시작하게 됩니다. 따라서 그만큼 위치를 이동시켜야 합니다. $\lfloor \frac{n}{k} \rfloor \cdot k$는 단순히 $-n \bmod k$라는 것을 알 수 있습니다. 그리고 $k$번째 수마다 제거했으므로, 결과 인덱스 앞에서 제거한 수의 개수를 더해야 합니다. 이는 결과 인덱스를 $k - 1$로 나누어 계산할 수 있습니다.

또한 $n$이 $k$보다 작아지는 경우를 처리해야 합니다. 이 경우 위의 최적화는 무한 루프를 일으키게 됩니다.

구현 (편의상 0-인덱스 기준):

int josephus(int n, int k) {
    if (n == 1)
        return 0;
    if (k == 1)
        return n-1;
    if (k > n)
        return (josephus(n-1, k) + k) % n;
    int cnt = n / k;
    int res = josephus(n - cnt, k);
    res -= n % k;
    if (res < 0)
        res += n;
    else
        res += res / (k - 1);
    return res;
}

이 알고리즘의 복잡도를 추정해 봅시다. 먼저 $n < k$인 경우는 기존 풀이로 처리하며, 이 경우 기존 풀이는 $O(k)$에 동작한다는 점에 유의하십시오. 이제 알고리즘 자체를 살펴봅시다. 실제로 매 반복마다 $n$개의 수 대신 $n \left( 1 - \frac{1}{k} \right)$개의 수가 남으므로, 알고리즘의 전체 반복 횟수 $x$는 대략 다음 방정식으로 구할 수 있습니다:

$$ n \left(1 - \frac{1}{k} \right) ^ x = 1, $$

양변에 로그를 취하면 다음을 얻습니다:

$$\ln n + x \ln \left(1 - \frac{1}{k} \right) = 0,$$ $$x = - \frac{\ln n}{\ln \left(1 - \frac{1}{k} \right)},$$

로그를 테일러 급수로 전개하면 다음과 같은 근사 추정치를 얻습니다:

$$x \approx k \ln n$$

따라서 이 알고리즘의 복잡도는 실제로 $O (k \log n)$입니다.

$k = 2$에 대한 해석적 해법¶

이 특수한 경우(요세푸스 플라비우스가 이 문제를 제시한 경우)에는 문제를 훨씬 쉽게 풀 수 있습니다.

$n$이 짝수인 경우 모든 짝수가 지워지고 나면 $\frac{n}{2}$에 대한 문제가 남으므로, $n$에 대한 답은 $\frac{n}{2}$에 대한 답에 2를 곱하고 1을 빼서(위치 이동에 따라) 얻을 수 있습니다:

$$ J_{2n, 2} = 2 J_{n, 2} - 1 $$

마찬가지로 $n$이 홀수인 경우 모든 짝수가 지워진 다음 첫 번째 수가 지워지고 $\frac{n-1}{2}$에 대한 문제가 남으므로, 위치 이동을 고려하면 두 번째 공식을 얻습니다:

$$J_{2n+1,2} = 2 J_{n, 2} + 1 $$

이 점화 관계를 구현에 그대로 사용할 수 있습니다. 이 패턴은 다른 형태로 바꾸어 표현할 수 있습니다. $J_{n, 2}$는 모든 홀수로 이루어진 수열을 나타내며, $n$이 2의 거듭제곱이 될 때마다 1부터 "다시 시작"합니다. 이는 하나의 공식으로 쓸 수 있습니다:

$$J_{n, 2} = 1 + 2 \left(n-2^{\lfloor \log_2 n \rfloor} \right)$$

$k > 2$에 대한 해석적 해법¶

문제의 형태가 단순하고 이 문제 및 관련 문제에 대한 논문이 많음에도 불구하고, 요세푸스 문제의 해에 대한 간단한 해석적 표현은 아직 발견되지 않았습니다. $k$가 작은 경우에는 몇 가지 공식이 유도되어 있지만, 실제로 적용하기는 모두 어려운 것으로 보입니다(예를 들어 Halbeisen, Hungerbuhler의 "요세푸스 문제"와 Odlyzko, Wilf의 "함수 반복과 요세푸스 문제"를 참고하십시오).