본문 바로가기

정렬

(5)
vector 정렬 (cmp 함수) #include 헤더의 sort 함수는 기본적으로 오름차순 정렬 배열을 sort 한다면 배열의 시작점 주소와 마지막 주소 + 1(end)를 쓴다. sort 함수의 인자에 마지막 cmp 함수를 추가하자! cmp 함수는 bool type 비교의 기준은 '왼쪽이 오른쪽에 비해서'를 기준으로 삼는다. 즉, return a > b를 하면 내림차순이 될 것이고 return a < b를 하면 오름차순이 될 것이다. 상어 초등학교의 cmp 함수를 살펴보자 순서대로 가는 것이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 bool cmp(POSITION A, POSITION B) { if (A.near_friend == B.near_friend) { if (A.near_empty == B.ne..
수 정렬하기 3 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제는 다른 정렬 문제와 다르다. 숫자가 중복해서 나온다. 근데 숫자가 1부터 10000까지밖에 안나온다. count 배열을 ++ 시키면 되겠다! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include using namespace std; int main() { ios::sync_with_stdio(fa..
기수 정렬(radix sort) 기수 정렬은 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교 시간 복잡도는 O(kn), k는 데이터의 자릿수 기수 정렬은 시간 복잡도가 가장 짧은 정렬이다! 코테에서 정렬해야 하는 데이터 개수가 너무 많으면 기수 정렬을 써보자. https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 10,000,000, N이 엄청 크다.. O(nlogn)보다 더 빠른 알고리즘이 필요하다. 숫자가 10000보다 작거나 같은 조건을 이용해서 계수 정렬(counting sort)를 ..
병합 정렬 https://www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다. www.acmicpc.net 버블 소트는 낚시다. N 범위가 500000 이고 제한시간 1초인데 O(N^2)을 쓴다? 절대로 못푼다 O(n log n)을 쓰자. 병합 정렬에서 두 그룹을 병합하는 과정에서 버블 정렬의 swap이 포함되어 있다 합치는 과정에서 뒤쪽 데이터가 더 작아 선택되는 경우 SWAP이 일어났다고 가정하며 현재 남아있는 앞쪽 데이터 개수만큼 결과값에 더함 result = result ..
퀵 정렬 분할 정복에 기반한 알고리즘 재귀 사용 최악: 내림차순일 경우 중간값을 pivot으로 설정만 해줘도 최악을 피할 수 있 최선 : O(nlog2n) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 void Swap(int* A, int* B) { int Temp = *A; *A = *B; *B = Temp; } // 나누고 바꾸는 함수 int Partition(int DataSet[], int Left, int Right) { //여기서는 가장 왼쪽 데이터를 pivot 설정 int First = Le..