분류 전체보기35 병합 정렬 다음 수를 오름차순 정렬하시오 >7 6 5 8 3 5 9 1 병합 정렬 시간복잡도 병합 정렬도 분할 정복 알고리즘이기에 퀵 정렬과 같이 시간복잡도가 O(N*logN)이다. 정렬 구조 일단 나누고 나중에 합쳐서 정렬하는 방식이다. 퀵 정렬과 다르게 피벗 값이 없고 항상 반으로 나눈다는 특징을 가지고 있다. 이 특징이 단계의 크기를 logN이 되도록 만들어준다. (S) | 7 | 6 | 5 | 8 | 3 | 5 | 9 | 1 | (1) | 6 7 | 5 8 | 3 5 | 1 9| (2) | 5 6 7 8 | 1 3 5 9| (3) | 1 3 5 5 6 7 8 9 | 이런 방식이 N*logN을 만드는 원리가 무엇일까 먼저 너비는 숫자의 개수인 N(=8)이라고 할 수 있다. 하지마 세로는 3개이다 이때 log2.. 2024. 2. 18. 힙 정렬 힙 정렬은 힙 트리 구조를 이용하는 정렬 방법이다. 이진트리 먼저 이진트리란 모든 노드가 두개의 자식노드를 가지는 것을 말한다. 트리라는 말 처럼 가지가 뻗어있는 형태다. 완전 이진 트리란 루트 노드부터 시작해서 자식 노드가 왼쪽 자식 노드, 오른쪽 자식 노드로 차근차근 들어가는 구조의 이진트리이다. 힙 힙(Heap)이란 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리이다. > 최대 힙: '부모 노드'가 '자식 노드'보다 큰 힙을 말한다. 힙 정렬을 하기 위해서는 정해진 데이터가 힙 구조를 가지도록 만들어야 한다. 힙 정렬을 수행하기 위해서는 힙 생성 알고리즘을 사용한다. 이는 특정한 '하나의 노드'에 대해서 수행하는 것이다. 또한 해당 하나의 노드를 제외하고는 최대 힙이 .. 2024. 2. 18. 계수 정렬 다음의 5이하 자연수 데이터들을 오름차순 정렬하시오 > 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 이번이는 데이터가 30개이다. 다만 모든 데이터가 1부터 5 사이에 속한다는 특징이 있다. 이처럼 범위 조건이 있는 경우에 한해서 굉장히 빠른 알고리즘이 있다. 이 알고리즘의 속도는 무려 O(N)이다. 계수 정렬은 단순하게 크기를 기준으로 세는 알고리즘이다. 계수 정렬 데이터의 크기 별로 갯수를 세고 갯수만큼 각 데이터를 출력하면 정렬이 이루어진다. #include using namespace std; int main(){ int temp; int count[5]; int arr[30] = { 1, 3, 2, 4, 3, 2, 5, 3, 1, 2.. 2024. 2. 18. 이전 1 ··· 6 7 8 9 다음