요세푸스 순열

요세푸스 순열이란

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

 

Ex) n = 7, k = 3인 경우 3, 6, 2, 7, 5, 1 순서로 제거된 후 4가 마지막으로 남는다.

 

---

 

Python

n = 7, k = 3일 때 요세푸스 순열을 구하라.

n, k = map(int, input().split());
arr = [];
result = [];
index = 0;

for i in range(1, n + 1):
    arr.append(i);

while arr:
    index = (index + k - 1) % len(arr);
    result.append(arr.pop(index));

print(result)

 

for문

• n은 1부터 7이기 때문에 for문을 통해서 arr 배열에 1부터 7을 넣는다.

 

while문

• 인덱스를 구하여 그 인덱스를 빼고 새로운 result 배열에 넣는 알고리즘이다.
• arr이 비어 있을 때까지 반복한다.
• index는 현재 0으로 설정되어 있고 k-1를 통해 k번째 인덱스를 뺀다.

Ex) 

• index = 0 + 3 - 1 % 7, index = 2 % 7, index = 2가 된다. 
• index = 2 + 3 - 1 % 7, index = 4 % 6, index = 4가 된다.
• index = 4 + 3 - 1 % 7, index = 6 % 5, index = 1이 된다.
• .... 반복

이렇게 반복하여 각 인덱스를 pop을 통해 뺀 값을 result 배열에 넣는다.