1. 꼭 필요한 자료구조 기초
탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
- DFS, BFS가 대표적인 탐색 알고리즘
이를 이해하기 위해서는 기본 자료구조인 스택과 큐에 대한 이해가 전제되어야 함!!
자료구조(Data Structure) : 데이터를 표현하고 관리하고 처리하기 위한 구조
- 스택과 큐는 자료구조의 기초 개념으로, 두 개의 핵심적인 함수로 구성
- 삽입(Push) : 데이터 삽입
- 삭제(Pop) : 데이터 삭제
- 실제 스택과 큐를 사용할 때는 오버플로와 언더플로도 고려
스택(Stack)
- 입구와 출구가 하나
- 선입후출(FILO) 구조 또는 후입선출(LIFO) 구조
- 파이썬에서는 별도의 라이브러리를 사용할 필요가 없음
- 기본 리스트에서 append( )와 pop( ) 메서드를 이용하면 스택 자료구조와 동일하게 동작
stack = []
stack.append(5)
# [5]
stack.append(2)
# [5, 2]
stack.append(3)
# [5, 2, 3]
stack.append(7)
# [5, 2, 3, 7]
stack.pop()
# [5, 2, 3]
stack.append(1)
# [5, 2, 3, 1]
stack.append(4)
# [5, 2, 3, 1, 4]
stack.pop()
# [5, 2, 3, 1]큐(Queue)
- 입구와 출구가 각각
- 선입선출(FIFO) 구조
- 파이썬에서 큐 구현을 위해 collections 모듈의 deque 라이브러리 활용
- deque는 스택과 큐의 장점을 모두 채택한 것
- 리스트 자료형에 비해 빠른 속도
- queue 라이브러리보다 간편
from collections import deque
q = deque()
q.append(5)
# [5]
q.append(2)
# [5, 2]
q.append(3)
# [5, 2, 3]
q.append(7)
# [5, 2, 3, 7]
q.popleft()
# [2, 3, 7]
q.append(1)
# [2, 3, 7, 1]
q.append(4)
# [2, 3, 7, 1, 4]
q.popleft()
# [3, 7, 1, 4]
재귀 함수 : 자기 자신을 다시 호출하는 함수
- DFS/BFS를 구현하기 위해 이해해야 함
- 파이썬 인터프리터는 호출 횟수 제한 존재
- 종료 조건을 명시해야 함
- 반복문에 비해 더 간결한 코드 작성 가능
- 수학의 점화식을 그대로 소스코드로 옮긴 것
def recursive_function():
print('재귀 함수를 호출합니다.')
recursive_function()
recursive_function()2. 탐색 알고리즘 DFS / BFS
그래프
- 노드(정점)와 간선으로 표현
- 그래프 탐색이란 하나의 노드의 시작으로 다수의 노드를 방문하는 것
- 두 가지 방식으로 표현
- 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식
- 파이썬에서는 리스트로 구현
- 연결 되지 않은 노드끼리는 무한의 비용이라고 작성 / 실제 코드에서는 999999999 등의 값으로 초기화
# 인접 행렬 예제
INF = 999999999
graph = [[0, 7, 5],
[7, 0, INF],
[5, INF, 0]]- 인접 리스트(Adjacency List) : 리스트로 그래프의 연결 관계를 표현하는 방식
- 모든 노드에 연결된 노드에 대한 정보를 차례로 연결하여 저장
# 행이 3개인 2차원 리스트
graph = [[] for _ in range(3)]
# 노드 0 연결 관계
graph[0].append((1, 7))
graph[0].apeend((2, 5))
# 노드 1 연결 관계
graph[1].append((0, 7))
# 노드 2 연결 관계
graph[2].apeend((0, 5))- 인접 행렬 방식은 노드의 개수가 많을수록 메모리 낭비
- 인접 리스트 방식은 정보를 얻는 속도가 상대적으로 느림
DFS(Depth-First Search), 깊이 우선 탐색
그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
1 - 2 - 7 - 6 - 8 - 3 - 4 - 5 순서로 탐색
스택을 이용하여 구현
# DFS 메서드 정의
def dfs(graph, n, visited):
# 현재 노드 방문 처리
visited[n] = True
print(n, end=' ')
# 현재 노드와 연결된 다른 노드들을 재귀적으로 방문
for i in graph[n]:
# 방문하지 않은 노드라면
if not visited[i]:
# 방문 처리
dfs(graph, i, visited)
# 노드 연결 정보를 리스트로 표현
graph = [
[], # 0번 노드는 없으므로..
[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)
BFS(Breadth-First Search), 너비 우선 탐색
가까운 노드부터 탐색하는 알고리즘
1 - 2 - 3 - 8 - 7 - 4 - 5 - 6 순서로 탐색
큐를 이용하여 구현
일반적으로 DFS 보다 수행 시간이 좋은 편
from collections import deque
# BFS 메서드 정의
def bfs(graph, start, visited):
queue = deque([start])
# 현재 노드 방문 처리
visited[start] = True
# 큐가 빌 때까지 반복
while queue:
# 제일 먼저 방문한 노드 꺼냄
n = queue.popleft()
print(n, end=' ')
# 해당 노드와 연결되고 아직 방문하지 않는 노드에 대해 반복
for i in graph[n]:
if not visited[i]:
queue.append(i)
visitied[i] = True
graph = [
[], # 0번 노드는 없으므로..
[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)
| DFS | BFS | |
|---|---|---|
| 동작 원리 | 스택 | 큐 |
| 구현 방법 | 재귀 함수 이용 | 큐 자료구조 이용 |
공부중입니다