Permutation [Permutation] - Josephus Permutation Problem (요세푸스 순열 문제)

[김건우]

안녕하세요.

오늘은 요세푸스 순열 문제에 대해 알아보는 시간을 가져보도록 하겠습니다.

그럼 시작하겠습니다.

출처 : https://i.pinimg.com/550x/fb/de/08/fbde08398de3fff3d2f3bbb0418543d8.jpg

요세푸스 순열이란?

고대 로마 시기, 유대인 지도자였던 요세푸스가 로마 지배에 대항하여 싸웠으나, 위기에 처하여 같이 대항하여 싸운 부하들과 동굴로 들어갑니다. 

그러나 당시 제사장이자, 유대인 지도자였던 요세푸스는 종교적인 이유로 자살은 안된다고 주장하였습니다.

그렇게 요세푸스와 그의 부하 40명 (총 41명) 은 규칙을 만들어 한 명씩 죽이고, 마지막 남은 한 사람은 자살하기로 결정하게 됩니다.

출처 : https://allenfrostline.com/images/josephus.png

그리고, 요세푸스와 요세푸스 41명은 서로 규칙을 정해 죽여갔고, 결국 마지막엔 요세푸스와 요세푸스 부하 1명이 남아 로마에 투항을 했다고 합니다.

이렇게 요세푸스의 이름을 따 요세푸스 순열이라고 명명되었고, 지금까지도 요세푸스 순열을 활용한 문제들을 풀어나가고 있습니다.

요세푸스 순열의 점화식

그렇다면 요세푸스 순열은 어떻게 구성되어 있을까요?

요세푸스 순열은 하단의 식과 같이 구성됩니다.

출처 : https://ko.wikipedia.org/wiki/%EC%9A%94%EC%84%B8%ED%91%B8%EC%8A%A4_%EB%AC%B8%EC%A0%9C

N 이 1이라고 가장 시, 맨 처음 시작하는 항을 f(1, k) = 1 이라고 잡을 수 있습니다.

그리고 N 과 K 간 관계식에 관한 설명도 위키백과에 나와있지만, 우리가 원하는 것은 N 과 K 를 활용하여 요세푸스 순열의 점화식을 구하는 것이기 때문에 우선 상단의 설명은 간략하게 읽고 넘어가도록 합시다.

출처 : https://www.acmicpc.net/problem/11866

다음과 같이 두 수가 주어집니다.

첫 번째 수는 N 값이고, 두 번째 수는 K 값입니다.

N = 7, K = 3

이제 7명을 세워놓고, 3번째마다 지울 때, 마지막 남은 사람의 자릿수 번호를 f(n) 이라 가정해보겠습니다.

상단 Wikipedia 에서 나온 설명 중, 일부 내용을 다시 발췌해보았습니다.

출처 : https://ko.wikipedia.org/wiki/%EC%9A%94%EC%84%B8%ED%91%B8%EC%8A%A4_%EB%AC%B8%EC%A0%9C

순서는 1번째부터 N번째 (7번째) 까지 차례대로 돌아갑니다.

여기서 우리는 f(n) 과 f(n + 1) 이라는 점화식을 가져갈 수 있게 됩니다.

우리가 원하는 숫자는 0부터 시작하는 것이 아닌 1부터 N 값까지 반복하면서 차례대로 순열 값을 찾는 것이 목표이므로, 관계식 끝 부분에 + 1 이 붙는 순열식을 선택하였습니다.

K = 3 이므로, 먼저 3의 배수로 시작하는 순서부터 제거됩니다.

그렇게 되면 3, 6 이 먼저 제거가 될 것입니다.

그럼 이제 남은 사람들은 1, 2, 4, 5, 7 만 남을 것입니다.

K = 3이었고, 3의 배수로 시작하는 순서가 제거되었으니, 그 다음은 7부터 Counting 을 시작하며 3번째로 Count 되는 숫자, 즉2가 제거가 됩니다.

또 K 값만큼 3칸을 Counting 해야하므로, 7이 제거됩니다.

다시 K 값 만큼 3칸을 Counting 하여 5가 제거되었습니다.

다시 K 값만큼 위치를 3칸 Counting 하였고, 이번엔 1이 제거되었습니다.
결국 마지막으로 남은 숫자를 4가 되겠습니다.

이와 같은 과정을 거치는 순열을 요세푸스 순열이라고 부릅니다.

Queue 와 원형 Queue

위에서 배웠던 요세푸스 순열을 알고리즘으로 구현하는 방법에 대해 소개해드리도록 하겠습니다.

이 요세푸스 순열 알고리즘을 사용하기 위해선 Queue 와 Deque 에 대해 알고 있어야 합니다.

우선 Queue 입니다.

출처 : https://upload.wikimedia.org/wikipedia/commons/thumb/5/52/Data_Queue.svg/1200px-Data_Queue.svg.png

Queue 는 쉽게 생각하자면 줄이라고 생각하면 됩니다.

출처 : https://i.guim.co.uk/img/media/f741f72813b9c5681d6a37450158e20322349532/2340_0_4269_2563/master/4269.jpg?width=1200&quality=85&auto=format&fit=max&s=fcf471fd4caca84d8c67bc2122107ce8

다음 Image 와 같이 사람들이 줄을 서 있고, 앞 사람이 한 명씩 건강검진을 받는다고 가정해보겠습니다.

그러면 앞에서 한 명씩 차례대로 호명을 받아 검색을 진행하고, 그리고 맨뒤에는 새로 건강검진을 받으려는 사람들의 줄이 이어져 있을 것 같습니다.

이처럼 Queue 는 기존의 Linked List 에서 좀 더 확정된 Version 이며, 앞으로 Data 가 하나 빠지면, 뒤로 하나 새로 추가되는 방식입니다.

우리가 이 문제를 풀기 위해선 원형 Queue 라는 것을 활용해야 하는데, 별로 어려운 내용은 아니니, 한 번 간단히 Image 를 통해 봐주시길 부탁드립니다.

출처 : https://miro.medium.com/max/1200/1*J9K866QWpLC9OkmLLn3nEA.png

위에 올려놓았었던 1자 형태로 되어 있는 Queue 와 다르게, 원형 Queue 로 되어 있어 기존 데이터를 꺼내거나, 아니면 새로운 데이터를 추가 시, Data 가 잘 추가되고 있는지 여부를 눈으로 확인하기 위해 사용합니다.

상단의 Image 와 같이 특정 Data 가 추가되기 위해선 기존 Data 의 맨 앞에 있는 Data 가 먼저 빠진 후, 맨 뒤에 새로운 Data 가 추가되는 구조입니다.

그럼 이 원형 Queue 를 활용하여 문제를 풀어보겠습니다.

문제 풀기

우선 다음과 같이 1부터 N 까지 반복문을 돌며 값을 Queue 에 추가합니다.

참고로 우리는 Python 의 Collections Module 의 Deque 를 활용하므로, 구현 방식은 이 Image 를 통해 소개해드리겠습니다.

[1, 2, 3, 4, 5, 6, 7] Queue

이제 K 의 배수로 시작하는 값부터 먼저 찾아 제거해야 하니, K 의 배수가 아닌 값들은 맨 앞 (Head) 에서 맨 뒤 (Tail) 로 보내버리겠습니다.

참고로 뒤에 보실 Code 중 K - 1 라는 코드를 보실 수가 있는데, 이는 Queue 의 Index 범위를 초과하여 값을 찾아 오류를 일으킬 수 있기 때문에 K - 1 을 사용하였습니다.

우선 1을 Tail 로 보내고, 2 를 Head 로 가지고 왔습니다.

그렇지만, 2도 K 의 배수 (여기서 K 는 3입니다) 가 아니므로, 2 또한 Tail 로 보냅니다.

이제 3은 K 의 배수이므로, 제거하고 답안을 출력하는 List (Answer List) 에 추가해주도록 하겠습니다.

[4, 5, 6, 7, 1, 2] Queue

그리고 4를 맨 앞 (Head) 에 배치하고, 이전에 맨 뒤 (Tail) 에 있었던 2는 그대로 맨 뒤 (Tail) 에 두도록 하겠습니다.

이번에는 5를 Head 에 배치하고, 이전에 Head 였던 4를 Tail 에 배치하도록 하겠습니다.

[6, 7, 1, 2, 4, 5] Queue

이제 6은 K 의 배수이므로, Queue 에서 제거하고 답안을 출력하는 Answer List 에 추가해주도록 하겠습니다.

그리고 7 을 맨 앞 (Head) 에 배치하고, 이전에 맨 뒤 (Tail) 에 있었던 5 를 그대로 맨 뒤 (Tail) 에 두도록 하겠습니다.

여기서부턴 K 의 배수가 6을 제외한 나머지 Index 에서 더 이상 확인이 되지 않기 때문에 기존에 있었던 6에서 3칸 앞으로 떨어진 위치에 있는 숫자를 추후 제거하도록 하겠습니다.

이번에는 1을 Head 에 배치하고, 7을 Tail 에 배치하도록 하겠습니다.

[2, 4, 5, 7, 1] Queue

K 의 배수로 판별하는 작업은 이제 끝났으니, 아까 6으로부터 3칸 떨어진 2를 Queue 에서 제거하고, 답안을 출력하는 Answer List 에 추가해보도록 하겠습니다.

그리고 4를 Head 에 배치하고, 1을 Tail 에 배치하도록 하겠습니다.

이번에는 4를 Head 에 배치하고, 1을 Tail 에 배치하도록 하겠습니다.

[7, 1, 4, 5] Queue

아까 2로부터 3칸만큼 떨어진 7을 Queue 에서 제거하고, 답안을 출력하는 Answer List 에 추가해보도록 하겠습니다.

그리고 1을 Head 로 배치하고, 5를 Tail 로 배치합니다.

이번에는 4를 Head 에 배치하고, 1을 Tail 에 배치합니다.

[5, 1, 4] Queue

아까 7의 위치로부터 3만큼 떨어진 5를 Queue 에서 제거하고, 답안을 출력하는 Answer List 에 추가해보도록 하겠습니다.

그리고 1을 Head 에 배치하고, 4를 Tail 로 배치합니다.

이번에는 1을 Head 에 배치하고, 4를 Tail 에 배치합니다.

[1, 4] Queue

아까 5의 위치로부터 3만큼 떨어진 1을 Queue 에서 제거하고, 답안을 출력하는 Answer List 에 추가해보도록 하겠습니다.

그리고 4는 Head 와 Tail 역할을 동시에 수행합니다.

[4] Queue

마지막으로 4를 Answer List 에 추가해 주도록 합시다.

그리고 Queue 는 Empty 인 상태로 남게되고, Answer List 의 모든 Index 에 값들이 모두 채워지게 되었습니다.

전체 코드

전체 코드입니다.

from collections import deque

n, k = map(int, input().split())

deque_list = deque([])

josephus_list = []

for i in range(1, n + 1):

    deque_list.append(i)

for i in range(len(deque_list)):

    for j in range(k - 1):

        deque_list.append(deque_list.popleft())

    josephus_list.append(deque_list.popleft())

print(deque_list)

print(josephus_list)

"""

Josephus Problem

1. Add into deque_list

2. Get the recurrence formula

- 1. Iterate deque_list and append into josephus_list which shows the result of josephus-permutation

- 2. If the number is multiples of K (In this case, it's 3), Add into Josephus_list and delete from deque_list

  = 1. Move the selected number to the

- 3. If it space 3 place from previous number, Add into Josephus_list and delete from deque_list

"""

이상 오늘은 여기서 마치도록 하겠습니다.

감사합니다.