파이썬 알고리즘 공부 - (2) 정렬, 이진 탐색

 

정렬 알고리즘

 

정렬 : 데이터를 특정한 기준에 따라 순서대로 나열한 것 

 

📍선택 정렬

: 처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것

시간 복잡도 : O(N^2)

array = [ 3,4,5...]

for i in range(len(array)):
	min_index = i
    for j in range(i+1, len(array)):
    	if array[min_index] > array[j]:
        	min_index = j
    array[i], array[min_index] = array[min_index], array[i]
    
print(array)

 

📍삽입 정렬

: 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입 -> 더 효율적

시간 복잡도 : O(N^2) , 최선: O(N)

for i in range(1, len(array)):
	for j in range(i, 0, -1):
    	if array[j] < array[j-1]:
        	array[j], array[j-1] = array[j-1], array[j]
        else:
        	break
# 자신의 왼쪽과 비교하여 더 작으면 스와핑

 

📍퀵 정렬

: 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법 -> 가장 많이 사용되는 알고리즘 중 하나

pivot 설정 (기본적으로 첫 번째 데이터)

시간 복잡도 : 평균 : O(NlogN), 최악 : O(N^2)

def quick_sort(array, start, end):
	if start >= end:
    	return
    pivot = start
    left = start +1
    right = end
    while(left <= right):
    	while(left <= end and array[left] <= array[pivot]):
        	left += 1
        while(right > start and array[right] >= array[pivot]):
        	right -= 1
        if(left > right):
        	array[right], array[pivot] = array[pivot], array[right]
        else:
        	array[left], array[right] = array[right], array[left]
    quick_sort(array, start, right-1)
    quick_sort(array, right+1, end)
    
quick_sort(array, 0, len(array)-1)

# 파이썬 더 간결한 코드
def quick_sort(array):
	if len(array) <= 1:
    	return array
   pivot = array[0]
   tail = array[1:]
   
   left_side = [ x for x in tail if x <= pivot] 
   right_side = [ x for in x tail if x > pivot]
   
   return quick_sort(left_side) + [pivot] + quick_sort(right_side)
   
print(quick_sort(array))

 

📍계수 정렬 

: 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘

시간 복잡도, 공간복잡도 : O(N+K) 보장 

공간복잡도는 높아질 수 있음 -> 모든 범위를 포함하는 리스트가 필요하기 때문에

array = [ 7,5,4,3,2,3,...]

count = [0] * (max(array)+1) #모든 범위를 포함하는 리스트 선언, 0으로 초기화

for i in range(len(array)):
	count[array[i]] += 1 #각 데이터에 해당하는 인덱스의 값 증가
    
for i in range(len(count)): #리스트에 기록된 정렬 정보 확인
	for j in range(count[i]):
    	print(i, end='') #띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

 

EX)

# A배열에서 가장 작은 원소를 구하기 (오름차순)
# B배열에서 가장 큰 원소 구하기  (내림차순)
# k번 반복 후 위의 두 원소를 바꿔치기한 A 배열의 합

a.sort()
b.sort(reverse=True)

for i in range(k):
	if a[i] < b[i]:
    	a[i], b[i] = b[i], a[i]
    else 
    	break
print(sum(a))

---

이진 탐색 알고리즘

 

순차 탐색

: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법

 

📍이진 탐색

: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법(시작점, 중간점, 끝점)

시간복잡도 : O(logN)

파이썬 이진 탐색 라이브러리 : from bisect import bisect_left, bisect_right

 -> bisect_left(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽/오른쪽 인덱스를 반환

# 재귀적 표현 - 이진탐색
def binary_search(array, target, start, end):
	if start > end:
    	return None
    mid = (start + end)//2
    if array[mid] == target:
    	return mid
    elif array[mid] > target:
    	return binary_search(array, target, start, mid-1):
    else:
    	return binary_search(array, terget, mid+1, end)

# 반복적 표현 - 이진탐색
def binary_search(array, target, start, end):
	while start <= end:
    	mid = (start+end)//2
        if array[mid] == target:
        	return mid
        elif array[mid] > target:
        	end = mid - 1
        else:
        	start = mid + 1
    return None

 

*파라메트릭 서치 : 최적화 문제를 결정문제(yes or no)로 바꾸어 해결하는 기법 

-> 이진탐색을 이용하여 해결

 

EX)

# 이진탐색 수행으로 H값 조절 
start = 0
end = max(array)
result = 0

while(start <= end):
	total = 0
    mid = (start+end)//2
    for x in array:
    	if x > mid:
        	total += x-mid
    if total < m: #양이 부족한 경우
    	end = mid - 1
    else:
    	result = mid
    	start = min + 1
        
print(result)

 

EX) 라이브러리 사용 

#시간복잡도를 줄이기 위해 선형 탐색보다 이진탐색으로 수행
from bisect import bisect_left, bisect_right

def count_by_range(array, left_value, right_value):
	right_index = bisect_right(array, right_value)
    left_index = bisect_left(array, left_value)
    return right_index-left_index
    
count = count_by_range(array, x, x) # left_value와 right_value 사이의 값이 몇 개

if count == 0:
	print(-1)
else:
	print(count)