파게로그

arr = [1, 2, 6, 2, 3, 2, 2, 4, 4]일 때, 정렬 결과는 [1, 2, 2, 2, 2, 3, 4, 4, 6]이 된다. 즉 중복 원소의 개수를 고려한다면, 인덱스의 개수가 정해진다는 것이다. arr에 대해서, arr의 각 원소에 대한 빈도값을 담는 countingArr와 countingArr의 누적합을 담는 idxArr를 만들면, 아래와 같다. countingArr = [0, 1, 4, 1, 2, 0, 1], idxArr = [0, 1, 5, 6, 8, 8, 9] coutingArr[n]의 의미는, arr에서 n이 countingArr[n]개 있다는 의미이다. 즉 countingArr[2] = 4라는 것은, arr에서 2가 4개 있다는 의미이다. idxArr[n]의 의미는, sorte..

문제 링크: 2751번 수 정렬하기 2 https://www.acmicpc.net/problem/2751 merge sort를 C++로 구현해 보았다. #include #include using namespace std; vector sliceVector(vector arr, int start, int end) { // arr[end]는 결과에 포함되지 않는다. // 파이썬에서 슬라이싱과 동일하게 구현했다. vector res; for (int i=start; i

문제 링크: 2750번 수 정렬하기 https://www.acmicpc.net/problem/2750 O(n^2) 알고리즘으로 풀린다고 하니, 정렬에서 설명하지 않았고 구현이 간단한 selection sort를 사용한다. #include #include using namespace std; void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } bool compare(int a, int b) { // 왼쪽이 더 크면 true, 그렇지 않으면 false if (a>b) return true; else return false; } void selectionSort(vector &arr) { // 바깥쪽 for문을 돌 때마다 arr[i]가 가장 작은..

퀵 정렬은 말 그대로 대부분의 경우에 최상의 성능을 보여주는 정렬 기법이라고 할 수 있다. 정렬은 다음과 같이 이루어진다. 1. 리스트에서 임의의 한 원소를 pivot으로 하여, 이를 기준으로 두 리스트로 나눈다. 리스트의 크기는 다를 수 있다. 2. 왼쪽 리스트에는 pivot보다 작은작거나 같은 값만을, 오른쪽 리스트에는 pivot보다 큰크거나 같은 값만을 남긴다. 3. 왼쪽 리스트와 오른쪽 리스트에 대해서 quick sort를 수행한 후 이를 병합한다. 여기서 2번 과정은 다음과 같이 이루어진다. [3, 6, 1, 8, 5, 9, 4, 2, 7]을 예로 들고 pivot은 항상 첫 번째 원소라고 하자. 1. arr = [6, 1, 8, 5, 9, 4, 2, 7], pivot = arr[first] = ..

insertion sort는 카드 게임을 할 때 우리가 카드를 정렬하는 방식과 굉장히 유사하다. 하나의 카드를 잡아서, 왼쪽부터 훑어나가면서 카드를 원하는 위치에 쏙 하고 집어넣기 때문이다. 다만 실제 구현에서는, 리스트에서 원소를 밀어주는 것이 꽤나 부담스럽게 다가온다. 0. i=1일 때, arr[1]은 이미 정렬된 상태이다. 1. i=2일 때, key = arr[2] key를 arr[1]과 비교하여 올바른 위치에 넣되, arr[1] 자리에 들어가야 한다면 원래 arr[1]을 뒤로 밀어낸다. 이 때 arr[0]까지 갈 수도 있다. 올바른 위치에 넣는다는 것은, arr[j]가 arr[i]보다 작을 때, 밀어내기를 중단하는 것이다. arr[0]~arr[i-1]은 이미 정렬된 리스트이지만 key는 완전히 새..

divide&conquer 방식의 알고리즘으로서 일반적으로 재귀 호출을 통해서 구현된다. 과정은 다음과 같다. 1. 리스트의 길이가 1 이하이면 이미 정렬된 리스트이다. 2. 정렬되지 않은 리스트를 동일한 또는 비슷한 크기의 두 개의 부분 리스트로 분할한다. (divide) 3. 각 부분 리스트를 재귀적으로 merge sort를 이용하여 정렬한다. (conquer) 4. 두 부분 리스트를 하나의 리스트로 병합한다. (combine) [5, 2, 4, 7, 6, 1, 3, 8] [5, 2, 4, 7] / [6, 1, 3, 8] [5, 2] / [4, 7] // [6, 1] / [3, 8] [5] / [2] // [4] / [7] /// [6] / [1] // [3] / [8] ↑divide ↓conquer..

bubble sort는 '정렬' 하면 빠질 수 없는 가장 무지막지한(?) 방법이라고 생각한다. 방법은 첫 번째 원소부터 마지막 원소까지 비교해감으로써 한 개의 원소를 정렬하고, 이 과정을 마지막 원소까지 반복하는 것이다. 시간복잡도 - 비교 횟수 i=0일 때 n-1번, 1일때 n-2번, ... 이렇게 해서 n(n-1)/2 - 교환 횟수 최악의 경우는 원소가 역순으로 정렬된 경우이고, n(n-1)/2회가 발생한다. (temp를 이용하는 swap()을 생각한다면, 3*n(n-1)/2회가 발생함) 최상의 경우는 원소가 정렬된 경우이고, 0회가 발생한다. - T(n) = O(n^2) def bubble_sort(arr): # 배열의 범위를 설정 # last는 마지막 원소의 index for last in ran..

완전이진트리(complete binary tree) 말단 노드를 제외한 모든 노드가 두 개의 자식 노드를 가지고 있는 이진 트리. 힙(heap) 완전이진트리에서, 모든 노드에 대해서 부모 노드의 값이 자식 노드의 값보다 크거나 같으면 Max heap, 작거나 같으면 Min heap이라 한다. heapify(힙 생성) 1. 루트 노드(A)부터 모든 노드를 순회하며, 2. A와 A의 자식 노드를 비교하여, 교환하거나 그대로 둔다. 3. 2를 반복한다. heapify는 하나의 노드에 대해 수행되는 과정을 반복하며, 해당하는 노드를 제외하고는 최대 힙이 구성되어 있는 상태라고 가정한다. 즉, 위에서부터 차례차례 서브 트리를 Max heap으로 만들어나가는 것이다. insert(삽입) 1. 마지막 자리에 추가할 ..