기초 자료구조

1. Stack

LIFO(후입선출, Last-in First-out)

대표적인 stack 자료구조 활용 : ctrl + z

 

파이썬에서의 구현 ➡️ 리스트

stack = []
stack.append(1) # [1]
stack.append(2) # [1,2]
stack.append(3) # [1,2,3]
stack.pop() # [1,2]

 

stack 자료 구조의 단점 ? 1 빼려면 2,3을 모두 빼야 함. 시간복잡도가 매우 큼. 맨 안쪽에 있는 블럭을 빼려면 느림.

 

2. Deque, double-ended queue

보통의 큐는 FIFO(선입선출, First-in First-out)

뒤에서는 push만, 앞에서는 pop만 가능하다.

 

deque는 앞/뒤 모두에서 push와 pop이 가능하다!

 

 

python에서의 구현 ➡️ from collections impoer deque

que = deque([1,2,3]) # 혹은 deque()도 가능
que.popleft() # [2,3]
que.appendleft(10) # [10,2,3]
que.append(4) # [10,2,3,4]
que.pop() # [10,2,3]

 

 

3. Graph

노드(node, vertex) 와 간선(edge)로 이뤄진 자료구조

굉장히 일반화된 자료구조

다양한 변형 (단방향성, 양방향성, 비용 등)

응용 : SNS,GNN, ...

 

파이썬에서의 구현 ➡️ 인접 리스트 or 인접 행렬

• 리스트는 연결 여부를 확인하는 데에 오래 걸림
• 행렬은 공간복잡도 측면에서 불리

https://velog.io/@eunchae2000/자료구조-그래프를-저장하는-방법-3가지-인접-행렬-인접-리스트-간선-리스트-with-Python

[자료구조] 그래프를 저장하는 방법 3가지 : 인접 행렬, 인접 리스트, 간선 리스트 with Python

# 인접 리스트 graph[from] = (to,cost)
graph = [
	[(1,7), (2,5)],
    	[(0,7)],
    	[(0,5)],
]

# 인접 행렬 graph[from][to] = cost
graph = [
	[0,7,5],
    	[7,0,float('inf')],
    	[5,float('inf'), 0],
]