1. 개요 정렬 알고리즘을 배운 것을 토대로 아래 네 가지 정렬 알고리즘을 만들고, 다양한 Case를 나누어 프로그램의 동작 방식을 이해하는 과제이다. 프로젝트 파일의 구성도는 다음과 같다. 1) SortAlgorithm.h Insertion Sort, Selection Sort, Merge Sort, Quick Sort를 수행하는 네 가지 알고리즘을 구현한 파일이다. 이때 이전에 구현한 ArrayVector와 그 내장함수를 사용하여 정렬할 배열을 선언하였다. - Insert/ InsertionSort : 삽입 정렬 - SelectionSort : 선택 정렬 - Merge/ MergeSort : 합병 정렬 - QuickSort : 빠른 정렬 - Swap/printVector : 두 개의 값을 바꾸는 Sw..
Stock Span problem 이란? https://thebook.io/006952/ch01-01/ 리얼월드 알고리즘: 1장 주가 스팬 - 1 thebook.io 배열이 주어졌을 때, 각각의 인덱스에서 해당하는 값과 앞의 인덱스와 연쇄적으로 비교한다. 이때 자신을 포함한 앞의 인덱스의 값들 중에서 자신의 값과 작거나 같은 인덱스의 개수를 스팬이라고 정의한다. Stock Span Problem 을 해결하는 코드는 두 가지 종류가 있는데, Quadratic-Time Algorithm O(n^2)의 Big Oh Notation을 가지는 알고리즘이다. #include using namespace std; int main() { int arr[7] = { 1,1,1,2,1,4,6 }; int ans[7] = ..
#include using namespace std; void printArray(int* S, int n) { for (int i = 0; i > arr[i]; } mergeSort(n, arr); printArray(arr, n); } #include #include using namespace std; vector buff; void __mergeSort(int a[], int left, int right) { if (left < right) { int center = (left + right) / 2; int p = 0; // 왼쪽 배열의 인덱스 int i; ..
검색 알고리즘이란? : 데이터 집합에서 원하는 값을 가진 요소를 찾아내는 알고리즘 검색 알고리즘의 종류 1) 배열 검색 - 선형 검색 - 이진 검색 2) 선형 리스트 검색 3) 이진검색트리 검색 선형 검색? : 요소가 직선 모양으로 늘어선 배열에서의 검색은 키 값을 갖는 요소를 만날 때까지 맨 앞에서부터 순서대로 요소를 검색한다. int search(const int a[], int n, int key) { int i = 0; while (1) { if (i == n) { return -1; } if (n == key) { return i; } i++; } } int main() { int nx, ky, idx; // 배열의 요소 개수, 선형검색할 수, 검색한 요소의 위치 int* x; // 배열 pri..
