내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
요세푸스 문제
ps:요세푸스_문제
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 요세푸스 문제 ====== * [[wp>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번째 원소를 찾고 삭제하는 것은, [[ps:Order Statistic Tree]]를 이용해서 O(logn)에 처리할 수 있다. 따라서 전체 시간복잡도는 O(nlogn)이 된다 ==== 관련 문제 ==== * [[ps:problems:boj:2161]] : k=2인 경우. deque 사용 * [[ps:problems:boj:1168]] : k≤n≤100,000. Order Statistic Tree 사용 ===== 마지막으로 남는 번호를 찾는 문제 ===== * 위의 방법처럼 전체 수열을 다 구해서, 마지막 숫자만 출력해도 되긴 하지만, 좀더 효율적으로 풀수 있는 방법들이 있다. * k=2일때는 마지막 숫자를 closed form으로 구할 수 있다. * $ J_{n,2} = 1+2(n-2^{\lfloor{log_{2}n}\rfloor}) $ * 비트 연산자를 활용하면 아래처럼 구현할 수 있다. * <dkpr py> def josephus(n): return ~(1 << n.bit_length()) & ((n << 1) | 1) </dkpr> * 일반적으로는 아래 점화식을 이용해서 O(n)에 풀 수 있다 * $ J_{n,k} = (J_{n-1,k}+k){\bmod n},{\text{ with }}J_{1,k}=0 $ * 이 식은 0-base 기준으로 계산한 값이라서, 계산이 끝나면 1을 더해줘야 한다 * 코드는 이런식이 된다 * <dkpr py> def josephus(n, k): answer = 0 for i in range(2, n + 1): answer = (answer + k) % i return answer + 1 </dkpr> * 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 이다. * 코드는 이런 식이 된다. * <dkpr py> 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) </dkpr> ==== 관련 문제 ==== * [[ps:problems:boj:2164]] : k=2 인 경우. * [[ps:problems:boj:11025]]: k≤n≤5,000,000. O(n) 알고리즘 필요 * [[ps:problems:boj:1179]] : n≤10*15, k≤90. O(klogn) 알고리즘 필요
ps/요세푸스_문제.txt
· 마지막으로 수정됨: 2021/08/06 14:13 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로