Pre-order traversal 은 tree 를 순회할 때 현재 node 를 먼저 방문하고, 그 다음 left subtree, right subtree 순서로 방문하는 방식이다.
root -> left -> right언제 쓰나
Tree 구조를 직렬화하거나, root 의 정보를 먼저 처리해야 하는 DFS 계열 traversal 에서 사용한다.
1 min read
pre-order: 자신 → 왼쪽 → 오른쪽 Inorder Search: 왼쪽 → 자신 → 오른쪽 post-order: 왼쪽 → 오른쪽 → 자신
사이클 검출, 위상 정렬, 연결 요소 찾기 모든 경우를 만들어 보며 조건에 안 맞으면 되돌아오는 완전 탐색 (backtracking) 트리 순회 — pre-order, Inorder Search, post-order 는 모두 DFS 의 방문 시점 차이다
Inorder Search preorder Search postorder Search
Inorder Search preorder Search postorder Search .
Post-Order Traversal Post-order traversal은 tree traversal에서 왼쪽 subtree → 오른쪽 subtree → 현재 node 순서로 방문하는 방식이다.
Depth-First Search. 그래프나 트리에서 한 갈래를 끝까지 따라 내려간 뒤, 더 갈 곳이 없으면 한 칸 되돌아와 아직 안 가본 갈래로 다시 내려가는 탐색 방식이다. “깊이 우선” 이라는 이름은 이웃을 폭넓게 훑기 전에 한 방향으로 먼저 파고든다는 뜻이다.
각 노드가 자식을 최대 두 개까지만 갖는 트리다. 두 자식은 왼쪽·오른쪽으로 구분되며, 자식이 하나뿐이어도 그것이 왼쪽인지 오른쪽인지가 구조상 의미를 갖는다.
BFS(Breadth First Search)는 시작 node 에서 가까운 node 부터 층별로 방문하는 graph/tree traversal 방식이다. 보통 queue 를 사용한다. 동작 흐름 시작 node 를 queue 에 넣고 방문 처리한다.
먼저 들어온 것을 먼저 내보내는 처리 순서다. 줄을 선 순서대로 처리한다고 보면 되고, 이 규칙을 구현한 자료구조가 큐(queue) 다. 반대는 나중에 들어온 것을 먼저 꺼내는 LIFO 이고, stack 이 그쪽이다.
가중치가 있는 무방향 그래프에서 minimum spanning tree (MST) 를 구하는 알고리즘이다. MST 는 모든 정점을 사이클 없이 연결하면서 간선 가중치 합이 가장 작은 부분 그래프를 말한다.
스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조 (LIFO - Last In First Out) 으로 되어 있다.
선택 정렬은 다음과 같은 순서로 이루어진다. 주어진 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 하나의 원소만 남을 때까지 위의 과정을 반복한다.
삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.