728x90
자세한 내용 보러 가기
탐색이란?
많은 양의 데이터 중 원하는 데이터를 찾는 과정
EX) DFS, BFS
재귀함수란?
자기 자신을 다시 호출하는 함수.
파이썬의 경우 최대 재귀 깊이 제한이 있음.
종료 조건을 반드시 명시해야 함.
반복문을 이용하여 재귀함수와 동일한 기능을 구현할 수 있음.
(재귀함수를 쓴다고 해서 반복문보다 항상 꼭 유리한 것은 아님. 유리할수도, 불리할수도 있음.)
+) 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓임.
그렇기 때문에 스택을 사용해야할 때 구현상 스택 라이브러리 대신 재귀함수 이용하는 경우가 많음.
DFS : 깊이 우선 탐색
그래프에서 깊은 부분을 우선적으로 탐색.
스택 / 재귀를 이용함.
- 탐색 시작 노드를 스택에 삽입한 후 방문 처리함.
- 스택 최상단 노드에 방문하지 않은 인접 노드가 하나라도 있다면 스택에 넣고 방문 처리함.
- 없다면 스택에서 최상단 노드를 꺼냄.
- 2번 과정을 수행할 수 없을 때까지 반복함.
BFS : 넓이우선탐색
그래프에서 가까운 노드부터 우선적으로 탐색.
최단 거리 찾기 문제에 적합함.
큐를 이용함.
1. 탐색 시작 노드를 큐에 삽입한 후 방문 처리함.
2. 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리함.
3. 2번 과정을 수행할 수 없을 때까지 반복함.
728x90
'자료구조' 카테고리의 다른 글
| +) [JAVA] static변수, static메서드, 일반 변수/메서드 차이점 이해하기 (0) | 2023.05.06 |
|---|---|
| +) JAVA Eclipse 자바 이클립스 디버깅하는 방법 (0) | 2023.04.01 |
| +) [JAVA] 기수정렬 알고리즘 정리 - radix sort (0) | 2023.03.22 |
| +) [JAVA] 합병(병합)정렬 알고리즘 정리 - merge sort (0) | 2023.03.22 |
| +) [JAVA] 퀵정렬 알고리즘 정리 - quick sort (0) | 2023.03.22 |