Soongle's Morgorithm

AVL 트리란, George Adelson-Velsky와 Evgenii Landis가 발표한 최초의 균형잡힌 이진트리(balanced binary tree)이다. AVL 트리 클래스를 Node구조체를 사용한 링크 표현법으로 구현하였다. AVL 트리의 가장 핵심적인 기술은 바로 회전(Rotation)이다. RR, LL, RL, LR 네 가지 경우에서의 회전을 통해 트리 전체의 좌우 균형을 맞추기 때문이다. 이렇게 균형이 맞춰진 트리는 값을 탐색할 때 최악의 경우에도 O(log n)의 시간안에 탐색을 끝낼 수 있다. 각각의 회전을 해야하는 경우는 아래와 같다 RR : 오른쪽, 오른쪽으로 치우친 경우 → 현재 노드 기준으로 왼쪽으로 회전시킨다 LL : 왼쪽, 왼쪽으로 치우친 경우 → 현재 노드 기준으로 오른쪽..

하노이 탑문제는 N개의 크기가 서로 다른 원판을 다른 기둥으로 옮기는 문제이다. 이 때 다음 두 가지 조건을 만족시키면서 원판을 다른 기둥으로 옮겨야 한다. 한 번에 하나의 원판만 옮길 수 있다. 큰 원판이 작은 원판 위에 있어서는 안된다. 전체 n개의 원판을 옮기는 것은 다음과 같이 재귀적으로 생각해 볼 수 있다. 크기 1 ~ (n-1)인 원판들을 A기둥에서 B기둥으로 옮긴다. 크기 n인 원판을 A기둥에서 C기둥으로 옮긴다. 1 ~ (n-1) 원판들을 B기둥에서 C기둥으로 옮긴다. 소스코드 void hanoi(int n, char from, char tmp, char to) { if(n > 0) { hanoi(n-1, from, to, tmp); cout

이진 탐색 트리란, 다음과 같은 특징을 갖는 이진 트리이다 모든 노드의 값은 유일하다. 왼쪽 노드의 값은 자신의 값보다 작다. 오른쪽 노드의 값은 자신의 값보다 크다. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. 이진 탐색 트리 클래스를 Node 구조체를 사용한 링크 표현법으로 구현하였다. 모든 함수들은 재귀로 구현하였다. #include #include using namespace std; struct Node { int data; Node* left; Node* right; }; class BinaryTree { public: BinaryTree(); ~BinaryTree(); int size(); int height(); bool search(int key); bool insert(int ite..

cin, cout은 C++의 Standard Stream Object이다. cin은 istream 클래스의 객체이고 cout은 ostream 클래스의 객체이다. template inline basic_ostream

Sort 선택 정렬(Selection Sort) 버블 정렬(Bubble Sort) 삽입 정렬(Insertion Sort) 삽입 정렬(Insertion Sort)을 구현해 보았다. void insertion_sort(int arr[], int n) { int j; for(int i = 1 ; i = 0 ; j--) { if(arr[j] > temp) arr[j+1] = arr[j]; else break; } arr[j+1] = temp; } } 우선, 자신이 삽입되어야 할 자리를 자신의 앞에서 찾기 때문에 아래의 동작을 i = 1에서부터 n-1까지 반복한다. temp 변수에 현재 자신의 값을 저장해둔다. 반복문을 사용해..

Sort 선택 정렬(Selection Sort) 버블 정렬(Bubble Sort) 삽입 정렬(Insertion Sort) 버블 정렬(Bubble Sort)을 구현해 보았다. void bubble_sort(int arr[], int n) { for(int i = n-1 ; i > 0 ; i--) { bool sorted = true; for(int j = 0 ; j arr[j+1]) { swap(arr[j], arr[j+1]); sorted = false; } } if(sorted) break; } } i : 정렬이 끝나는 칸(뒤에서 부터 정렬됨) j : (0 ~ i-1) 앞에서 부터 양 옆의 값을 비교하며 앞의 값이 뒤의 값보다 클 경우 두 값을 교환한다. 아..