blog.1028web.com 이동중

분할정복

           > 1. 주어진 문제의 입력을 나눌수 없을 때까지 두개이상 작은 문제로 순환적으로 분할

              2. 작은 문제들을 각각 해결

              3. 그해를 결합하여 원래 문제의 해를 구하는 방식

분할 > 정복  > 결합

이진탐색 : n개 -> n/2 + (n/2) 분할 -> (n/4) + n/4 + (n/4 + n/4) 분할한 것의 일부만 사용

합병정렬 : n개 -> n/2 + n/2 분할 -> n/4 + n/4 + n/4 + n/4

퀵정렬 :   n개 -> a + b 분할 ->c+d+e+f

선택문제: n개 ->  a + (b) 분할 ->(c)+d+(e+f) 분할한 것의 일부만 사용

퀵정렬

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

> 특정원소 : 피벗 pivot : 두 부분배열로 분할할떄 기준이 되는 특정원소, 보통 주어진 배열 첫번째 원소 지정

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

A[] = {30, 45, 20, 15, 40, 25, 35, 10}

30: 피벗.    분할 후 {25, 10, 20, 15, 30 , 45, 35, 45}

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

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

결합 : 부분배열에 대한 탐색 결과가 직접 반환되므로 결합이 불필요

-순환형태-

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);//오른쪽 부분배열에 대한 순환 호출
    }
}

-분할함수 Partition-

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]) //피벗과 right 교환

   }
    return Right;
}

몇번 비교?

Θ(n):  n번비교 : 데이터 갯수에 비교. 

성능

T(n) : 입력 크기 n에 대한 탐색 가정에서의 모든 비교횟수의 합. 

     = 맨 바깥 수준에서의 비교횟수 + 순환 호출에서의 비교횟수. 

-퀵 정렬 수행시간-

한번의 분할 Partition()

+ 두번의 Quick Sort()순환호출

T(n)=T(왼)+T(오) +Θ(n) (n>1)

T(1)=Θ(1) 

- 최악의 경우

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

> 극심한 불균형적 분할 = 피벗이 최소값 or최대값일 떄.

                               = 입력데이터 정렬되어 있고, 피벗이 배열 처음 원소로 지정할떄. 

T(n) =T(n-1) +T(0) + Θ(1)  (n>0) T(0)=0

T(n) = T(n-1)+Θ(n)

T(n)=T(n-1) +Θ(1)

T(n) = O(n^2) 

- 최선의 경우

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

T(n)=T(n/2) +T(n/2) + Θ(n)  (n>1)

T(1)=1

T(n) = 2T(n/2) +Θ(n)

T(n) = O(nlogn)

- 부분배열의 모든 분할 비율에 따른 수행 시간의 평균

T(1) =T(0)=0

T(n)=O(nlogn)

>피벗 선택의 임의성만 보장되면 평균적인 성능을 보일 가능성이 매우 높음.

> 배열에서 임의로 값을 선택해서 배열의 처음 원소와 서로 교환한 후 정렬 수행. 

   >> 가운데 임의의 데이터를 처음으로 놓고 실행 >> 최악의 경우 발생 안함.  

분할정복

           > 1. 주어진 문제의 입력을 나눌수 없을 때까지 두개이상 작은 문제로 순환적으로 분할

              2. 작은 문제들을 각각 해결

              3. 그해를 결합하여 원래 문제의 해를 구하는 방식

분할 > 정복  > 결합

이진탐색 : n개 -> n/2 + (n/2) 분할 -> (n/4) + n/4 + (n/4 + n/4) 분할한 것의 일부만 사용

합병정렬 : n개 -> n/2 + n/2 분할 -> n/4 + n/4 + n/4 + n/4

퀵정렬 :   n개 -> a + b 분할 ->c+d+e+f

선택문제: n개 ->  a + (b) 분할 ->(c)+d+(e+f) 분할한 것의 일부만 사용

이진탐색

> 정렬된 상태의 데이터에 대해 적용 

분할 : 가운데 원소를 기준으로 왼쪽과 오른쪽 부분배열로 분할, 탐색키와 가운데 원소가 같으면 해당 원소의 배열 인덳를 반환/종료

정복 : 탐색 키 X가 가운데 원소보다 작으면 왼쪽 부분배열 대상으로 이진 탐색을 순환 호출, 크면 오른쪽 부분배열을 대상으로 이진탐색 순환 호출

결합 : 부분배열에 대한 탐색 결과가 직접 반환되므로 결합이 불필요

-순환형태-

BinarySearch(A[] , Left, Right, x)

{

    if(Left > Right)return -1;//탐색 실패

   Mid = (Left+Right/2);

   if(x == A[Mid]) return Mid;

   else if(x < Mid)Binary Search(A, Left, Mid-1, x) //왼쪽 부분배열

   else BinarySearch(A, Mid+1, Right, x)//오른쪽 부분배열

}

-반복형태- >> 효율이 좋음

BinarySearch(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;

}

n/2^k =1

k = logn  ==> 데이터 8 개 면 3번 분할. 

> 최대 비교횟수 = 최대 분할 횟수 +1  ==>4번 분할. 

성능

T(n) : 입력 크기 n에 대한 탐색 가정에서의 모든 비교횟수의 합. 

     = 맨 바깥 수준에서의 비교횟수 + 순환 호출에서의 비교횟수. 

-점화식-

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

T(n) = logn

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

> 삽입/삭제 연산 시 데이터 정렬 상태 유지가 필요

    - 평균 n/2개의 데이터 이동이 발생 -> 삽입/삭제가 빈번한 응용에는 부적합. 

2019년이 5달 남은시점.. 경력 3년이 채워지는시점.. 

난 아직도. 알고리즘을 모르겠다.  5번정도 스터디를 시도하거 같은데.. 아직도 모르겠다. 

자료구조와 알고리즘은... 2019안에 확실히 알고 갔으면 하는 마음으로 시작한다. 

1. 분할정복알고리즘 - 이진탐색, 퀵정렬

2. 동적 프로그래밍

3. 욕심쟁이 알고리즘

4 . 정렬알고리즘

5. 탐색알고리즘

6. 근사알고리즘

7. 해 탐색 알고리즘.