Soongle's Morgorithm

이진 탐색 트리란, 다음과 같은 특징을 갖는 이진 트리이다 모든 노드의 값은 유일하다. 왼쪽 노드의 값은 자신의 값보다 작다. 오른쪽 노드의 값은 자신의 값보다 크다. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. 이진 탐색 트리 클래스를 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) 앞에서 부터 양 옆의 값을 비교하며 앞의 값이 뒤의 값보다 클 경우 두 값을 교환한다. 아..

Sort 선택 정렬(Selection Sort) 버블 정렬(Bubble Sort) 삽입 정렬(Insertion Sort) 선택 정렬(Selection Sort)을 구현해 보았다. void selection_sort(int arr[], int n) { for(int i = 0 ; i < n-1 ; i++) { int minIndex = i; for(int j = i+1 ; j < n ; j++) { if(arr[j] < arr[minIndex]) minIndex = j; } if(minIndex != i) swap(arr[minIndex], arr[i]); } } 마지막 원소인 n-1번째 원소는 자동 정렬되기 때문에 n-1전까지 반복해 주었다. (i+1) ~ (n-1)번째 원소들 중 가장 작은 값을 찾아 ..

이진 탐색(binary search)알고리즘은 정렬되어있는 데이터에서 특정 값의 위치를 찾는 알고리즘이다. ※정렬되어있지 않은 데이터에 사용할 수 없다※ 재귀로 구현하면 매우 간단해진다. 중간 값(mid)을 잡는다 원하는 값을 찾지 못하였을 때 탈출 조건(first > last)에 의해 -1을 반환한다 : 탐색 실패 원하는 값을 찾았을 때(arr[mid] == key) 해당 위치(mid)를 반환한다 : 탐색 성공 현재 중간 값이 찾고자 하는 값보다 큰 경우, 중간 값의 왼쪽 범위에서 탐색을 시작한다 : 재귀 호출 현재 중간 값이 찾고자 하는 값보다 작은 경우, 중간 값의 오른쪽 범위에서 탐색을 시작한다 : 재귀 호출 소스코드 #include #include using namespace std; int b..