study introalgo divide and conquer insertion sort

2. 시작하기(3)

2.3 분할정복

삽입 정렬 : 점진적인 방법 사용

원소 A[j]를 정렬된 부분 배열 A[1 .. j-1]의 적절한 위치에 삽입

2.3.1 분할정복 접근법

재귀적 구조 : 주어진 문제를 풀기 위해 자기 자신을 재귀적으로 여러 번 호출함으로써 밀접하게 연관된 부분 문제를 다룸. => 분할정복 접근법 분할정복 접근법 : 전체 문제를 원래 문제와 유사하지만 크기가 작은 몇 개의 부분 문제로 분할하고, 부분 문제를 재귀적으로 품. 찾은 해를 결합하여 원래 문제의 해를 만들어 낸다.

분할정복의 3단계

  1. 분할 : 현재의 문제를 같은 문제를 다루는 다수의 부분 문제로 분할
  2. 정복 : 부분 문제를 재귀적으로 풀어서 정복. 부분 문제가 충분히 작은 크기면 직접적인 방법으로 푼다.
  3. 결합 : 부분 문제의 해를 결합하여 원래 문제의 해가 되도록 만듬.

ex) 병합 정렬

  1. 분할 : 정렬한 n개 원소의 배열을 n/2개씩 부분 수열 두 개로 분할한다.
  2. 정복 : 병합 정렬을 이용해 두 부분 배열을 재귀적으로 정렬한다.
  3. 결합 : 정렬된 두 개의 부분 배열을 병합해 정렬된 배열 하나로 만듬.

정렬할 수열의 크기가 1이 되면 재귀호출이 “바닥에 이르게” 됨. 병합 정렬 알고리즘에서 핵심 작업은 “결합”단계에서 정렬된 두 부분 수열을 병합하는 것 병합을 위해 보조 procedure Merge(A,p,q,r)가 필요

A : 배열

p,q,r : 인덱스, (p<=q<r)

Merge는 두 부분배열 A[p..q]와 A[q-1..r]이 정렬되어 있다고 가정하고 이를 병합해서 정렬된 배열 하나를 만드는데, 이것이 원래 부분 배열 A[p..r]을 대체.

수행시간 : O(n)

n = r-p+1(병합할 원소들의 개수)실행 과정

  1. 탁자 위에 두 더미의 카드가 앞면이 위로 향하게 쌓여 있음.
  2. 각 카드 더미는 정렬되어 가장 작은 카드가 위에 놓여 있음.

(두 카드 더미를 병합해 카드의 앞면을 아래로 하는 정렬된 새로운 카드더미 생성이 목적)

  1. 주어진 두 카드 더미에서 각각 맨 위에 놓인 카드 비교
  2. 더 작은것 골라 내기(새 카드가 맨 위에 나타남)
  3. 골라낸 카드를 앞면이 아래로 되게 하여 결과 카드 더미에 추가
  4. 3~5를 두 카드 더미 중 하나가 빌 때까지 반복
  5. 남은 카드 더미를 앞면이 아래로 되게 하여 출력 카드 더미에 통째로 합침.

기본 단계마다 카드 더미가 비었는지 조사하는 것은 비효율적 각 카드 더미 바닥에 경계 카드 삽입 무한대를 경계 카드의 값으로 이용 : 경계 카드가 나오면 이외 모든 카드 출력되었다는 의미

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Merge(A,p,q,r)
1  n1 = q - p + 1
2  n2 = r - q
3  배열 L[1..n1 + 1]과 R[1..n2+1]을 생성한다.
4  for i = 1 to n1
5    L[i] = A[p + i - 1]
6  for j = 1 to n2
7    R[j] = A[q+j]
8  L[n1+ 1] = infinite
9  R[n2+1] = infinite
10 i = 1
11 j = 1
12 for k = p to r
13   if L[i] <= R[j]
14     A[k] = L[i]
15      i=i+1
16   else A[k] = R[j]
17      j = j + 11행 : 부분 배열 A[p..q]의 크기 n1을 계산

2행 : 부분 배열 A[q+1..r]의 크기 n2 계산

3행 : 크기가 각각n1 + 1과 n2+1인 배열 L과 R 생성

4~5행 : 부분 배열 A[p..q]를 L[1..n1]로 복사

6~7행 : 부분 배열 A[q + 1 .. r]을 R[1..n2]로 복사한다.

8~9행 : 배열 L과 R의 끝에 경계 카드를 삽입한다.

10~17행 : 루프 불변성을 유지하면서 기본 작업을 r-p+1번 수행12~17행의 for 루프에서 각 반복이 시작될 때, 부분 배열 A[p..k-1]은 L[1..n1+1]과 R[1..n2+1]의 원소 중 가장 작은 값을 가진 k-p 개 원소를 정렬된 순서로 가진다. 또한 L[i]와 R[j]는 각 배열에서 A로 복사되지 않은 원소 중 가장 작은 값이 된다.

이런 루프 불변성을 12-17행의 for 루프가 처음 반복하기 전에 만족하는지, 루프의 매 반복 시 불변식이 유지되는지, 루프가 종료될 때 타당성을 설명할 유용한 어떤 특성이 있는지 증명해야 함

  • 초기조건 : 루프의 첫 번째 반복이 시작되기 직전에는 k = p이므로 부분 배열 A[p..k-1]은 비어 있다. 이 빈 배열은 L과 R에서 갖아 작은 k - p = 0개의 원소를 가지고 있고, i = j = 1이므로 L[i]와 R[j]는 각각 A로 복사되지 않은 원소 중 가장 작은 원소를 가지고 있다.
  • 유지조건 : 각 반복 시 루프 불변성이 유지됨을 보이기 위해 먼저 L[i] <= R[j]의 경우 확인. L[i]는 아직 A로 복사되지 않은 가장 작은 원소. A[p..k-1]은 k-p개의 가장 작은 원소를 가지고 있음. 따라서 14행에서 L[i]를 A[k]로 복사하면 부분 배열 A[p..k]는 k-p+1개의 가장 작은 원소를 정렬된 순서로 저장. k(for 루프의 갱신에서)와 i(15행에서)를 증가시키는 것은 다음 반복에서의 루프 불변성 확립. L[i] > R[j]라면 비슷하게 16~17행에서 루프 불변성을 유지하기 위한 적절한 작업.
  • 종료조건 : 종료될 때 k = r + 1이다. 루프 불변성에 의해 부분 배열 A[p..k-1], 즉 A[p..r]은 L[1..n1 + 1]과 R[1..n2 +1]에서 가장 작은 k-p = r-p+1개의 원소를 정렬된 순서로 저장. 배열 L과 R은 모두 합쳐 n1 + n2 + 2 = r-p+3개의 원소를 가짐. 가장 큰 두 개의 원소(경계 카드)를 제외하고 모두 A로 복사.

MERGE 프로시저 는 = r-p+1 일때 O(n)시간에 수행 : 1~3행과 8~11행에서 상수 시간, 4~7행의 for 루프에서 O(n1+n2) = O(n)시간, 12~17행의 for 루프에서 n번 반복 발생하고 각 루프에 상수 시간 이다.

정렬 알고리즘의 서브 루틴으로 MERGE 프로시저 이용

MERGE-SORT(A,p,r) : 부분 배열 A[p..r]을 정렬하는 프로시저.

if p>=r : 부분 배열이 많아야 한개의 원소 => 이미 정렬

else : 분할 단계에서 A[p..r]을 원소가 [n/2]개인 A[p..q]와 [n/2]개인 A[q+1..r]로 분할하기 위해 인덱스 q를 계산

1
2
3
4
5
6

MERGE-SORT(A,p,r)
1 if p<r
2 q = [(p+r)/2]
3 MERGE-SORT(A,p,q,)
4 MERGE-SORT(A,q+1,r)
5 MERGE(A,p,q,r)

전체 수열 A = <A[1], A[2], … , A[n]>을 정렬하려면 MERGE-SORT(A,1,A.length)를 호출. A.length = n

2.3.2 분할정복 알고리즘의 분석

알고리즘이 자기 자신을 호출하는 재귀 호출을 할 경우 수행시간 : 재귀 방정식 or 점화식으로 설명.

입력의 크기가 n인 문제에 대한 전체 수행시간을 더 작은 크기의 입력에 대한 수행시간으로 나타내는 것.

분할정복 알고리즘의 수행시간에 관한 점화식. T(n) = 입력 크기가 n인 문제에 대한 수행시간

  • 문제의 크기가 충분히 작아 상수 c에 대해 n<=c 이면 O(1)
  • 주어진 문제가 원래 문제의 1/b인 a개의 부분 문제로 분할 => 크기가 n/b인 부분 문제에 T(n/b) 시간이 걸렸다면 a개 문제 해결에는 aT(n/b) 걸림.
  • 문제 분할 시간 D(n)이고 부분 문제들의 해를 결합하여 원래 문제의 해 만드는데 C(n) 걸린다면 점화식은 다음과 같음

if n <= c,

\[T(n) = O(1)\]

otherwise,

\[T(n) = aT(n/b) + D(n) + C(n)\]

병합 정렬의 분석

n개의 수를 정렬하는 병합 정렬에서 최악의 경우 수행시간 T(n)에 관한 점화식에 대한 추론.

n = 1, 상수 시간 걸림

n>1 일때,

  • 분할 : 분할 단계는 부분 배열의 중간 위치를 계산. 그러므로 상수시간. D(n) = O(1)
  • 정복 : 두 개의 부분 문제를 재귀적으로 푼다. 각 크기는 n/2이므로 2T(n/2)
  • 결합 : n개 원소에 대해 MERGE 프로시저는 O(n)시간. C(n) = O(n)

따라서 점화식은 다음과 같다.

if n=1,

\[T(n) = O(1)\]

if n >1,

\[T(n) = 2T(n/2) + O(n)\]

4장의 “마스터 정리” 이용 : T(n)은 O(n lg n), lg n 은 log(2)n -> 밑이 2인 로그

로그함수는 선형 함수보다 훨씬 천천히 증가 => 충분히 큰 입력에 대해 병합 정렬이 O(n^2)인 삽입 정렬보다 성능좋음.

CATALOG
    algorithm