병합정렬

📍 데이터의 범위가 작고 정수형 데이터인 경우 - 카운팅 정렬 → 시간 복잡도 : O(n) 📍 데이터의 범위가 크거나 데이터 유형이 다양한 경우 (실수형 데이터, 문자열 데이터 등) - 퀵 정렬, 병합 정렬, 힙 정렬 → 시간 복잡도 : O(n log n) (버블 / 삽입 / 퀵 / 머지 / 카운팅)

🔺 문제 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 🔺 코드 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 52 53 54 55 56 57 58 59 60 61 62 63 64 import java.util.*; import java.io.*; public class Mai..

🔺 문제 24060번: 알고리즘 수업 - 병합 정렬 1 첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다. 다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109) www.acmicpc.net 🔺 코드 import java.util.*; import java.io.*; public class Main { int[] A; static int[] tmp; static int k; static int cnt = 0; static int result = -1; // 오름차순 정렬 public static void merge_sort(int A[], int p, int r) { if(cnt > k) ret..

🔺 문제 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 🔺 코드 - 풀이1) Collections.sort() 사용 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(n..