이 글은 요세푸스 문제(Josephus Problem)가 무엇인지, 그리고 요세푸스 문제의 해법에 대한 내용을 대략적으로 정리해둔 글이다.
1. 유래
요세푸스 문제는 1세기 로마시대의 유대인 역사가인 플라비우스 요세푸스(Titus Flavius Josephus)의 이름을 따 이름붙은 문제로 그 유래는 다음과 같다.
유대-로마 전쟁이 일어나던 시기, 요세푸스와 40명의 동료가 로마군에게 포위되었다. 동료들은 로마군에게 죽을 바에는 스스로 목숨을 끊기로 결정한다. 그러나 유대교에서 자살은 불명예스러운 죽음이므로, 서로 대신 죽여주기로 결정하였다.
구체적인 방법은 전해지지 않지만 그 방법에 대한 야사가 존재한다. 요세푸스와 동료들은 원형으로 둘러앉아, 앉은 순서대로 3명에 한 명씩 규칙적으로 죽여나갔다는 것이다. 그러나 다른 동료들과 달리 죽고싶지 않았던 요세푸스와 그의 친구는 기지를 발휘해 그 둘이 마지막까지 생존할 자리를 계산했고, 그 둘은 결국 죽지 않고 살아남게 된다. 이후 둘은 로마군에 투항하게 된다.
요세푸스와 그 친구가 앉아있던 위치는 어디였을까? 이 글을 읽고 문제를 해결해보자.
2. 요세푸스 문제(Josephus problem)와 요세푸스 순열(Josephus permutation)
이 글에서 요세푸스 문제(Josephus problem)는 다음과 같은 문제를 의미한다.
두 양의 정수 n과 k가 주어진다.
0부터 n - 1까지의 양의 정수를 시계방향으로 차례대로 원형으로 배치하고 0부터 시작해 시계방향으로 k-1개의 수를 건너뛰고 k번째 수를 제거하는 것을 하나의 정수가 남을 때까지 반복할 때, 마지막으로 남은 정수는 무엇일까?
정수의 index가 1이 아닌 0부터 시작함에 유의하자. 1이 아닌 0부터 시작하는 것으로 문제를 정의한 이유는 풀이를 더욱 간결하게 서술하기 위해서이다.
유래의 상황은 n = 41이고 k = 3인 요세푸스 문제의 상황과 매우 유사하다는 점을 관찰할 수 있다. (유래에서는 총 두 명이 살아남는다는 점이 다르다.)
또한, 위의 과정(단, 여기에서는 모든 정수가 제거될 때까지 반복한다)에서 제거되는 정수들을 차례로 나열해 얻는 순열을 요세푸스 순열(Josephus permutation)이라 한다.
다음 문단부터는 요세푸스 순열을 구하는 알고리즘과 요세푸스 문제를 해결하는 알고리즘에 대해 알아보자.
3. 요세푸스 순열을 구하는 알고리즘
3.1. O(nk) 해법
가장 단순한 풀이 중 하나로 큐(queue) 자료구조를 이용해 요세푸스 문제의 시행을 직접 시뮬레이션하는 풀이가 존재한다. 구체적으로, 다음과 같이 문제를 해결할 수 있다.
(1) 1부터 n까지의 양의 정수가 차례대로 들어있는 큐를 준비한다.
(2) 큐의 앞에 있는 원소 x를 빼고, 다시 x를 큐에 넣는 것을 k-1번 반복한다.
(3) 큐의 앞에 있는 원소 x를 뺀다. 이 x가 다음으로 제거되는 수이다.
(4) 큐에 원소가 남아있다면 2로 돌아간다.
큐의 앞에 있는 원소를 빼고 넣는(O(1)) 작업을 k번 반복해 다음 수를 얻는 것을 n번 시행해 문제를 해결하므로 이 해법의 시간복잡도는 O(nk)이다.
3.2. O(nlgn) 해법
위 방법보다 조금 더 빠른 풀이로 세그먼트트리를 이용한 방법이 있다.
구체적으로, 구간합을 다루는 세그먼트트리를 이용해 남아있는 수중 다음 k번째 수가 무엇인지를 세그먼트트리 위에서의 이진탐색으로 찾아내고 해당 수를 0으로 업데이트하는 것을 반복해 문제를 해결할 수 있다. 각 작업의 시간복잡도는 O(lgn)이므로 전체 시간복잡도는 O(nlgn)이 된다.
4. 요세푸스 문제를 해결하는 알고리즘
두 양의 정수 n과 k에 대하여 J(n, k)를 n과 k에 대한 요세푸스 문제의 해답으로 정의하자.
4.1. 요세푸스 순열을 구해 해결하는 방법
위의 3문단에서 구한 요세푸스 순열의 마지막 수는 요세푸스 문제의 해답과 같다. 따라서 3문단에서 소개한 방법들을 이용해 요세푸스 문제를 O(nk)또는 O(nlgn)에 해결할 수 있다.
4.2. O(n) 해법
두 양의 정수 n과 k에 대하여 J(n, k)에 대해 다음과 같은 점화관계가 성립함을 관찰할 수 있다.
J(n, k) = (J(n-1, k) + k) % n
이와 같은 점화관계를 이용해 요세푸스 문제를 O(n)에 해결할 수 있다.
4.3. O(klgn) 해법
k가 n에 비해 크기가 많이 작은 경우 O(n)보다 더욱 빠르게 작동하는 풀이 또한 존재한다. 이 방법은 위의 점화관계를 차례대로 한 단계씩 계산하는 대신 한 바퀴 단위로 계산하는 것으로 효율의 상승을 꾀한다.
구체적으로, 두 양의 정수 n과 k에 대하여 n을 k로 나눈 몫을 p라 정의하자. 이 때, 다음과 같은 점화관계가 성립함을 관찰할 수 있다.
J(n, k) = (J(n-p, k) + pk) % n
단, p = 0인 경우 위의 식은 더 이상 사용할 수 없으므로 4.2의 식을 이용해 마저 계산을 이어나가자.
아래는 위 점화식을 이용해 요세푸스 문제를 해결할 때의 시간복잡도를 계산하는 과정이다:
두 양의 정수 n과 k에 대하여, 위와 같은 단계를 x회 거친 뒤 남는 정수의 개수는 대략 n*(1 - 1/k)^x로 계산해낼 수 있다. 남는 정수의 개수가 하나가 될 때까지 이를 반복한다고 이상적으로 생각하면 대략적으로 n*(1 - 1/k)^x = 1와 같은 관계식을 얻을 수 있고, 이 식으로부터 x = - lgn / lg(1 - 1/k)를 얻어낼 수 있다. 따라서 이 과정의 시간복잡도는 O(x) = O(klgn)과 같다는 것을 알 수 있다. p = 0 이후의 계산 횟수는 O(k)이므로 이 값은 시간복잡도에 영향을 주지 않음을 확인하자.
4.4. k=2인 경우(O(1) 해법)
유래의 상황과 같이 k=2인 경우에는 더욱 빠른 풀이가 존재한다. 바로 공식을 이용하는 것이다.
구체적으로, k=2인 경우 다음과 같은 공식으로 답을 구할 수 있다:
n = 2^m+l, l<2^m을 만족하는 음이 아닌 정수 m과 l에 대하여, J(n, 2) = 2*l + 1이다.
증명은 귀납법을 이용하여 간단히 할 수 있다.
위 공식을 활용하면 n의 이진표기에서 최상위 비트(msb;most-significant bit) 1을 지우고 최하위 비트(lsb;least-significant bit) 1을 하나 추가하는 것으로 문제를 해결할 수 있다는 것을 알 수 있다.
5. 연습문제 추천
이제 개념 연습문제를 풀면서 요세푸스 문제와 그 풀이를 더 깊이 이해하고 PS/CP 연습문제를 풀면서 코드로 직접 구현해보자. ★이 붙은 문제는 꼭 풀어보고 넘어가자.
5.1. 개념 연습문제
★(1) 1부터 41까지의 양의 정수를 시계방향으로 차례대로 원형으로 배치하고 1부터 시작해 시계방향으로 두 개의 수를 건너뛰고 세번째 수를 제거하는 것을 두 개의 정수가 남을 때까지 반복할 때, 마지막으로 남은 정수 두 개는 무엇일까?
(2) 세 양의 정수 n, m과 k가 주어질 때, 다음과 같은 문제의 해답을 J'(n,m,k)라 하자. (단, m<n)
0부터 n - 1까지의 양의 정수를 시계방향으로 차례대로 원형으로 배치하고 0부터 시작해 시계방향으로 k-1개의 수를 건너뛰고 k번째 수를 제거하는 것을 m개의 정수가 남을 때까지 반복할 때, 남겨진 정수들의 집합을 구하시오.
J'(n,m,k)의 값을 O(nm)에 찾아내는 알고리즘을 설계해보자.
(3) 임의의 짝수 2n에 대하여 1부터 2n까지의 양의 정수를 시계방향으로 차례대로 원형으로 배치하고 1부터 시작해 시계방향으로 k - 1개의 수를 건너 뛰고 k번째 수를 제거하는 것을 n개의 정수가 남을 때까지 반복하자. 이 때, (a) n+1 이상 2n 이하의 정수들만 남게 하는 k가 존재할까? 또한 (b) 1 이상 n 이하의 정수들만 남게 하는 k가 존재할까? 이유와 함께 설명해보자.
5.2. PS/CP 연습문제(BOJ)
6. 인용
'휴지통 > 기타' 카테고리의 다른 글
| [Recreation] 6174와 Kaprekar's routine, Kaprekar's constant (0) | 2022.05.29 |
|---|---|
| [조합론] Erdős–Szekeres Theorem (0) | 2021.02.28 |