25_Searching Algorithm_22.09.26

트리 순회

>의미

: (특정 목적을 위해)트리의 모든 노드를 한 번씩 방문하는 것.

>전위 순회

: [루트 - 왼쪽 자식 - 오른쪽 자식] 순으로 순회

>중위 순회

: [왼쪽 자식 - 루트 - 오른쪽 자식] 순으로 순회

>후위 순회

: [왼쪽 자식 - 오른쪽 자식 - 루트] 순으로 순회

 

그래프 순회

>의미

: (특정 목적을 위해) 그래프의 모든 정점을 한 번씩 방문하는 것.

>BFS(Breadth-First Search)

: 너비 우선 탐색

: 두 정점의 최단 경로를 찾을 때 주로 사용

: 시작점에 인접한 정점을 먼저 탐색하는 방법

: 검색 속도는 DFS보다 상대적으로 빠르다

: 검색 방법은 DFS보다 상대적으로 복잡하다
: 보통 재귀적인 방식보다는 큐를 이용하고, 어떤 정점을 방문했는지의 여부를 검사하여 무한 루프에 빠지지 않게 만든다.

>DFS(Depth-First Search)

: 깊이 우선 탐색

: 장애물이 있는 길(ex-미로)에서 길을 찾을 때 주로 사용

: 다른 분기(branch)로 넘어가기 전에 해당 분기를 모두 탐색하는 방법

: 검색 속도는 BFS보다 상대적으로 느리다

: 검색 방법은 BFS보다 상대적으로 간단하다

: 스택 or 재귀 함수로 알고리즘을 구성하며, 어떤 정점을 방문했는지의 여부를 검사하여 무한 루프에 빠지지 않게 만든다.

 

 

//순회의 공통점 : 정렬되어 있지 않은 자료구조에서 데이터를 찾기 위함.

//지금 완벽히 다 알 필요는 없지만, 나중에 제대로 공부할 때 뭔지 알 정도는 하자.

//특히 BFS, DFS는 코테에서 중요도가 높다.

//어떤 상황에서 어떤 순회방법이 적합한 지 연습할 것.

//코플릿_자료구조_11,12,13 완벽 숙지할 것.

//추가 공부로 탐색 알고리즘 공부를 하자(알고리즘과 자료구조는 자연스레 같이 공부될 것)