[알고리즘] (Java) 1. 분할정복 - 병합정렬

몇일간 Python으로 단련된 코테실력을 Java로 바꿔가는데 집중하고 있었다.
Do it, 알고리즘 코딩테스트 Java편으로 한바퀴 돌리면서 개념과 구현에 익숙해지는 것을 목적으로 공부중에 있다.
이해를 제대로 하지 못하고 넘겼던 개념들을 차근차근 정리해볼계획이다.

1. 분할정복 - 병합정렬

병합정렬은 분할정복 방식을 사용해서 데이터를 분할하고 분할한 집합을 정렬해가며 합치는 알고리즘이다.
병합 정렬의 시간 복잡도 평균값은 O(nlogn)이다.
잘게 분할하고 합쳐가면서 정렬, 개념은 이해된다. 이걸 어떻게 구현하는 것인지 아래 코드를 보면서 이해해보자.

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

public class Main {
    public static int[] arr;
    public static long answer = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        sort(arr, 0, n - 1);

        bw.write(Long.toString(answer));
        bw.flush();
        br.close();
        bw.close();
    }

    // 분할 정복 : 재귀로 구현
    private static void sort(int[] arr, int left, int right) {
        // 길이가 1이면 빠져나오기
        if (left == right) {
            return;
        }

        int mid = (left + right) / 2;

        // 왼쪽 분할
        sort(arr, left, mid);
        // 오른쪽 분할
        sort(arr, mid + 1, right);
        // 정렬
        merge(arr, left, mid, right);
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int leftLength = mid - left + 1;
        int rightLength = right - mid;

        int[] leftTmp = new int[leftLength];
        int[] rightTmp = new int[rightLength];

        for (int i = 0; i < leftLength; i++) {
            leftTmp[i] = arr[left + i];
        }
        for (int i = 0; i < rightLength; i++) {
            rightTmp[i] = arr[mid + 1 + i];
        }

        int leftIdx = 0;
        int rightIdx = 0;
        int oriIdx = left;

        // 분할 이후 합병 정렬
        while (leftIdx < leftLength && rightIdx < rightLength) {
            if (leftTmp[leftIdx] <= rightTmp[rightIdx]) {
                arr[oriIdx] = leftTmp[leftIdx];
                if ((left + leftIdx) > oriIdx) {
                    answer += (left + leftIdx) - oriIdx;
                }
                leftIdx++;
            } else {
                arr[oriIdx] = rightTmp[rightIdx];
                if ((rightIdx + mid + 1) > oriIdx) {
                    answer += (rightIdx + mid + 1) - oriIdx;
                }
                rightIdx++;
            }
            oriIdx++;
        }

        // 왼쪽 배열 나머지 채우기
        while (leftIdx < leftLength) {
            arr[oriIdx] = leftTmp[leftIdx];
            leftIdx++;
            oriIdx++;
        }

        // 오른쪽 배열 나머지 채우기
        while (rightIdx < rightLength) {
            arr[oriIdx] = rightTmp[rightIdx];
            rightIdx++;
            oriIdx++;
        }
    }
}

분할

전체코드는 이렇다. 재귀호출로 분할을 하고, 재귀에서 빠져나오면서 정렬이 되는 방식으로 구현하였다.
재귀호출로 분할하고 빠져나오는 부분은 다음과 같다.

    private static void sort(int[] arr, int left, int right) {
        // 길이가 1이면 빠져나오기
        if (left == right) {
            return;
        }

        int mid = (left + right) / 2;

        // 왼쪽 분할
        sort(arr, left, mid);
        // 오른쪽 분할
        sort(arr, mid + 1, right);
        // 정렬
        merge(arr, left, mid, right);
    }

이해해보기

1st

sort라는 메서드를 재귀호출하는 과정을 생각해보면
1. 배열의 중간값을 계산
2. 왼쪽, 오른쪽으로 분할
3. 분할할 배열 길이가 1이 될때까지 왼쪽 분할
로 이어진다.

2nd

길이가 1이되고 나서 재귀에서 빠져나오면 오른쪽 분할 재귀로 넘어가는데,
이때 전달된 왼쪽, 오른쪽 인덱스 파라미터를 생각해보면 길이가 1짜리인 오른쪽 배열이 새롭게 정렬 대상이 된다.
그렇게 merge라는 메소드를 만나게 되면서 분할된 왼쪽과 오른쪽이 만나면서 병합 정렬이 일어난다.

병합 및 정렬

private static void merge(int[] arr, int left, int mid, int right) {
        int leftLength = mid - left + 1;
        int rightLength = right - mid;

        int[] leftTmp = new int[leftLength];
        int[] rightTmp = new int[rightLength];

        for (int i = 0; i < leftLength; i++) {
            leftTmp[i] = arr[left + i];
        }
        for (int i = 0; i < rightLength; i++) {
            rightTmp[i] = arr[mid + 1 + i];
        }

        int leftIdx = 0;
        int rightIdx = 0;
        int oriIdx = left;

        // 분할 이후 합병 정렬
        while (leftIdx < leftLength && rightIdx < rightLength) {
            if (leftTmp[leftIdx] <= rightTmp[rightIdx]) {
                arr[oriIdx] = leftTmp[leftIdx];
                if ((left + leftIdx) > oriIdx) {
                    answer += (left + leftIdx) - oriIdx;
                }
                leftIdx++;
            } else {
                arr[oriIdx] = rightTmp[rightIdx];
                if ((rightIdx + mid + 1) > oriIdx) {
                    answer += (rightIdx + mid + 1) - oriIdx;
                }
                rightIdx++;
            }
            oriIdx++;
        }

        // 왼쪽 배열 나머지 채우기
        while (leftIdx < leftLength) {
            arr[oriIdx] = leftTmp[leftIdx];
            leftIdx++;
            oriIdx++;
        }

        // 오른쪽 배열 나머지 채우기
        while (rightIdx < rightLength) {
            arr[oriIdx] = rightTmp[rightIdx];
            rightIdx++;
            oriIdx++;
        }
    }

1. 원본 배열에서 인덱스를 파라미터로 받아 왼쪽 배열과 오른쪽 배열을 임시적으로 만들고
2. 왼쪽, 오른쪽 배열 투포인터 방식으로 인덱스를 옮겨가며 원본배열에 값을 다시 채운다.
3. 한쪽이 배열의 끝까지 탐색이 끝났으면, 나머지 한쪽 배열을 그대로 이어붙인다.
   이 때, 양쪽 배열 모두 각각 정렬이 끝난 상태이니 나머지 요소를 그대로 이어붙여도 정렬 상태가 깨지지 않는다.

2. etc...

    private static boolean isPrime(int num) {
        if (num < 2) {
            return false;
        }
        for (int i = 2; i <= (int) Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

시간 복잡도를 생각한 소수 판별 메서드인데 for (int i = 2; i <= (int) Math.sqrt(num); i++) 이부분 암기해놓자. 종종 쓰인다.

3. 정리하며...

분할정복에 관한 아이디어는 코테 문제를 풀면서 떠오르긴하지만, 어떻게 구현을 했더라에서 막힌 경험이 여러번 있었다.
O(nlogn)이라는 시간복잡도로 최적화에 많은 도움을 줄 듯하다.