테페리넷

사용자 도구

사이트 도구

현재 위치: 테페리넷 » Problem Solving » 요세푸스 문제
ps:요세푸스_문제

목차

요세푸스 문제

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

  • 그냥 하나씩 삭제하는 과정을 그대로 시뮬레이션을 해보면서 삭제되는 원소를 출력하는 식으로 구현한다.
  • 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)

관련 문제

토론

댓글을 입력하세요:
Q L X B P
 
ps/요세푸스_문제.txt · 마지막으로 수정됨: 2021/08/06 14:13 저자 teferi