요세푸스 문제

Josephus problem과 https://cp-algorithms.com/others/josephus_problem.html을 참고하자.
제외되는 번호를 순서대로 나열한 요세푸스 순열을 구하는 문제와, 마지막으로 제외되는 번호를 구하는 문제가 있다.
- 1~n번까지 번호가 있을때, 매 k번째 번호를 제외시킨다

요세푸스 순열을 모두 나열하기

그냥 하나씩 삭제하는 과정을 그대로 시뮬레이션을 해보면서 삭제되는 원소를 출력하는 식으로 구현한다.
k가 작을 때는 deque를 이용해서 시뮬레이션 한다. 맨 앞의 원소를 삭제하고, 그다음 k-1개의 원소를 맨 뒤로 rotate 시키는 것을 반복한다. 이러면 O(kn)에 처리할 수 있다.
k가 크면, x번째 원소를 삭제하고, 남은 원소중에서 (x + k - 1) % {남은 원소의 수} 번째 원소를 삭제하는 것을 반복하는 식으로 처리한다. x번째 원소를 찾고 삭제하는 것은, Order Statistic Tree를 이용해서 O(logn)에 처리할 수 있다. 따라서 전체 시간복잡도는 O(nlogn)이 된다

마지막으로 남는 번호를 찾는 문제

위의 방법처럼 전체 수열을 다 구해서, 마지막 숫자만 출력해도 되긴 하지만, 좀더 효율적으로 풀수 있는 방법들이 있다.
k=2일때는 마지막 숫자를 closed form으로 구할 수 있다.
- $ J_{n,2} = 1+2(n-2^{\lfloor{log_{2}n}\rfloor}) $
- 비트 연산자를 활용하면 아래처럼 구현할 수 있다.
- ```
def josephus(n):
    return ~(1 << n.bit_length()) & ((n << 1) | 1)
```
일반적으로는 아래 점화식을 이용해서 O(n)에 풀 수 있다
- $ J_{n,k} = (J_{n-1,k}+k){\bmod n},{\text{ with }}J_{1,k}=0 $
  - 이 식은 0-base 기준으로 계산한 값이라서, 계산이 끝나면 1을 더해줘야 한다
- 코드는 이런식이 된다
- ```
def josephus(n, k):
    answer = 0
    for i in range(2, n + 1):
        answer = (answer + k) % i
    return answer + 1
```
k가 작을 때에는 O(klogn)에 계산할 수 있는 다른 점화식이 있다
- $ {\displaystyle g(n,k)={\begin{cases}0&{\text{if }}n=1\\(g(n-1,k)+k){\bmod {n}}&{\text{if }}1<n<k\\\left\lfloor {\frac {k((g(n',k)-n{\bmod {k}}){\bmod {n}}')}{k-1}}\right\rfloor {\text{where }}n'=n-\left\lfloor {\frac {n}{k}}\right\rfloor &{\text{if }}k\leq n\\\end{cases}}} $
  - g(n,k)은 앞에서 쓰던 J_n,k와 같은 값이다. 0-base 이다.
- 코드는 이런 식이 된다.
- ```
def josephus(n, k):
    def _josephus(n):
        if n == 1:
            return 0
        if k > n:
            return (_josephus(n - 1) + k) % n    
        res = _josephus(n - n // k) - n % k
        return res + (n if res < 0 else res // (k - 1))
    
    return (n if k == 1 else _josephus(n) + 1)
```

목차

요세푸스 문제

요세푸스 순열을 모두 나열하기

관련 문제

마지막으로 남는 번호를 찾는 문제

관련 문제