TIL16: Algorithm / BFS and DFS

Algorithm(알고리듬)이란 주어진 문제를 해결하기 위한 일련의 절차들을 정의한 것이라고 할 수 있습니다.

알고리듬을 생각해내고 코드로 구현하는 것은 개발자에게 반드시 필요한 능력이지만 고통스러운 과정이기도 합니다. 따라서 능력 개발을 위해 자주 경험하고 훈련해보는 것이 중요합니다.

Data Structure(자료 구조)에서 각 노드들을 순회하는 방법에 따라 Breadth First Search(BFS, 너비우선 탐색) 또는 Depth First Search(DFS, 깊이우선 탐색)이 있습니다.

• BFS: "가능한 모든 경우 생각해보기" - 문어발식
  • Queue, Graph 자료구조
  • 예를 들면, 지도에서 각 지점을 노드, 지점간 연결 여부를 간선, 그리고 거리를 가중치라고 가정하여 가장 적은 갯수의 노드와 간선을 가지면서 가중치가 작을 경우(최단 경로)를 탐색하는 알고리듬
• DFS: "갈 때까지 가보기" - 막장식
  • Stack, Graph 자료구조: 특히, Dicision Making Tree 단, Backtraking 테크닉 필요
  • 예를 들면, 미로에서 일단 더 이상 갈 수 없을 때까지 경로를 진행해보고 올바른 경로가 아닐 경우 돌아와 다른 출구 경로를 탐색하는 알고리듬(게임 또는 퍼즐 문제에 많이 적용)

자료 구조의 깊이나 너비 우선 기준이 아닌 정해진 탐색 순서에 따라 순회할 수도 있습니다. 탐색 순서에는 Preorder Traversal(전위 순회), Inorder Traversal(중위 순회), Postorder Traversal(후위 순회)가 있습니다.

• Preorder Traversal : Left-Root-Right
• Inorder Traversal : Root-Left-Right
• Postorder Traversal : Left-Right-Root

Binary Tree's Traversal

(1) BFS : 1, 2, 3, 4, 5
(2) DFS
- Preorder: 1, 2, 4, 5, 3
- Inorder: 4, 2, 5, 1, 3
- Postorder: 4, 5, 2, 3, 1

자료 출처: GeeksforGeeks