정의 데이터 값의 갯수를 count해 그 데이터가 얼마나 있는지를 알 수 있는 정렬 알고리즘이다 조건 데이터가 양수만 존재해야 한다 데이터의 크기가 매우 작아야한다 핵심 주어진 수의 +1만큼 배열을 미리 만들어 준다 입력받은 값에 속하는 index번지에 count를 +1씩 해준다 출력시 배열이 0 이 아닌 index에 count한 수만큼 index를 출력해준다 구현 #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n{}; int input{}; int arr[10001]{}; cin >> n; for (int i = 0; i > in..

정의 값을 비교하지 않는 특이한 정렬 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교한다 시간 복잡도는 O(KN)이고 K는 자리수를 의미한다 핵심 이론 10개의 큐를 사용한다 각 큐는 값의 자리수를 대표한 구현 #include #include #include using namespace std; int findMax(vector v) { int maxValue = v[0]; for (int i = 1; i maxValue) { maxValue = v[i]; } } return maxValue; }\ void radixSort(vector& v) { int maxValue = findMax(v); int exp = 1; int size = (i..

정의 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘 시간 복잡도는 O(NlogN)이다 핵심이론 데이터 집합을 쪼갤수 있을 때 까지 모두 쪼갠다 쪼갠 데이터들을 병합하면서 정렬을 한다 이 과정을 하나의 더이상 병합할 데이터들이 없을 때 까지 반복한다 2개의 그룹을 병합하는 과정 투 포인터 개념을 사용해 왼쪽, 오른쪽 그룹을 병합한다 왼쪽 오른쪽 배포인터의 값을 비교하여 작은 값을 결과 배열게 추가하고 포인터를 오른쪽으로 이동시킨다 구현 #include #include using namespace std; void Marge(vector& v, int left, int mid, int right) { int n = mid - left + 1; int n2 = right -..

정의 기준값 Pivot을 선정해 해당 값보다 자은 데이터와 큰 데이터로 분류하여 반복해 정렬하는 알고리즘 기준값 선정에 따라 시간 복잡도가 달라진다 평균 시간 복잡도는 O(nlogn)이며 최악의 경우 O(n^2)이다 핵심이론 Pivot을 중심으로 계속 데이터를 2개의 집합으로 나누면서 정렬하는 것 구현 #include #include using namespace std; int Partition(vector& v, int start, int end) { int pivot = end; int index = start - 1; for (int i = start; i v[i]) { index++; swap(v[index], v[i]); } } swap(v[p..

정의 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시키는 방식 시간 복잡도는 O(N^2)이다 핵심이론 선택 데이터를 현재 정렬된 데이터 범위 내에 적절한 위치에 삽입하는 것 적절한 삽입 위치를 탐색하는 부분에서 이진탐색등과 같은 탐색 알고리즘을 사용하면 시간 복잡도를 log(N)으로 줄일 수 있다 구현 #include #include using namespace std; void InsertionSort(vector& v) { int pivot = 1; for (int i = 0; i = 0; j--) { int a{}; if (v[j] > v[temp])..

정의 최대/최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법 시간 복잡도는 O(N^2)이다 핵심 이론 최대/최소 값을 찾고 남은 정렬 부분의 가장 앞에 있는 데이터와 Swap하는 것이 핵심이다 구현 #include #include using namespace std; void SelectionSort(vector& v) { for (int i = 0; i v[j]) { min = j; } } swap(v[min], v[i]); } } int main() { vector v = { 42,40,24,62,32 }; Selection..

정의 다른 정렬에 비해 시간이 오래걸리지만 로직이 단순하고 구현이 간단하다 데이터의 인접 요소끼리 비교, swap연산을 수행하며 정렬하는 방식 핵심 인접한 데이터의 크기를 비교해 정렬하는 방식 시간복잡도는 O(n^2)으로 다른 알고리즘에 비해 느리다 인접한 데이터간에 Swap 연산으로 정렬한다 정렬 과정 비교 연산이 필요한 루프 범위를 설정한다 인접한 데이터 값을 비교한다 swap 조건에 부합하면 swap 연산을 수행한다 루프 범위가 끝날 때 까지 2,3번 과정을 반복한다 정렬 영역을 설정하여 다음 루프를 실행할 때 이 영역을 제외한다 비교대상이 없을 때 까지 위의 과정을 반복한다 구현 #include #include using namespace std; void BubbleSort(vector& v) ..

스택 정의 삽입 삭제 연산이 후입선출로 이뤄지는 자료구조 삽입 삭제가 한 방향에서 이뤄진다 스택에 값이 들어오면 top이 새 값을 가리킨다 값을 빼낼 때는 top이 가리키는 값이 빠지고 이전 값을 가리키게 된다 용어 top: 현재 값이 들어있는 위치, 값이 없을 땐 -1에서 시작한다 pop: 데이터를 삭제하고 확인하는 연산 push 값을 넣어주는 연산 우선 탐색(DFS), 백트래킹등 재귀함수를 이용하는 알고리즘에서 효과적이다 큐 정의 스텍과 반대롤 삽입 삭제 연산이 선입선출로 이뤄진다 삽입삭제가 양 방향에서 이뤄진다 push는 back, pop은 front에서 이뤄진다 용어 back: 큐의 가장 끝의 데이터 front: 큐의 가장 처음 데이터 push: back부분에 새로운 데이터를 삽입하는 연산 pop..

정의 합 배열을 이용해 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 합 배열 S[i] = A[0] + A[1] + A[2]+ ... + A][i]를 통해 미리 합을 구해 배열에 저장해 놓는 것 합 배열을 미리 구하면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(n)에서 O(1)이 된다