🥕 [ 백준 2750, 2751 ] 수 정렬하기 문제 링크 url : https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제 링크 url : https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc...
병합 정렬
[병합 정렬] 자료 구조를 분할하고 각각의 분할된 자료구조를 정렬한 후, 다시 병합하여 정렬한다. 병합 정렬은 정확히 반절씩 나눈다는 점에서 늘 항상 \( O(N*logN) \) 의 시간 복잡도를 가집니다. 퀵 정렬의 경우 피벗 값에 따라 편향되었을 때, 최악의 경우 \( O(N^2) \) 를 갖는다는 점에서 병합 정렬은 이보다 나은 장점을 갖는다. 하지만 그렇다고 해서 평균적으로 병합 정렬이 더 빠르다는건 아니다. 분할 단계 가로의 길이는 \(N\), 높이는 \( log_2N \) 이 됩니다. 처리하는 데이터의 갯수는 한번 쪼갤 때 마다, 2의 지수로 증가하기 때문에 N이 아니라 훨씬 적은 \( log_2N\) 만으로 처리 할 수 있게 된 것 입니다. 병합 단계 정렬하며 병합해갑니다. 이미 정렬이 되어..
