이 글의 작성 배경
요세푸스 문제를 다양한 방법으로 풀어보면서 배열, 큐, 링크드 리스트, 세그먼트 트리 등 여러 알고리즘적 접근을 시도해 보았다. 각 방법에서 최적화를 시도했지만, 시간 복잡도는 여전히 \( O(n^2) \) 정도였고, 세그먼트 트리를 사용해도 \( O(n \log n) \) 이 최대였다. 조금 더 최적화할 방법이 뭔가 있을 것 같은데... 고민하다가 문제를 가상의 순환 구조로 해석하면 어떤 규칙이나 패턴이 존재하지 않을까 하는 의문이 생겼다. 그러던 중, 점화식 풀이법을 알게 되며 이 방식에 주목하게 되었다.
점화식을 활용한 풀이법은 흥미로웠지만, 문제는... 어려웠다. 😭 특히, 이 점화식을 어떻게 유도할 수 있는지, 그 논리적 근거와 직관이 어떻게 도출되는지, 그리고 실제로 이 점화식이 어떻게 작동하는지 물음표가 켜졌다. 이 글은 이러한 궁금증을 풀기 위해 공부하면서 작성한 내용이다.
문제 소개
요세푸스 문제는 역사적인 사건에서 유래한 고전적인 순열 문제로, 원형으로 앉은 사람들 중 특정 간격으로 사람들을 제거해 나갈 때 마지막에 남는 사람 또는 제거되는 순서를 구하는 문제이다.
문제 설명은 다음과 같다.
N명의 사람들이 원형으로 앉아 있고, 순서대로 K번째 사람을 제거합니다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나갑니다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속됩니다.
원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다.
예를 들어, (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.
점화식으로 마지막 남은 사람 구하기
문제에 따라 순열을 전부 구해야 하는 경우도 있고, 마지막 남은 사람만 구해야하는 경우도 있다. 마지막 남은 사람만 구하는 경우, 재귀식을 이용해서 효율적으로 풀 수 있다.
이때, 마지막 남은 사람만 구하는 경우에 대해서 원형 구조를 가진 문제에서 실제로 자료구조를 회전시키는 대신, 수학적으로 인덱스를 계산하여 문제를 해결할 수 있다.
점화식
사람들은 1번부터 N번까지 번호가 매겨져 있고, 인덱스는 계산의 편의를 위해 0부터 N-1까지 사용할 때, 재귀식은 다음과 같다.
\[
J(n, k) = (J(n - 1, k) + k) \mod n
\]
여기서
- \( J(n, k) \): \( n \)명의 사람이 있을 때 요세푸스 순열에서 마지막으로 남는 사람의 위치 (0부터 시작하는 인덱스)
- \( k \): 제거할 사람의 간격
단계별 풀이 과정
먼저 이와 같은 점화식이 어떻게 작동하는지 데이터 흐름을 시각화해서 살펴보자.
1. 재귀식 수립
- 기저 사례:
\[
J(1, K) = 0
\]
- 재귀 관계식:
\[
J(n, K) = (J(n - 1, K) + K) \mod n
\]
여기서
- \( J(n, K) \): \(n\)명의 사람이 있을 때 마지막으로 남는 사람의 위치 (0부터 시작하는 인덱스)
- \( K \): 제거할 사람의 간격
2. 단계별 점화식 흐름
이제 \( N = 7 \), \( K = 3 \)인 경우에 대해 단계별로 점화식이 어떻게 작동하는지 살펴보자.
\( n \)을 1부터 7까지 증가시키면서 \( J(n, K) \)의 값을 계산한다.
1. n = 1
- 계산:
\[
J(1, 3) = 0
\] - 설명: 사람이 한 명 남았을 때, 마지막으로 남는 사람의 위치는 0번 인덱스이다.
2. n = 2
- 이전 값: \( J(1, 3) = 0 \)
- 계산:
\[
J(3, 3) = (J(2, 3) + 3) \mod 3 = (1 + 3) \mod 3 = 1
\] - 데이터 흐름:
- 현재 남은 사람들: 인덱스 0 (1번), 인덱스 1 (2번)
- 제거되는 사람의 위치: 인덱스 ( (J(1, 3) + K - 1) \mod n = (0 + 3 - 1) \mod 2 = 0 )
- 제거된 사람: 인덱스 0 ⇒ 1번
- 마지막으로 남는 사람: 인덱스 1 ⇒ 2번
3. n = 3
- 이전 값: \( J(2, 3) = 1 \)
- 계산:
\[
J(3, 3) = (J(2, 3) + 3) \mod 3 = (1 + 3) \mod 3 = 1
\] - 데이터 흐름:
- 현재 남은 사람들: 인덱스 0 (1번), 인덱스 1 (2번), 인덱스 2 (3번)
- 제거되는 사람의 위치: 인덱스 \( (J(2, 3) + K - 1) \mod n = (1 + 3 - 1) \mod 3 = 0 \)
- 제거된 사람: 인덱스 0 \( \Rightarrow \) 1번
- 남은 사람들: 인덱스 1 (2번), 인덱스 2 (3번)
- 마지막으로 남는 사람: 인덱스 1 \( \Rightarrow \) 2번
4. n = 4
- 이전 값: \( J(3, 3) = 1 \)
- 계산:
\[
J(4, 3) = (J(3, 3) + 3) \mod 4 = (1 + 3) \mod 4 = 0
\] - 데이터 흐름:
- 현재 남은 사람들: 인덱스 0 (1번), 인덱스 1 (2번), 인덱스 2 (3번), 인덱스 3 (4번)
- 제거되는 사람의 위치: 인덱스 \( (J(3, 3) + K - 1) \mod n = (1 + 3 - 1) \mod 4 = 3 \)
- 제거된 사람: 인덱스 3 ⇒ 4번
- 남은 사람들: 인덱스 0 (1번), 인덱스 1 (2번), 인덱스 2 (3번)
- 마지막으로 남는 사람: 인덱스 0 ⇒ 1번
5. n = 5
- 이전 값: \( J(4, 3) = 0 \)
- 계산:
\[
J(5, 3) = (J(4, 3) + 3) \mod 5 = (0 + 3) \mod 5 = 3
\] - 데이터 흐름:
- 현재 남은 사람들: 인덱스 0 (1번), 인덱스 1 (2번), 인덱스 2 (3번), 인덱스 3 (4번), 인덱스 4 (5번)
- 제거되는 사람의 위치: 인덱스 \( (J(4, 3) + K - 1) \mod n = (0 + 3 - 1) \mod 5 = 2 \)
- 제거된 사람: 인덱스 2 ⇒ 3번
- 남은 사람들: 인덱스 0 (1번), 인덱스 1 (2번), 인덱스 3 (4번), 인덱스 4 (5번)
- 마지막으로 남는 사람: 인덱스 3 ⇒ 4번
6. n = 6
- 이전 값: \( J(5, 3) = 3 \)
- 계산:
\[
J(6, 3) = (J(5, 3) + 3) \mod 6 = (3 + 3) \mod 6 = 0
\] - 데이터 흐름:
- 현재 남은 사람들: 인덱스 0 (1번), 인덱스 1 (2번), 인덱스 2 (3번), 인덱스 3 (4번), 인덱스 4 (5번), 인덱스 5 (6번)
- 제거되는 사람의 위치: 인덱스 \( (J(5, 3) + K - 1) \mod n = (3 + 3 - 1) \mod 6 = 5 \)
- 제거된 사람: 인덱스 5 ⇒ 6번
- 남은 사람들: 인덱스 0 (1번), 인덱스 1 (2번), 인덱스 2 (3번), 인덱스 3 (4번), 인덱스 4 (5번)
- 마지막으로 남는 사람: 인덱스 0 ⇒ 1번
7. n = 7
- 이전 값: \( J(6, 3) = 0 \)
- 계산:
\[
J(7, 3) = (J(6, 3) + 3) \mod 7 = (0 + 3) \mod 7 = 3
\] - 데이터 흐름:
- 현재 남은 사람들: 인덱스 0 (1번), 인덱스 1 (2번), 인덱스 2 (3번), 인덱스 3 (4번), 인덱스 4 (5번), 인덱스 5 (6번), 인덱스 6 (7번)
- 제거되는 사람의 위치: 인덱스 \( (J(6, 3) + K - 1) \mod n = (0 + 3 - 1) \mod 7 = 2 \)
- 제거된 사람: 인덱스 2 ⇒ 3번
- 남은 사람들: 인덱스 0 (1번), 인덱스 1 (2번), 인덱스 3 (4번), 인덱스 4 (5번), 인덱스 5 (6번), 인덱스 6 (7번)
- 마지막으로 남는 사람: 인덱스 3 ⇒ 4번
최종 결과
- 마지막으로 남는 사람의 위치: \( J(7, 3) = 3 \)
- 실제 사람 번호: \( 3 + 1 = 4 \)번
즉, 최종 남는 사람은 4번으로 확인된다.
이와 같은 결과가 맞는 것인지, 순서를 추적해보면서 확인해보자.
점화식 검증하기
- 사람들: [1번, 2번, 3번, 4번, 5번, 6번, 7번]
- 현재 인덱스: 0
단계별 제거 과정
- 첫 번째 제거
- 계산:
\[
\text{제거할 인덱스} = (\text{현재 인덱스} + K - 1) \mod \text{남은 사람 수} = (0 + 3 - 1) \mod 7 = 2
\] - 제거된 사람: 인덱스 2 ⇒ 3번
- 남은 사람들: [1번, 2번, 4번, 5번, 6번, 7번]
- 다음 시작 인덱스: 2 (제거된 인덱스 그대로)
- 계산:
- 두 번째 제거
- 계산:
\[
\text{제거할 인덱스} = (2 + 3 - 1) \mod 6 = 4
\] - 제거된 사람: 인덱스 4 ⇒ 6번
- 남은 사람들: [1번, 2번, 4번, 5번, 7번]
- 다음 시작 인덱스: 4
- 계산:
- 세 번째 제거
- 계산:
\[
\text{제거할 인덱스} = (4 + 3 - 1) \mod 5 = 1
\] - 제거된 사람: 인덱스 1 ⇒ 2번
- 남은 사람들: [1번, 4번, 5번, 7번]
- 다음 시작 인덱스: 1
- 계산:
- 네 번째 제거
- 계산:
\[
\text{제거할 인덱스} = (1 + 3 - 1) \mod 4 = 3
\] - 제거된 사람: 인덱스 3 ⇒ 7번
- 남은 사람들: [1번, 4번, 5번]
- 다음 시작 인덱스: 3 \mod 3 = 0
- 계산:
- 다섯 번째 제거
- 계산:
\[
\text{제거할 인덱스} = (0 + 3 - 1) \mod 3 = 2
\] - 제거된 사람: 인덱스 2 ⇒ 5번
- 남은 사람들: [1번, 4번]
- 다음 시작 인덱스: 2 \mod 2 = 0
- 계산:
- 여섯 번째 제거
- 계산:
\[
\text{제거할 인덱스} = (0 + 3 - 1) \mod 2 = 0
\] - 제거된 사람: 인덱스 0 ⇒ 1번
- 남은 사람들: [4번]
- 다음 시작 인덱스: 0
- 계산:
- 마지막 남은 사람
- 남은 사람: 4번
따라서 점화식의 계산 결과와 실제로 순열 메커니즘을 추적하며 최종 확인된 결과가 일치한 것을 볼 수 있다.
점화식 도출 과정
그런데 여전히 풀리지 않는 부분이 있다. 그것은 도대체 이러한 점화식은 어떤 원리에 의해 작동하느냐는 것이다. 즉, 이 점화식이 어떻게 도출되는지가 궁금하다.
재귀 관계식 \( J(n, K) = (J(n - 1, K) + K) \mod n \)이 어떻게 유도되는지, 그리고 이 관계식을 어떻게 떠올릴 수 있는지에 대해 자세히 살펴보자.
1. 요세푸스 문제의 구조 이해
요세푸스 문제는 원형으로 배열된 \( n \)명의 사람들 중에서 \( K \)번째 사람을 반복적으로 제거해 나가는 과정에서 마지막에 남는 사람의 위치를 구하는 문제이다.
- 사람들은 원형으로 앉아 있으므로, 마지막 사람까지 제거되는 순서는 순환 구조를 가진다.
- 이때, 사람들의 위치는 1번부터 \( n \)번까지 번호가 매겨져 있다.
2. 재귀 관계식의 기본 아이디어
재귀 관계식은 기본적으로 작은 문제를 기반으로 더 큰 문제를 해결하는 방식이다.
요세푸스 문제의 경우 이를 통해 \( n \)명의 사람 중 마지막으로 남는 사람의 위치를 구할 수 있다. 핵심은 \( n \)명에서 \( K \)번째 사람을 제거한다면, 남은 순열은 \( n-1 \)명에 대해서 적용되므로, 결국 남은 \( n-1 \)명의 문제로 귀결된다는 점이다. 즉, \( n \)과 \( n-1 \)의 선형적 관계에 따라, 이를 재귀적으로 풀어낼 수 있는 관계식을 설정할 수 있다. 단계적으로 살펴보자.
1) 기저 사례:
먼저, 문제를 가장 작은 형태인 \( n = 1 \)의 경우로 시작한다. 이 경우 제거할 사람도 없기 때문에 마지막으로 남는 사람은 자명하게 1번 자리이다. 따라서,
\[
J(1, K) = 0
\]
여기서 0은 편의상 1번 자리를 나타내기 위해 사용된 것이다. 즉, 남은 사람이 한 명일 때는 바로 그 사람이 승자가 된다.
2) 일반적인 재귀 과정:
그렇다면, \( n \)명이 있을 때 어떻게 문제를 풀 수 있을까? 먼저 \( K \)번째 사람을 제거한 후에는 남은 사람들이 \( n-1 \)명이 된다. 이 상황에서 다시 \( K \)번째 사람을 제거하는 문제로 귀결된다. 문제를 \( n-1 \)명의 상황으로 축소했으므로, 우리는 \( n-1 \)명에서 마지막으로 남는 사람의 위치를 알 수 있다. 이를 \( J(n-1, K) \)라고 하자.
그렇다면, \( n \)명에서 \( K \)번째 사람을 제거한 후 남는 사람의 위치를 어떻게 구할 수 있을까? 중요한 점은 \( K \)번째 사람을 제거함으로써 남은 사람들의 번호가 재정렬된다는 것이다. 구체적으로는, 원형 구조에서 제거된 사람 다음의 사람이 첫 번째 사람처럼 되기 때문에, 남은 사람들의 위치는 한 칸씩 앞으로 이동한다. 이 변화를 반영하기 위해서, \( J(n-1, K) \)에서 나온 결과에 \( K \)를 더한 후, \( n \)으로 나눈 나머지를 구한다. 이를 수식으로 나타내면,
\[
J(n, K) = (J(n-1, K) + K) \mod n
\]
요세푸스 문제의 본질은 제거된 사람들에 의해 남은 사람들의 번호가 계속해서 변화하는 점에 있다. 한 명이 제거될 때마다, 남은 사람들이 다시 첫 번째부터 번호가 매겨지듯 재정렬되는 것이며, 이러한 동작을 반복적으로 추적해 나가는 것이 재귀 관계식의 핵심 아이디어이다.
이를 바탕으로 재귀 관계식을 유도해보자.
3. 재귀 관계식의 유도 과정
Step 1: 작은 문제에서 큰 문제로의 전환
- \( n - 1 \)명의 사람이 남았을 때의 마지막 생존자의 위치를 알고 있다고 가정한다.
- 이제, 이 정보를 이용하여 \( n \)명의 사람이 있을 때의 마지막 생존자의 위치를 찾으려고 한다.
Step 2: 사람들의 번호 재정의
- 원형 구조이기 때문에, 사람들의 위치는 제거될 때마다 변경된다.
- 그러나, 제거되는 순서는 사람들의 상대적인 위치에 의해 결정된다.
- 따라서, 사람들의 번호를 재정의하여 문제를 단순화할 수 있다.
Step 3: 새로운 인덱스 체계 도입
- 제거될 때마다 남은 사람들의 번호를 0부터 시작하는 새로운 인덱스로 표현한다.
- 이렇게 하면, 각 단계에서의 사람들의 위치를 쉽게 추적할 수 있다.
Step 4: 재귀 관계식 수립
- \( n \)명의 사람이 있을 때 마지막 생존자의 위치를 \( J(n, K) \)라고 하자.
- \( n - 1 \)명의 사람이 있을 때의 마지막 생존자의 위치를 \( J(n - 1, K) \)라고 하자.
- \( n \)명의 사람이 있을 때 첫 번째로 제거되는 사람의 위치는 \( (K - 1) \mod n \)이다.
- 이때, 제거된 후 남은 \( n - 1 \)명의 사람들의 새로운 위치는 다음과 같이 재배열된다.
Step 5: 위치 조정
- 제거된 사람 다음 위치부터 시작하여 남은 사람들을 0부터 \( n - 2 \)까지 재인덱싱한다.
- 그러면, \( n - 1 \)명의 사람들로 이루어진 새로운 문제로 변환된다.
- 이 부분이 핵심이므로, 간단한 예시를 통해 살펴보자.
예를 들어, \( n = 5 \), \( K = 3 \)일 때, 원형으로 앉아 있는 5명의 사람에 대해서, 다음과 같은 배열로 시작할 것이다.
- 사람들의 번호: [0, 1, 2, 3, 4] (0부터 시작하는 인덱스 사용)
- 원형 배열:
[0] - [1] - [2] - [3] - [4] - (다시 [0]으로 연결)
이때, 제거할 사람의 위치는
\[
\text{제거할 위치} = (K - 1) \mod n = (3 - 1) \mod 5 = 2
\]
로 인덱스 2번 사람이 된다. 그렇다면, 이후의 배열에서 다음 사람을 찾아내는 작업은 실질적으로, 3번 사람부터 다시 계산해야 하는 상황과 같다. 즉, 3번 사람이 0번 인덱스가 된 상황과 동일한 문제가 되는 것이다. 따라서, 제거된 사람 다음부터 순서대로 새로운 인덱스를 부여하면,
- 제거된 사람 다음 인덱스: 3번부터 시작
- 새로운 번호 부여:
기존 인덱스 사람 번호 새로운 인덱스 3 3 0 4 4 1 0 0 2 1 1 3
재배열된 사람들은 [3, 4, 0, 1]가 되며, 이는 이제 \( n = 4 \)명에 대한 문제와 동일해진다.
이제 이를 수학적으로 표기해보면,
Step 6: 수학적 표현
- \( n \)명의 사람들 중에서 첫 번째로 제거된 사람의 위치는 \( (K - 1) \mod n \)이다.
- 제거 후 남은 사람들의 위치를 조정하면, \( n - 1 \)명의 사람들로 구성된 새로운 문제에서의 마지막 생존자의 위치는 \( J(n - 1, K) \)이다.
- 원래 \( n \)명의 사람들 중에서의 위치로 변환하려면, 조정된 위치를 다시 실제 위치로 변환해야 한다.
Step 7: 실제 위치로의 변환
- 새로운 위치에서의 생존자 위치 \( J(n - 1, K) \)를 원래 위치로 변환하려면 다음과 같이 계산한다.
- 실제 위치:
\[
(J(n - 1, K) + K) \mod n
\] - 여기서 \( K \)는 제거된 사람의 다음 위치로의 이동을 반영하며, \( n \)으로 모듈러 연산을 하여 원형 구조를 유지한다.
4. 재귀 관계식 완성
따라서, 재귀 관계식 유도는 다음과 같이 완성된다.
\[
J(n, K) = (J(n - 1, K) + K) \mod n
\]
즉, 이 관계식은 \( n - 1 \)명의 사람들로 이루어진 문제의 해답을 이용하여 \( n \)명의 사람들로 이루어진 문제의 해답을 구할 수 있게 해준다.
이 관계식을 어떻게 떠올릴 수 있을까?
결국 수학적 귀납법 도출 과정과 유사하다. 작은 \( n \) 값에 대해 직접 시뮬레이션을 해보면서 제거되는 사람의 위치와 마지막으로 남는 사람의 위치 사이의 패턴을 찾고, 기저 사례에서 시작하여, \( n \)에서의 해답이 \( n - 1 \)에서의 해답과 어떻게 연결되는지 찾아내야 한다.
끝.
'알고리즘' 카테고리의 다른 글
| 세그먼트 트리에 대해 알아보자: 해결하는 문제와 데이터 구조, 작동 방식, 사용 사례, 자바 코드 (0) | 2024.12.21 |
|---|---|
| 모노토닉 스택(monotonic stack) 개념, 작동원리 + 예제 문제들 (주식 가격, 탑, 히스토그램에서 가장 큰 직사각형 찾기) (0) | 2024.10.06 |
