정렬 & 이진 탐색

 

 정렬 알고리즘

정렬이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다. 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다. 블로그의 [모두의 알고리즘] 탐색과 정렬 편에 정리 해두긴 했지만 장기기억으로 변화시키기 위해 한번 더 정리해본다.

 

 

• 선택정렬 O(N^2)

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복하며 정렬한다.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)):
	min_index = i # 가장 작은 원소의 인덱스, 첫 번재 인덱스의 값이 가장 작다고 가정.
    for j in range(i+1, len(array)): # i 다음 값 부터 살펴봄
    	if array[min_index] > array[j]:
        	min_index = j
    array[i], array[min_index] = array[min_index], array[i] # 자리바꿈
    
print(array)
 
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

• 삽입정렬 O(N^2)

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다. 선택 정렬에 비해 구현 난이도가 높은 편이지만, 리스트 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작할 수 있기 때문에 일반적으로 더 효율적으로 동작한다. 최선의 경우 O(N)의 시간 복잡도(데이터를 확인하는 정도)로 동작한다.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in ragne(1, len(array)):
	for j in range(i, 0, -1): # i부터 0까지 1씩 작아지며 반복    
		if array[j] < array[j-1]: # 지금게 앞에꺼 보다 작으면
        	array[j], array[j-1] = array[j-1], array[j] # 자리 바꿈
        else:
        	break
               
print(array)
 
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

• 퀵정렬 O(NlogN) ~ O(N^2)

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다. 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이며 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리 근간이 되는 알고리즘이다. 가장 기본적인 퀵정렬은 첫 번째 데이터를 기준 데이터로 설정한다. 

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
	if start >= end: # 원소가 1개인 경우 종료
    	return
        
    piovt = 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)
print(array)
 
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

위 함수는 정석적이긴 하나 다소 복잡하고 구현하기 힘들 수 있다.

재귀함수를 호출해 퀵정렬을 실행하는 경우 코드도 간결하고 훨씬 직관적으로 이해할 수 있다. 

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
	if len(array) <= 1:
        return arraay # 리스트 원소가 1개 이하라면 그대로 반환
        
    pivot = array[0] # 기준으로 첫 번째 원소 지정
    tail = array[1:] # 기준을 제외한 리스트
    
    left = [i for i in tail if x <= pivot] # 기준보다 작은 값들 리스트
    right = [i for i in tail if x > pivot] # 기준보다 큰 값들 리스트
    
    return quick_sort(left) + [pivot] + quick_sort(right)
               
print(quick_sort(array))
 
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

• <두 배열의 원소 교체>
• 두 개의 배열 A와 B가 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다. 최대 K번의 바꿔치기를 통해 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것이다. 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이다.
• N, K 그리고 배열 A와 B의 정보가 주어졌을 때, 최대 K 번의 바꿔치기 연산을 통해 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 만들어라.
  • 첫 번째 줄에 N과 K가 공백을 기준으로 구분되어 입력된다. (1 <= N <= 100,000, 0 <= K <= N)
  • 두 번째 줄에 배열 A의 원소들이 공백을 기준으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수.
  • 세 번째 줄에 배열 B의 원소들이 공백을 기준으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수.

n, k = map(int, input().split()) # N과 K 입력받기
a = list(map(int, input().split())) # 배열 A의 모든 원소를 입력 받기
b = list(map(int, input().split())) # 배열 B의 모든 원소를 입력 받기

## 좀 더 빠른 입력을 받기 원한다면
# from sys import stdin # sys 라이브러리를 활용
# n, k = map(int, sys.stdin.readline())
# a = list(map(int, sys.stdin.readline()))
# b = list(map(int, sys.stdin.readline()))

a.sort() # 배열 A는 오름차순 정렬
b.sort(reverse=True) # 배열 B는 내림차순으로 정렬

for i in range(k): # K 번 만큼 수행
	if a[i] < b[i]: # A의 원소가 B의 원소보다 작은 경우
    	a[i], b[i] = b[i], a[i]
    else: # A의 원소가 B의 원소보다 크거나 같을 때, 반복문 탈출 (바꿀 필요 없이 그냥 더하는게 크므로)
    	break
        
    print(sum(a)) # 배열 A의 모든 원소의 합을 출력

 

 

---

이진 탐색 알고리즘

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 이진 탐색은 시작점, 끝점, 중감점을 이용하여 탐색 범위를 설정한다.  단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log2N에 비례한다. 

예를 들어 초기 데이터 개수가 32개 일 대, 이상적으로 1단계를 거치면 16개 가량의 데이터만 남는다. 2단계를 거치면 8, 3단계를 거치면 4개 가량의 데이터만 남는다. 다시 말해 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(logN)을 보장한다. 

재귀적으로 구현된 이진 탐색의 코드는 이렇다.

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: # target 값이 중간 점의 값보다 작은 경우 왼쪽 확인
    	retrun binary_search(array, target, start, mid -1)
    else: # target 값이 중간 점의 값보다 큰 경우 오른쪽 확인
    	return binary_search(array, target, mid + 1, end)

 

• 파이썬 이진 탐색 라이브러리

# bisect_left(a, x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 위치를 반환
# bisect_right(a, x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 위치를 반환

from bisect import bisect_left, bisect_right

a = [1, 2, 4, 4, 8]
x = 4

print(bisect_left(a, x))
print(bisect_right(a, x))

# 실행결과: 
2
4


## 이진 탐색 라이브러리를 이용해 값이 특정 범위에 속하는 데이터 개수 구하기 ##

from bisect import bisect_left, bisect_right

def count_by_range(a, left_value, right_value):
    right_index = bisect_right(a, right_value) # 배열 a에서 right_value가 들어갈 가장 오른쪽 위치
    left_index = bisect_left(a, left_value) # 배열 a에서 left_value가 들어갈 가장 왼쪽 위치
    return right_index - left_index # 둘 사이의 데이터 개수
    
    
a = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]

print(count_by_range(a, 4, 4)) # 값이 4인 데이터 개수 출력

print(count_by_range(a, -1, 3)) # 값이 -1~3 범위에 있는 데이터 개수 출력

# 실행결과
2
6

 

• 파라메트릭 서치

파라메트릭 서치란 최적화 문제를 결정 문제(예 혹은 아니오)로 바꾸어 해결하는 기법이다.

    예) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제 

일반적으로 코딩테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있다.

 

• <떡볶이 떡 만들기>
• 자주가는 떡집의 떡볶이 떡은 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰져있다. 절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다.
• 예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm이다. 손님은 6cm만큼의 길이를 가져간다.
• 떡집에 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하라.
  • 첫째 줄에 떡의 개수 N과 얻고 싶은 떡의 길이 M이 주어진다. (1<= N <=1,000,000, 1<= M <=2,000,000,000)
  • 둘째 줄에는 떡의 개별 높이가 주어진다. 떡 높이의 총합은 항상 M 이상 이므로, 손님은 필요한 양만큼 떡을 사갈 수 있다. 높이는 10억보다 작거나 같은 양의 정수 혹은 0이다.
  • 적어도 M만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력

이 문제는 적절한 높이를 찾을 때까지 이진 탐색을 수행하여 높이 H를 반복해서 조정하면 된다. '현재 이 높이로 자르면 조건을 만족할 수 있는가?' 를 확인하고, 조건의 만족여부에 따라 탐색 범위를 좁혀서 해결할 수 있다.

절단기의 높이는 0부터 10억까지의 정수 중 하나이고 이렇게 큰 범위일 경우 이진 탐색을 떠올릴 수 있어야 한다. 중간점의 값은 시간이 지날수록 '최적화된 값'이 되기 때문에, 과정을 반복하면서 얻을 수 있는 떡의 길이 합이 필요한 떡의 길이보다 크거나 같을 때마다 중간점의 값을 기록하면 된다.

 

# 떡의 개수 N과 요청한 떡의 길이 M을 입력
n, m = list(map(int, input().split()))
# 각 떡의 개별 높이 정보를 입력
array = lst(map(int, input().split()))

# 이진 탐색을 위한 시작점과 끝점 설정
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
        
    # total이 M보다 작은 경우 더 많이 자르기(왼쪽 부분 탐색)
    if total < m:
    	end = mid -1
    # total이 M보다 큰 경우 덜 자르기(오른쪽 부분 탐색)
    else:
    	result = mid # 최대한 덜 잘랐을 때 정답이므로, 여기서 result에 값을 기록
        start = mid + 1
        
print(result)

 

• <정렬된 배열에서 특정 수의 개수 구하기>
• N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있다. 이때 수열에서 x가 등장하는 횟수를 계산하라. 예를 들어 수열 [1, 1, 2, 2, 2, 2, 3]이 있을 때 x =2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력한다.
• 단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않을 경우 시간 초과 판정을 받는다.
  • 첫째 줄에 N과 x가 정수 형태로 공백으로 구분되어 입력된다. (1 <= N <= 1,000,000, -10^9 <= x <= 10^9)
  • 둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력된다. (-10^9 <= x <= 10^9)
  • 수열의 원소 중에서 값이 x인 원소의 개수를 출력한다. 단, 값이 x인 원소가 하나도 없다면 -1을 출력한다.

from bisect import bisect_left, bisect_right

def count_range(array, left, right):
	left_indx = bisect(array, left)
    right_indx = bisect(array, right)
    return right_indx - left_indx
    
# N과 x 입력 받기
n, x = map(int, input().split())

# 원소 입력받아 리스트 만들기
arr = list(map(int, input().split()))

if count_range(arr, x, x) == 0: # 값이 x인 원소가 없는 경우
    print(-1) 
    
else: # 값이 x인 원소가 있는 경우
    print(count_range(arr, x, x)) # 값이 x인 원소의 개수 출력