[BOJ/백준][2164번][PYTHON] Stack, Queue, Deque

백준 2164번 : https://www.acmicpc.net/problem/2164

 

1주일 간 Stack, Queue, Deque에 대해서 공부를 하였다.

 

짧게 짧게 설명한 후, 백준 문제 풀다가 deque의 메서드 중 popleft에 대해서 설명할 것임

 

Stack은 쉽게 말하여 선입 후출(FILO) 구조이다.

쉽게 비유하자면, 웹 페이지에서 뒤로 가기 버튼을 누르게 되면, 가장 최근에 접속한 이전 페이지부터 순서대로 나오게 된디.

실제로 가장 먼저 들어간 페이지는 가장 마지막에 나오는 구조라고 생각하면 된다.

 

그 다음은 Queue이다.

큐는 선입 선출(FIFO) 구조이다.

이것 또한 일상 생활에 비유하자면, 놀이동산 입장 줄 같은 느낌이 될 것이다. 가장 먼저 온 사람이 가장 먼저 들어가는 아주 훌륭한 세상이 되는 구조이다.

 

다음은 Deque이다.

데크의 경우, 양방향 큐라고 생각하면 된다. 앞, 뒤 양쪽 방향에서 element를 추가하거나 제거할 수 있다.

이거 관련하여 해결 했던 문제가 있다. Queue에서 맨 앞의 값을 pop시키는 방식 중 pop(0)을 하게 되면 가장 왼쪽 값에 대해서 제거하는 것이 가능하다. 하지만 이 방식의 시간 복잡도는 O(n)이 된다. 하지만 데크의 popleft()의 시간 복잡도는 O(1)이라 시간 초과 문제에 걸리지 않고 해결하는 것이 가능하다. 각각의 장단점이 있겠지만, 가장 기억에 남는 차이였다.

 

파이썬에서의 Deque 사용은 보통 다음과 같이 import 하여 사용한다.

from collections import deque

보통 자주 쓰는 함수로는 메서드로는 다음과 같은 것이 있다.

# 양방향 큐에 대한 메서드 정리
d = deque()
# appendleft의 경우 가장 왼쪽에 값을 추가
d.appendleft(0)
# append는 가장 오른쪽에 값을 추가 
d.append(0)
# popleft는 가장 왼쪽 값을 pop시킴 (제거)
d.popleft()
# pop은 가장 오른쪽 값을 pop시킴 (제거)
d.pop()

 

재밌는 메서드도 존재한다.

그것은 바로 rotate 메서드이다. 

# 해당 rotate 메서드를 실행하게 되면, 데크를 좌우로 회전시킬 수 있다.
d.rotate(1)
# 1 2 3 4 5 -> 5 1 2 3 4
d.rotate(-1)
# 5 1 2 3 4 -> 1 2 3 4 5
# 이런 식의 이동이 가능함

 

큐를 구현할 때 보통 데크를 사용했다.

시작점을 건드리지 않고 끝 값을 건드리면, 큐와 동일하게 작동시키는 것이 가능하기 때문이다.

 

실제 구현을 통해 연습한다면 class, def를 통해서 구현을 할 수도 있지만, 실전에서 빠르게 사용할 때는 기존에 있던 것을 통해서

빠르게 구현하는게 좋다고 생각했다.

 

이제 조금 딥하게 찾아보자!

CPython의 소스 코드 확인을 통해서 deque의 실제 구동 방식에 대해서 찾아보자!

(다른 거는 그렇게 궁금하지 않은데, Queue의 pop(0)와 Deque의 popleft()를 찾아보고 싶기 때문)

 

#CPython의 popleft에 관련한 구조체 및 해당 메서드 구현

typedef struct BLOCK {
    struct BLOCK *leftlink;    // 왼쪽 블록을 가리키는 포인터
    struct BLOCK *rightlink;   // 오른쪽 블록을 가리키는 포인터
    PyObject *data[BLOCKLEN];  // 실제 데이터를 저장하는 배열
} block;

/* deque 객체 구조체 */
typedef struct {
    PyObject_VAR_HEAD         // Python 객체 헤더
    block *leftblock;         // 가장 왼쪽 블록
    block *rightblock;        // 가장 오른쪽 블록
    Py_ssize_t leftindex;     // 왼쪽 블록에서의 인덱스
    Py_ssize_t rightindex;    // 오른쪽 블록에서의 인덱스
    size_t state;             // 이터레이터 무효화를 위한 상태값
    Py_ssize_t maxlen;        // 최대 길이 (-1은 제한없음)
} dequeobject;

 

이것이 해당 Deque 객체 구조체 구조이다.

한 번 살펴보면, leftlink와 rightlink로 블록을 나눠서 index에 접근하는 것을 볼 수 있다.

이렇게 블록에 대해서도 left right를 통해서 나누고, 그 후 해당 블록 내의 index의 접근에 대해서도 leftindex, rightindex를 통해서 접근한다. 이렇게 하는 이유는 파이썬과 다르게 c에서는 좀 더 메모리 관리에 대해서도 접근하기 때문이라 생각한다.

(파이썬에서 Queue구조에 대해서 구현을 할 때도 crnt 등으로 현재 index에 대해서 움직이던 생각이 난다. 그때도 다른 변수를 하나 더 만들어서 뒤 쪽 접근을 가능하게 했었다.)

 

이제 popleft 구현에 대해서 살펴보겠다.

deque->leftindex--;  // 왼쪽 인덱스를 하나 감소

// 만약 leftindex가 -1이 되면 (현재 블록의 범위를 벗어나면)
if (deque->leftindex < 0) {
    // 새로운 블록이 필요
    block* newblock = allocate_block();  // 새 블록 할당
    
    // 새 블록을 현재 leftblock과 연결
    newblock->rightlink = deque->leftblock;
    deque->leftblock->leftlink = newblock;
    
    // leftblock 포인터를 새 블록으로 변경
    deque->leftblock = newblock;
    
    // 새 블록의 마지막 위치부터 시작
    deque->leftindex = BLOCKLEN - 1;
}

// 실제 데이터 저장
deque->leftblock->data[deque->leftindex] = new_value;

 

이것으로 보게 되면, 더 명확하게 볼 수 있다.

 

-- 혹시나 문법을 잘 모르시는 경우를 위해서 --

(-> : C에서 이 문법의 경우, 포인터를 사용하여 구조체에 대한 접근)

-- 이어서 설명 --

 

deque에서 leftindex의 값을 하나 감소시킨다.

여기서 if 문을 보게 되면, leftindex의 값이 0보다 작아지는 경우를 확인한다.

이유는 block으로 단위를 나눠서 접근하여 해당 block 내에서 leftindex를 통해 접근하는 구조이기 때문이다.

그렇기에 만약 leftindex 값이 0보다 작아지게 되면,

block* newblock = allocate_block();

이 부분에 따라 새로운 block을 할당해주는 것을 볼 수 있다.

여기서 leftindex의 값이 0보다 작아지는 경우를 확인하는 이유는,

일반 배열에서 값이 추가되는 경우는 C에서 선언된 배열보다 커지는 지를 확인하면 된다.

하지만, 지금의 경우 left에 대한 append, pop만을 확인하기 때문에 기존의 경우와 반대로 움직인다.

 

그 후 새 블록을 현재의 leftblock과 연결함. (leftblock 포인터를 연결)

연결한 다음, 새 블록의 마지막 위치부터 시작하며 다시 뒤로 가게 된다.

 

이제 이와 비교해서 Cpython 속 pop(0)에 대해서 알아보자

// O(n) 시간 복잡도
memmove(self->ob_item, self->ob_item + 1,
        (Py_SIZE(self) - 1) * sizeof(PyObject *));
// 모든 요소를 한 칸씩 이동해야 함

(memmove는 c 표준 라이브러리, 메모리의 내용을 기존 영역에서 새로운 영역으로 복사할 때 사용)

void *memmove(void *dest, const void *src, size_t n);

dest : 복사 대상의 메모리 포인터 (목적지)

src : 복사할 원본 메모리 포인터 (출발지)

n : 복사할 바이트 수 (위와 같다)

 

pop에 대한 메서드는 위와 같이 구현되어있다.

 

차이를 본다면, popleft의 경우는 leftindex만 하나 조절을 하게 되면, 기존에 선언된 블록 내에서 움직이며

O(1)의 작업만 수행한다.

하지만, pop(0)의 경우 memmove를 통해서 전체 메모리의 위치를 옮기며, 모든 요소의 위치를 하나 옮기게 된다.

즉, 1 2 3 4 5에서 1을 삭제한다는 가정에서 단순히 1을 가리키고 있던 index포인터를 하나 옆으로 옮기는 것이 아닌

1 2 3 4 5 -> 2 3 4 5 5 이런 식의 메모리를 덮어 씌우게 된다. 제거 하는 1 위치에 2부터 다시 덮으면서 저장하게 되는 것이다.

이렇기 때문에 시간의 차이가 나게 된다. 전체를 이동시키면서 시간복잡도는 O(n)이 들게 된다.

 

 

이제 백준에서 느낀 문제에 대해서 확인해보자

'''

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

'''

그냥 하나를 버리고 그 다음 꺼를 밑에다 껴넣는 문제이다. 근데 시간 제한이 2초(추가 시간 없음)로 되어있다.

그러면 누가봐도 뭔가 께름직한 느낌이 든다. 여기까지 글을 읽었다면, 딱 봐도 뭐가 문제고 뭐가 해결 방법인 지 확인할 수 있다.

 

시간초과의 제한을 건 이유는 pop(0) 하지 말라는 뜻이고

popleft를 통해서 해결하란 뜻이다.

 

아래는 정답 코드이다.

from collections import deque
import sys
n = int(sys.stdin.readline().rstrip())

q = deque()
for i in range(n):
    q.append(i+1)

while(True):
    if len(q) == 1:
        print(q[0])
        break
    q.popleft()
    if len(q) == 1:
        print(q[0])
        break
    q.append(q.popleft())

다시 돌린 이유는, 깜빡하고 백준 plugin 등록을 안해서 깃헙에 안올라감 ;