지난 해시 구조에 이어 가장 기본적인 자료 구조 중 큐/스택 구조에 대해 알아볼 차례이다.
자료구조 / 알고리즘에 대한 간략한 설명
큐(Queue) 구조란 FIFO(First In First Out)이 구현된 구조이며,
스택(Stack) 구조란 LIFO(Last In First Out)이 구현된 구조이다.
이 두 구조는 기본이 되지만 너무나 중요한 자료구조로 큐 구조의 경우 CPU의 스케줄링, 요청 처리 등에서 사용되며 스택 구조의 경우 함수 콜 스택, DFS 등에서 다양하게 사용된다.
"순서" 가 담긴 가장 기본적인 자료 구조라고 생각하면 되겠으며 지난 시간 해시 구조가 파이썬의 딕셔너리에 대응된다면 큐/스택 구조는 파이썬의 리스트에 대응된다고 생각하면 편하다.
그럼 파이썬의 리스트는 어떻게 구현되느냐 ?
기본적으로 파이썬의 리스트는 동적 배열 구조를 가진다. 처음 생성 시 연속된 메모리 공간을 할당받고 여기에 순차적으로 값들을 쌓아나가는 구조이다.
이러한 구조를 가진 탓에 리스트의 가장 큰 장점을 인덱싱 과정의 시간 복잡도가 O(1)로 매우 빠르다는 점이다. 연속된 메모리니까 당연한 이야기.
그러나 앞선 딕셔너리와 다르게 리스트의 경우 기준 주소와 주어진 인덱스를 토대로 새로운 주소를 별도로 계산하여 데이터에 접근해야하므로 조금 더 긴 시간이 소요된다. O(1)은 그저 이론상...
연속된 메모리 구조에 따른 단점 역시 존재하는데 바로 그 수정 과정이 유연하지 못하다는 점이다. 만일 중간에 존재하는 하나의 요소를 제거하고 싶다면 "연속된 메모리"를 유지하기 위해 뒤따른 모든 요소를 한 칸 씩 앞으로 당겨야 한다는 구조적인 문제점을 가지고 있다.
이에 따라 삽입 및 삭제의 경우 O(n)의 시간복잡도를 가지게 된다.
여러가지 파이썬 구현 방식
1) 리스트 이용
가장 기본적인 방법은 역시 파이썬의 기본 자료형인 리스트를 그대로 이용하는 것이다. 리스트의 .pop(index=-1) 과 .append(object) 를 이용하면 이를 구현할 수 있다.
# 큐(Queue) 구조
queue = []
queue.append("스케줄 1")
queue.append("스케줄 2")
queue.pop(0)
>>> "스케줄 1"
queue.pop(0)
>>> "스케줄 2"
# 스택(stack) 구조
stack = []
stack.append("함수 1")
stack.append("함수 2")
stack.pop()
>>> "함수 1"
stack.pop()
>>> "함수 2"리스트의 .pop() 메소드가 index 값을 받기에 가능한 구조이다.
2) collections.deque 클래스 이용
그 다음으로는 지난 주와 마찬가지로 파이썬의 기본 자료형을 확장시킨 collections 에 존재하는 deque 클래스를 이용하는 방법이다.
deque 클래스는 큐/스택 구조를 구현하기 위한 파이썬 라이브러리로 "양방향 접근이 가능한 리스트"이다.
기존 리스트가 "연속된 메모리 공간"을 이용하기에 생긴 수정 과정에서의 문제점을 해결하기 위해 deque는 이중 연결 블록 구조를 사용한다.
여러 개의 블록으로 나누어 데이터를 관리, 이들간의 연결을 별도로 정의하여 수정 시 전체 요소를 변경할 필요없이 그 연결만을 변경할 수 있도록 만들었다.
이에 따라 양방향 요소 삽입 시에 전체 요소를 변경할 필요없이 기존 deque에 새로운 요소를 연결하기만 하면 되어 요소 삽입 및 삭제에 있어 큰 장점을 가지지만 그 덕에 리스트가 가지던 장점인 빠른 인덱싱은 존재하지 않게 되었다.
이제 그 사용법을 알아보자.
from collections import deque
# deque 객체 생성
de = deque([-2, -1, 0]) # 당연하게도 Iterable을 받을 수 있다.
de.append(1)
de.append(2)
de
>>> deque([-2, -1, 0, 1, 2])
# 양방향 삽입 / 삭제 메소드
de.append(3)
de.appendleft(-3)
de
>>> deque([-3, -2, -1, 0, 1, 2, 3])
de.pop()
de.popleft()
de
>>> deque([-2, -1, 0, 1, 2])
# 새롭게 추가된 rotate 메소드
de.rotate() # .rotate(n=1), 오른쪽 방향 한 칸 밀기가 기본값
de
>>> deque([2, -2, -1, 0, 1])
de.rotate(-2)
de
>>> deque([-1, 0, 1, 2, -2])기존 list 자료형을 상속받았으므로 기존의 .count(), .index(), .find(), .reverse() 등의 메소드는 여전히 사용할 수 있다.
이에 더해 .append(), .extend(), .pop() 으로 정의된 삽입 / 삭제 메소드는 양방향으로 바뀌었으며 별도의 .rotate() 함수가 추가되었다.
몇 가지 주의할 점이 있다면 "연속된 메모리 공간"을 버린 탓에 deque에서는 슬라이싱이 불가능하다는 점, 인덱싱의 시간 복잡도가 O(n)으로 매우 느려졌다는 점, 그리고 .popleft() 메소드의 추가로 기존의 .pop() 메소드가 더 이상 index 파라미터를 받지 않는다는 점이 존재하겠다.
따라서 무턱대고 사용하기 보다는 "인덱싱이나 정렬"이 최소화되며 "양방향 삽입/삭제"가 많은 경우에 사용하면 되겠다.
프로그래머스 문제 풀이
1) 같은 숫자는 싫어 Lv.1
연속적으로 나타나는 숫자를 제거하는 문제이다.
def solution(arr):
answer = []
# 첫 요소이거나 마지막 요소와 다르면 추가
for i, num in enumerate(arr):
# if i == 0 or num != answer[-1]:
if num != answer[-1:]:
answer.append(num)
return answer
solution([1, 2, 1, 1, 1, 3, 3, 3, 1])
>>> [1, 2, 1, 3, 1]간단한 문제라 별도의 테크닉 없이 일반 리스트로 풀어냈다.
2) 기능개발 Lv.2
각 기능별로 진행률을 계산하여 한 번에 배포되는 기능 수들을 구하는 문제이다.
def solution(progresses, speeds):
answer = []; days = 1; cnt = 0
while progresses:
# 0번 째 기능 개발 완료 계산 / 그 당시 days에서 개발 완료된 n번 째 기능까지 다 반환
if (progresses[0] + speeds[0]*days) >= 100:
progresses.pop(0)
speeds.pop(0)
cnt += 1
else:
if cnt: # 0번 째 기능 개발 완료 시
answer.append(cnt)
cnt = 0
days += 1
answer.append(cnt)
return answer
solution([93, 30, 55], [1, 30, 5])
>>> [2, 1]0번 째 기능 개발까지 걸리는 days 를 계산, 해당 days 에서 개발 완료된 기능들을 앞에서 부터 전부 다 반환하는 방식으로 계산하였다.
리스트의 .pop(0) 은 시간 복잡도 상 굉장히 불리하지만 사용은 가능하다는 점 !
3) 올바른 괄호 Lv.2
괄호가 올바르게 짝지어져 있는지 여부를 판단하는 문제이다.
from collections import deque
def solution(s):
de = deque()
for string in s:
if string == ")" and de and de[-1] == "(":
de.pop()
else:
de.append(string)
return len(de) == 0
solution("(())()")
>>> True앞서 살펴보았던 collections.deque 를 이용하여 읽히는 대로 풀어내었다. 양방향 삽입이 적극적으로 활용되는 문제가 아니라 리스트로 풀어도 비슷한 시간이 걸릴 것 같지만 한 번은 연습해보고 가자 싶어서....ㅎㅎ
4) 프로세스 Lv.2
중요도에 따라 큐 구조로 프로세스를 실행하는 문제이다.
from collections import deque
def solution(priorities, location):
de = deque(priorities)
answer = 0
while de:
prior = de.popleft()
if any(p > prior for p in de):
de.append(prior)
location += -1 if location > 0 else len(de)-1
else:
answer += 1
if location == 0:
return answer
location += -1 if location > 0 else len(de)
solution([2, 1, 3, 2], 2) # 2번 째 자료가 몇 번째로 실행될까 ?
>>> 1deque 구조를 활용해 왼쪽에서 요소를 뽑아 다른 프로세스와의 중요도를 비교, 가장 중요한 프로세스가 아닌 경우 오른쪽으로 요소를 추가하고 location 변수를 추적 수정하여 풀어내었다.
조금 더 효율성을 따진다면 한 칸 한 칸 넘기는 것이 아니라 가장 중요도가 높은 프로세스의 위치까지 .rotate() 를 실행하여 뽑아내는 방법이 존재할 듯 싶다.
5) 다리를 지나는 트럭 Lv.2
최대 무게를 넘지 않도록 트럭들이 다리를 전부 건너는 데에 걸리는 시간을 구하는 문제이다.
from collections import deque
def solution_poor(bridge_length, weight, truck_weights):
answer = 0
bridge = deque([0 for _ in range(bridge_length)]) # 다리의 위치마다 존재하는 트럭의 무게
trucks = deque(truck_weights)
while trucks or any(b for b in bridge):
answer += 1
# 도착한 트럭
if bridge[0]:
bridge[0] = 0
bridge.rotate(-1)
# 새로 타는 트럭
if trucks and sum(bridge) + trucks[0] <= weight:
truck = trucks.popleft()
bridge[-1] = truck
return answer
solution_poor(2, 10, [7,4,5,6])
>>> 8 (시간 초과)처음에 풀어낸 풀이이다. 다리를 건너는 트럭들의 위치와 각 무게를 추적하기 위해 deque를 이용해 bridge 를 정의, 그 전체 무게를 any() 와 sum() 을 이용하여 계산하였다. 이후 지나는 시간을 .rotate() 함수를 이용해 구현하였다.
하지만 결과는 시간 초과..... 열심히 짱구를 굴려보고 찾아보니 any() 와 sum() 함수를 통해 매번 bridge 의 값들을 계산하는 과정이 너무 많은 시간을 잡아먹고 있었다.
파이썬의 any(), all(), sum(), min(), max() 등의 함수가 효율적이라 이들이 잡아먹는 시간을 너무 과소 평가한 것이 실패 요인이었다.
def solution_good(bridge_length, weight, truck_weights):
answer = 0
bridge = deque([0 for _ in range(bridge_length)])
trucks = deque(truck_weights)
while trucks or bridge_weight:
answer += 1
# 도착한 트럭
bridge_weight -= bridge.popleft()
# 새로 타는 트럭
if trucks and bridge_weight + trucks[0] <= weight:
truck = trucks.popleft()
bridge.append(truck)
bridge_weight += truck
else:
bridge.append(0)
return answer위 요인을 없애주기 위해 별도의 bridge_weight 변수를 추가하여 전체 다리의 무게를 매번 계산하지 않도록 하였다. 또한, .rotate() 를 통해 매번 전체 deque 를 돌리지 않고 .popleft() 와 append() 를 통해 알아서 돌아가도록 변경하였다.
결과는 성공 !!
6) 주식가격 Lv.2
초 단위로 기록된 주식 가격이 떨어지지 않은 시간 초를 구하는 문제이다.
def solution_poor(prices):
answers_done = [True]; answers = [0]; prices_index = [0]
for i, ki in enumerate(prices): # i번째 애랑 비교했을 때
if i == 0: continue
for index in prices_index: # 대기중인 애들중에
if answers_done[index]: # 아직 안 떨어져 본 아이들
if prices[index] > ki: # 합격이면
answers_done[index] = False # 넌 끝..
answers[index] += 1
# 그 아이도 대기에 추가
prices_index.append(i)
answers_done.append(True)
answers.append(0)
return answers
solution_poor([1, 2, 3, 2, 3])
>>> [4, 3, 1, 1, 0]처음 풀어낸 풀이이다.
각각의 시간에 해당하는 주식 가격별로 별도의 answer_done 리스트를 만들어 완료 여부를 판단, 시간이 지나면서 아직 완료되지 않은 주식 가격이 새로운 주식 가격에 대해 떨어졌으면 그 값을 기록하는 방식으로 풀어내었다.
하지만 결과는 효율성 탈락....
10만 개에 해당하는 리스트를 인덱싱으로 관리하려던 것이 문제였다.
def solution_good(prices):
answer = [0 for _ in range(len(prices))]; de = deque([(-1, 0)])
for i, price in enumerate(prices):
while de[-1][-1] > price:
j, p = de.pop()
answer[j] = (i-j)
de.append((i, price))
de.popleft()
while de:
j, p = de.pop()
answer[j] = len(prices)-1-j
return answer결국 deque 를 이용한 스택 구조를 구현하여 풀어내었다. 당시 시간과 해당 주식 가격을 튜플로 관리하여 시간초를 계산할 수 있었다. 사실 그냥 리스트로도 풀어낼 수 있지만 조금 더 있어보이니까....
인덱싱 에러가 나지 않도록 while 문에 별도의 조건을 추가하기 보다는 첫 요소로 (-1초, 0원) 을 추가하여 해결하려고 하였다. 매번 별도의 조건을 고려하면 시간이 오래 걸릴 것 같아서.
마찬가지로 마지막 요소의 경우에도 (100_001초, 0원) 을 추가하여 끝나는 시점에 대한 계산도 한 번에 하고 싶었지만 시간초 계산 방법이 다르고 매 while 문마다 끝났나 ? 를 판단하는 조건이 들어가게 되기에 마지막 요소의 경우에는 아래에서 별도로 계산해주었다.
결과는 역시 성공 !!
아직까지는 그래도 괜찮은데... 자료구조나 알고리즘이 어려워지면 주마다 한 주제 씩 진행하기 어려워질 수 있겠다는 생각도 든다.
그것과는 별개로 코딩 테스트는 공부하면 공부할수록 파이썬의 내부 구조나 작동 방식에 대해 알아가게 되는 느낌이다. 점점 더 성장하는 느낌이 썩 나쁘지 않다.
