요세푸스 문제

전산학이나 수학에서 요세푸스 문제(Josephus problem) 혹은 요세푸스 순열(Josephus permutation)은 다음과 같이 정의한다.

n과 k가 자연수이고, k < n이라고 가정한다. n명이 동그랗게 모여있을 때 임의의 한 명부터 순서를 세어 k번째 사람을 모임에서 제외한다. 남은 n-1명에서 다시 다음 사람부터 순서를 세서 k번째 사람을 모임에서 제외한다. 이것을 아무도 남지 않을 때까지 계속해서 반복한다. 이때 모임에서 제외되는 사람의 순서를 (n, k) 요세푸스 순열이라고 하며 마지막으로 제외되는 사람을 구하는 문제를 요세푸스 문제라고 한다.

예를 들어 (7,3) 요세푸스 순열은 {3,6,2,7,5,1,4}이며 4번째 위치한 사람이 마지막으로 제외되게 된다.

이 순열은 역사가 요세푸스가 겪은 일화에서 유래하였다.

해결법

요세푸스 문제를 해결하는 O(n)의 시간복잡도를 가지는 알고리즘이 존재한다.

n이 1이라고 가정하면 다음과 같이 초항을 구할 수 있다.

$f(1,k)=1\,$

n과 k사이의 관계식을 구하면 다음과 같다.

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

만약 사람의 순서를 1번째부터 n번째로 두는 대신 0번째부터 n-1번째로 가정하면 다음과 같이 관계식을 단순화할 수 있다.

$g(n,k)=(g(n-1,k)+k){\bmod {n}},{\text{ }}g(1,k)=0$

만약 n이 매우 큰 수이고, k가 상대적으로 작은 수 일 때, 빠르게 답을 구할 수 있다는 사실이 알려져 있다. http://stackoverflow.com/questions/4845260/josephus-for-large-n-facebook-hacker-cup에서 조세퍼스 문제에 대한 O(k log n) 알고리즘을 구현한 코드를 확인할 수 있다.