2018/05/22 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [알고리즘] 2강 알고리즘 소개

2018/03/19 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [알고리즘] 1강 알고리즘 소개

 

1. 분할정복 방법의 원리

  • 순환적으로 문제를 푸는 하향식 접근 방법
    주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 두 개 이상의 작은 문제로 순환적으로 분할하고, 이렇게 분할된 작은 문제들을 각각 해결한 후 그 해를 결합하여 원래 문제의 해를 구하는 방식
  • 특징
    분할된 작은 문제는 원래 문제와 동일 → 단, 입력 크기만 작아진다.
    분할된 문제는 서로 독립적 → 순환적 분할 및 결과 결합이 가능
  • 각 순환 호출 시의 처리 과정
    분할: 주어진 문제를 여러 개의 작은 문제로 분할
    정복: 작은 문제들을 순환적으로 분할. 만약 작은 문제가 더 이상 분할되지 않을 정도로 크기가 작다면 순환호출 없이 작은 문제에 대한 해를 구함
    결합: 작은 문제에 대해 정복된 해를 결합하여 원래 문제의 해를 구함.

1) 적용 알고리즘에서의 분할 과정

1-1) 이진탐색

중간 값을 기준으로 양쪽으로 분할한다. 한쪽은 사용 할 필요가 없다. 한쪽에서 분할 하고 분할하고 분할되지 않을때까지 분할한다.

n > n/2 , n/2 > n/4 , n/4 ...

1-2) 합병 정렬

정확히 절반크기의 두 개로 분할한다. 여기까지는 이진탐색과 동일하나 이진탐색은 한쪽은 사용하지않지만 합병정렬은 양쪽을 전부 사용한다.

n > n/2 , n/2 > n/4 , n/4 , n/4 , n/4 > ... 

1-3) 퀵 정렬

두개로 분할하는것은 맞으나 합병정렬은 정확히 두 개로 분할했다면 퀵정렬은 크기를 모름. 한쪽은 크고 한쪽은 작고 똑같을 수 도있고 크기가 다양한 일정하지않은 두 개로 분할하는 특징을 가진다.

n (=a+b) > a , b > ...

1-4) 선택 문제

 

 

2. 이진 탐색

  • 정렬된 상태의 데이터 대해 적용 가능한 효과적인 탐색 방법
    오름차순으로 정렬되었다고 가정

탐색방법

  • 배열의 가운데 원소와 탐색키 x(내가 찾고싶은 데이터) 를 비교
    1) 탐색키 = 가운데 원소 => 탐색 성공
    2) 탐색키 < 가운데 원소 => '이진탐색(크기 ½의 왼쪽 부분배열)' 순환 호출
    3) 탐색키 > 가운데 원소 => '이진탐색(크기 ½의 오른쪽 부분배열)' 순환 호출
  • 탐색을 반복할 때마다 대상 원소의 개수가 ½씩 감소

이진탐색의 분할 정복 결합 적용

  • 분할 : 배열의 가운데 원소를 기준으로 왼쪽과 오른쪽 부분배열로 분할. 탐색키와 가운데 원소가 같으면, 해당 원소의 배열 인덱스를 반환/종료
  • 정복 : 탐색키 x가 가운데 원소보다 작으면 왼쪽 부분배열을 대상으로 이진탐색을 순환 호출, 크면 오른쪽 부분배열을 대상으로 이진 탐색을 순환 호출
  • 결합 : 부분배열에 대한 탐색 결과가 직접 반환되므로 결합이 불필요

알고리즘_(순환형태)

1
2
3
4
5
6
7
8
BinarySearch(A[], Left, Right, x)
{
    if(Left > Right) return -1// 탐색실패
    Mid = (Left + Right)/2;
    if(x==A[Mid]) return Mid;
    else if (x<Mid) BinarySearch(A, Left, Mid-1, x); // 왼쪽 부분배열
    else BinarySearch(A, Mid+1, Right, x); // 오른쪽 부분배열
}
cs

     알고리즘 (반복형태)

1
2
3
4
5
6
7
8
9
10
11
BinarySearch_Iteration(A[], n, x)
{
    Left = 0; Right = n-1;
    While(Left <= Right){
        Mid == (Left+Right) / 2;
        if(x==A[Mid]) return Mid;
        else if (x<Mid) Right = Mid - 1// 왼쪽 부분배열
        else Left = Mid + 1;    // 오른쪽 부분배열
    }
    return -1// 
}
cs

 

이진 탐색에서의 분할과 비교

  • 입력 크기 n 일 때 최대 분할 횟수는?

n/2의k제곱 = 1 이 될때 까지 → k = log n

  • 최대 비교 횟수는? "최대 분할 횟수 + 1"

    예시) 입력 데이터 크기 n = 8 일 경우 최대 분할 횟수 k = 3이다 8/2의3제곱 = 1 이므로...
         최대 비교 횟수는 최대 분할 횟수 k 에 1을 더한 값이므로 3 + 1 = 4 이다.


성능 분석

T(n) = 입력 크기 n에 대한 탐색 과정에서의 모든 비교 횟수의 합
     = 맨 바깥 수준에서의 비교 횟수 + 순환 호출에서의 비교 횟수

T(n) = T(n/2) + O(1) (n>1), T(1) = 1

T(n) = logN

이진탐색 특징

  • 입력이 정렬된 리스트에 대해서만 적용 가능

  • 삽입 / 삭제 연산 시 데이터의 정렬 상태 유지가 필요
    평균 n/2개의 데이터 이동이 발생 > 삽입/삭제가 빈번한 응용에는 부적합하다.

 

3. 퀵 정렬

특정 원소를 기준으로 주어진 배열을 두 부분배열로 분할하고, 각 부분배열에 대해서 퀵 정렬을 순환적으로 적용하는 방식
- 오름차순으로 정렬한다고 가정한다.

피벗 pivot
두 부분배열로 분할할 때 기준이 되는 특정 원소 (보통 주어진 배열의 첫 번째 원소로 지정)

(피벗을 기준으로 왼쪽과 오른쪽으로 나누고 각각의 부분배열에 대해서 퀵정렬을 순환적으로 한다.)

 

1) 피벗이 제자리를 잡도록 하여 정렬하는 방식

분할 전 데이터 : 30, 45, 20, 15, 40, 25, 35, 10

1. (첫 데이터인 30을 피벗으로 정한다.)

분할 후 : { 25, 10, 20, 15 } 30 { 40, 35, 45 }
             왼쪽 부분배열       오른쪽 부분배열

피벗을 기준으로 보았을 때 왼쪽부분배열의 모든값은 피벗보다 작은 값들이다.
오른쪽 부분배열의 모든 값은 피벗보다 다 크다.

 

  • 분할: 피벗을 기준으로 주어진 배열을 두 부분배열로 분할

  • 정복: 두 부분배열에 대해서 퀵 정렬을 순환적으로 적용하여 각 부분배열을 정렬

  • 결합: 필요없음

 

2) 알고리즘

1
2
3
4
5
6
7
8
QuickSort(A[], n)
{
    if(n>1){
        pivot = Partition(A[0..n-1], n);    // 두 부분배열로 분할
        QuickSort(A[0..pivot-1], pivot);     // 왼쪽 부분배열에 대한 순환 호출
        QuickSort(A[pivot+1..n-1], n-pivot-1);    //오른쪽 부분배열에 대한 순환 호출
    }
}
cs

 

알고리즘 분할함수 Partition()

1
2
3
4
5
6
7
8
9
10
11
12
13
int Partition(A[], n)
{
    Left = 1; Right = n-1;
    while(Left < Right){                // 피벗 A[0]
        // 피벗보다 큰 값의 위치를 찾음
        while(Left < n && A[Left] < A[0]) Left++;
        // 피벗보다 작은 값의 위치를 찾음
        while(Right > 0 && A[Right] >= A[0]) Right--;
        if(Left < Right) 교환(A[Left] ↔ A[Right])
        else 교환(A[0] ↔ A[Right])
    }
    return Right;
}
cs

 

3) 분할과정

 

퀵 정렬의 적용 예

85보다도 88 피벗이 더 큰값이므로 맨오른쪽에 무한대의 값이 있다고 가정한다.

 

4) 성능분석

4-1) 분할함수 Partition() 수행 시간

피벗을 제외한 모든 원소는 1번~ 최대 2번 비교한다.
n ~ 2n
선형시간 Θn 을 갖는다.

4-2) 퀵 정렬 Quicksort() 수행 시간

한 번의 분할 Partition() + 두 번의 Quicksort() 순환 호출
T(n) = T(배열) + T(배열) + Θ(n) (n > 1)
T(1) = Θ(1)

 

4-3) 최악의 경우

피벗만 제자리를 잡고, 나머지 모든 원소가 하나의 부분배열로 분할되는 경우

극심한 불균형적 분할
- 피벗만 제자리를 잡고, 나머지 모든 원소가 하나의 부분배열로 분할되는 경우
- 피벗이 항상 부분배열의 최솟값 또는 최댓값이 되는 경우
- 입력 데이터가 정렬된 경우 AND 피벗을 배열의 처음 원소로 지정한 경우

T(n) = (Tn-1) + T(0) + Θ(n) (n>0), T(0)=0
                        ▼▼▼
                T(n) = T(n-1) + Θ(n)
                        ▼▼▼
                   T(n) = O(n2제곱)

 

4-4) 최선의 경우

피벗을 중심으로 항상 동일한 크기의 두 부분배열로 분할되는 경우

가장 균형적인 분할
- 피벗을 중심으로 항상 동일한 크기의 두 부분배열로 분할되는 경우
- 피벗이 항상 부분배열의 중간값이 되는 경우

T(n) = T(n/2) + T(n/2) + Θ(n) (n>1)
T(1) = 1
                        ▼▼▼
            T(n) = 2T(n/2) + Θ(n)
                        ▼▼▼
                    T(n) = O(nlogn)

 

4-5) 평균적인 경우

부분배열의 모든 분할 비율에 따른 수행시간의 평균
- 피벗은 동일한 확률로서 분할 후 배열의 어느 곳에나 위치 가능
- 0:n-1, 1:n-2, 2:n-3, ... , n-2:1, n-1:0

T(1) = T(0) = 0
T(n) = 1/n n∑i=1 (T(I-1) + T(n-I)) + Θ(n),  n ≥ 2
                        ▼▼▼
                     T(n) = O(nlogn)

퀵 정렬의 특징

  • 최선/평균의 경우 → O(nlogn)
  • 최악의 경우 → O(n2제곱)
    최악을 피하고 싶다면... 피벗 선택의 임의성만 보장되면 평균적인 성능을 보일 가능성이 매우 높음
    배열에서 임의로 값을 선택해서 배열의 처음 원소와 서로 교환한 후 정렬 수행