IT 방랑기

알고리즘에서 가장 기본이 되는 탐색 알고리즘인 DFS와 BFS에 대하여 정리한다. DFS는 깊이 우선 탐색으로 그래프가 주어졌을 때 함수 스택을 이용하여 현재 노드와 연결된 노드로 탐색하며, BFS는 너비 우선 탐색으로 큐를 이용하여 현재 노드와 연결된 노드들을 탐색한 다음 연결된 노드들에 연결된 노드들을 차례로 탐색한다. 그래프 V와 E가 주어졌을 때 배열으로 노드를 방문하였는 여부를 저장하여, 다시금 방문하지 않도록 강제한다. 그래프가 아래와 같이 주어졌다고 하자. A - B1 - C1 - B2 - C2 - B3 - C3 DFS는 A에 연결된 B1노드, 그리고 B1노드에 연결된 C1노드를 바로 탐색하기 때문에 트리의 순회에 자주 이용된다. 반면 BFS는 A노드에 연결된 모든 노드 B1, B2, B3를..

트리 순회는 가장 기본적인 알고리즘인 DFS에 바탕을 두고 있다. DFS는 함수 스택을 이용한 재귀 호출로 구현하며, 스택이라는 특징을 바탕으로 트리를 순회할 수 있다. 트리 순회는 트리의 특성과 DFS를 묻는 가장 기초적인 내용이다. 트리 순회 방법으로는 전위 / 중위 / 후위 순회가 있으며, 이는 각각 부모와 좌, 우의 자식 노드가 있을 때, 어느 노드부터 출력할 것인가에 대한 방식이다. 전위 순회는 [부모 / 좌 / 우] 순서이며, 중위 순회는 [ 좌 / 부모 / 우 ] 그리고 후위 순회는 [ 좌 / 우 / 부모 ] 순서로 출력한다. 즉 부모(루트)의 출력 순서에 따라 나뉘게 된다. 이러한 순서를 출력하는 것은 DFS의 출력 위치에 따라서 간단하게 구현할 수 있다. DFS(X)는 루트 X에 대하여 ..