다락방

SortedDictionary.NET에서 제공하는 제네릭 컬렉션 클래스 중 하나로, 키와 값의 쌍을 저장하고 키를 기준으로 자동으로 정렬하는 사전(Dictionary)이다.이 클래스는 System.Collections.Generic 네임스페이스에 포함되어 있으며, 키가 정렬 순서로 저장되어야 하는 시나리오에서 유용하다.주요 특징키의 정렬키를 기준으로 자동으로 정렬한다. 기본적으로 키는 기본 제공된 비교자(기본적으로 IComparable 구현 또는 지정된 IComparer)를 사용하여 정렬된다.키와 값의 쌍다른 사전 컬렉션과 마찬가지로 키와 값의 쌍을 저장한다. 각 키는 고유하며, 동일한 키를 두 번 저장할 수 없다.빠른 검색키에 대한 검색, 추가, 삭제가 모두 로그(log) 시간 내에 수행된다. 이는 내..

병합 정렬(Merge Sort)합병 정렬이라고도 부르며, 분할 정복 방법을 통해 구현된다.빠른 정렬로 분류되며, 퀵소트와 함께 많이 언급되는 정렬 방식이다.퀵소트와는 반대로 안정 정렬에 속한다.요소는 분리하고 다시 합병시키면서 정렬해나가는 방식으로, 분리하는 방식은 퀵정렬과 유사하다.Quick Sort : 피벗을 통해 정렬 → 분리Merge Sort : 분리되지 않을 때 까지 분리 → 정렬Merge Sort는 순차적인 비교로 정렬을 진행하므로, LinkedList의 정렬이 필요할 때 사용하면 효율적이다.시간복잡도O(nlogn)공간복잡도병합 정렬이 입력 배열에서 분할 및 정복 방식으로 작동하고 정렬된 후 하위 배열이 다시 병합되기 때문에 공간복잡도는 O(n)이다.장점병합 정렬은 동일한 값을 가진 요소의 상..

퀵 정렬(Quick Sort)분할 정복(divide and conquer) 방법을 통해 주어진 배열을 정렬한다.분할 정복문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.Quick Sort은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 또한 Merge Sort는 배열을 비균등하게 분할한다.과정배열 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗(pivot)이라고 한다.피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눈다. 이렇게 배열을 둘로 나누는 것을 분할(Divide) 이라고 한다. 분할을 마친 뒤에 피벗은 더 ..

삽입 정렬(Insertion Sort)손 안의 카드를 정렬하는 방법과 유사하다.Selection Sort와 유사하지만, 좀 더 효율적인 정렬 알고리즘이다.2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다.최선의 경우 O(N)이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬 알고리즘이다.과정정렬은 2번째 위치(index)의 값을 temp에 저장한다.temp와 이전에 있는 원소들과 비교하며 삽입해나간다.‘1’번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복한다.시간복잡도평균, 최악의 경우 O(n^2)최선의 경우 O(n)공간복잡도주어진 ..

선택 정렬(Selection Sort)해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다.배열에서 해당 자리를 선택하고 그 자리에 오는 값을 찾는 것이다.과정주어진 배열 중에 최소값을 찾는다.그 값을 맨 앞에 위치한 값과 교체한다.맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.시간복잡도비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 배열을 정렬하는데 O(n^2) 만큼의 시간이 걸린다. 최선, 평균, 최악이 경우 시간복잡도는 O(n^2)으로 동일하다.공간복잡도주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n) 이다.장점알고리즘이 단순하다.정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟..

18870 좌표 압축 #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); vector x1; vector x2; int n; cin >> n ; for (int i = 0; i > tmp; x1.push_back(tmp); x2.push_back(tmp); } sort(x1.begin(), x1.end()); x1.erase(unique(x1.begin(), x1.end()), x1.end()); for (int i = 0; i < n; ++i) { cout

25305 커트라인 #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); vector num_arr; int n, k; cin >> n >> k; for (int i = 0; i > tmp; num_arr.push_back(tmp); } sort(num_arr.begin(), num_arr.end(),greater()); cout

2587 대표값2 #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); vector num_arr(5); int sum = 0; for (int i = 0; i > tmp; sum += tmp; num_arr[i] = tmp; } sort(num_arr.begin(), num_arr.end()); cout

11651 좌표 정렬하기2 #include using namespace std; bool compare(pair a, pair b) { if (a.second == b.second) return a.first > n; for (int i = 0; i > x >> y; n_arr.push_back({x, y}); } sort(n_arr.begin(), n_arr.end(),compare); fo..

11650 좌표 정렬하기 #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; vector n_arr; cin >> n; for (int i = 0; i > x >> y; n_arr.push_back({x, y}); } sort(n_arr.begin(), n_arr.end()); for (auto i : n_arr) { cout