축소정복기법
◆ 주어진 문제와 더 작은 문제간의 관계를 이용하는 전략
- 예 : 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)
'개발일기 > Python' 카테고리의 다른 글
[Python] - 이진검색트리 (0) | 2023.04.24 |
---|---|
[Python] 알고리즘 - 완전탐색 (0) | 2023.04.24 |
[Python] 기본적인 자료구조 - 그래프(Graph) (0) | 2023.04.24 |
[Python] 알고리즘 효율성 분석 (0) | 2023.04.24 |
[Python] 알고리즘 - 최대 공약수 구하기(유클리드 알고리즘) (0) | 2023.03.14 |