요세푸스 문제

2. 역사

요세푸스 문제는 1세기에 살았던 유대인 역사가이자 지도자인 플라비우스 요세푸스의 이름에서 유래되었다. 요세푸스는 요드팟 포위전에서 40명의 병사들과 함께 로마군에 갇혔는데, 포로로 잡히는 대신 자살을 택했다. 그들은 제비를 뽑아 서로를 죽이기로 결정했고, 요세푸스는 운 좋게, 혹은 신의 섭리로 마지막까지 살아남아 항복했다.^[1] 이 이야기는 요세푸스의 《유대 전쟁》 3권 8장 7절에 기록되어 있다.

이때 사용된 방법에 대한 자세한 내용은 명확하지 않다. 제임스 도디와 마이클 메이즈에 따르면, 1612년 클로드 가스파르 바셰 드 메지리악은 사람들을 원형으로 배치하고 3명씩 세어 제거하는 방식을 제안했다. 이 이야기는 여러 차례 반복되었으며, 세부 사항은 출처에 따라 다르다. 이스라엘 네이선 허스타인과 어빙 카플란스키는 요세푸스와 39명의 동료가 원을 이루고 7번째 사람마다 제거되었다고 설명한다.

요세푸스는 자신의 생존을 "신의 섭리"인지 "운"인지 질문했지만,^[1] 요세푸스의 슬라브어 필사본에는 그가 "숫자를 교묘하게 세고, 다른 모든 사람을 속였다"는 다른 이야기가 전해진다.^[1][2] 요세푸스에게는 공범이 있었고, 마지막 두 생존자의 자리를 찾는 것이 문제였다고 한다. 그는 자신과 다른 사람을 31번째와 16번째 자리에 배치했다고 알려져 있다.

서기 370년경 헤게시푸스(편의상)라는 인물이 플라비우스 요세푸스의 『유대 전쟁』을 바탕으로 쓴 문제에서 요세푸스 문제의 기원이라고 여겨진다. 해당 기록에 따르면, 유대 전쟁 당시 유대 측 총사령관 요세푸스는 요타파타 마을에서 로마군에 포위되어 46일 만에 함락되었다. 동료 40명과 동굴로 도망쳤지만 식량이 떨어져, 항복 대신 자결을 택했다. 요세푸스와 그의 친구 2명은 살아남고 싶어, 집단 자결을 하는 순간 요세푸스는 모두를 원형으로 세우고 3번째 위치에 있는 사람이 다른 동료에게 살해당하게 하고, 이를 반복해 마지막 한 사람은 자살한다는 방법을 제안했다. 모두가 이 제안에 찬성하여 요세푸스와 그의 친구는 16번째와 31번째 위치에 있어 살아남았다. 이 내용은 요세푸스의 『유대 전쟁』에서 "요세푸스 문제" 방식을 취했다는 부분을 제외하면 거의 그대로이다.^[4]

2. 1. 요세푸스와 유대 전쟁

2. 2. 중세의 변형: 터키인과 기독교도 문제

다른 버전에서는 터키인과 기독교인의 역할이 바뀌기도 한다.

17세기경의 기록에는 다음과 같은 이야기가 "요세푸스 문제"로 불리기도 한다.

"어느 날, 기독교도 15명과 이교도인 터키인 15명이 탄 배가 난파되었다. 짐을 버려 배를 가볍게 했지만, 여전히 위험했다. 이에 선장은 15명이 희생되어 바다에 뛰어들어야 한다고 말하며 승객들을 원형으로 배열했다. 먼저 기독교도 13명, 터키인 15명을 고리 모양으로 배열하고, 선장이 세어 9번째마다 바다에 몸을 던지도록 했다. 그리고, 이 배열을 통해 기독교도 전원을 구했다."

2. 3. 일본의 "마마코타테(ままこ立て)"

일본에서는 이와 유사한 이야기를 "계자산법(継子算法)" 또는 "마마코타테(ままこ立て)"라고 부른다. 무로마치 시대의 책 중 가마쿠라 말기에 편찬된 것으로 여겨지는 『아즈마카가미』에는 "사이교 법사가 미나모토노 요리토모에게 받은 은으로 된 잠자는 고양이를 요리토모 저택 문 앞에서 놀고 있던 아이에게 '계자산법'의 요령으로 주어버렸다"라는 내용이 실려 있다. 『쓰레즈레구사』(겐코 법사)나 『진겁기』(요시다 미쓰요시)에도 관련 내용이 있으며, 세키 고와도 연구한 것으로 전해진다. 고안자는 불명이다.

3. 해결법

요세푸스 문제를 해결하는 데에는 다양한 접근 방식이 존재한다.

• O(n) 시간 복잡도 알고리즘:

n이 1일 때, f(1, k) = 1 이다. n과 k 사이의 관계식은 다음과 같다.

:$f(n,k)=((f(n-1,k)+k-1)\; \backslash bmod\; n)+1$

사람의 순서를 0부터 n-1번째로 가정하면 관계식은 다음과 같이 단순화된다.

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

• O(k log n) 시간 복잡도 알고리즘: n이 매우 크고 k가 상대적으로 작을 때 사용 가능한 더 빠른 알고리즘이다.

• 비트 연산자 활용 (k=2 특수 케이스): n을 이진법으로 표현했을 때 최상위 비트를 최하위 비트로 이동시키면 안전한 위치를 얻을 수 있다. (입력은 양의 정수여야 한다.)

3. 1. 일반적인 경우

Josephus problem^영어의 일반적인 해결법으로는 동적 계획법이 사용된다. 초기 조건은 f(1, k) = 1 (n=1일 때 생존자는 1)이며, 점화식은 다음과 같다.

:$f(n,k)\; =\; ((f(n-1,k)+k-1)\; \backslash bmod\; n)+1,\backslash text\{\; with\; \}f(1,k)=1\backslash ,,$

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

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

이 방식은 O(n)의 시간 복잡도를 갖는다. 만약 n이 매우 크고 k가 상대적으로 작다면, 더 빠른 해법(O(k log n))이 존재한다.

n은 초기 원에 있는 사람의 수를 나타내고, k는 각 단계에서 건너뛸 사람의 수를 나타낸다. (k-1명을 건너뛰고 k번째 사람을 제거한다.) 원 안의 사람들은 1부터 n까지 번호가 매겨져 있으며, 계산은 포함이다.

$f(n,k)$를 생존자의 위치라고 하면, k번째 사람이 제거된 후 n-1명의 사람이 남는다. 다음 계산은 원래 문제에서 $(k\backslash bmod\; n)+1$번째 사람부터 시작한다. 나머지 원에서 생존자의 위치는 계산이 1에서 시작하는 경우 $f(n-1,k)$가 되며, 시작점을 고려하여 점화식을 다시 쓰면 위와 같은 식이 된다.

k=2인 특수한 경우, 점화식을 이용하여 다음을 얻을 수 있다.

:$f(2n)=2f(n)-1\backslash ,$ (첫 번째 사람이 짝수일 때)

:$f(2n+1)=2f(n)+1\backslash ,$ (첫 번째 사람이 홀수일 때)

$n=2^m+l$이고 이면, $f(n)\; =\; 2l+1$이다. 이는 수학적 귀납법으로 증명할 수 있다.

이진법 표현을 사용하면 더 간결하게 해를 구할 수 있다. n을 이진수로 표현했을 때 $n=b\_0\; b\_1\; b\_2\; b\_3\backslash dots\; b\_m$이라면, f(n)은 n을 1비트 왼쪽으로 순환 시프트하여 얻을 수 있다. 즉, $f(n)=b\_1\; b\_2\; b\_3\; \backslash dots\; b\_m\; b\_0$이다.

k가 한정되지 않은 일반적인 경우, 가장 간단한 해법은 동적 계획법을 사용하는 것이다. 점화식은 다음과 같다.

:$f(n,k)=(f(n-1,k)+k)\; \backslash bmod\; n$， 단, $f(1,k)=0$

이 방법은 O(n)의 계산량을 갖지만, k가 작고 n이 큰 경우에는 첫 번째 단계에서 ''k''번째, 2''k''번째, …, $\backslash lfloor\; n/k\; \backslash rfloor$번째 사람을 제거하고 번호 매기기를 변경하는 O(k log n) 방식이 더 효율적이다.

3. 2. k가 작고 n이 큰 경우

Josephus problem^영어에서 ''k''가 작고 ''n''이 큰 경우, 실행 시간 $O(k\backslash log\; n)$의 동적 계획법을 사용한 효율적인 접근 방식이 있다. 이 방식은 ''k''번째, 2''k''번째, ..., $(\backslash lfloor\; n/k\; \backslash rfloor\; k)$번째 사람을 한 번에 제거하고 번호를 다시 매기는 방식으로 작동한다.

개선된 접근 방식은 다음과 같다:

:$g(n,k)\; =\; \backslash begin\{cases\}$

0 & \text{if } n=1\\

(g(n-1,k)+k) \bmod n & \text{if } 1 < n < k\\

\begin{Bmatrix}

g(n- \left \lfloor \frac{n}{k} \right \rfloor,k)-n \bmod k + n & \text{if } g(n- \left \lfloor \frac{n}{k} \right \rfloor,k)< n \bmod k \\

\lfloor \frac{k(g(n- \left \lfloor \frac{n}{k} \right \rfloor,k)-n \bmod k) }{k-1} \rfloor & \text{if } g(n- \left \lfloor \frac{n}{k} \right \rfloor,k) \ge n \bmod k

\end{Bmatrix} & \text{if } k \le n\\

\end{cases}

참조

_[1] 서적 Making History: The Storytellers Who Shaped the Past https://books.google[...] Simon & Schuster 2022
_[2] PDF https://gustavus.edu[...] 2024-08
_[3] 문서 「本物の」教会史家聖ヘゲシッポス(ヘゲシップス/ヘゲシッパス)の実際の生没年はおよそ紀元110年-180年頃
_[4] 문서 The War of the Jews 3.387-391　ヨセフス本人は死ぬ順番を選ぶのに「くじを引いた」としか書いておらず、どのようなルールだったかは不明。また助かったもう1人は最初から助かるつもりではなく、ヨセフスが彼を殺す番になった時に説得したという。

---

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com