728x90
반응형
탐색이란?
- 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
- 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룸
- 대표적으로 DFS 알고리즘과 BFS 알고리즘이 있음
이를 위해서는 기본 자료구조인 스택과 큐, 그리고 재귀함수에 대한 이해가 먼저 필요하기 때문에, 해당 내용을 간략하게 설명하도록 하겠음
# 01 스택(Stack)
- 데이터를 차곡차곡 쌓는 구조
- LIFO (Last In First Out), FILO (First In Last Out)
- 파이썬에서는 list 자료형을 그대로 이용하면 됨
stack = []
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()
print(stack) # 최하단 원소부터 출력
print(stack[::-1]) # 최상단 원소부터 출력
# 02 큐(Queue)
- 놀이공원 줄서기와 같이 먼저 들어온 데이터가 먼저 나가는 구조
- FIFO (First In First Out), LILO (Last In Last Out)
- 파이썬에서는 queue 라이브러리의 Queue 클래스 혹은 collections 라이브러리의 deque 클래스를 이용
from collections import deque
queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
queue.popleft()
queue.append(4)
queue.append(5)
queue.popleft()
print(queue) # 선입순 출력
queue.reverse()
print(queue) # 후입순 출력
# 03 재귀함수 (Recursive Function)
- 자기 자신을 다시 호출하는 함수
- 일반적으로 파이썬 인터프리터에서는 재귀 함수의 최대 호출 횟수 제한이 있음 - 이 한계를 벗어나지 못함
- 다이나믹 프로그래밍에 비해서 더욱 직관적인 코드
- 종료 조건을 반드시 명시하는 것에 유의! 그렇지 않으면 무한 반복 호출 발생 가능
- 내부적으로 스택 자료구조와 동일하게 구현되어 있어서, 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료됨
def recursive(n):
if n == 10:
return
print(n, '번째 함수에서', n+1, '번째 재귀 함수를 호출합니다')
recursive(n+1)
print(n, '번째 재귀 함수를 종료합니다')
recursive(1)
# 04 DFS와 BFS는 그래프 탐색을 위한 알고리즘이다 ! 그래프는 어떻게 표현할까?
- 그래프: 노드(정점)와 엣지(간선)으로 표현되며, 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 의미함!
- 그래프를 표현하는 방법에는 두 가지 방법이 있음 → 인접 행렬과 인접 리스트
- 인접행렬: 2차원 배열로 그래프의 연결 관계를 표현하는 방식
- 서로 연결되어 있지 않은 노드끼리는 무한의 비용이라고 작성 (예: 999,999,999)
- 시간 복잡도 측면: 노드 번호 값을 인덱스로 활용함으로써, 매우 빠르게 접근 가능
- 공간 복잡도 측면: 모든 관계를 저장하므로 메모리가 불필요하게 낭비됨 (특히 간선에 방향이 없는 경우, 동일한 데이터를 2배로 저장하게 됨)
- 인접리스트: 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장
- 연결 리스트라는 자료구조 활용 가능! 파이썬에서는 인접행렬처럼 list를 사용하여도 무방함
- 시간 복잡도 측면: 파악하고자 하는 노드에 대한 인접 리스트를 앞에서부터 하나씩 차례대로 확인해야 하기 때문에, 인접 행렬에 비해 느림
- 공간 복잡도 측면: 필요한 정보만 저장하기 때문에, 메모리 공간의 낭비가 적음
DFS란? Depth-First Search
- 깊이 우선 탐색! 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
- [1] 탐색 시작 노드를 스택에 삽입하고, 방문 처리를 한다
- [2] 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면, 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다
- [3] 위의 [2]번의 과정을 더 이상 수행할 수 없을 때 까지 반복한다.
- 위 절차에 따라서 순서대로 그래프를 탐색하면 '1 2 7 6 8 3 4 5' 순서로 노드를 방문하게 된다
이를 재귀함수를 사용하지 않는 다이나믹 프로그래밍으로 구현하면 다음의 코드와 같다
visited, find, dfs_stack = [], [], []
adj_list = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
working_node = 1
find.append(working_node)
while True:
# 모든 노드를 찾았는지 매번 확인
if len(visited) == len(adj_list)-1:
break
# 최초 방문하면 방문 목록에 추가 - 아니면 pass
if working_node not in visited:
visited.append(working_node) # 현재 작업 노드를 방문 목록에 추가
dfs_stack.append(working_node) # 현재 작업 노드를 작업 스택에 추가
discover = adj_list[working_node] # 인접 리스트로 연결 노드 불러오기
discover.sort() # 작은 수 부터 방문하기 위함
check = 0
for i in discover: # 다음 작업 노드를 탐색
if i not in visited: # 이동할 작업 노드가 있는 경우
working_node = i
break
else: # 이동할 작업노드가 없는 경우 (= 모두 이미 방문한 경우)
check += 1
print(check, len(discover), dfs_stack)
# 만약 이동할 작업 노드가 없는 경우, 작업 스택에서 pop
if check == len(discover):
dfs_stack.pop()
working_node = dfs_stack[-1]
# DFS 탐색을 종료하고 방문 순서를 출력
print(visited)
하지만 위에서 설명했다시피, 재귀함수를 사용하면 메모리를 많이 사용하더라도, 코드의 가독성이 좋고 비교적 짧게 구현이 가능하다.
따라서 재귀함수를 사용하여 구현하면 다음과 같다.
재귀함수를 사용한다면 다이나믹 프로그래밍 때와 다르게 별도의 작업 스택을 사용하지 않아도 된다! 왜냐하면 재귀함수 자체가 스택 자료구조로 호출이 되기 때문이다!! 🥸
# 본 코드는 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 교재에 수록된 코드입니다
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]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현 (1차원 리스트)
visited = [False] * 9
# 정의된 DFS 함수 호출
DFS(graph, 1, visited)
BFS란? Breath-First Search
- 너비 우선 탐색! 가까운 노드부터 탐색한다!
- DFS는 최대한 멀리 있는 노드, 즉 깊숙한 노드부터 우선으로 탐색하는 방식으로 동작하고 BFS는 그 반대로 동작한다
- BFS는 큐 자료구조에 기반하기 때문에 구현이 간단하고, 탐색을 수행하는데 O(N)의 시간이 소요된다
- 일반적인 경우, 실제 수행 시간은 DFS보다 조금 더 좋은 편이다
- [1] 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다
- [2] 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에서 삽입하고 방문 처리를 한다
- [3] 위의 [2] 번의 과정을 더이상 수행할 수 없을 때까지 반복한다
- 위 절차에 따라서 순서대로 그래프를 탐색하면 '1 2 3 8 7 4 5 6' 순서로 노드를 방문하게 된다
BFS를 다이나믹 프로그래밍으로 구현하면 아래의 코드와 같다
from collections import deque
# 그래프 정보를 인접 리스트로 표현
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# Create queue and list
queue = deque()
visited = [False] * (len(graph))
find = []
# Strat setting
working_node = 1
queue.append(working_node)
visited[working_node] = True
find.append(working_node)
while True:
# 그래프를 모두 탐색하였는지 확인
if len(find) == len(graph)-1:
break
# 가까운 인접 노드 확인 및 방문하지 않은 노드는 추가
discover = graph[working_node]
discover.sort()
for i in discover:
if visited[i] == False:
visited[i] = True
queue.append(i)
find.append(i)
working_node = queue.popleft()
print(find)
다이나믹 프로그래밍을 이용한 또 다른 풀이는 다음과 같다
from collections import deque
# 본 코드는 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 교재에 수록된 코드입니다
def BFS(graph, start, visited):
# 큐 구현을 위한 deque 라이브러리 사용
queue = deque([start])
# 현재 노드를 방문처리
visited[start] = True
# 큐가 빌 때까지 반복
while queue:
# 큐에서 하나의 원소를 뽑아 출력
v = queue.popleft()
print(v, end=' ')
# 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
# 각 노드가 연결된 정보를 리스트 자료형으로 표현 (2차원 리스트)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현 (1차원 리스트)
visited = [False] * 9
# 정의된 BFS 함수 호출
BFS(graph, 1, visited)
DFS 와 BFS의 특징을 간단히 정리하자면 다음 표와 같이 나타낼 수 있다
| 분류 | DFS | BFS |
| 동작 원리 | 스택 | 큐 |
| 구현 방법 | 재귀함수 이용 | 큐 자료구조 이용 |
본 포스트는 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책 내용을 토대로 작성되었습니다
728x90
반응형
