5장 컴퓨터 과학/Data Structure & Algorithm27 [알고리즘] 이진 트리 순회(Binary Tree Traversal) 전위 순회(Preorder Traversal) 이진 트리는 트리의 일종으로 일반적인 트리에 대한 전위 순회 알고리즘이 똑같이 적용될 수 있다. template void preorder(Node* node) { if (node == nullptr) return; coutGetLeft()); postorder(node->GetRight()); cout 2021. 6. 11. [알고리즘] 트리 순회(Tree traversal) 깊이와 높이 node를 트리 T의 노드라 하자. node의 깊이(depth)는 node의 조상의 수이다. 만약 node가 루트이면, node의 깊이는 0이 된다. 그렇지 않으면, node의 깊이는 node의 부모의 깊이에 1을 더한 것과 같다. template int depth(Node* node) { if (node->is_root()) return 0; return 1+depth(node->parent()); } 트리 T에서 node의 높이(height)도 재귀적으로 정의된다. 만약 p가 외부 노드이면 p의 높이는 0이다. 그렇지 않으면 node의 높이는 node의 자식의 높이 중 가장 높은 값에 1을 더하면 된다. template int height(Node* node) { if (node->is_.. 2021. 6. 10. [알고리즘] 버블 정렬(Bubble Sort) 버블 정렬은 각 단계에서 노드 전체를 검사한다. 차례대로 각 노드에 대해 다음 노드와의 크기를 비교하여 위치를 바꾸고 이런 과정을 원소의 개수만큼 반복한다. 특성 첫 번째 과정에서 가장 큰 원소를 만나면 마지막 노드에 도달할 때까지 계속 교환이 이루어진다. 두 번째 과정에서 두 번째로 큰 원소를 만나면 끝에서 두 번째 노드에 도달할 때까지 계속 교환이 이루어진다. 일반적으로 각 i번째 과정이 끝나면 끝에서 i개의 원소들은 최종 위치에 도달한 것이다. C++ 구현 template void bubble_sort(RandomIt first, RandomIt last) { while (first != last--) for (RandomIt it = first; it *.. 2021. 6. 9. [알고리즘] 재귀 함수(Recursive Function) 개념 재귀 함수는 직간접적으로 자기 자신을 호출하는 함수이다. 재귀 함수에는 중요한 세 가지 특징이 있다. 재귀 함수는 종료 조건이 있어야 한다. 재귀 함수는 종료 조건에 도달하게 상태를 변경해야 한다. 재귀 함수는 자기 자신을 호출해야 한다. 계승 함수(Factorial Function) 팩토리얼 함수 factorial(n)은 일반적으로 factorial(n) = n*factorial(n-1)을 만족한다. 따라서 factorial 함수를 재귀적으로 정의하면 다음과 같다. int factorial(int n) { if (n == 0) return 1; return n * factorial(n-1); } 배열의 합 배열 A가 n개의 정수를 갖는 배열일 때, A의 합은 n=1 일 때 A[0]이고 그렇지 않으.. 2021. 6. 8. [알고리즘] 삽입 정렬(Insertion Sort) 삽입 정렬은 임의의 배열을 정리하는 방법으로 알고리즘의 각 반복 단계마다 다음 원소를 현재의 정렬된 배열 부분에 삽입한다. 삽입 정렬은 두 번째 원소부터 시작한다. 만약 두 번째 원소가 첫 번째 원소보다 작다면 두 원소의 위치를 바꾼다. 그리고 다음 원소로 넘어간다. 만약 세 번째 원소가 두 번째 원소보다 작다면 위치를 바꾸고, 첫 번째 원소보다 작다면 위치를 또 바꾼다. 배열의 각 원소에 대해 원소의 적정 위치에 도달할 때까지 왼쪽으로 교체를 반복한다. C++ 구현 template void insertion_sort(RandomIt first, RandomIt last) { for (RandomIt it = first+1; it != last; ++it) { int i = it-first; while .. 2021. 6. 8. 이전 1 2 3 4 5 6 다음 반응형
