백준에서 변형 문제 2개를 제외하면 정통(?) 요세푸스 문제는 아래와 같습니다.
| 요세푸스 순열을 구하는 문제 | 마지막 생존자를 구하는 문제 | ||||
| 문제 제목 | 요세푸스 문제 0 11866번 2초/512MB |
요세푸스 문제 1158번 2초/256MB |
요세푸스 문제 2 1168번 0.15초/128MB |
요세푸스 문제3 11025번 1 초/ 16 MB |
마지막 요세푸스 문제 1179번 2초 128MB |
| 입력범위 및 부가조건 |
1 ≤ K ≤ N ≤ 1,000 |
1 ≤ K ≤ N ≤ 5,000 |
1 ≤K≤ N≤ 100,000 Java X: 0.8 PythonPyPy: 0.75 Kotlin (JVM): 0.8 |
1 ≤K≤N≤ 5,000,000 |
1 ≤ N ≤ 10^15 1 ≤ K ≤ 90 |
요세푸스 문제 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 전산학이나 수학에서 요세푸스 문제(Josephus problem) 혹은 요세푸스 순열(Josephus permutation)은 다음과 같이 정의한다. n과 k가 자연수이고, k < n이라고 가정한다. n명
ko.wikipedia.org
이 글은 주로 # 1168번 요세푸스 문제에 대한 글입니다.
문제
요세푸스 문제는 다음과 같다.
1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.
N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 100,000)
출력
예제와 같이 요세푸스 순열을 출력한다.
예제 입력 1
7 3
예제 출력 1
<3, 6, 2, 7, 5, 1, 4>이전 문제인 1158번에 제출한 코드는 다음과 같습니다.
도넛 리스트를 만드는 방법입니다.
class DounutList:
def __init__(self, elements):
self.elements = elements
def __len__(self):
return len(self.elements)
def pop(self, index):
index = index % len(self.elements)
return self.elements.pop(index)
def put(self, item):
self.elements.append(item)
N, K = map(int, input().split())
dounut = DounutList([x for x in range(1, N + 1)])
result = []
index = 0
while len(dounut) > 0:
index = (index + K - 1) % len(dounut)
result.append(dounut.pop(index))
print("<" + ", ".join(str(number) for number in result) + ">")실행속도를 높여보려고 이런저런 방법을 써 보고 코드를 줄여 봤지만 효과가 없었습니다.
def josephus(n, k):
# 0부터 시작하는 인덱스 사용
people = list(range(n))
result = []
index = 0 # 현재 인덱스
for _ in range(n):
index = (index + k - 1) % len(people) # 제거될 사람의 인덱스 계산
result.append(people.pop(index)) # 사람 제거 및 결과에 추가
# 1부터 시작하는 인덱스로 조정하여 반환
return [x + 1 for x in result]
# 입력 받기
n, k = map(int, input().split())
# 요세푸스 순열 구하기
result = josephus(n, k)
# 출력
print("<" + ", ".join(map(str, result)) + ">")
다른 알고리즘으로는 절대 안 풀려서 결국 세그먼트 트리를 공부해야만 문제를 풀 수 있게 되었습니다.
이 문제에 대체 어떻게 적용되는 것인지 이해가 잘 안 갔고, 빌드방법도 잘 이해가 안 갔습니다.
하지만 이 문제를 풀어보면서 세그먼트트리의 개념이 많이 이해되었습니다.
요세푸스 문제를 세그먼트 트리로 푸는 것이 빠른 이유는 세그먼트 트리의 효율적인 구간 쿼리 및 업데이트 능력 때문입니다. 요세푸스 문제는 n명의 사람이 원을 이루어 앉아 있고, k번째 사람을 순차적으로 제거해 나가면서 마지막으로 남는 사람을 찾는 문제입니다. 이 문제를 직접적으로 시뮬레이션하는 방법은 매우 비효율적일 수 있습니다. 특히, 매번 k번째 사람을 찾기 위해 순차적으로 탐색하는 과정은 시간 복잡도가 O(nk)에 달할 수 있습니다. 그러나 세그먼트 트리를 사용하면 다음과 같은 이유로 훨씬 빠르게 문제를 해결할 수 있습니다.
효율적인 구간 쿼리
세그먼트 트리는 구간 쿼리를 O(log n) 시간 안에 처리할 수 있습니다. 요세푸스 문제에서는 k번째로 제거될 사람을 찾기 위해 원형 큐에서 k번 이동하는 것과 유사한 연산이 필요합니다. 세그먼트 트리를 사용하면, 현재 살아 있는(제거되지 않은) 사람들을 표현하는 구간에 대해 k번째 위치를 빠르게 찾을 수 있습니다. 이는 세그먼트 트리가 각 노드에 구간의 합(또는 최솟값, 최댓값 등 구간에 대한 다양한 정보)을 저장하기 때문에 가능합니다.
효율적인 업데이트
세그먼트 트리는 구간 내의 데이터를 업데이트하는 연산도 O(log n) 시간 안에 처리할 수 있습니다. 요세푸스 문제에서 사람이 제거되면, 해당 위치를 업데이트하여 더 이상 그 사람을 고려하지 않도록 해야 합니다. 세그먼트 트리를 사용하면, 특정 인덱스의 값을 변경하고, 그 변경사항을 반영하여 빠르게 트리를 재구성할 수 있습니다.
시간 복잡도
세그먼트 트리를 사용하여 요세푸스 문제를 해결할 경우, 각 사람을 제거하는 데 O(log n) 시간이 걸리며, 총 n명의 사람을 제거해야 하므로 전체 시간 복잡도는 O(n log n)이 됩니다. 이는 직접적인 시뮬레이션 방법에 비해 훨씬 효율적입니다.
결론
세그먼트 트리를 사용하면 요세푸스 문제와 같은 순차적 제거 문제를 더 빠르고 효율적으로 해결할 수 있습니다. 세그먼트 트리의 구간 쿼리와 업데이트 기능을 활용하여, 문제의 복잡도를 크게 줄일 수 있기 때문입니다.
파이게임으로 시각화해 보았습니다.
구간 합을 빠르게 업데이트하며 다음 k 번째((현재 인덱스+k)mod 남은 사람 수)를 찾을 수 있습니다.
class SegmentTree:
def __init__(self, n):
self.n = n # 세그먼트 트리의 크기 (입력된 사람의 수)
self.tree = [0] * (4 * n) # 세그먼트 트리를 저장할 리스트, 충분한 크기 할당
self.build(1, 0, n-1) # 세그먼트 트리 초기화
def build(self, node, start, end):
# 세그먼트 트리를 구축하는 함수
if start == end:
# 리프 노드에 도달했을 때, 해당 위치를 1로 설정 (해당 위치의 사람이 존재함을 의미)
self.tree[node] = 1
else:
mid = (start + end) // 2
# 왼쪽과 오른쪽 자식 노드를 재귀적으로 구축
self.build(node*2, start, mid)
self.build(node*2+1, mid+1, end)
# 부모 노드는 자식 노드들의 값을 합하여 저장
self.tree[node] = self.tree[node*2] + self.tree[node*2+1]
def update(self, node, start, end, idx, val):
# 세그먼트 트리를 업데이트하는 함수, idx 위치의 값을 val로 변경
if start == end:
self.tree[node] = val
else:
mid = (start + end) // 2
if start <= idx <= mid:
self.update(node*2, start, mid, idx, val)
else:
self.update(node*2+1, mid+1, end, idx, val)
self.tree[node] = self.tree[node*2] + self.tree[node*2+1]
def query(self, node, start, end, k):
# k번째로 제거될 사람의 인덱스를 찾는 함수
if start == end:
return start
mid = (start + end) // 2
if k <= self.tree[node*2]:
return self.query(node*2, start, mid, k)
else:
return self.query(node*2+1, mid+1, end, k - self.tree[node*2])
def josephus_with_segment_tree(n, k):
seg_tree = SegmentTree(n) # 세그먼트 트리 초기화
result = [] # 제거된 사람들의 순서를 저장할 리스트
current_index = 0 # 현재 인덱스
for _ in range(n):
remaining = n - len(result) # 남은 사람의 수
current_index = (current_index + k - 1) % remaining
if current_index == 0:
current_index = remaining
survivor_index = seg_tree.query(1, 0, n-1, current_index)
result.append(survivor_index + 1) # 1-based indexing으로 조정하여 결과에 추가
seg_tree.update(1, 0, n-1, survivor_index, 0) # 제거된 사람을 세그먼트 트리에서 업데이트
return result
n, k = map(int, input().split()) # 사용자로부터 n과 k를 입력받음
sequence = josephus_with_segment_tree(n, k) # 요세푸스 순열을 계산
print("<" + ", ".join(map(str, sequence)) + ">") # 결과 출력이 코드는 세그먼트 트리를 활용하여 요세푸스 문제의 순열을 구하는 알고리즘을 구현한 것입니다. 세그먼트 트리는 구간 쿼리 문제를 효율적으로 해결하기 위한 자료구조로, 여기서는 살아있는 사람들의 수를 관리하는 데 사용됩니다.
SegmentTree 클래스
- __init__: 세그먼트 트리를 초기화합니다. **n**은 총 사람의 수, **tree**는 세그먼트 트리를 저장하는 배열입니다. **tree**의 크기는 **4*n**으로 설정되어 있으며, 이는 세그먼트 트리의 최대 크기를 고려한 것입니다.
- build: 세그먼트 트리를 구축하는 함수입니다. 리프 노드는 각각의 사람을 나타내며 1의 값을 가집니다(살아있음을 의미). 내부 노드는 자식 노드들의 값을 합한 값으로 설정됩니다(해당 구간에 살아있는 사람의 수).
- update: 트리의 특정 위치(사람)를 업데이트하는 함수입니다. 사람이 제거될 때 호출되며, 해당 위치를 0으로 설정합니다(제거됨을 의미).
- query: 세그먼트 트리에서 **k**번째 살아있는 사람의 인덱스를 찾는 함수입니다. 이 함수는 이진 탐색과 유사한 방식으로 작동합니다.
josephus_with_segment_tree 함수
- 이 함수는 주어진 **n**과 **k**에 대해 요세푸스 순열을 구합니다.
- 먼저, SegmentTree 인스턴스를 생성하여 세그먼트 트리를 초기화하고 구축합니다.
- result 리스트는 순열을 저장할 리스트입니다.
- 반복문을 통해 각 단계에서 제거될 사람을 결정하고, 이를 결과 리스트에 추가합니다. **current_index**는 현재 제거될 사람의 순서를 나타냅니다.
- **remaining**은 남은 사람의 수를 나타냅니다. **current_index**는 (current_index + k - 1) % remaining 식을 통해 계산됩니다. 이는 현재 위치에서 **k-1**만큼 이동한 후 남은 사람의 수로 나눈 나머지를 구하는 것입니다.
- **survivor_index**는 세그먼트 트리를 통해 구한 **k**번째 살아있는 사람의 인덱스입니다.
- update 함수를 호출하여 제거된 사람을 세그먼트 트리에서 업데이트합니다.
마지막으로, 순열을 출력하기 위해 result 리스트의 값을 1부터 시작하는 인덱싱으로 조정하고, 이를 문자열로 변환하여 출력합니다.
세그먼트 트리
https://book.acmicpc.net/ds/segment-tree
세그먼트 트리
누적 합을 사용하면, 1번 연산의 시간 복잡도를 $O(1)$로 줄일 수 있습니다. 하지만, 2번 연산으로 수가 변경될 때마다 누적 합을 다시 구해야 하기 때문에, 2번 연산의 시간 복잡도는 $O(N)$입니다.
book.acmicpc.net
아주 설명이 잘 되어 있습니다.
지금부터는 # 11025번 요세푸스 문제 3 에 대한 글입니다.
너무 안 풀려서 이런 저런 공부를 하다가 요세푸스 문제에 대해 공부하게 되었습니다.
위키피디아에서 점화식이 있는 것을 보았는데 마지막 생존자를 구하는 문제는 그 식으로 간단히 풀겠네라고 생각했습니다. 그런데 그 문제가 있었습니다.
11025번: 요세푸스 문제 3
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000,000)
www.acmicpc.net
심지어 플래티넘 3 문제입니다. 그러니까 이 점화식을 직접 유도하라는 의도의 난이도인 것 같습니다.
점화식을 알면 너무 쉬운데 설마 플래티넘 3이 이런 짧은 코드로 되겠어? 하는데 되었습니다....
다음은 위키피디아 내용입니다.
n, k = map(int, input().split())
index = 0
for i in range(n):
index = (index + k) % (i + 1)
print(index + 1)기본 아이디어
조세푸스 문제를 해결하는 데 있어서 중심이 되는 것은 'n명이 있을 때 마지막에 남는 사람의 위치를 찾는 방법'입니다. 이를 위해 재귀적 접근법을 사용합니다. 즉, n명이 있을 때의 문제를 n-1명이 있을 때의 문제로 단순화해 나가는 방식입니다.
점화식의 역할
재귀적 방법의 핵심은 점화식에 있습니다. f(n, k) = ((f(n-1, k) + k - 1) mod n) + 1이라는 공식은 문제를 단계적으로 단순화합니다. 여기서 f(n, k)는 n명이 있고, k번째 사람을 제거할 때 마지막에 남는 사람의 위치를 나타냅니다.
점화식 해석
이 점화식은 'n-1명이 있을 때의 해결책에서 출발하여 n명이 있을 때의 해결책을 찾는다'는 아이디어를 수학적으로 표현한 것입니다. n명이 남았을 때와 n-1명이 남았을 때의 상황이 유사함을 기반으로, 한 사람을 제거한 상태에서의 해결책을 알고 있다면, 그것을 사용하여 전체 문제의 해결책을 구할 수 있습니다.
큐를 사용한 시각화
큐를 사용하여 문제를 시각화하면, 이 공식이 어떻게 동작하는지 더 명확히 이해할 수 있습니다. 큐는 사람들이 앉은 순서를 나타내며, k번째 사람을 제거하는 과정을 단계별로 보여줍니다. 이 과정을 반복하면서 큐에서 사람을 제거해 나가면, 마지막에 한 사람만 남게 되며, 이 사람이 바로 찾는 해답입니다.
코드 해석
위 코드에서는 for 문을 이용하여 재귀를 초항부터 마지막 항까지 거꾸로 반복하며 스스로에게 값을 더해 주는 방법으로 구현하고 있습니다.
마지막 요세푸스 문제는 다음 식을 이용합니다.
import sys
input=sys.stdin.readline
n, k = map(int, input().split())
index = 0 # 마지막에 남는 사람의 위치를 저장할 변수 초기화
i = 1 # 현재까지 고려한 사람의 수(이전 코드의 for문의 i역할)
if k == 1: # k가 1인 경우, 모든 사람이 마지막까지 남으므로 n을 출력
print(n)
else:
# k가 1이 아닌 경우, 반복문을 통해 요세푸스 순열 계산
while True:
# 다으 인덱스까지의 거리 계산
dist = ((i - index - 1) // (k - 1)) + 1
# i + dist가 n을 초과하는 경우, 마지막 사람에 도달함
if i + dist > n:
# 남은 사람들을 모두 제거한 후 반복문 종료
index += (n - i) * k
break
# i + dist가 n을 초과하지 않는 경우, index를 업데이트하고 i 증가
index = (index + k * dist) % (i + dist)
i += dist
print(index + 1) # 결과 출력 (1부터 시작하는 순서로 조정)
점화식을 통해 나온 값 f(n, k)는 n명을 원형으로 앉히고 k번째마다 제가하면 최종적으로 남는 인덱스를 출력한다.
그러런데 dist값을 이용해 인덱스가 일순하기 전까지 한 번에 계산하는 것이다.
41 3
dist = 1 result: f(1,3) = (index + k * dist) % (i + dist) = (0 + 3 * 1) % (1 + 1) = 1
dist = 1 result: f(2,3) = (index + k * dist) % (i + dist) = (1 + 3 * 1) % (2 + 1) = 1
dist = 1 result: f(3,3) = (index + k * dist) % (i + dist) = (1 + 3 * 1) % (3 + 1) = 0
dist = 2 result: f(4,3) = (index + k * dist) % (i + dist) = (0 + 3 * 2) % (4 + 2) = 0
dist = 3 result: f(6,3) = (index + k * dist) % (i + dist) = (0 + 3 * 3) % (6 + 3) = 0
dist = 5 result: f(9,3) = (index + k * dist) % (i + dist) = (0 + 3 * 5) % (9 + 5) = 1
dist = 7 result: f(14,3) = (index + k * dist) % (i + dist) = (1 + 3 * 7) % (14 + 7) = 1
dist = 10 result: f(21,3) = (index + k * dist) % (i + dist) = (1 + 3 * 10) % (21 + 10) = 0
dist = 16(n - i) * k30
31
(index + k) % (i + 1) = (0 + 3) % (0 + 1) = 0
(index + k) % (i + 1) = (0 + 3) % (1 + 1) = 1
(index + k) % (i + 1) = (1 + 3) % (2 + 1) = 1
(index + k) % (i + 1) = (1 + 3) % (3 + 1) = 0
(index + k) % (i + 1) = (0 + 3) % (4 + 1) = 3
(index + k) % (i + 1) = (3 + 3) % (5 + 1) = 0
(index + k) % (i + 1) = (0 + 3) % (6 + 1) = 3
(index + k) % (i + 1) = (3 + 3) % (7 + 1) = 6
(index + k) % (i + 1) = (6 + 3) % (8 + 1) = 0
(index + k) % (i + 1) = (0 + 3) % (9 + 1) = 3
(index + k) % (i + 1) = (3 + 3) % (10 + 1) = 6
(index + k) % (i + 1) = (6 + 3) % (11 + 1) = 9
(index + k) % (i + 1) = (9 + 3) % (12 + 1) = 12
(index + k) % (i + 1) = (12 + 3) % (13 + 1) = 1
(index + k) % (i + 1) = (1 + 3) % (14 + 1) = 4
(index + k) % (i + 1) = (4 + 3) % (15 + 1) = 7
(index + k) % (i + 1) = (7 + 3) % (16 + 1) = 10
(index + k) % (i + 1) = (10 + 3) % (17 + 1) = 13
(index + k) % (i + 1) = (13 + 3) % (18 + 1) = 16
(index + k) % (i + 1) = (16 + 3) % (19 + 1) = 19
(index + k) % (i + 1) = (19 + 3) % (20 + 1) = 1
(index + k) % (i + 1) = (1 + 3) % (21 + 1) = 4
(index + k) % (i + 1) = (4 + 3) % (22 + 1) = 7
(index + k) % (i + 1) = (7 + 3) % (23 + 1) = 10
(index + k) % (i + 1) = (10 + 3) % (24 + 1) = 13
(index + k) % (i + 1) = (13 + 3) % (25 + 1) = 16
(index + k) % (i + 1) = (16 + 3) % (26 + 1) = 19
(index + k) % (i + 1) = (19 + 3) % (27 + 1) = 22
(index + k) % (i + 1) = (22 + 3) % (28 + 1) = 25
(index + k) % (i + 1) = (25 + 3) % (29 + 1) = 28
(index + k) % (i + 1) = (28 + 3) % (30 + 1) = 0
(index + k) % (i + 1) = (0 + 3) % (31 + 1) = 3
(index + k) % (i + 1) = (3 + 3) % (32 + 1) = 6
(index + k) % (i + 1) = (6 + 3) % (33 + 1) = 9
(index + k) % (i + 1) = (9 + 3) % (34 + 1) = 12
(index + k) % (i + 1) = (12 + 3) % (35 + 1) = 15
(index + k) % (i + 1) = (15 + 3) % (36 + 1) = 18
(index + k) % (i + 1) = (18 + 3) % (37 + 1) = 21
(index + k) % (i + 1) = (21 + 3) % (38 + 1) = 24
(index + k) % (i + 1) = (24 + 3) % (39 + 1) = 27
(index + k) % (i + 1) = (27 + 3) % (40 + 1) = 30
31
종료 코드 0(으)로 완료된 프로세스레퍼런스 사이트
https://ps.mjstudio.net/tip-josephus-problem
Tip - 요세푸스 문제
Wikipedia
ps.mjstudio.net
요세푸스 문제 - 나무위키
마지막에 남는 수만 알아내면 되는 경우와, 제거된 수의 순서도 알아내야 하는 경우의 효율적인 풀이가 다르다. 본 항목에서 배열의 첫 번째 원소는 인덱스 1로 표시한다. 즉, 원소의 번호는 1부
namu.wiki
https://www.acmicpc.net/user/hanzch
hanzch 정보
www.acmicpc.net
'Tech > Coding' 카테고리의 다른 글
| # 11659번 구간 합 구하기 4 (0) | 2024.02.05 |
|---|---|
| #1927번 최소 힙 (0) | 2024.02.05 |
| #2563번 색종이 (0) | 2024.02.02 |
| 백준1003🐨피보나치 함수.py - DP, MEMO + 분할 정복 (0) | 2024.02.02 |
| 백준20920🐨영단어 암기는 괴로워.py (0) | 2024.02.02 |
