728x90

분할정복

           > 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) 

- 최악의 경우

오름차순 내림차순

10 20 30 40 50  //pivot 10

10 20 30 40 50  

10 20 30 40 50  

10 20 30 40 50  

10 20 30 40 50  

10 20 30 40 50 

50 40 30 20 10 //pivot 50

10 40 30 20 50

10 40 30 20 50

10 20 30 40 50

10 20 30 40 50

10 20 30 40 50    //n번


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

> 극심한 불균형적 분할 = 피벗이 최소값 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)

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

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

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

 

 

 

 

 

 

 

'Made by Miseong > 2019 알고리즘' 카테고리의 다른 글

2. 분할정복 - 퀵정렬  (0) 2019.08.04
1. 분할정복 - 이진탐색  (0) 2019.08.04
2019알고리즘  (0) 2019.08.04
728x90

분할정복

           > 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개의 데이터 이동이 발생 -> 삽입/삭제가 빈번한 응용에는 부적합. 

 

 

 

 

 

 

'Made by Miseong > 2019 알고리즘' 카테고리의 다른 글

2. 분할정복 - 퀵정렬  (0) 2019.08.04
1. 분할정복 - 이진탐색  (0) 2019.08.04
2019알고리즘  (0) 2019.08.04
728x90

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

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

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

 

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

2. 동적 프로그래밍

3. 욕심쟁이 알고리즘

4 . 정렬알고리즘

5. 탐색알고리즘

6. 근사알고리즘

7. 해 탐색 알고리즘. 

 

 

'Made by Miseong > 2019 알고리즘' 카테고리의 다른 글

2. 분할정복 - 퀵정렬  (0) 2019.08.04
1. 분할정복 - 이진탐색  (0) 2019.08.04
2019알고리즘  (0) 2019.08.04

+ Recent posts