탐색
- 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘
깊이우선탐색(DFS)
시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행
한 번 방문한 노드를 다시 방문하면 안 되므로 방문 여부를 체크해야 함
기능 | 특징 | 시간 복잡도 |
그래프 완전 탐색 | 재귀 함수로 구현(스택 오버플로 유의) 스택 이용 |
O(노드 수+에지 수) |
너비우선탐색(BFS)
시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색
선입선출 방식으로 탐색해 큐를 이용해 구현
목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장
기능 | 특징 | 시간 복잡도 |
그래프 완전 탐색 | FIFO 탐색 큐 이용 |
O(노드 수 + 에지 수) |
반응형
'개발로그 > 알고리즘' 카테고리의 다른 글
[DFS] 백준 연결 요소의 개수 11724번 (0) | 2023.08.09 |
---|---|
[DFS] 백준 DFS와 BFS 1260번 (0) | 2023.08.09 |
프로그래머스 Lv.1 이상한 문자 만들기 (0) | 2023.08.08 |
프로그래머스 Lv.1 명예의 전당 (1) (0) | 2023.08.08 |
[그리디] 백준 잃어버린 괄호 1541번 (0) | 2023.08.05 |
댓글