다른 알고리즘으로는 절대 안 풀려서 결국 또 다시 세그먼트 트리
요세푸스 문제를 세그먼트 트리로 푸는 것이 빠른 이유는 세그먼트 트리의 효율적인 구간 쿼리 및 업데이트 능력 때문입니다. 요세푸스 문제는 n명의 사람이 원을 이루어 앉아 있고, k번째 사람을 순차적으로 제거해 나가면서 마지막으로 남는 사람을 찾는 문제입니다. 이 문제를 직접적으로 시뮬레이션하는 방법은 매우 비효율적일 수 있습니다. 특히, 매번 k번째 사람을 찾기 위해 순차적으로 탐색하는 과정은 시간 복잡도가 O(nk)에 달할 수 있습니다. 그러나 세그먼트 트리를 사용하면 다음과 같은 이유로 훨씬 빠르게 문제를 해결할 수 있습니다.
세그먼트 트리는 구간 쿼리를 O(log n) 시간 안에 처리할 수 있습니다. 요세푸스 문제에서는 k번째로 제거될 사람을 찾기 위해 원형 큐에서 k번 이동하는 것과 유사한 연산이 필요합니다. 세그먼트 트리를 사용하면, 현재 살아 있는(제거되지 않은) 사람들을 표현하는 구간에 대해 k번째 위치를 빠르게 찾을 수 있습니다. 이는 세그먼트 트리가 각 노드에 구간의 합(또는 최소값, 최대값 등 구간에 대한 다양한 정보)을 저장하기 때문에 가능합니다.
세그먼트 트리는 구간 내의 데이터를 업데이트하는 연산도 O(log n) 시간 안에 처리할 수 있습니다. 요세푸스 문제에서 사람이 제거되면, 해당 위치를 업데이트하여 더 이상 그 사람을 고려하지 않도록 해야 합니다. 세그먼트 트리를 사용하면, 특정 인덱스의 값을 변경하고, 그 변경사항을 반영하여 빠르게 트리를 재구성할 수 있습니다.
세그먼트 트리를 사용하여 요세푸스 문제를 해결할 경우, 각 사람을 제거하는 데 O(log n) 시간이 걸리며, 총 n명의 사람을 제거해야 하므로 전체 시간 복잡도는 O(n log n)이 됩니다. 이는 직접적인 시뮬레이션 방법에 비해 훨씬 효율적입니다.
세그먼트 트리를 사용하면 요세푸스 문제와 같은 순차적 제거 문제를 더 빠르고 효율적으로 해결할 수 있습니다. 세그먼트 트리의 구간 쿼리와 업데이트 기능을 활용하여, 문제의 복잡도를 크게 줄일 수 있기 때문입니다.
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:
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):
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):
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())
sequence = josephus_with_segment_tree(n, k)
print("<" + ", ".join(map(str, sequence)) + ">")
이 코드는 세그먼트 트리를 활용하여 요세푸스 문제의 순열을 구하는 알고리즘을 구현한 것입니다. 세그먼트 트리는 구간 쿼리 문제를 효율적으로 해결하기 위한 자료구조로, 여기서는 살아있는 사람들의 수를 관리하는 데 사용됩니다.
__init__: 세그먼트 트리를 초기화합니다. **n**은 총 사람의 수, **tree**는 세그먼트 트리를 저장하는 배열입니다. **tree**의 크기는 **4*n**으로 설정되어 있으며, 이는 세그먼트 트리의 최대 크기를 고려한 것입니다.build: 세그먼트 트리를 구축하는 함수입니다. 리프 노드는 각각의 사람을 나타내며 1의 값을 가집니다(살아있음을 의미). 내부 노드는 자식 노드들의 값을 합한 값으로 설정됩니다(해당 구간에 살아있는 사람의 수).update: 트리의 특정 위치(사람)를 업데이트하는 함수입니다. 사람이 제거될 때 호출되며, 해당 위치를 0으로 설정합니다(제거됨을 의미).query: 세그먼트 트리에서 **k**번째 살아있는 사람의 인덱스를 찾는 함수입니다. 이 함수는 이진 탐색과 유사한 방식으로 작동합니다.