Pre-order traversal 은 tree 를 순회할 때 현재 node 를 먼저 방문하고, 그 다음 left subtree, right subtree 순서로 방문하는 방식이다.
root -> left -> right언제 쓰나
Tree 구조를 직렬화하거나, root 의 정보를 먼저 처리해야 하는 DFS 계열 traversal 에서 사용한다.
pre-order: 자신 → 왼쪽 → 오른쪽 Inorder Search: 왼쪽 → 자신 → 오른쪽 post-order: 왼쪽 → 오른쪽 → 자신
... 요소 찾기 모든 경우를 만들어 보며 조건에 안 맞으면 되돌아오는 완전 탐색 (backtracking). 예: Generate Parentheses, Permutations 트리 순회 — pre-order, Inorder Search, post-order 는 모두 DFS 의 방문 시점 차이다
Inorder Search preorder Search postorder Search
Inorder Search preorder Search postorder Search
Post-order traversal은 tree traversal에서 왼쪽 subtree → 오른쪽 subtree → 현재 node 순서로 방문하는 방식이다. 자식 node를 모두 처리한 뒤 parent를 처리하므로, tree를 아래에서 위로 접어 올리는 계산에 잘 맞는다.
Depth-First Search. 그래프나 트리에서 한 갈래를 끝까지 따라 내려간 뒤, 더 갈 곳이 없으면 한 칸 되돌아와 아직 안 가본 갈래로 다시 내려가는 탐색 방식이다. "깊이 우선" 이라는 이름은 이웃을 폭넓게 훑기 전에 한 방향으로 먼저 파고든다는 뜻이다.
각 노드가 자식을 최대 두 개까지만 갖는 트리다. 두 자식은 왼쪽·오른쪽으로 구분되며, 자식이 하나뿐이어도 그것이 왼쪽인지 오른쪽인지가 구조상 의미를 갖는다.
BFS(Breadth First Search)는 시작 node 에서 가까운 node 부터 층별로 방문하는 graph/tree traversal 방식이다. 보통 queue 를 사용한다.
먼저 들어온 것을 먼저 내보내는 처리 순서다. 줄을 선 순서대로 처리한다고 보면 되고, 이 규칙을 구현한 자료구조가 큐(queue) 다. 반대는 나중에 들어온 것을 먼저 꺼내는 LIFO 이고, stack 이 그쪽이다.
가중치가 있는 무방향 그래프에서 minimum spanning tree (MST) 를 구하는 알고리즘이다. MST 는 모든 정점을 사이클 없이 연결하면서 간선 가중치 합이 가장 작은 부분 그래프를 말한다. 도시를 전부 잇는 도로망을 최소 비용으로 까는 문제가 이 모양이다.
선택 정렬은 다음과 같은 순서로 이루어진다.
Insertion Sort Selection Sort Merge Sort Bubble Sort quick Sort Heap Sort
삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. More efficient in practice than most other simple quadratic: Selection Sort or Bubble...