2. Getting Started

2.1. Insertion sort

우리가 배울 첫 알고리즘은 1장에서 설명한 삽입 정렬이다. 이 책에서는 알고리즘에만 집중하기 위해 유사코드를 사용하기로 한다.

입력 : 숫자 () n개의 순열 \{a_1, \cdots, a_n\}

출력 : a'_{1} \leq \cdots \leq a'_{n} 을 만족하는 입력 순열의 재배열.

삽입 정렬은 입력된 숫자를 제자리에서 정렬한다. 즉, 순열 밖에 저장된 숫자의 개수는 언제나 최대 상수 개수이다.

INSERTION-SORT(A)
for j = 2 to A.length
    key = A[j]
    // Insert A[j] into the sorted sequence A[1, ..., j - 1]
    i = j - 1
    while i > 0 and A[i] > key
        A[i + 1] = A[i]
        i = i - 1
    A[i + 1] = key

각각 for문에서 A[1, …, j -1]은 지금까지 정렬된 부분열이다. 이렇게 루프마다 보존되는 특성을 루프 불변성이라 한다. 이는 알고리즘의 정당성을 증명하는 데 중요하다. 어떤 특성이 루프 불변성이 되려면 3가지를 증명해야 한다.

초기성 : 첫 번째 루프 이전에 사실이어야 한다.

유지성 : 루프 이전에도 성립해야 하고, 루프가 돈 이후에도 성립해야 한다.

종료성 : 루프가 끝날 때, 루프 불변성을 이용해 알고리즘의 정당성을 보일 수 있어야 한다.

삽입 정렬에 이를 적용하면 다음과 같다.

초기성 : j = 2일 때 A[1]은 원소 하나밖에 없으므로 당연.

유지성 : for문 한 번마다 A[j – 1], …, A[j – 3]은 A[j]보다 더 작은 원소를 찾을 때까지 오른쪽으로 한 칸 밀려난다. 이 때문에 정렬성은 보존된다. A[j]보다 더 작은 원소를 찾으면 A[j]가 그 자리로 들어가기 때문에 A[j]가 들어간 곳 왼쪽 부분의 정렬성도 보존된다.

종료성 : 이 알고리즘은 j = n + 1일 때 종료되는데, 이 시점에는 A[1, …, j]가 정렬되어 있으므로 알고리즘의 정당성이 성립한다.

이 책에서는 유사코드에 다음 규칙을 적용하기로 한다.

  • 들여쓰기는 불록 구조를 나타낸다.
  • while, for, repeat-until, if-else문으로 반복문이나 제어 흐름을 나타낸다.
  • //는 주석이다.
  • 다중 대입 i = j = e는 i, j 모두가 e로 대입됨을 나타낸다.
  • 프로시져 내에서의 변수는 지역 변수이다.
  • A[i] 등의 표현으로 배열 원소를 나타낸다.
  • 복합 데이터는 특성으로 구성된 오브젝트로 생각한다.
  • 변수는 값으로 전달된다.
  • return 문은 함수를 종료해 반환한다.
  • and/or 연산자는 짧은 회로 연산이다.
  • error 키워드는 조건이 맞지 않을 때 발생하는 에러문이다.

2.2. Analyzing algorithms

알고리즘을 분석하는 것은 알고리즘이 필요로 하는 자원을 예측하는 것이다. 이 책 대부분에서는 동시성을 가정하지 않고, 하나의 무작위 접근 기계(RAM)을 사용함을 가정한다. 가상 메모리나 캐싱 등은 가정하지 않는다.

Analysis of insertion sort

알고리즘의 수행 시간은 입력에 비례한다. 입력 크기는 대부분 입력 내 항목의 개수를 말한다. 어떨 때는 입력을 표현하는 데 필요한 비트의 수를 나타내기도 한다.

입력의 수행 시간은 기초적 연산의 수행 회수나 스텝 회수를 말한다.

삽입 정렬에 대해 이를 분석하면 다음과 같다. t_j는 값 j에 대해 while문이 수행된 횟수이다.


for j = 2 to A.length                                             // c_1 * n
    key = A[j]                                                    // c_2 * (n - 1)
    // Insert A[j] into the sorted sequence A[1, ..., j - 1]
    i = j - 1                                                     // c_4 * (n - 1)
    while i > 0 and A[i] > key                                    // c_5 * (t_2 + ... + t_n)
        A[i + 1] = A[i]                                           // c_6 * ((t_2 - 1) + ... + (t_n - 1))
        i = i - 1                                                 // c_7 * ((t_2 - 1) + ... + (t_n - 1))
    A[i + 1] = key                                                // c_8 * (n - 1)

최적의 수행 시간은 배열이 정렬되었을 때로, 모든 j에 대해 t_j = 1이 된다. 이 경우에는 총 수행 시간 T(n)은 선형 함수가 된다.

최악의 수행 시간은 배열이 역순으로 정렬되었을 때로, 모든 j에 대해 t_j = j이 된다. 이 경우에는 총 수행 시간 T(n)은 이차 함수가 된다.

보통은 최악의 수행 시간에 집중하는 것이 좋다.

  • 임의의 입력에 대해 수행 시간의 상한을 알 수 있게 해 주고
  • 최악의 수행 시간을 발생시키는 입력은 자주 있으며
  • 평균 수행 시간은 보통 최악의 수행 시간과 비슷하기 때문이다.

일부 경우에는 랜덤화된 알고리즘을 통해 기대 수행 시간에 대한 확률적 분석을 통한 평균적 수행 시간에 집중할 것이다.

Order of growth

입력 크기에 따라 수행 시간의 증가 정도에 집중하게 될 것이다.

2.3. Designing algorithms

삽입 정렬에서는 증가적 접근 방식을 이용했다. 이 장에서는 분할 정복 접근 방식을 이용할 것이다.

2.3.1. The divide-and-conquer approach

많은 유용한 알고리즘은 재귀적이다. 문제를 풀기 위해서, 해당 알고리즘 자신을 한 번 또는 여러 번 호출해 연관된 부분 문제를 푼다. 이는 보통 분할 정복 접근 방식을 따른다. 이는 다음과 같다.

분할 : 본래 문제를 본래 문제와 똑같은 더 작은 부분 문제들로 분할한다.

정복 : 부분 문제들을 재귀적으로 푼다.

결합 : 부분 문제의 해법을 결합해 본래 문제의 해법으로 만든다.

병합 정렬 알고리즘은 이를 따른다.

분할 : n개 항목을 n / 2개의 부분 순열로 분할한다.

정복 : 병합 정렬을 통해 2개의 부분 순열을 재귀적으로 정렬한다.

결합 : 두 개의 정렬된 부분 순열을 병합해 하나의 정렬된 큰 순열을 만든다.

병합 정렬에서 가장 중요한 파트는 병합을 하는 마지막 부분일 것이다. 이는 worst O(n)이다. 이를 유사코드로 나타내면 다음과 같다. 코드를 간소화하기 위해 무한대의 값을 갖는 감시자 변수를 이용했다.

MERGE(A, p, q, r)
n_1 = q - p + 1
n_2 = r - q
L[1, .., n_1 + 1], R[1, ..., n_2 + 1] : new arrays
for i = 1 to n_1
    L[i] = A[p + i - 1]
for j = 1 to n_2
    R[j] = A[q + j]
L[n_1 + 1] = ∞
R[n_2 + 1] = ∞
i = 1
j = 1
for k = p to r
    if L[i] ≤ R[j]
        A[k] = L[i]
        i = i + 1
    else
        A[k] = R[j]
        j = j + 1

이로부터 다음의 루프 불변성을 얻는다.

아래 쪽의 for문 각각에 대해, A[p, …, k – 1]은 L[1, …, n_1 + 1]과 R[1, …, n_2 + 1]의 원소 중 가장 작은 k – p 개의 원소를 정렬된 상태로 저장한다. 또한, L[i]와 R[j]는 각각 A로 복사되지 않은 L, R의 원소들 중 가장 작은 값이다.

이를 증명하면 다음과 같다.

초기성 : k = p이므로 A[p, …, k – 1]은 빈 배열이다. i = 1, j = 1이고 L, R은 정렬되었으므로 L[i]와 R[j]는 A에 복사되지 않은 L, R의 원소들 중 가장 작은 값이다.

유지성 : L[i] ≤ R[j]인 경우엔 L[i]가 A로 복사되지 않은 배열의 원소 중 가장 작은 값이고 이 값이 복사되므로 A[p, …, k]는 k – p + 1개의 최소 원소를 정렬된 상태로 저장한다. L[i] > R[j]인 경우도 비슷하다.

종료성 : A [p, …, r]은 r + 1 – p 개의 최소 원소들을 정렬된 형태로 저장하고 있기 때문에 문제의 요구조건을 만족한다. L, R의 원소 중 A로 복사되지 않은 원소들은 감시자 원소들이다.

이제 전체 병합 정렬 알고리즘은 다음과 같다.

MERGE-SORT(A, p, r)
if p < r
    q = (p + r) / 2
    MERGE-SORT(A, p, q)
    MERGE-SORT(A, q + 1, r)
    MERGE(A, p, q, r)

2.3.2. Analyzing divide-and-conquer algorithm

알고리즘이 자신에 대한 재귀 호출을 수행할 때, 그 수행 시간은 재귀식으로 표현할 수 있다. 재귀 호출 알고리즘의 수행 시간은 다음과 같이 나타내어진다.

T(n) = Θ(1) if n ≤ c, aT(n / b) + D(n) + C(n) otherwise

여기서 c는 베이스 케이스 기준, a는 나누는 부분 문제의 개수, D(n)은 문제를 부분문제로 나누는 데 걸리는 시간, C(n)은 나눈 부분 문제의 해법을 본 문제로 병합하는 시간이다.

Analysis of merge sort

병합 정렬에 이를 적용하면 다음과 같다.

분할 : Θ(1)

정복 : 2T(n / 2)

병합 : Θ(n)

즉 수행 시간은 T(n) = Θ(1) if n = 1, 2T(n / 2) + Θ(n) for n > 1이 된다. 이를 풀면 T(n) = Θ(n log n) 이 된다. 이를 도식화하면 재귀 트리가 된다. 재귀 트리의 높이는 log n이다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중