요세푸스가 겪은 일화에서 유래된 문제인 요세푸스 문제. 요세푸스는 의리가 없는 놈이었다..;
풀이 방법은 대강 아래와 같음
- 제일 쉬운 방법: circular queue를 만들어서 iterating + erase
-> 느리고 n이 큰 경우 메모리 많이 차지함 - 약간 더 좋은 방법: 위 방법에서 iterating에 index mod를 적용
-> 여전히 메모리는 많이 차지함 - 치트키: 점화식을 이용
-> 마지막 생존자를 빠르게 찾을 수 있다
초항과 일반항은 위와 같다. 유도하는 건 여기 참고. 내일 복귀라 정리하기 싫당
반응형
'알고리즘 > 미분류' 카테고리의 다른 글
| a^n 계산을 O(log n)으로 하는 법 (분할정복을 이용한 거듭제곱) (0) | 2020.07.03 |
|---|---|
| 수학적 귀납법 (Mathematical Induction) (0) | 2020.06.08 |
| 좌표 압축(Coordinate compression) (0) | 2020.05.09 |
