2. 시작하기

많은 알고리즘에서는 루프를 사용하여 문제를 해결하곤 한다.

우리는 코드가 문제없이 작성 되었다면, 그 루프가 정상적으로 작동하여 문제를 해결할 것을 알고 있다.

그러나 이를 논리적으로 증명하기는 어려웠다.

이때 사용할 수 있는 것이 루프 불변성(Loop Invariant)이다.

루프 불변성은 루프를 사용한 알고리즘이 타당(correct)한지 증명하기 위해 사용된다.

루프 불변성임을 확인하기 위해서는 세 가지 특성이 만족되어야 한다.

초기조건 : 루프가 첫 번째 반복을 시작하기 전에 루프 불변성이 참이어야 한다.

유지조건 : 루프의 반복이 시작되기 전에 루프 불변성이 참이었다면, 다음 반복이 시작되기 전까지도 계속 참이어야 한다.

종료조건 : 루프가 종료될 때 그 불변식이 알고리즘의 타당성을 보이는데 도움이 될 유용한 특성을 가져야 한다.

2.1 삽입정렬

반복문을 사용하는 삽입정렬 코드를 보며 루프 불변성에 대해 알아보자.

초기조건 : 루프의 첫 반복이 시작하기 전, A[1 .. j - 1]은 바뀌지 않은 A[1]인 한 개의 원소로 구성되므로, 루프 불변성이 성립한다.

유지조건 : 루프가 반복하면서 A[j] 원소를 A[1 .. j - k] 부분 배열의 알맞은 자리에 끼워 넣어 정렬시킨다. A[1 .. j] 배열은 정렬되기 전과 그 이후에도 동일한 원소를 갖기 때문에 루프 불변성이 성립한다.

종료조건 : 루프는 j가 A.length (= n) 보다 커지면 종료된다. A[1 .. n - 1] 배열은 A 전체 배열이며, A[1 .. n - 1] 배열은 루프가 시작되기 전과 동일한 원소지만 정렬된 순서로 저장되었다. 그러므로 삽입정렬 알고리즘은 타당하다.

import java.util.Arrays;

public class InsertionSort {
    public static void insertionSortAsc(int[] testCase) {
        for (int j = 1; j < testCase.length; j++) {
            int key = testCase[j];
            int i = j - 1;

            while (i >= 0 && testCase[i] > key) {
                testCase[i + 1] = testCase[i];
                i--;
            }
            testCase[i + 1] = key;
        }
    }

    public static void insertionSortDesc(int[] testCase) {
        for (int j = 1; j < testCase.length; j++) {
            int key = testCase[j];
            int i = j - 1;

            while (i >= 0 && testCase[i] < key) {
                testCase[i + 1] = testCase[i];
                i--;
            }
            testCase[i + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] testCase = {5, 2, 4, 6, 1, 3};
        insertionSortAsc(testCase);
        System.out.println(Arrays.toString(testCase));
    }
}

2.2 알고리즘의 분석

알고리즘의 수행시간을 분석할 때에는 일반적으로 worst case를 기준으로 둔다.

그 이유는 해당 시간이 모든 입력에 대한 상한임을 보증할 수 있고, 의외로 최악의 경우가 종종 발생하기 때문이다.

2.3 알고리즘의 설계

알고리즘을 설계하는 방법에는 여러가지가 있다.

앞에서 알아본 삽입 정렬은 점진적인 방법으로 해를 구한다.

임의의 원소 A[j]를 정렬된 A[1 .. j-1]의 적절한 위치에 삽입하여, 정렬된 A[1 .. j] 배열을 만들기 때문이다.

이 외에 자주 사용되는 방법은 분할 정복이다.

말 그대로 문제를 유사하지만 크기가 작은 부분 문제로 분할하고, 이를 재귀를 통해 모두 푼 후에 해를 결합하여 원래 문제의 해를 구하는 방법이다.

조금 더 짜임새 있게 정리하자면, 세 단계로 구성할 수 있다.

분할 : 현재의 문제를 같은 문제를 다루는 다수의 부분 문제로 분할한다.

정복 : 부분 문제를 재귀적으로 풀어서 정복한다. 부분 문제의 크기가 충분히 작으면 직집적인 방법으로 푼다.

결합 : 부분 문제의 해를 결합하여 원래 문제의 해가 되도록 만든다.

분할정복의 대표적인 예시는 병합정렬이다.

아래의 코드를 통해 분할 / 정복 / 결합의 사례를 살펴보자.

public class MergeSort {
    public static void merge(int[] A, int p, int q, int r) {
        int n1 = q - p + 1, n2 = r - q;
        int[] L = new int[n1 + 1], R = new int[n2 + 1];

        for (int i = 0; i < n1; i++) L[i] = A[p + i];
        for (int i = 0; i < n2; i++) R[i] = A[q + i + 1];

        L[n1] = Integer.MAX_VALUE;
        R[n2] = Integer.MAX_VALUE;

        int i = 0, j = 0;
        for (int k = p; k <= r; k++) {
            if (L[i] <= R[j]) {
                A[k] = L[i++];
            } else {
                A[k] = R[j++];
            }
        }
    }

public static void mergeSort(int[] A, int p, int r) {
        if (p < r) {
            // 분할 : O(1) ; 부분 배열의 중간위치 계산은 상수시간이 걸린다.
            int q = (p + r) / 2;
            // 정복 : 2T(n/2) ; 입력이 n인 문제에 대한 수행시간이 T(n)이고, 각 부분 문제의 크기는 n/2이기 때문이다. 
            mergeSort(A, p, q);
            mergeSort(A, q + 1, r);
            // 결합 : O(n) ; n개의 원소만큼을 돌면서 결합하기 때문이다.
            merge(A, p, q, r);
        }
    }
    public static void main(String[] args) {
        int[] t = {5, 2, 4, 7, 1, 3, 2, 6};
        mergeSort(t, 0, t.length - 1);
    }
}

책에서는 편의를 위해 시작 인덱스를 1로 설정하여 가르치고 있다.

그러나 나는 불필요한 메모리 낭비를 위해 인덱스를 0으로 두어 구현하였다.

병합정렬 알고리즘의 수행시간을 살펴보자.

분할은 O(1), 정복은 2T(n/2), 결합에는 O(n)이기 때문에 T(n)에 대한 점화식을 다음과 같이 표현할 수 있다.

$T(n)= \begin{cases} \mathsf{\Theta}(1), & if\ \ n = 1 \\ 2T(n/2) + \mathsf{\Theta}(n), & if\ \ n > 1 \\ \end{cases}$

위 점화식은 마스터 정리를 통해 T(n)을 $\mathsf{\Theta}(n \ lg \ n)$ 으로 표현할 수 있다.

그러나 아직 마스터 정리를 배우지 않았더라도, 직관적인 방법으로 T(n)이 $\mathsf{\Theta}(n \ lg \ n)$ 임을 도출할 수 있다.

먼저, c라는 상수를 “크기가 1인 문제를 푸는 데 걸리는 시간”, “배열의 원소 개수 당 분할과 결합 단계에서 걸리는 시간” 을 동시에 나타낼 수 있다고 정의하자.

(물론 정확히 같다고 표현할 수는 없다. 그러나 둘 중 더 오래 걸리는 시간을 해당 점화식의 상한으로, 더 짧게 걸리는 시간을 해당 점화식의 하한으로 구하면, 두 한계 모두 $n\ lg\ n$ 의 차수로 나타난다.)

$T(n)= \begin{cases} c, & if\ \ n = 1 \\ 2T(n/2) + cn, & if\ \ n > 1 \\ \end{cases}$

그렇다면, T(n)은 다시 다음과 같이 나타낼 수 있다.

결과적으로 트리형태인 그림 c를 보자.

마지막 최하위 레벨에서는 노드가 n개 존재하고, 각각의 레벨에서 모든 노드의 합을 구하면 cn이 된다.

이러한 트리의 총 레벨 수는 $lg \ n + 1$ 이기 때문에, 레벨 당 비용 * 총 레벨 수를 곱해 총 비용 $cn (lg \ n + 1)$ 을 구할 수 있다.

여기서 낮은 차수항과 상수 c를 무시하면, $\mathsf{\Theta}(n\ lg\ n)$ 라는 결과가 나온다.

// 연습문제 2.3-1
// int[] A = {3, 41, 52, 26, 38, 57, 9, 49}
// mergeSort(A, 0, A.length - 1)
// 정답 :

Divide
{3, 41, 52, 26}
{3, 41}
{3} {41}

Conquer
{3} {41}
{3, 41}
A = {3, 41, 52, 26, 38, 57, 9, 49}

Divide
{52, 26}
{52} {26}

Conquer
{52} {26}
{26, 52}
A = {3, 41, 26, 52, 38, 57, 9, 49}

Conquer
{3, 41} {26, 52}
{3, 26, 41, 52}
A = {3, 26, 41, 52, 38, 57, 9, 49}

Divide
{38, 57, 9, 49}
{38, 57}
{38} {57}

Conquer
{38} {57}
{38, 57}
A = {3, 26, 41, 52, 38, 57, 9, 49}

Divide
{9, 49}
{9} {49}

Conquer
{9} {49}
{9, 49}
A = {3, 26, 41, 52, 38, 57, 9, 49}

Conquer
{38, 57} {9, 49}
{9, 38, 49, 57}
A = {3, 26, 41, 52, 9, 38, 49, 57}

Conquer
{3, 26, 41, 52} {9, 38, 49, 57}
{3, 9, 26, 38, 41, 49, 52, 57}
A = {3, 9, 26, 38, 41, 49, 52, 57}

// 연습문제 2.3-2
// 경계값을 사용하지 않도록 병합정렬을 재작성하라
// 정답 :
public class MergeSort {
    public static void merge(int[] A, int p, int q, int r) {
        int n1 = q - p + 1, n2 = r - q;
        int[] L = new int[n1], R = new int[n2];

        for (int i = 0; i < n1; i++) L[i] = A[p + i];
        for (int i = 0; i < n2; i++) R[i] = A[q + i + 1];

        int i = 0, j = 0;
        for (int k = p; k <= r; k++) {
            if (i >= n1) {
                A[k] = R[j++];
            }
            else if (j >= n2) {
                A[k] = L[i++];
            }
            else if (L[i] <= R[j]) {
                A[k] = L[i++];
            } else {
                A[k] = R[j];
            }
        }
    }

    public static void mergeSort(int[] A, int p, int r) {
        if (p < r) {
            int q = (p + r) / 2;
            mergeSort(A, p, q);
            mergeSort(A, q + 1, r);
            merge(A, p, q, r);
        }
    }
    public static void main(String[] args) {
        int[] t = {3, 26, 41, 52, 9, 38, 49, 57};
        mergeSort(t, 0, t.length - 1);
    }
}

'CS > 알고리즘' 카테고리의 다른 글

[Introduction to Algorithms] 4. 분할정복 (0)	2022.02.14
[Introduction to Algorithms] 3. 함수의 증가 (0)	2022.02.12
[Introduction to Algorithms] 1. 알고리즘의 역할 (0)	2022.02.02
유클리드 알고리즘 (Euclid’s algorithm) (0)	2021.11.03

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

CODE CPR

[Introduction to Algorithms] 2. 시작하기

2. 시작하기

2.1 삽입정렬

2.2 알고리즘의 분석

2.3 알고리즘의 설계

'CS > 알고리즘' 카테고리의 다른 글

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역

[Introduction to Algorithms] 2. 시작하기

2. 시작하기

2.1 삽입정렬

2.2 알고리즘의 분석

2.3 알고리즘의 설계

'CS > 알고리즘' 카테고리의 다른 글

'CS/알고리즘' Related Articles

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역