1. 유래
유대인 역사가 플라비우스 요세푸스가 겪은 경험을 바탕으로 만들어진 문제이다.당시 예루살렘에서 살았던 요세푸스는 유대-로마 전쟁 때 유대군 장교로 참전했다가 동료 병사들, 자신을 포함해 총 41명과 함께 요타파타[1]에서 서기 70년에 황제가 될 베스파시아누스가 지휘하는 로마군에게 포위되었고, 동료들은 로마군의 손에 죽느니 스스로 죽겠다고 집단자살하기로 했다. 그러나 직접 자살하는 것이 어려웠는지, 그들은 서로 죽이기 위한 알고리즘을 세운다. 요세푸스를 따라온 동료들은 위의 그림과는 다르게 2명 살리고 한 명 죽이는 식으로 자살했다.[2] 그러나 요세푸스는 동료들의 뜻에 반대하고 살고 싶었고, 수학적 논리력을 발휘하여 끝까지 살기 위한 자리를 찾아서 결국 살아남아 베스파시아누스에게 항복했다.
2. 문제
1부터 41까지의 숫자를 원형으로 배치한 다음, 1부터 시작하여 다음 숫자로 넘어가며 숫자를 하나 건너뛰고 다음 숫자를 제거하는 것을 반복하여 마지막에 남는 숫자를 구하는 문제이다. 출처이 문제의 일반화된 버전도 존재한다. 두 자연수 [math(n)]과 [math(k)]가 주어졌을 때, [math(1)]부터 [math(n)]까지의 자연수를 원형으로 배치한 다음, [math(1)]부터 시작하여 [math(k-1)]개의 수를 건너뛰고 그 다음 [math(k)]번째 수를 제거하는 것을 숫자가 하나만 남을 때까지 반복했을 때, 마지막으로 남는 수가 무엇인지 구하는 것이다. 변형된 형태로 마지막에 남은 수뿐 아니라 제거된 수의 순서를 물어보는 경우도 있다. 예를 들어 [math(n=7, \; k=3)]인 경우, [math(3, \; 6, \; 2, \; 7, \; 5, \; 1)]의 순서로 제거된 후 [math(4)]가 마지막으로 남는다. 원본 문제는 [math(n=41, \; k=2)]인 경우이다.
3. 풀이
마지막에 남는 수만 알아내면 되는 경우와, 제거된 수의 순서도 알아내야 하는 경우의 효율적인 풀이가 다르다.본 항목에서 배열의 첫 번째 원소는 인덱스 1로 표시한다. 즉, 원소의 번호는 1부터 시작한다.
3.1. 제거되는 순서와 마지막 남은 수를 모두 구하는 풀이
이 경우엔 문제의 상황을 그대로 구현하여 풀게 된다. 즉, 이 항목의 풀이는 모두 [math(n)]개의 수를 적어놓고 지워지는 수를 직접 세어서 푸는 형태이다. 이 방법은 상대적으로 느리지만, 제거되는 수의 순서까지 모두 파악할 수 있다는 장점이 있다.3.1.1. 배열
n개의 수를 저장하는 배열을 [1, 1, ..., 1]과 같이 선언해서, 왼쪽부터 직접 k개씩 세어가며 수가 제거될 때 해당 위치에서 배열의 값을 0으로 바꾸는 방법이다. 사람에게 손으로 직접 문제를 풀으라고 할 때 가장 먼저 떠올릴 만한 방법을 선형으로 펼친 형태이다.- n개의 1을 저장하는 배열 live = [1, 1, ..., 1]를 선언한다. 이후 live[x]=1이면 x는 아직 제거되지 않은 것이고, live[x]=0이면 x는 제거된 것이다.
- 변수 x=1을 선언한다. 이후 과정에서 x가 제거될 수인지 아닌지 판단하는 과정을 반복적으로 거치게 된다.
- 다음을 n-1회 반복한다.
- 변수 c=1을 선언한다. c는 제거할 수를 고르기 위한 변수로, 지금 보는 수 x가 최근에 제거한 수로부터 몇 번째 수인지를 의미한다.
- 다음을 하나의 수가 제거될 때까지 반복한다.
- live[x]=0이라면 그대로 둔다.
- live[x]=1이라면,
- c=k라면 live[x]=0으로 바꾼다. 이는 다음으로 제거되는 수가 x라는 의미이므로, ans에 x를 추가한다. c!=k라면 그대로 둔다.
- 이후 c에 1을 더한다. live[x]=0이라면 c에 1을 더하지 않음에 유의한다.
- 이후 x에 1을 더한다. 더한 후 x=n+1이라면 x=1로 바꾼다.
- live[x]=1인 남은 x가 마지막으로 남는 수이다.
수를 제거하는 과정에서 남은 수의 개수가 k보다 작아진다면 위 알고리즘의 3번 과정은 배열을 여러 차례 돌게 된다. 이를 방지하기 위해 수를 세는 횟수를 k가 아닌 (k-1)%(남은 수의 개수)+1로 바꿔서 최적화할 수 있다.
이를 적용한 파이썬 코드는 아래와 같다. 아래 코드에서 수를 세는 횟수를 바꾼 값이 변수 t에 저장된다.
- [ 파이썬 코드 펼치기 · 접기 ]
#!syntax python def josephus(n, k): live = [1]*(n+1) # 파이썬에선 인덱스가 0부터 시작하므로 크기를 n+1로 잡는다. live[0] = 0 ans = [] x = 1 for i in range(n-1): c = 1 t = (k-1) % (n-i) + 1 prev = len(ans) # 하나의 수가 제거되는 순간을 포착하기 위해 사용한다. while len(ans) == prev: # 수가 제거되어 ans가 더 길어지면 루프 탈출 if live[x] == 1: if c == t: live[x] = 0 ans.append(x) c += 1 x += 1 if x == n+1: x = 1 last = live.index(1) # 마지막 남은 수 ans.append(last) return ansjosephus(n, k)는 주어진 n과 k에 대해 제거되는 수와 마지막에 남는 수를 순서대로 담은 리스트를 반환한다.
위 풀이의 시간복잡도는 [math(\mathcal{O} \left( n^2 \right))]이다.
3.1.1.1. 세그먼트 트리
배열을 활용한 풀이에서 배열을 구간합 세그먼트 트리에 저장하면, 다음으로 제거할 수를 이분 탐색으로 찾을 수 있게 된다. 이때, 다음으로 제거할 수를 찾는 데와 해당 수를 제거하는 데에 모두 [math(\mathcal{O} \left( \log{n} \right))]의 시간이 들어가므로, 전체 시간복잡도가 [math(\mathcal{O} \left( n\log{n} \right))]으로 대폭 개선된다.3.1.2. 원형 연결리스트
1부터 n까지의 수를 순서대로 원형 연결리스트에 넣은 다음, 1부터 시작해서 k개의 수를 세어가며 제거할 수를 찾는 방법이다.- 원형 연결리스트에 1부터 n까지의 수를 순서대로 넣는다. 이때 각 수는 시계방향 순서로 배열되어 있다고 가정한다.
- n부터 시작하여 다음을 n-1회 반복한다.
- 시계방향으로 k칸 이동한다.
- 가리키고 있는 수를 삭제한다. 삭제된 수가 다음으로 제거되는 수이다. 삭제 후에는 그 반시계방향 바로 옆에 있는 수를 가리킨다.
- 리스트에 남아있는 수가 마지막에 남는 수이다.
문제의 상황을 가장 그대로 받아들여서 시뮬레이션하는 풀이로, 덕분에 과정도 단순하다. 이 방법에서도 배열에서 사용한 최적화 방법을 동일하게 적용하여 이동 횟수를 줄임으로써, 리스트를 여러 번 빙빙 도는 것을 방지하는 최적화를 적용할 수 있다.
위 풀이의 시간복잡도는 [math(\mathcal{O} \left( nk \right))]이다. k회 이동하는 것을 약 n회 반복하기 때문이다. 최적화를 적용할 경우 기존 시간복잡도와 [math(\mathcal{O} \left( n^2 \right))] 중 빠른 쪽의 복잡도를 갖는다.
3.1.3. 큐
원형 연결리스트를 사용하는 방법과 유사하게 문제의 상황을 그대로 시뮬레이션하는 방법이지만, 원형인 문제 상황을 일자로 펴서 구현하는 방식이다. 이를 효율적으로 구현하기 위해 다음과 같이 큐를 활용하게 된다.- 큐에 1부터 n까지 작은 수부터 순서대로 삽입한다.
- 다음을 n-1회 반복한다.
- k-1회 큐에서 수를 꺼낸 다음 곧바로 다시 삽입한다.
- 큐에서 수를 하나 꺼낸다. 이 수가 다음으로 제거되는 수이며, 다시 삽입하지 않는다.
- 큐에 남아있는 수가 마지막에 남는 수이다.
사실상 연결리스트를 활용한 방법과 동일한 원리로 작동하므로 동일한 최적화 방식 역시 적용할 수 있고, 시간복잡도 역시 [math(\mathcal{O} \left( nk \right))]이다.
3.1.4. 이진 탐색 트리
이진 탐색 트리(BST)는 일종의 항상 정렬된 배열로 생각할 수 있으며, 트리에서의 동적 프로그래밍을 활용하면 BST 내의 x번째 수에 [math(\mathcal{O} \left( \log{n} \right))] 안에 접근할 수 있다. 또한, BST는 임의의 원소를 중간에 삽입 또는 삭제하는 것도 [math(\mathcal{O} \left( \log{n} \right))] 안에 수행하므로, 이를 시뮬레이션에 활용할 수 있다.초기에 1부터 N까지의 수를 노드로 갖는 BST를 생성한 다음, 매 차례 몇 번째 수를 제거하면 되는지 계산하여 해당 수를 BST에서 제거하면 된다. 이때, BST를 처음 생성할 때에 균형이 깨지지 않도록 생성하거나, 자가 균형 이진 탐색 트리를 활용해야 검색 및 삭제 시에 [math(\mathcal{O} \left( \log{n} \right))]의 시간복잡도가 보장된다.
초기에 BST를 생성할 때 [math(\mathcal{O} \left( n \right))], 그리고 [math(n)]회에 걸쳐 [math(\mathcal{O} \left( \log{n} \right))]이 소요되는 검색 및 삭제를 수행하므로, 총 시간복잡도는 [math(\mathcal{O} \left( n\log{n} \right))]이다.
3.2. 마지막 남은 수만 구하는 풀이
마지막에 남은 수만 구하면 될 경우 훨씬 효율적인 풀이가 존재한다.본 항목에선 [math(f( n, \; k ))]를 주어진 n과 k에 대해 마지막에 남는 수로 정의한다.
3.2.1. 일반적인 경우
[math(f ( n, \; k ))]는 다음과 같은 점화식을 만족한다.[math(f ( n, \; k ) = \left( \left( f( n-1, \; k ) + k - 1 \right ) \mod{n} \right) + 1)]
이해를 돕기 위해 [math(f(7, 3))]을 구하기 위해 큐를 활용한 풀이를 수행하는 상황을 생각해보자. 처음엔 큐에 [1,2,3,4,5,6,7]이 들어있을 것이고, 첫 번째 루프가 시행된 후 3이 제거되고 큐는 [4,5,6,7,1,2]가 될 것이다. 이후, 원소가 6개 남아있는 이 큐에 대해 2개의 수를 꺼낸 후 삽입하고, 수를 하나 꺼내어 제거하는 것을 하나의 수가 남을 때까지 반복하여 답을 구하게 될 것이다. 이때 사용하는 큐를 [math(X)]라고 하자.
그런데 이를 관찰해보면 이때 큐 [math(X)]에 일어나는 일은, [math(f(6, 3))]을 계산하는 과정에서 초기 큐인 [1,2,3,4,5,6]에 적용하는 연산과 완전히 동일하다. 이 큐를 [math(Y)]라고 부르기로 하면, 이는 곧 [math(X)]와 [math(Y)]의 원소가 그 순서 그대로 1대1 대응된 채로 수가 하나 남을 때까지 같은 연산이 반복된다는 의미이다. 즉, [math(f(7, 3))]을 구하기 위해 큐 [math(X)]에서 2개의 수를 꺼냈다가 넣고 하나의 수를 제거하는 행위가, [math(f(6, 3))]을 구하기 위해 큐 [math(Y)]에서 시행하는 연산과 1대1로 원소가 대응된 채로 동일하다는 뜻이다.
| X | 4 | 5 | 6 | 7 | 1 | 2 | |||||||||||||
| Y | 1 | 2 | 3 | 4 | 5 | 6 | |||||||||||||
| 1회 연산 후... | |||||||||||||||||||
| X | 7 | 1 | 2 | 4 | 5 | ||||||||||||||
| Y | 4 | 5 | 6 | 1 | 2 | ||||||||||||||
이때 큐 [math(Y)]에 있는 각각의 원소에 3을 더해서, 7보다 큰 원소에 한해 7을 빼주면 큐 [math(X)]에 대응되는 원소가 된다. 즉, 큐 [math(Y)]에 있는 임의의 원소 [math(Y[i])]에 대해 [math(X[i] = \left(\left( Y[i]+3 \right )-1 \mod{7} \right ) + 1)]로 적을 수 있다. 한편 [math(f(7, 3))]의 값은 [math(X)]에 수가 하나 남을 때까지 연산을 반복한 결과이고, [math(f(6, 3))]의 값은 [math(Y)]에 수가 하나 남을 때까지 동일한 연산을 반복한 결과이므로, [math(f(7, 3))]의 값은 위 식에 [math(f(6, 3))]을 그대로 대입한 [math(\left(\left( f(6,3)+3 \right )-1 \mod{7} \right ) + 1)]이 된다.
이를 일반화하면 위 점화식을 얻게 된다. 기저 케이스는 [math(n=1)]인 경우로, 시작부터 수가 1개뿐이면 그 수가 마지막에 남는 수이므로 [math(f(1, \; k) = 1)]이다. 이 케이스부터 시작해서 위 점화식을 적용하면 [math(\mathcal{O} \left( n \right))] 안에 [math(f(n, \; k))]를 구할 수 있다.
3.2.2. k=2인 경우
[math(n = 2^m + l \; \left( 0 \leq l < 2^m \right))]으로 [math(n)]을 표현했을 때, [math(f(n, \; 2) = 2l+1)]이다.| [math(n)] | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | ... |
| [math(f(n,\ 2))] | 1 | 1 | 3 | 1 | 3 | 5 | 7 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | ... |
3.2.3. n이 매우 크고 k가 작은 경우
출처[math(f(n,\ k))]는 다음과 같은 점화식으로도 표현된다. [math(g(n,\ k):=f(n,\ k)-1)]로 정의하면 다음과 같은 식이 성립한다.
[math(g(n,\ k) = \begin{cases}
0 & \mathrm{if} \ n=1 \\
\left( g(n-1,\ k)+k \right ) \mod{n} & \mathrm{if} \ 1<n<k \\
\mathrm{for} \ h := g(n - \lfloor \frac{n}{k} \rfloor,\ k ) - \left( n \mod{k} \right ), \quad \begin{cases}
h+n & \mathrm{if}\ h<0 \\
h+ \lfloor \frac{h}{k-1} \rfloor & \mathrm{otherwise}
\end{cases} & \mathrm{otherwise}
\end{cases})]위 점화식은 앞선 점화식과 발상은 같으나, 해당 1대1 대응의 논리를 [math(n)]개의 수를 한 바퀴 돌면서 [math(\lfloor \frac{n}{k} \rfloor)]개의 수를 한번에 제거한 다음 따지는 식으로 얻을 수 있다. 시간복잡도는 [math(\mathcal{O} \left( k \log{n} \right))]이다.