개발 노트

속도가 O(N * log N)이 나오는 퀵 정렬, 병합 정렬, 힙 정렬보다 빠르게 정렬하는 방법. 단 범위조건이 있어야 한다. 시간복잡도는 O(N)으로 매우 빠르다. 크기를 기준으로 갯수를 센 후 그 수 만큼 출력하면 된다. 크기가 한정되어 있는 배열만이 계수정렬을 사용할 수 있다는 특징이 있다. #include int main(void) { int temp; int count[6]; int array[30] = {1, 3, 2, 4, 3, 2, 5, 3, 1, 2, 3, 4, 4, 3, 5, 1, 2, 3, 5, 2, 3, 1, 4, 3, 5, 1, 2, 1, 1, 1}; for(int i = 1; i

힙 정렬은 빠른 알고리즘을 가지고 있다. 힙 정렬은 이진트리구조를 사용한다. 이진트리 구조(자식 노드가 2개 이하인 트리 구조) 완전 이진 트리는 루트부터 자식노드가 왼쪽부터 오른쪽으로 차례대로 데이터가 들어가는 구조이다. 힙 생성 알고리즘은 특정 노드의 두 자식 중 더 큰 자식과 자신의 위치를 바꾸는 알고리즘이다. 위치를 바꾼 뒤에도 자식이 존재하는 경우 계속해서 반복한다. 이 힙 생성 알고리즘의 시간복잡도는 높이와 같기 때문에 O(log N) 이다. 1. 배열에 그대로 삽입한다. 2. 앞의 1/2개만 확인한다.(소수점은 버림) 위의 그림에서는 7, 6, 5, 8까지만 본다. 3. 밑에서부터 자식과 확인하며 정렬한다. 1) 8은 1, 6보다 크므로 그대로 2) 5는 9보다 작으므로 9와 자리 바꿈. 해..

pair와 vector 라이브러리 사용해서 정렬하는 방법이다. pair는 한 쌍의 데이터를 사용할 수 있는 라이브러리이다. 아무런 조건 없이 단순 정렬을 하는 경우 처음에 있는 항목 기준으로 정렬된다. (ex 하단 코드에서는 int 기준으로 정렬된다.) 문제 1. #include #include #include using namespace std; int main(void) { vector v; //v.push_back : 리스트 마지막에 삽입 v.push_back(pair(90, "박한울")); v.push_back(pair(85, "이태일")); v.push_back(pair(82, "나동빈")); v.push_back(pair(98, "강종구")); v.push_back(pair(79, "이상욱")..

정렬 라이브러리가 있기 때문에 정렬 문제에서 굳이 코드를 만들 필요 없이 정렬 라이브러리를 쓰면 된다. c++에서 다양한 stl 라이브러리를 제공하기 때문에 c++를 사용한다. #include #include using namespace std; //비교함수 bool compare(int a, int b) { return a b이면 내림차순 정렬이 됨. } int main(void) { int a[10] = {9, 3, 5, 4, 1, 10, 8, 6, 7, 2}; //정렬할 기준을 직접 설정. //두 번째에는 a+10처럼 변수의 개수를 더한 값을 작성 //세 번째에 직접 만든 함수를 집어넣으면, 해당 함수의 반환값에 맞게 정렬 동작 sort(a, a + 10, compare);..

- 지난번의 퀵 정렬은 편향되게 분할될 가능성이 있기 때문에 최악의 시간복잡도가 O(N*N)이다. 하지만 병합 정렬은 정확히 반씩 나누기 때문에 최악의 경우에도 O(N*logN) 시간복잡도를 보장한다. - 정확히 반으로 쪼갠 후 나중에 합친다. 피벗값은 없다. - 실행 순서 : 1) 처음엔 각각 전부 한 개씩 나눈다. 2) 2개씩 정렬을 하며 합친다. (합칠땐 2의 배수만큼 합친다.) 3) 또 정렬을 하며 이번엔 4개가 합쳐진다 4) ... - 계산 속도는 상단 그림상 너비는 N(8)이고 높이는 logN(로그 2의 8=3)이기 때문에 총 시간복잡도는 O(N*logN)가 된다. 퀵 정렬보다 빠르진 않지만 O(N*logN) 를 보장할 수 있기 때문에 좋다. - 인덱스는 총 3개를 사용한다. 1) i와 j를 ..