[Do it] 알코테 자바 7일차

_05-5 병합 정렬 (Merge Sort)

병합 정렬은 분할 정복(Divide and Conquer) 방식을 사용하여 데이터를 분할하고, 분할된 집합을 정렬하며 합치는 알고리즘이다.

즉, 배열을 계속해서 반으로 나누어 더 이상 나눌 수 없는 단위까지 분할한 뒤, 작은 단위부터 차례대로 정렬하며 합치는 방식으로 전체 배열을 정렬한다.

---

1. 병합 정렬의 핵심: 두 그룹을 병합하는 과정

1. 분할된 왼쪽 그룹과 오른쪽 그룹에 포인터를 각각 하나씩 두고 비교한다.
2. 왼쪽 포인터 값과 오른쪽 포인터 값을 비교하여 작은 값을 결과 배열에 추가한다.
3. 값을 추가한 쪽의 포인터를 오른쪽으로 한 칸 이동시킨다.
4. 한쪽 그룹의 데이터가 모두 결과 배열에 들어가면, 남은 다른 쪽 그룹 데이터를 모두 추가한다.
5. 이 과정을 반복하여 점점 큰 배열 단위로 합치면 최종적으로 정렬된 배열이 완성된다.

이 과정을 통해 투 포인터를 이용한 효율적인 병합이 가능하며, 배열의 순서를 유지하면서 안정적인 정렬이 이루어진다.

---

2. 예시 (오름차순 정렬)

초기 배열

8 5 6 2 4

배열을 반으로 나누기

[8 5 6] [2 4]

왼쪽 배열 [8 5 6] 분할 및 정렬

[8] [5 6] → [5 6 8]

오른쪽 배열 [2 4] 분할 및 정렬

[2] [4] → [2 4]

두 그룹 병합

[5 6 8] + [2 4] → [2 4 5 6 8]

---

3. 병합 정렬 특징

• 분할 정복 방식으로 안정적인 정렬 가능
• 재귀적 구조로 구현이 간단
• 안정 정렬: 같은 값의 상대적 순서가 유지됨
• 대용량 데이터 정렬에 적합

---

4. 시간 복잡도

경우	시간 복잡도
최선	O(N log N)
평균	O(N log N)
최악	O(N log N)

---

5. 공간 복잡도

O(N)

추가적인 배열을 사용하여 병합 과정에서 데이터를 저장한다.

---

6. 한줄 정리

병합 정렬은 데이터를 계속 나눈 뒤, 투 포인터를 이용해 두 그룹을 효율적으로 병합하면서 정렬하는 분할 정복 기반 알고리즘이다.

 

__[020] 수 정렬하기 2

백준 온라인 져지 2751번 https://www.acmicpc.net/problem/2751

import java.io.*;

public class Main {
    static int[] a, t;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        a = new int[n]; t = new int[n];
        for(int i=0;i<n;i++) a[i]=Integer.parseInt(br.readLine());

        merge(0,n-1); // 정렬 수행

        StringBuilder sb = new StringBuilder();
        for(int v:a) sb.append(v).append('\n'); // 결과 출력
        System.out.print(sb);
    }

    static void merge(int s,int e){
        if(s>=e) return;
        int m=(s+e)/2;
        merge(s,m); merge(m+1,e); // 좌우 분할 정렬
        int i=s,j=m+1,k=s;
        while(i<=m && j<=e) t[k++] = a[i]<=a[j]?a[i++]:a[j++];
        while(i<=m) t[k++]=a[i++];
        while(j<=e) t[k++]=a[j++];
        for(i=s;i<=e;i++) a[i]=t[i]; // 병합
    }
}

__[021] 버블 정렬 프로그램 2

백준 온라인 져지 1517번 https://www.acmicpc.net/problem/1517

import java.io.*;
import java.util.*;

public class Main {
    static long swapCount = 0; // Swap 횟수 저장

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long[] arr = Arrays.stream(br.readLine().split(" "))
                           .mapToLong(Long::parseLong)
                           .toArray();

        mergeSort(arr, new long[N], 0, N - 1);
        System.out.println(swapCount);
    }

    // 병합 정렬 수행
    static void mergeSort(long[] arr, long[] tmp, int left, int right) {
        if(left >= right) return;
        int mid = (left + right) / 2;
        mergeSort(arr, tmp, left, mid);
        mergeSort(arr, tmp, mid + 1, right);
        merge(arr, tmp, left, mid, right);
    }

    // 병합하며 역전수 계산
    static void merge(long[] arr, long[] tmp, int left, int mid, int right) {
        int i = left, j = mid + 1, k = left;
        while(i <= mid && j <= right) {
            if(arr[i] <= arr[j]) tmp[k++] = arr[i++];
            else {
                tmp[k++] = arr[j++];
                swapCount += mid - i + 1; // 오른쪽 요소가 왼쪽 요소보다 작으면 swap 발생
            }
        }
        while(i <= mid) tmp[k++] = arr[i++];
        while(j <= right) tmp[k++] = arr[j++];
        for(int l = left; l <= right; l++) arr[l] = tmp[l];
    }
}

_05-6 기수 정렬 (Radix Sort)

기수 정렬은 값을 직접 비교하지 않고 자릿수 단위로 정렬하는 특이한 방식의 정렬 알고리즘이다.

숫자의 크기를 비교하는 대신, 정렬할 값의 특정 자릿수를 기준으로 데이터를 나누고 정렬하는 방식으로 동작한다.
보통 0부터 9까지 10개의 큐(Queue)를 사용하며, 각 큐는 해당 자릿수의 값을 대표한다.

---

1. 기수 정렬의 동작 원리

1. 정렬할 자릿수 선택
   • 가장 낮은 자리수부터 시작하여, 한 자리씩 높은 자리수로 이동하며 정렬한다.
2. 자릿수 기준 분류
   • 각 숫자를 선택한 자릿수의 값에 따라 0~9까지의 큐에 넣는다.
3. 큐 순서대로 재배치
   • 큐에 들어간 데이터를 0번 큐부터 9번 큐까지 순서대로 꺼내 배열에 다시 배치한다.
4. 다음 자릿수로 이동
   • 가장 높은 자리수까지 반복하면 전체 배열이 정렬된다.

---

2. 예시 (오름차순 정렬, 2자리 수 기준)

초기 배열

34 12 45 23 51

1. 1의 자리 기준 정렬

12 23 34 45 51

1. 10의 자리 기준 정렬

12 23 34 45 51

최종 정렬 결과

12 23 34 45 51

---

3. 기수 정렬 특징

• 비교를 사용하지 않는 정렬
• 안정 정렬: 동일한 값의 상대적 순서 유지
• 큐(Queue)를 이용한 단계적 정렬
• 숫자나 고정 길이 문자열 정렬에 적합
• 자리수의 수에 따라 수행 시간 결정

---

4. 시간 복잡도

경우	시간 복잡도
평균/최악/최선	O(d × (N + k))

• N: 데이터 수
• d: 자릿수
• k: 큐 개수 (보통 10)

---

5. 공간 복잡도

O(N + k)

• 추가적인 큐 공간이 필요하다.

---

6. 한줄 정리

기수 정렬은 값을 직접 비교하지 않고 자릿수 단위로 큐에 나누어 정렬하며, 낮은 자리수부터 높은 자리수까지 반복해 전체를 정렬하는 알고리즘이다.

__[022] 수 정렬하기 3

백준 온라인 져지 10989번 https://www.acmicpc.net/problem/10989

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        for(int i = 0; i < N; i++) arr[i] = Integer.parseInt(br.readLine());

        int max = 10000; // 문제 조건 상 최대값
        int exp = 1; // 1의 자리부터 시작

        int[] aux = new int[N];
        while(exp <= max) {
            int[] count = new int[10];
            for(int i = 0; i < N; i++) count[(arr[i]/exp)%10]++;
            for(int i = 1; i < 10; i++) count[i] += count[i-1];
            for(int i = N-1; i >= 0; i--) aux[--count[(arr[i]/exp)%10]] = arr[i];
            System.arraycopy(aux, 0, arr, 0, N);
            exp *= 10;
        }

        for(int v : arr) sb.append(v).append('\n');
        System.out.print(sb);
    }
}