분할정복(Divide and Conquer)

분할정복

 

-주어진 문제를 둘 이상의 부분 문제로 나누어서 푸는 방법

-비슷한 크기로 문제를 나눔

-재귀호출 사용

 

 

 

분할정복 과정

1. Divide :부분 문제로 나눌 수 있는 경우 2개 이상의 문제로 나눈다.
2. Conquer : 더 이상 나눌 수 없는 경우 현재 문제를 정복한다.
3. Combine : 해결된 문제들을 병합하여 기존 문제를 해결한다.

 

 

분할 횟수

입력의 크기가 n이고 총 분할한 횟수가 k라면.

-1번 분할 후 입력 크기 : n/2

-2번 분할 후 입력 크기 : n/2^2

...

-k번 분할 후 입력 크기 : n/2^k

--> n/2^k 가 1 이라면 더 이상 분할 불가

 

분할 횟수

 

 

분할정복의 사용

1. 합병정렬(Merge Sort)

입력이 2개의 부분문제로 크기가 반씩 줄어드는 분할 정복 알고리즘

-n개의 숫자들을 n/2개씩 2개의 부분문제로 분할

-2개의 정렬된 부분을 합병하여 정렬(정복)

 

시간복잡도 : O(nlogn) 

 각 층(분할)에서 비교 계산 횟수 = O(n)

 층 수=분할 횟수=log2n

 시간복잡도=> log2n*O(n)=O(nlogn)

 

알고리즘 구현(python)

import random
size=15
num=[]
result=[0]*size
#랜덤으로 숫자 리스트를 만드는 함수
def makeList(num):
    for i in range(size):
      num.append(int(random.random()*100+1))
      #1부터 100까지의 수 중 하나

def merge(num,result,left,mid,right):
    i=left;j=mid+1;k=left
    #합병
    while(i<=mid and j<=right):
        if(num[i]<=num[j]):
            result[k]=num[i]
            k+=1
            i+=1
        else:
            result[k]=num[j]
            k+=1
            j+=1
    if(i>mid):
        for a in range(j,right+1):
            result[k]=num[a]
            k+=1
    else:
        for a in range(i,mid+1):
            result[k]=num[a]
            k+=1
    for a in range(left,right+1):
        num[a]=result[a]
    print(num,result)
    ##합병 후 다시 대입


def mergeSort(num,result,left,right):
    if(left<right):
        mid=(left+right)//2
        mergeSort(num,result,left,mid)
        mergeSort(num,result,mid+1,right)
        merge(num,result,left,mid,right)

makeList(num)
print(*num)
mergeSort(num,result,0,size-1)
print(*result)

 

 

2. 퀵정렬

사실 정복 후 분할하는 알고리즘으로 각 부분 문제의 크기가 일정하지 않은 형태의 분할정복 알고리즘

-pivot을 설정하여 pivot보다 작은 원소는 왼쪽으로 큰 원소는 오른쪽으로 분할하고 중간에 pivot을 놓는다.

-분할된 부분 문제들에 대해서도 새로운 pivot을 설정하여 위와 동일한 과정을 수행한다.

 

시간복잡도

pivot으로 어느 것을 선택하는지에 따라 성능이 좌우된다.

-최악의 경우(가장 작은/큰 원소가 pivot인 경우): (n-1)+(n-2)+...+1=> O(n^2)

-최선의 경우(중간 크기의 원소가 pivot인 경우): 층수 * O(n) = logn*O(n) = O(nlogn)

-평균의 경우(항상 랜덤하게 선택하는 경우): O(nlogn)

 

알고리즘 구현(python)

import random
size=15
num=[]
result=[0]*size
#랜덤으로 숫자 리스트를 만드는 함수
def makeList(num):
    for i in range(size):
      num.append(int(random.random()*100+1))
      #1부터 100까지의 수 중 하나

def partition(num,left,right):
    pivot=num[left] #pivot을 랜덤으로 설정해도 됨
    low=left; high=right

    while(low<high):
        while(num[low]<=pivot and low<right):
            low+=1
        while(num[high]>=pivot and high>left):
            high-=1
        if low<high:
            ##low위치의 원소는 pivot보다 크고 high위치의 원소는 pivot보다 작으므로 swap
            num[low],num[high]=num[high],num[low]
        
    num[left],num[high]=num[high],num[left] #pivot위치 고
    ##pivot의 위치 return
    return high 

def quickSort(num,left,right):
    if(left<right):
        q=partition(num,left,right)
        quickSort(num,left,q-1)
        quickSort(num,q+1,right)
        #pivot을 기준으로 두 그룹으로 분할

makeList(num)
print(*num)
quickSort(num,0,size-1)
print(*num)

 

 

3.이진탐색(이분탐색)

탐색 범위를 두 부분으로 나눠가면서 원하는 원소를 찾는 알고리즘으로 탐색 전 원소가 정렬되어 있어야한다.

-탐색 범위 설정 ex)[s,e]

-탐색 지점(mid) 설정 후 찾는 값과 비교 ex)mid=(s+e)//2

-mid가 더 크면 [s,mid-1]에서 다시 탐색, 더 작으면 [mid+1,e]에서 다시 탐색

-s>e일 때 까지 위의 과정 반복

 

시간복잡도 : O(logn)

 

알고리즘 구현(python)

import random
size=15
num=[]
result=[0]*size
#랜덤으로 숫자 리스트를 만드는 함수
def makeList(num):
    while True:
        temp=random.randint(1,20)
        #1부터 20사이의 숫자
        if temp not in num:
            num.append(temp)
        if len(num)==size:
            break

def binary_search(target,num):
    start=0
    end=size-1
    while(start<=end):
        mid=(start+end)//2
        if num[mid]==target:
            return mid
        elif num[mid]>target:
            end=mid-1
        else:
            start=mid+1
    return None ##찾고자 하는 수가 없는 경우


target=random.randint(1,20) #찾고자하는 수
makeList(num)
num.sort()
print(target)
print(num)
print(binary_search(target,num),"번째 원소")

 

 

4.선택문제

n개의 숫자들 중에서 k번째로 작은 숫자를 찾는 알고리즘이다.

k번째로 작은 숫자를 찾는 방법은

-최소 숫자를 k번 찾는 방법 (O(kn))

-숫자를 정렬한 후, k번째 숫자를 찾는 방법 (O(nlogn))

-두 그룹으로 나눠서 두 그룹 중 어느 그룹에 속하는지 찾아가는 방법

   ->왼쪽 그룹 (k번째 작은 숫자) 

   ->오른쪽 그룹(k-왼쪽그룹 크기-1(pivot) 번째로 작은 숫자)

 

시간복잡도

입력 크기가 n에서부터 평균적으로 3/4배로 감소, 크기가 1일 경우 분할 완료

n+3/4n+(3/4)^2n+...(3/4)^in = n[1+3/4+(3/4)^2+...+(3/4)^i] <= 2n

평균 2회에 좋은 분할이 되므로 2*O(n) = O(n)

 

알고리즘 구현(python)

import random
import sys
sys.setrecursionlimit(10**6)
size=15
num=[]

#랜덤으로 숫자 리스트를 만드는 함수
def makeList(num):
    for i in range(size):
      num.append(int(random.random()*100+1))
      #1부터 100까지의 수 중 하나
      
def partition(num,left,right):
    pivot=num[left] #pivot을 랜덤으로 설정해도 됨
    low=left; high=right

    while(low<high):
        while(num[low]<=pivot and low<right):
            low+=1
        while(num[high]>=pivot and high>left):
            high-=1
        if low<high:
            ##low위치의 원소는 pivot보다 크고 high위치의 원소는 pivot보다 작으므로 swap
            num[low],num[high]=num[high],num[low]
        
    num[left],num[high]=num[high],num[left] #pivot위치 고
    ##pivot의 위치 return
    return high

def selection(num,left,right,k):
    p=partition(num,left,right)
    s=p-left #왼쪽 그룹의 크기
    if k<=s:
        return selection(num,left,p-1,k)
    elif k==s+1:
         return num[p]
    else:
        return selection(num,p+1,right,k-s-1)


makeList(num)
print(*num)
k=int(input())
print(selection(num,0,size-1,k))

 

 

출처 : 알기 쉬운 알고리즘(개정판), 양성봉, 생능 출판사