1. 병합 정렬 (Merge Sort)
- 개념: 배열을 더 이상 나눌 수 없을 때까지 반으로 쪼갠 뒤(Divide), 두 개의 정렬된 부분 배열을 비교하며 하나의 정렬된 배열로 합치는(Merge) 방식을 재귀적으로 반복하는 알고리즘.
- 핵심 원리 (분기 조건): 투 포인터(i, j)를 사용하여 두 부분 배열의 값을 비교.
- if (arr[i] <= arr[j]): 왼쪽 값이 작거나 같으면 임시 배열에 넣고 i++ (안정 정렬 유지).
- else: 오른쪽 값이 작으면 임시 배열에 넣고 j++.
- 한쪽 배열이 먼저 소진되면, 남은 배열의 원소들을 그대로 뒤에 이어 붙임.
- 시간 복잡도: 최선, 평균, 최악 모두 O(N \log N) (항상 반으로 나누고 N번 비교하므로 보장됨).
- 자주 쓰는 상황: 데이터의 상태와 무관하게 항상 일정한 정렬 속도가 필요할 때, 혹은 상대적인 순서가 유지되어야 하는 안정 정렬(Stable Sort)이 필요할 때.
2. 기수 정렬 (Radix Sort)
- 개념: 데이터를 비교하지 않고, 낮은 자릿수(일의 자리)부터 높은 자릿수까지 차례대로 각 자릿수를 기준으로 정렬을 반복하여 최종적으로 전체를 정렬하는 방식.
- 핵심 원리 (분기 조건): 값의 '비교' 대신 '빈도수 누적합'을 이용해 자리를 예약.
- 현재 자릿수를 기준으로 count 배열에 빈도수를 저장하고, 이를 누적합으로 변환하여 각 숫자가 들어갈 '마지막 인덱스'를 계산.
- 역순 탐색: 원본 배열을 뒤에서부터(i = N-1) 훑으며 자리를 찾아 들어감. 앞선 자릿수 정렬에서 만들어둔 상대적 순서(Stable)를 깨뜨리지 않기 위함.
- 시간 복잡도: O(kN) (k는 데이터의 최대 자릿수). 비교 연산이 없으므로 O(N \log N)보다 빠를 수 있음.
- 자주 쓰는 상황: 데이터 개수(N)가 매우 많지만, 데이터의 길이(자릿수)가 짧고 일정할 때. (예: 100만 개의 5자리 이하 숫자 정렬)
2751번: 수 정렬하기 2 (병합 정렬 구현)
1. 주요 오개념 및 시행착오 (Pain Point)
- 반복문(Bottom-Up)으로 병합 정렬을 구현하려다 보니, 데이터 개수가 2의 거듭제곱이 아닐 때 배열 범위를 초과하는 OutOfBounds 에러 제어에 실패함.
- 정렬 로직 내부에서 두 그룹을 비교하는 조건과, 한쪽 그룹이 소진된 후 남은 값을 처리하는 로직의 경곗값(i <= m 등) 설정이 가장 헷갈렸음. 이를 하나의 복잡한 while문 안에서 break와 if-else로만 욱여넣으려다 논리가 완전히 꼬임.
- 출력 시 100만 개의 데이터를 System.out.println으로 처리하여 시간 초과가 발생할 위험을 간과함.
2. 핵심 원리 및 수학적 근거 (Logic & Math)
- 분할과 병합의 독립성: 병합 정렬의 핵심은 merge_sort 재귀 함수로 배열을 더 이상 쪼갤 수 없을 때까지 두 갈래로 계속 분할한 뒤, 쪼개져서 이미 정렬된 상태의 두 배열을 merge 함수로 다시 합치는 것임.
- 정확한 중앙값 분할: mid = start + (end - start) / 2 공식을 사용하면 배열을 안전하게 반으로 나눌 수 있음.
- 명확한 경계 조건: 두 그룹을 병합할 때 while (i <= mid && j <= end)처럼 고정된 경곗값(mid, end)을 명확히 설정해야 반복문이 엇나가지 않음.
1번 2번으로 분할되고 1-2로 1번이 분할-병합되면 2번도 3-4으로 분할 병합 후 마지막으로 병합!
3. 설계 통찰
- 인덱스를 수동으로 쫓아가는 반복문 방식보다, 재귀 방식이 '분할 -> 병합'라는 병합 정렬의 본질적인 로직을 훨씬 직관적이고 안전하게 구현할 수 있음.
- 병합(merge) 과정은 ① 두 그룹 비교 후 삽입, ② 왼쪽 남은 그룹 털어넣기, ③ 오른쪽 남은 그룹 털어넣기라는 3개의 독립된 while문으로 분리해야 코드가 꼬이지 않음.
4. 구현상의 유의점 (Implementation Wisdom)
- 병합 결과를 담을 tmp 임시 배열은 재귀 호출마다 새로 생성하지 않고, 전역(static)으로 한 번만 할당하여 메모리 오버헤드를 막아야 함.
- 대량의 출력은 반드시 StringBuilder나 BufferedWriter를 사용해 한 번에 방출(flush)해야 함.
1517번: 버블 소트 (병합 정렬 응용)
1. 주요 오개념 및 시행착오 (Pain Point)
- 오른쪽 값이 왼쪽으로 넘어올 때 발생하는 교환 횟수를 j - i로 계산함. 다음에 코드를 다시 봤을 때 j와 i가 정확히 어떤 상태를 의미하는지 직관적으로 파악하기 어려웠음.
- 교환 횟수 count 변수를 int형으로 선언하여, 최대 500,000개의 역순 정렬 시 발생하는 1,250억 번의 연산을 담지 못해 오버플로우로 틀림.
2. 핵심 원리 및 수학적 근거 (Logic & Math)
- 교환 횟수 = 역전 쌍(Inversion Count): 오른쪽 그룹의 값(arr[j])이 선택된다는 것은, 해당 값이 현재 왼쪽 그룹에 남은 모든 원소들보다 작아서 앞으로 점프한다는 뜻임.
- j와 m의 본질적 차이: j는 탐색을 진행하며 배열의 끝(end)을 향해 계속 값이 변하는 이동 포인터임.
- m은 왼쪽 그룹의 끝을 나타내는 고정된 경곗값임.
- 따라서 점프하는 거리는 변동하는 j가 아니라, 고정된 m을 기준으로 한 m - i + 1(왼쪽 그룹에 남은 실제 원소 개수)로 계산해야 항상 정확함.
3. 설계 통찰
- 문제 이름이 "버블 소트"라고 해서 O(N^2)인 버블 정렬을 그대로 쓰면 안 됨. 교환이 일어나는 횟수를 병합 정렬의 '역전 쌍' 원리로 치환하여 O(N \log N)으로 해결하는 아이디어가 핵심임.
4. 구현상의 유의점 (Implementation Wisdom)
- 최악의 시나리오(역순 정렬)를 고려해 결과값이 21억을 초과할 수 있다면 무조건 long count를 사용해야 함.
- 교환 횟수 누적은 오른쪽 원소가 더 작아서 선택되는 단 한 번의 조건(else 분기)에서만 count += (m - i + 1)로 깔끔하게 처리함.
10989번: 수 정렬하기 3 (기수 정렬 직접 구현)
1. 주요 오개념 및 시행착오 (Pain Point)
- 처음엔 실제 Queue 10개를 만들거나, 인덱스와 값을 저장하는 Node 클래스를 만들려 했으나 데이터의 차원과 구조가 너무 복잡해져서 포기함.
- 자릿수를 추출할 때, 10의 자리일 때는 if문으로 나누고, 100의 자리일 때는 또 다른 if문을 쓰는 식의 비효율적인 하드코딩을 시도함.
- 임시 배열 output의 크기를 전체 개수 N이 아닌 10으로 착각했고, 누적합 배열인 count를 매 자릿수마다 새로 초기화해야 한다는 사실을 놓침.
2. 핵심 원리 및 수학적 근거 (Logic & Math)
- 수식 하나로 자릿수 추출: (arr[i] / exp) % 10 공식을 사용하면 복잡한 if문 분기 없이 exp가 1, 10, 100으로 커짐에 따라 해당 자릿수의 숫자만 정확히 떼어낼 수 있음.
- 빈도수와 누적합의 마법: 복잡한 객체나 큐 없이도, 각 숫자의 빈도수(Count)를 구하고 이를 누적합으로 변환하면 "이 그룹은 배열의 몇 번 인덱스까지 차지한다"는 방 예약 시스템이 완성됨.
3. 설계 통찰
- 큐(Queue) 없이 배열만으로 구현하는 계수 정렬(Counting Sort) 원리를 차용하는 것이 기수 정렬의 최적화 핵심임.
- 역순 탐색 (Stable Sort): 원본 배열을 반드시 뒤에서부터(i = N-1 -> 0) 훑으며 자리를 배치해야 함. 그래야 앞선 자릿수 정렬에서 기껏 맞춰둔 상대적인 위치(순서)가 파괴되지 않음.
4. 구현상의 유의점 (Implementation Wisdom)
- 매 자릿수(exp) 루프가 돌 때마다 count = new int[10]을 새로 생성하여 빈도수를 초기화해야 함.
- 자리를 찾아 들어갈 때 output[count[value] - 1]에서 -1을 하는 이유는, 누적합은 1부터 시작하는 개수이고 배열 인덱스는 0부터 시작하기 때문임.
- 정렬된 output 배열을 원본 arr로 덮어씌울 때는 for문 대신 네이티브 복사인 System.arraycopy()를 사용하여 속도를 극대화함.
