요세푸스 문제의 유래
이 문제의 이름은 고대 역사가 요세푸스(Josephus)의 일대기에서 가장 극적인 사건에서 따온 것입니다. 그의 이야기에 따르면, 요세푸스와 부하 병사 40명은 로마군의 포위 공격으로 동굴에 갇히게 됩니다.
적에게 항복하기를 거부한 그들은 집단 자결을 택했는데, 여기에 독특한 규칙이 있었습니다. 원형으로 둘러선 뒤 세 번째 사람마다 차례로 제거해 나가 단 한 명만 남을 때까지 반복하고, 마지막에 남은 사람이 스스로 목숨을 끝내기로 한 것입니다.
요세푸스와 다른 한 사람이 최후의 두 사람까지 살아남았습니다. 그리고 우리가 이 이야기의 결말까지 알고 있다는 사실에서 짐작할 수 있듯, 두 사람은 원래의 약속을 그대로 지키지는 않았습니다.
요세푸스 순열이란?
우리가 작성해야 할 함수는 요세푸스 순열(Josephus permutation)을 반환하는 자바스크립트 함수입니다.
함수는 두 가지 매개변수를 받습니다. 하나는 원형으로 배치되어 있다고 가정한 항목들의 초기 배열이며, 다른 하나는 매번 k번째 항목을 제거할 때 사용할 값 k입니다. 이 과정을 모든 항목이 제거될 때까지 반복합니다.
예를 들어 n=7, k=3일 때 josephus(7, 3)는 다음과 같이 동작합니다.
[1,2,3,4,5,6,7] - 초기 시퀀스 [1,2,4,5,6,7] => 3이 제거되어 결과에 추가 [3] [1,2,4,5,7] => 6이 제거되어 결과에 추가 [3,6] [1,4,5,7] => 2가 제거되어 결과에 추가 [3,6,2] [1,4,5] => 7이 제거되어 결과에 추가 [3,6,2,7] [1,4] => 5가 제거되어 결과에 추가 [3,6,2,7,5] [4] => 1이 제거되어 결과에 추가 [3,6,2,7,5,1] [] => 4가 제거되어 결과에 추가 [3,6,2,7,5,1,4]
따라서 최종 결과는 다음과 같습니다.
josephus([1,2,3,4,5,6,7],3)==[3,6,2,7,5,1,4];
구현 코드
이를 구현한 코드는 다음과 같습니다.
const arr = [1, 2, 3, 4, 5, 6, 7];
const num = 3;
const helper = (n, k, i, map) => {
if (map.hasOwnProperty([n, k, i]))
return map[[n, k, i]];
if (i === 1)
return map[[n, k, i]] = (k - 1) % n;
return map[[n, k, i]] =
(k + helper(n - 1, k, i - 1, map)) % n;
}
const josephus = (arr, k) => {
let n = arr.length;
let result = new Array(n);
let map = {};
for (let i = 1; i <= n; i++)
result[i - 1] = arr[helper(n, k, i, map)];
return result;
};
console.log(josephus(arr, num));
코드 동작 원리
핵심은 재귀적 점화식입니다. n명 중 i번째로 제거될 사람의 위치는 다음 규칙으로 구할 수 있습니다.
- i = 1인 경우: 위치는 (k - 1) % n 입니다.
- i > 1인 경우: 위치는 (k + helper(n - 1, k, i - 1)) % n 입니다.
helper 함수는 한 번 계산한 결과를 map 객체에 캐싱하는 메모이제이션(memoization) 기법을 사용해 중복 연산을 방지합니다. 덕분에 동일한 하위 문제를 반복해서 풀지 않으므로, 입력 크기가 커져도 효율적으로 동작합니다.
josephus 함수는 이 helper를 활용해 1번째부터 n번째까지 제거되는 요소의 인덱스를 차례로 찾아내고, 해당 인덱스의 값을 결과 배열에 담아 최종 순열을 완성합니다.
실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
[ 3, 6, 2, 7, 5, 1, 4 ]