Jesephus problem은 이번에 배운 큐를 이용하여 풀 수 있는 대표적인 문제다.
Joesphus(n, k) => n 총 인원 k => 몇번째 사람마다 제외할것인가
가령 Joesphus(5, 2)일때 5명 중 2번째 마다 제외해서 마지막에 누가 남는지 알아보는 것이다.
이때 [1, 2, 3, 4, 5] 큐를 만들어서 enqueue와 dequeue를 이용하여 풀어보자
[1, 2, 3, 4, 5] 1은 dequeue하고 바로 enqueue => [1, 2, 3, 4, 5, 1]
2는 해당되기 때문에 dequeue만 실행 => [1, 2, 3, 4, 5, 1]
3은 dequeue하고 바로 enqueue => [1, 2, 3, 4, 5, 1, 3]
4는 해당되기 때문에 dequeue만 실행 => [1, 2, 3, 4, 5, 1, 3]
5는 dequeue하고 바로 enqueue => [1, 2, 3, 4, 5, 1, 3, 5]
1은 해당되기 때문에 dequeue만 실행 => [1, 2, 3, 4, 5, 1, 3, 5]
3은 dequeue하고 바로 enqueue => [1, 2, 3, 4, 5, 1, 3, 5, 3]
5는 해당되기 때문에 dequeue만 실행 => [1, 2, 3, 4, 5, 1, 3, 5, 3]
최종적으로 3이 남음 => [1, 2, 3, 4, 5, 1, 3, 5, 3]
'CS > Data Structure & Algorithm' 카테고리의 다른 글
| 한방향 연결리스트 및 연산(삽입, 삭제, 탐색) (0) | 2022.02.06 |
|---|---|
| 연결리스트 (Linked List) 기본개념 (0) | 2022.02.04 |
| Queue (FIFO, 순차적자료구조) (0) | 2022.02.02 |
| Infix(중위표기법) -> Postfix(후위표기법), 그리고 스택 계산 (0) | 2022.01.29 |
| Stack (LIFO, 순차적자료구조) (0) | 2022.01.28 |