요세푸스 문제 문서 원본 보기

{{위키데이터 속성 추적}}
[[컴퓨터 과학|전산학]]이나 [[수학]]에서 '''요세푸스 문제'''(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번째 위치한 사람이 마지막으로 제외되게 된다.

이 순열은 역사가 [[플라비우스 요세푸스|요세푸스]]가 겪은 일화에서 유래하였다. {{출처|날짜=2021-02-12}}

== 해결법 ==
요세푸스 문제를 해결하는 [[점근 표기법|O]](n)의 시간복잡도를 가지는 알고리즘이 존재한다.

''n''이 1이라고 가정하면 다음과 같이 초항을 구할 수 있다.
: <math>f(1,k)=1\,</math>
''n''과 ''k''사이의 관계식을 구하면 다음과 같다.
: <math>f(n,k)=((f(n-1,k)+k-1) \bmod n)+1</math>
만약 사람의 순서를 1번째부터 n번째로 두는 대신 0번째부터 n-1번째로 가정하면 다음과 같이 관계식을 단순화할 수 있다.
: <math>g(n,k)=(g(n-1,k)+k) \bmod n,\text{ }g(1,k)=0</math>

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

{{토막글|조합론}}

[[분류:조합론]]
[[분류:순열]]
[[분류:수학 문제]]
[[분류:계산 문제]]