_01.algorithm_stack_queue

알고리즘

시간 복잡도

O(1) – 상수 시간 : 문제를 해결하는데 오직 한 단계만 처리함.
O(log n) – 로그 시간 : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬.
O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐.
O(n log n) : 문제를 해결하기 위한 단계의 수가 N*(log2N) 번만큼의 수행시간을 가진다. (선형로그형)
O(n^2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱.
O(C^n) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱.

1. 스택(stack) 자료구조

• 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조
• 입구와 출구가 동일한 형태로 스택을 시각화 가능
• 박스를 쌓고 다시 내려놓을 때 제일 나중에 올려둔 박스부터 내려 놓아야 하는 것을 생각하면 됨

스택 구현 예제

• list는 append와 pop method를 모두 지원하기에 스택 구현가능
• 시간 복잡도는 상수시간으로 stack에 적합
• stack =[]

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()

stack.append(5)  
stack.append(2)  
stack.append(3)  
stack.append(7)  
stack.pop() # 나중에 들어온 것 삭제. 삭제7  
stack.append(1)  
stack.append(4)  
stack.pop() # 나중에 들어온 것 삭제. 삭제4

print(stack\[::-1]) # 최상단 원소부터 출력 (원소의 순서를 뒤집은것)  
[1,3,2,5]  
print(stack) # 최하단 원소부터 출력  
[5,2,3,1]

2. 큐 (queue) 자료구조

• 먼저 들어 온 데이터가 먼저 나가는 형식(선입선출)의 자료구조
• 큐는 입구와 출구가 모두 둟려 있는 터널과 같은 형태
  • 줄 서기 생각하면 됨

큐 구현 예제

• list로 기능적으로는 구현은 가능하나 시간 복잡도에 인해 비추
• 따라서 queue를 구현할 땐 deque 라이브러리를 사용
• 시간 복잡도는 상수시간
• from collections import deque

queue = deque ()

# 삽입(5) - 삽입(3) - 삽입(2) - 삽입(6) - 삭제() - 삽입(7) - 삽입(4) - 삭제()

queue.append(5)  
queue.append(3)  
queue.append(2)  
queue.append(6)  
queue.popleft() # 먼저 들어온 것 부터 삭제. 삭제 5  
queue.append(7)  
queue.append(4)  
queue.popleft() # 먼저 들어온 것 부터 삭제. 삭제 3

print(queue) # 먼저 들어온 순서대로 출력  
deque(\[2,6,7,4\])  
queue.reverse() # 역순  
print(queue) # 역순이 되어서 나중에 들어온 원소부터 출력  
deque(\[4,7,6,2\])