백트래킹(Back-Tracking)?
트리 탐색 알고리즘의 일종이다. 거슬러 추적한다는 의미를 담고 있다. 이전 노드로 돌아가서 다시 다른 노드들을 탐색한다는 것.
깊이 우선 탐색 [Depth First Search] , 너비 우선 탐색 [Breadth First Search] , 최선 우선 탐색 [Best First Search] 로 나뉜다.
DFS의 특징
-깊이를 고려하는 문제인지 확인해야한다. 무한한 깊이일 경우 피해야 한다.
-스택 오버플로를 조심해야 한다. 재귀 호출을 이용할 시, 너무 많이 시도할 경우 스택 오버 플로가 발생한다.
-스택을 이용한 방법 / 재귀 호출을 이용한 방법으로 두가지로 구현이 가능하다.
BFS의 특징
-최단 거리 구하기 문제에서 사용하기 알맞다. 레벨별로 서치하기 때문이다.
-큐를 이용한 방식으로 구현이 가능하다.
Best Fs의 특징
-데이터의 중요도를 고려한 탐색 알고리즘이다.
-우선 순위 큐를 이용한다.
'컴퓨터 공학 > 알고리즘' 카테고리의 다른 글
👉 [번역] 객체 인식(Object Recognition) 이해 : 딥러닝 vs 머신러닝 방식 (0) | 2019.10.29 |
---|---|
👉 [SQL] 기본적이고 자주 사용하는 SQL 문법 정리 (0) | 2019.10.20 |
👉 [SQL] column 내 가장 길이 긴 값 찾기 (0) | 2019.06.29 |
BFS / DFS (0) | 2018.04.10 |
펜윅 트리 (0) | 2018.04.10 |