[Python] - 축소정복

축소정복기법

◆ 주어진 문제와 더 작은 문제간의 관계를 이용하는 전략

- 예 : n! = n * (n-1)!

- 분할정복기법의 일종

◆ 적용방식

- 하향식 : 순환(재귀)구조

#팩토리얼(하향식 축소정복기법)
def factorial_recur(n):
	if n == 1:
    	return 1
    else:
    	return(n*factorial_recur(n-1))

- 상향식 : 반복구조

#팩토리얼(상향식 축소정복기법)
def factorial_iter(n):
	result = 1
    for k in range(1,n+1):
    	result = result * k
    return result

 

문제 축소형태

1. 고정크기축소 

- 팩토리얼(일정한 크기의 수만큼 일정하게 줄어든다)

2. 고정 비율 축소

- 이진탐색, 거듭제곱(문제가 일정한 비율로줄어든다, 대표적으로 절반)

3. 가변크기 축호

- 유클리드 알고리즘(크기 줄어드는게 일정하지 않다.)

 

삽입정렬

정렬을 위한 축소정복전략

정렬된  n개의 리스트 -> 정렬된 n-1개의 리스트에 새로운 원소 1개를 순서에 맞게 끼워넣기(원소하나씩뽑아서 줄세우기)

 

*효율적인 끼워넣기를 위한 삽입 위치 찾기

def insertion_sort(A):
	n = len(A)     #리스트 A의 크기는 n
    for i in range(1,n):	#리스트 두번째 원소부터 끝까지 
    	key = A[i]			#key는 A의 i번째원소
        j = i-1				#j는 i-1
        while j >=0 and A[j] > key:	#j가 0이상이고 j번째 원소가 key보다 클동안
        	A[j+1] = A[j]		
            j = j-1
        A[j+1] = key
        printStep(A,i)

입력의 크기 : n=len(A)

기본연산 : 1

복잡도

최선 : O(n)

최악 : O(n^2)

평균 : O(n^2)

 

위상정렬

방향그래프가 주어졌다, 각 정점들의 선행순서를 위배하지 않으면서 모든 정점들을 순서대로 나열

진입차수 : 정점으로 들어오는 간선

진출차수 : 정점에서 나가는 간선

1. 진입차수가 0인 임의의 정점 선택

2. 선택된 정점을 삭제, 이 정점에서 진출하는 모든 간선들도 삭제, 차수갱신, 이 과정을 반복 -> 문제크기1줄어든다.

def topological(graph):
	inDeg = {}
    for v in graph:
    	inDeg[v] = 0	#각 정점의 진입차수를 초기화
    for v in graph:
    	for u in graph[v]:
	    	inDeg[u] += 1	#각 정점으로 들어가는 간선의 수를 계산해 진입차수를 구함
    
    vlist = []
    for v in graph:
    	if inDeg[v] == 0:
        	vlist.append(v)		#진입차수가 0인 정점을 찾는다. vlist에 저장
    while vlist:
    	v = vlist.pop()
        print(v, end= ' ')
        
        for u in graph[v]:
        	inDeg[u] -= 1
            if inDeg[u] == 0:
            	vlist.append(u)   #삭제하는 정점이 연결된 간선만큼 빼서 진입차수 갱신

복잡도 : O(n+e)

 

이진탐색

리스트에 n개의 항목이 있을 때 리스트에서 탐색키를 가진 항목을 찾아라. 

#이진탐색(순환구조)
def binary_search(A,key,low,high):
	if(low <= high):
    	mid = (low + high) // 2
        if key == A[mid]:
        	return mid
        elif key < A[mid]:
        	return binary_search(A,key,low,mid-1)
        else:
        	return binary_search(A,key,mid+1,high)
     return -1

#이진탐색(반복구조)
def binary_search_iter(A, key, low, high):
	while(low <= high):
    	mid = (low+high) // 2
        if key == A[mid]:
        	return min
        elif key > A[mid]:
        	low = mid + 1
        else:
        	hith = mid -1
     return -1

복잡도

최선 : O(1)

최악 : O(log2n)

평균 : O(log2n) --> 무시..

 

거듭제곱문제

 

*억지기법

def slow_power(x,n):
	result = 1.0
    for i in range(n):
    	result =result * x
    return result

복잡도 : O(n)

 

*거듭제곱 축소정복기법

def power(x,n):
	if n == 0 :
    	return 1
    elif (n%2)==0:
    	return power(x*x, n //2)
    else:
    	return x*power(x*x, (n-1)//2)

복잡도 : O(log2n)

순환호출을 한번 할때마다 n이 크기가 절반씩 줄어든다.

 

* 행렬의 곱셈함수(MultMat(x,y)가 구현되어있다고 가정)

def powerMat(x,n):
	if n ==1:
    	return x
    elif(n%2) == 0:
    	return powerMat(multMat(x,x), n //2)
    else:
    	return multMat(x,powerMat(multMat(x,x),(n-1) //2))

복잡도 : O(log2n)

 

K번째 작은 수 찾기

리스트에서 K번째로 작은 항목을 찾아라, 리스트 정렬안되어있다.

#정렬을 이용한 k번째 작은 수 찾기
def kth(A,k):
	A.sort()
    return A[k-1]

방법2. 축소정복기법(피봇)

*partition알고리즘

def partition(A,left,right):
	low = left + 1
    high = right
    pivot = A[left]
    while(low<=high):
    	while low <= right and A[low] <= pivot:
        	low += 1
        while high >= left and A[high] > pivot:
        	high -= 1
        if low < high:
        	A[low],A[high] = A[high], A[low]
    A[left],A[high] = A[high], A[left]
    return high

* 축소정복을 이용한 k번째 작은 수 찾기

def quick_select(A,left,right,k):
	pos = partition(A,left,right)
    
    if(pos+1 == left +k):
    	return A[pos]
    elif(pos+1 > left+k):
    	return quick_select(A,left,pos-1,k)
    else:
    	return quick_select(A,pos+1, right, k-(pos+1-left))

복잡도

최선 : O(n)

최악 : O(n^2)

평균 : O(n)

 

 

위조 동전 찾기

고정비율축소문제

1. 동전을 두 집합으로 반반

2. 가벼운 쪽이 가짜가 포함된 것

-> 가벼운 쪽만 갖고 다시 반복

* 3집합으로 나누기

O(k) = O(log3n)=O(logn)