파이썬에서 자료구조 이해가 코딩 테스트 및 알고리즘 성능 (시간복잡도)에 미치는 영향
주의) 제목은 거창하지만 본 내용은 노 베이스 비전공자 출신인 본인에게만 새롭고 유용한 내용이고
자료구조에 대해 빠삭한 사람에겐 너무 당연해서 어이없는 얘기.
본인과 같이 근본 없는 코딩 어린이는 코딩 문제를 파이썬으로 풀 때 가장 만만한 게
list 형태라고 느껴져 list를 참 많이 쓰는데 list에서 스택 형태의 참조나 연산을 할 때는 괜찮지만
큐 형태의 연산을 할 때는 주의가 필요하다. 이게 무슨 소리인고 하니
큐는 그림과 같은 구조로 데이터 삽입을 뒤에서 하면 삭제는 반대로 앞에서 하는 구조로
다시 말하자면 큐(queue)는 들어간 쪽과 나온 쪽 양쪽이 뚫려서 처음 들어간 게 쭉쭉 밀려서 앞쪽으로 나오고
그다음 들어간 게 그다음 앞으로 나오게 되는 FIFO (First In First Out)의 구조를 가진 자료형이다.
그러나 스택(stack)은 한쪽면만 뚫려있기 때문에 방금 넣은 건 입구 쪽에 있어서 바로 꺼낼 수 있지만
한참 전에 넣고 그 뒤에 여러 층이 쌓이게 되면 그걸 다시 꺼내보고 싶을 때 위에서부터 한층씩 한층씩 다 꺼내서
끄집어내야 하기 때문에 오히려 LIFO (Last In Fist Out)가 특징이 되는 구조이다.
파이썬에서 list에서 pop() 연산을 하면 스택의 연산상 쉽게 할 수 있는 연산(가장 얕은 것 하나만 제거)이기 때문에
문제가 없으나 pop(0), 즉 첫번째 요소를 제거하려고 하면 가장 깊숙한 요소를 제거해야 하므로
스택이 아니라 큐 연산이 용이한데 list에서 그대로 시행하게 되면 O(n)의 시간 복잡도를 가져서 비효율적이다.
따라서 pop(0)같은 연산은 collections.deque()를 통해 데큐 자료형으로 바꾼 후에 연산하면 더 깊숙히까지 한층 한층을 뒤지며 찾는 대신 양쪽 말미의 요소는 한 번에 처리할 수 있게 되어 시간상 성능이 훨씬 증가하게 된다.
또한 파이썬 collections.deque()는 양쪽에서 데이터를 pop(),popleft()를 통해 삭제할 수 있고 삽입 역시 append(), appendleft()를 통해 할 수 있는데 자료 구조상 양 쪽으로 큐가 뚫린 형태라서
큐보다 더 효율적으로 양쪽으로 삽입, 삭제를 할 수 있으므로 시간복잡도를 줄이는데 매우 좋은 자료구조이다.
2021.08.16 - [몸에좋은뱀_Python] - Python collections 모듈 deque와 일반 list 구조 비교
또한 이 포스팅의 그림처럼 rotate()를 통해 자료를 변형할 수 있으니 읽어볼 것.