탐색이란?
많은 양의 데이터 중 원하는 데이터를 찾는 과정이다.
이것은 그래프, 트리 등의 자료구조에서 자주 다루고 대표적인 알고리즘으로는 dfs/bfs 가 있다.
dfs/bfs를 잘 이해하려면 스택, 큐, 재귀함수를 먼저 이해해야 한다.
자료구조란?
데이터를 표현, 관리, 처리하기 위한 구조이다.
그 중 스택과 뷰가 기초적인 개념이며 이는 push(삽입), pop(삭제)함수로 구성된다.
- 오버플로: 특정한 자료구조가 수용가능한 데이터 크기를 넘어서 삽입할 때 발생한다.
- 언더플로: 특정한 자료구조에 데이터가 없는 상태에서 삭제 연산을 수행할 때 발생한다.
스택
박스를 아래에서부터 위로 쌓는 방식, 위에 있는 박스부터 치워야한다.
선입후출 구조(First In Last Out) or 후입선출 구조(Last in First Out) 라고 부른다.
스택은 다른 모듈없이 append(), pop() 메소드만 사용하면 동작가능하다. 둘 다 가장 뒤쪽에 데이터를 삽입하고 꺼내는 작업을 한다.
큐
큐는 대기줄에 비유한다. 나중에 오면 나중에 들어가는 공정한 자료구조이다.
선입선출(First In First Out)구조이다.
큐를 구현하려면 collections 모듈에서 제공하는 deque 자료구조를 사용해야한다.
deque는 스택과 큐의 장점을 모두 사용한 것인데 데이터를 넣고 빼는 속도가 리스트 자료형보다 효율적이고 queue라이브러리를 이용하는 것보다 더 간단하다.
from collections import deque
queue = deque()
queue.append(5)
queue.append(3)
queue.popleft()
...
print(queue)이것을 출력하면 deque([3, 7, 1, 4]) 이런식으로 deque 객체가 출력되는데 list()메서드를 사용하면 리스트 자료형이 반환된다.
재귀 함수
DFS/BFS를 구현하려면 재귀 함수를 이해해야 한다. 이해할 것이 참 많은데.....ㅠㅠ
이것은 자기 자신을 다시 호출하는 함수를 의미한다!
무한대로 반복하지 않게 종료 조건을 명시해야한다.
컴퓨터 내부에서 재귀함수의 수행은 스택 자료구조를 이용하는데 그 이유는, 함수를 계속 호출할 때 마지막 호출된 함수가 먼저 수행 끝내야 그 앞의 함수 호출이 종료되기 때문이다. 연속 호출되는 함수는 메인 메모리의 스택에 적재되고, 재귀 함수는 내부적으로 스택 자료구조와 동일하다고 한다.
스택구조를 활용하는 알고리즘은 재귀 함수를 이용해서 쉽게 구현될 수 있는데 대표적으로 dfs가 있다!
ex. 팩토리얼 문제
#반복적으로 구현
def factorial_iterative(n):
result = 1
for i in range(1, n+1):
result *= i
return result
#재귀 구현
def factorial_recursive(n):
if n <= 1:
return 1
n * factorial_recursive(n-1)이제 드디어 dfs를 알아보겠다.
DFS
depth-first search로 깊이 우선 탐색이라 불리며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
여기서 그래프는, 노드(정점)와 간선으로 표현된다. 두 노드가 간선으로 연결되면 두 노드는 인접하다고 표현한다.
- 인접 행렬: 2차원 배열로 그래프의 연결 관계를 표현하는 방식
- 인접 리스트: 리스트로 그래프의 연결 관계를 표현하는 방식, 연결리스트 라는 자료구조를 이용해 구현한다.
인접 행렬 방식은 모든 관계를 저장하므로 메모리가 불필요하게 낭비되는 반면, 인접 리스트 방식은 연결된 정보만 저장해서 메모리를 효율적으로 사용한다.
하지만 이 때문에 인접 리스트 방식은 두 노드가 연결되어 있는지 알아내는 속도가 느리다.
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 = [
[], [sdfsd...]...
]
vistied = [False] * 9
dfs(graph, 1, visited)
BFS
Breadth First Search의 줄임말로, 너비 우선 탐색 이라는 의미이다. 가까운 노드부터 탐색하는 알고리즘이다.
구현은 선입선풀 방식인 큐 자료구조를 이용한다. 입접한 노드를 반복적으로 큐에 넣도록 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어서 가까운 노드부터 탐색하게 된다.
deque 라이브러리를 사용한다.
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[i]:
queue.append(i)
visited[i] = True
graph = [
[],[dfs ]
...
]
visited = [False] * 9
bfs(graph, 1, visited)
