Stack
- 선입후출 (First In Last Out)
- list가 이에 해당.
- append() 함수로 stack 맨 뒤에 원소 추가 가능.
- pop() 함수로 stack 맨 뒤 원소 꺼내기 가능.
Queue
- 선입선출 (First In First Out)
- deque가 이에 해당. 엄밀하게 따지자면 stack과 queue의 장점을 모두 채택한 것인데, 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적.
- append() 함수로 queue 맨 뒤에 원소 추가 가능.
- popleft() 함수로 queue 맨 앞의 원소 꺼내기 가능.
재귀함수
- 자기 자신을 다시 호출하는 함수
- 무한 루프에 빠지지 않기 위해선 종료 조건이 꼭 필요함.
- 컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조 사용.
- 대표적으로 factorial 문제가 있음.
def fibonacci(x):
if x == 0 or x == 1:
return 1
return fibonacci(x-2) + fibonacci(x-1)
DFS
- Depth-First Search (깊이우선탐색)
- 그래프는 인접 행렬 (Adjacency Matrix)와 인접 리스트 (Adjacency List)로 표현 가능함.
- 인접행렬 예제
INF = 99999999
graph = [
[0,7,5],
[7,0,INF]
[5,INF,0]
]
- 인접 리스트 예제
graph = [[] for _ in range(3)]
graph[0].append((1,7)) # (연결된 노드, 거리)
graph[0].append((2,5))
graph[1].append((0,7))
graph[2].append((0,5))
- 메모리 측면에서는 인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을 수록 메모리가 불필요하게 낭비됨.
- 필요한 데이터로 접근하는 속도가 느려짐. 예를 들어, 노드 0에 노드 2가 연결되어 있는지 보고 싶으면 노드 1과 연결되어 있는지부터 차례대로 확인해야함.
- DFS 동작 과정 (보통 재귀함수로 구현함)
def dfs(graph, v, visited):
visited[v] = True
print(v, end = ' ')
for i in graph[v]:
if not visited[i]:
dfs(graph,i,visited)
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
visited = [False]*9
dfs(graph,1,visited)
- 노드의 개수가 N개인 경우 O(N)의 시간이 소요 됨.
BFS
- Breadth-First Search (너비우선탐색)
- 인접 노드를 모두 방문하고 인접 노드들의 인접노드들을 탐색.
- 구현 시 deque 사용 권장.
- O(N)의 시간 소요.
- BFS 동작 과정
from collections import deque
def bfs(graph, start, visited):
queue = deque([start])
visited[start] = True
while queue:
v = queue.popleft()
print(v, end = ' ')
for i in graph[v]:
if not visited[v]:
queue.append(i)
visited[i] = True
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
visited = [False]*9
bfs(graph,1,visited)
Comments