Queue를 이용한 Josephus Problem구현

Queue를 이용한 Josephus 문제 풀이입니다. 

1. Queue는 FIFO다.
따라서, 선입 선출 형태가 되어야 한다.

2. enqueue
items 라는 빈 리스트에 enqueue 메서드는 value를 append한다.

 

3. dequeue

비어있는지 확인하고, 데이터를 추출하여, 위치이동을 시킨다. 그리고 결과 반환

 

Queue를 그림으로 표기해보았습니다.

4. Josephus 문제
 

4-1. Josephus를 원형으로 이해해보자

• 한 바퀴 돌면 제거
• k 번째 사람 제거
• 제거 안 된 사람은 뒤로 다시 감
• 마지막 1명 남으면 winner

4-2. Queue의 FIFO 개념을 연결하자

• 앞에서 꺼내고
• 제거 대상 아니면 뒤로 넣고
• 제거 대상이면 버린다.

4-3. front_index 방식으로 queue 구현하자

• pop(0) 안쓰고
• front_index를 하나씩 증가시키는 방식으로 구현

Josephus 문제를 시각화 해봤어요..ㅋㅋ;

 

생존한 사람의 number는 dequeue된 후, enqueue로 맨 끝 인덱스에 append시킨다.

 

이것을 Python으로 구현해 보았습니다.

class Queue:
    def __init__(self):
        self.items = [] # 빈 리스트 생성
        self.front_index = 0 # pop(0) 안쓰고 front_index를 하나씩 증가시키는 방식

    def __len__(self): # 전체 칸 수 
        return len(self.items) - self.front_index #self.front_index는 이미 꺼내서 무시해야 하는 칸 수

    def enqueue(self, val):
        self.items.append(val)

    def dequeue(self):
        if self.front_index == len(self.items):
            return None
        x = self.items[self.front_index]
        self.front_index += 1
        return x
    
def josephus(n, k):
    q = Queue()

    for i in range(1, n + 1): # 1부터 n까지 반복하는 for문 (루프) +1은 마지막값은 출력안되므로 
        q.enqueue(i)
        
    while len(q) > 1:
        for _ in range(k - 1):
            q.enqueue(q.dequeue()) 
        q.dequeue() # k 번쨰 사람 제거 
        
    return q.dequeue()
    
print("Resuelt:", josephus(14, 3))

 

 

결과 값

 

 

해당 방식으로 Josephus 문제를 구현해보았습니다.

이 방식은
장점 : pop(0)을 쓰면 뒤에 있는 모든 데이터를 앞으로 한 칸씩 당겨야 해서 시간이 오래 걸립니다 O(n)
하지만 이 방식은 front_index 즉 다음 데이터를 가리키도록 한 칸 옆으로 옮기기 때문에 매우 빠릅니다. 그래서 O(1) 상수 시간이 됩니다.
단점 : 리스트에서 데이터를 실제로 지우지 않고 front_index만 옮기기 때문에, 앞부부엔 사용하지 않는 데이터가 메모리를 계속 차지 하게되는 단점이 존재합니다.

 

장점은 시간 복잡도가 빠른 대신, 단점은 공간 복잡도가 비효율적이게 되면서 메모리를 계속 갉아먹는 구조가 됩니다. 

해결책은 두 가지 방법을 사용합니다.

 

1.  원형 큐 (Circular Queue)
   리스트의 끝에 도달하면 다시 앞쪽(0번 인덱스)의 빈 공간으로 돌아가서 데이터를 채우는 방식입니다.
   정해진 크기의 메모리를 효율적으로 돌려 막기 할 수 있습니다.
2. collections.deque 
   Python 표준 라이브러리인 collecctions.deque를 사용하면 됩니다.
   
   • 내부 구조 : 양방향 연결 리스트(Doubly Linked List)와 유사한 블록 단위 구조입니다.
   • 장점 : 앞쪽 데이터를 뺄 때(popleft())공간을 즉시 반환하며, 시간 복잡도도 O(1)로 매우 빠릅니다.

요약하자면 제가 작성한 방식은 시간 복잡도에서는 고려를 해보았지만, 공간 복잡도는 전혀 고려하지 않은 형태가 되었던것 같습니다.