나동빈님의 책과 유튜브 강의인 '이것이 코딩 테스트다'를 바탕으로 스스로 공부한 내용을 정리한 글입니다.
참고한 영상의 링크는 아래와 같습니다.
이것이 코딩테스트다 - 정렬 알고리즘
선택정렬
- 처리(=정렬)되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복합니다.
array = [7,5,9,0,3,1,6,2,4,8]
for i in range(len(array)):
min_index = i
for min_index in range(len(array)):
if array[i] < array[min_index]:
array[min_index], array[i] = array[i], array[min_index]
print(array)선택정렬의 시간복잡도
- 매번 정렬되지 않은 N번만큼의 가장 작은 수를 앞으로 보내야 한다.
- N, (N-1), (N-2), ... 2
삽입정렬
- 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입하는 정렬.
- 즉, 현재 인덱스 앞에 있는 모든 아이템들은 모두 정렬이 되어있다고 가정하고, 현재 인덱스의 아이템을 그 앞에 있는 아이템들과 비교해서 올바른 위치에 삽입하는 알고리즘이다.
array = [7,5,9,0,3,1,6,2,4,8]
for i in range(1, len(array)):
for j in range(i,0,-1): # i는 index를 하나씩 줄이면서 첫번째 원소까지
if array[j] < array[j-1]:
array[j] , array[j-1] = array[j-1], array[j]
else: # 자기 자신보다 작은 원소를 만나면 멈춤 (i번째 이전까지는 모두 정렬이 되어있다고 가정하기 때문)
break
print(array)삽입정렬의 시간복잡도
- 반복문을 2번 돌아야함으로 의 시간복잡도이나
- 현재 리스트가 거의 정렬되어있을 경우 매우 빠르게 동작함.
퀵 정렬
- 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
- 가장 기본적인 퀵 정렬은 첫번째 데이터를 기준 데이터(Pivot)으로 상정합니다.
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array, start, end):
if start >= end:
return
pivot = start
left = start + 1
right = end
# pivot을 기준으로 left, right을 탐색할 예정인데 엇갈리는 순간 pivot을 기준으로
# 정렬이 되어있다는 의미임으로 while문 탈출.
while (left <= right):
# 좌측의 데이터에 대해서, puvot보다 큰 데이터를 찾기 때문에
# piovot보다 같거나 작으면 한칸씩 이동
while left <= end and array[pivot] >= array[left]:
left += 1
# 우측의 데이터에 대해서, puvot보다 작은 데이터를 찾기 때문에
# piovot보다 같거나 크면 한칸씩 이동
while start < right and array[pivot] <= array[right]:
right -= 1
# pivot을 기준으로 left에 있는 데이터보다 right에 있는 데이터가 더 큰 상황
# index 상으로도 left > right인 상황.
# 이 말은 곧 pivot이 제대로 동작하고 있음을 의미하니, pivot을 right
# (좌측의 최우단)에 배치시킨다.
if left > right:
array[pivot], array[right] = array[right], array[pivot]
# pivot을 기준으로 left에 있는 데이터보다 right에 있는 데이터가 더 큰 상황
# 그러나 index 상으로 left < 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)
개인적으로 이해하기 어려웠던 알고리즘이라 코드를 짜면서 들었던 생각들이다.
- 한번의 함수 호출 후에 pivot이 어느 위치에 있을지 모르겠지만, pivot 좌측에는 pivot보다 작은 값들이 pivot 우측에는 pivot보다 큰 값들이 위치해 있도록 하는 것이 목표인 알고리즘이다. (log 복잡도를 위해)
- 따라서 pivot이 맨 첫 데이터라고 할때, 왼쪽에 있는 데이터를 searching할때는 pivot보다 큰 데이터를, 오른쪽에 있는 데이터를 searching할때는 pivot보다 작은 데이터를 search하면 되며 한번 탐색한 index는 더이상 볼 필요가 없기 때문에 while문으로 탐색해도 무방하다. (대신 out-of-index 뜨지 않게 종료조건 잘 맞춰주기)
- (좌>우로 탐색해서) 찾은 pivot보다 큰 데이터의 index가 (우>좌로 탐색해서) 찾은 pivot보다 작은 데이터의 index보다 클 경우 pivot을 기준으로 정렬이 되어있다는 것을 의미한다. 따라서 (우>좌로 탐색해서) 찾은 pivot보다 작은 데이터와 pivot의 위치를 바꿔주면 pivot을 기준으로 좌측은 크기가 무조건 작고, 우측은 무조건 큰게 보장이 되기에 좌/우 영역에 한정해서 재귀호출을 걸어주면 된다.
내가 했던 고민들을 보다 더 직관적으로 파이썬으로 풀어서 반영해준 코드는 아래와 같다.
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8,7,7]
def quick_sort(array):
print(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 x in tail if x>pivot]
return quick_sort(left_side) + [pivot] + quick_sort(right_side)
print(quick_sort(array))
- if len(array) <=1인 이유는 left_side나 right_side에 빈 array가 넘어올 수도 있기 때문이다.
계수(count) 정렬
- 데이터의 크기 범위가 제한되어 정수 형태로 표현되어 있을때 사용가능한 정렬 알고리즘이다.
- 데이터 개수가 N, 데이터(양수) 중 최대값이 K일 때 최악의 경우애도 수행시간 을 보장한다.
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8, 7, 7]
count = [0] * (max(array) - min(array) + 1) # array의 max, min값을 알고 있다고 가정
for i in array: # N회 반복
count[i] += 1
for idx, cnt in enumerate(count): # K회 반복
for _ in range(cnt): # N회 반복
print(idx, end=" ")- 이 알고리즘은 array내 최소값과 최대값이 무엇인지 알고 있어야 사용할 수 있다. (차이+1 만큼의 count array를 선언)
- 또한 동일한 값을 가지는 데이터가 여러개 등장할 때 효율적으로 사용할 수가 있다.
문제 - 두 배열의 원소 교체
- 첫번째 줄에 n,k가 공백되어 입력된다. (0<=N<=100,000, 0<=K<=N)
- 두번째 줄에 배열 A의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 100,000,000보다 작은 자연수이다.
- 세번째 줄에 배열 B의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수입니다.
- 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력한다.
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort()
b.sort(reverse=True)
for i in range(k):
if a[i] < b[i]:
a[i], b[i] = b[i], a[i]
print(sum(a))- 첫번째 배열은 오름차순, 두번째 배열은 내림차순으로 정렬한 후 1>K까지 원소를 탐색하면서 첫번째 배열의 원소가 두번째 배열의 원소보다 작으면 swapping하면 벼열 A의 합을 최대화할 수 있다.
