BFS/DFS : 그래프를 탐색하기 위한 대표적인 두 가지 알고리즘
꼭 필요한 자료구조 기초
- 탐색: 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
1) 그래프, 트리 등 자료구조 안에서 탐색하는 문제를 자주 다룸.
2) 대표적인 탐색 알고리즘 ==> BFS, DFS - 자료구조: 데이터를 표현하고 처리하기 위한 구조 ==> 스택과 큐는 자료구조의 기초 개념!
1) 삽입(Push): 데이터를 삽입
2) 삭제(Pop) : 데이터를 삭제
스택과 큐를 사용할 때에는 오버플로와 언더플로를 고려해야 함.
- 오버플로우(Overflow) : 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생. => 저장 공간을 벗어나 데이터가 넘쳐흐를 때 발생.
- 언더플로(Underflow) : 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하면 데이터가 전혀 없는 상태 -> 언더플로 발생
스택(Stack)
선입후출 구조 (FILO)!!!!
- 별도의 라이브러리 사용이 필요 없다.
- 기본 리스트에서 append()와 pop() 메서드를 이용하면 스택 자료구조와 동일하게 동작함.
큐(Queue)
선입선출 구조 (FIFO)!!!!
- 큐를 구현할 때에는 colleciton 모듈에서 제공하는 deque 자료구조를 활용하면 된다.
- deque는 큐와 스택의 장점을 모두 채택한 것인데 데이터를 넣고 뺀ㄴ 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러리를 이용하는 것보다 더 간단하다.
재귀함수(Recursive Function)
- DFS, BFS 구현시 재귀함수 이해는 필수적이다.
- 재귀함수란 자기 자신을 다시 호출하는 함수를 의미한다.
- 재귀함수 구현시 종료 조건 명시는 필수적이다.
- 컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조를 이용한다.
- ex. 재귀함수 예시 => factorial
def factorial_recursive(n): if n <= 1: return 1 return n * factorial_recursive(n-1) print(factorial_recursive(5)) # 결과값으로 120 반환됨.
탐색 알고리즘 DFS/BFS
DFS
- 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘.
- 그래프는 노드와 간선으로 표현되며 이때 노드를 정점이라고도 말한다.
- 최대한 멀리 있는 노드를 우선하는 탐색으로 동작
- 그래프 탐색: 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다.
- 인접 행렬: 2차원 배열로 그래프의 연결 관계를 표현하는 방식 => 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식.
- 인접 리스트: 리스트로 그래프의 연결 관계를 표현하는 방식 => 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장함. (연결 리스트 자료구조)
- 스택 자료구조를 이용하여 구현
BFS
- 너비 우선 탐색, 가까운 노드부터 탐색하는 알고리즘.
- 큐 자료구졸르 이용하여 구현.
- 가까운 노드부터 탐색.
내 안에 있는 힘을 믿어라.