미국 개발자 산만한 일기 미국 개발자 산만한 일기

리트코드 - leetcode.com/problems/serialize-and-deserialize-binary-tree/ 구글 인터뷰 문제 TOP10 중 2 위인 BFS 알고리즘 BFS 는 트리 구조의 Data를 너비 먼저 탐색하는 (Breath First Search) 알고리즘이다. 꼭 binary tree 가 아니여도 된다. BFS DFS ▪ 깊이가 얕고 노드가 적을 때 유리 ▪ DFS 보다 메모리를 더 많이 쓸 수 있다. 탐색할 모든 노드를 큐에 저장 ▪ 큐 (Queue) ▪ 답이 되는 경로가 최단경로 보장 ▪ 깊이가 깊고 노드가 많을 때 유리 ▪ BFS 보다 메모리를 더 적게 쓴다. 백트래킹을 해야하는 노드만 저장 ▪ 스택 (Stack), 재귀 (Recursive) ▪ 끝까지 찾아봐야 최단경로를 ..