Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |
Tags
- paper review
- LLM
- peft
- 머신러닝
- 이분탐색
- Scaling Laws
- 최단경로
- Generative AI
- Study
- DP
- Python
- Fine-Tuning
- 판다스
- 코딩테스트
- English
- 파인튜닝
- 파이썬
- 그래프이론
- 코드트리
- 완전탐색
- 코딩테스트실력진단
- 플로이드와샬
- bfs/dfs
- Lora
- 알고리즘
- speaking
- 스터디
- 프로그래머스
- Coursera
- 데이터분석
Archives
- Today
- Total
생각하는 아져씨
DFS 와 BFS 본문
DFS/BFS 들어가기 전
- 탐색은 그래프, 트리 등 자료구조 안에서 자주 다룬다.
- DFS와 BFS를 이해하려면 기본 자료구조인 스택과 큐 그리고 재귀함수를 이해하고 있어야 함
- 스택: FILO(First In Last Out)
- 큐: FIFO(First In First Out)
- 스택과 큐를 사용할 땐 Overflow와 Underflow를 고려해야 함
- 파이썬에서는
- 스택 → 파이썬 리스트
- 큐 → collections 모듈에서 제공하는 deque 자료구조
- 재귀함수: 자기 자신을 다시 호출하는 함수
- 재귀함수는 내부적으로 스택 자료구조 이용 (가장 마지막에 호출한 함수가 끝나야 그 앞의 함수 호출이 종료되기 때문이다.)
- 꼭 종료조건을 구현해줘야 함
- 반복문 보다 코드가 간결
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)
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
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)
- O(N)
BFS(Breadth-First Search)
- 너비 우선 탐색, 가까운 노드부터 탐색하는 알고리즘
- 큐 자료구조 이용 (가까운 노드, 즉 먼저 들어온 것 부터 처리)
- 동작 과정
- 탐색 시작 노드를 큐에 삽입하고 방문 처리.
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리.
- 2번의 과정을 더 이상 수행할 수 없을 때 까지 반복
(그림 삽입)
from collections import deque
# BFS 메서드 정의
def bfs(graph, start, visited):
# 큐(Queue) 구현을 위해 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)
- O(N)
- DFS 보다 수행시간 좋은 편
(계속 추가 중)
'Study > Algorithm' 카테고리의 다른 글
[BOJ] 1260 - DFS와 BFS (0) | 2022.07.14 |
---|---|
[BOJ] 2606번 - 바이러스 (0) | 2022.07.14 |
구현 (0) | 2022.06.21 |
그리디(Greedy) (0) | 2022.06.21 |
[Algorithm] 2019 카카오 블라인드 테스트 - 무지의 먹방 라이브 (0) | 2022.06.15 |