📑
파이썬 정렬 알고리즘
버블 정렬
: 인접한 두 수 를 비교하며 정렬. O(n^2)
def bubble_sort(array):
n = len(array)
for i in range(n - 1):
for j in range(n - i - 1):
if array[j] > array[j + 1]:
array[j], array[j + 1] = array[j + 1], array[j]
print(array)
선택 정렬
: 한 바퀴 도는 동안 가장 작은 값을 찾아 맨 앞과 교환하는 방식. O(n^2)
def selection_sort(array):
n = len(array)
for i in range(n):
min_index = i
for j in range(i + 1, n):
if array[j] < array[min_index]:
min_index = j
array[i], array[min_index] = array[min_index], array[i]
print(array[:i+1])
삽입 정렬
: 정렬된 데이터 그룹을 늘려가며 추가되는 데이터를 알맞은 자리에 삽입하는 방식. O(n^2)
def insertion_sort(array):
n = len(array)
for i in range(1, n):
for j in range(i, 0, - 1):
if array[j - 1] > array[j]:
array[j - 1], array[j] = array[j], array[j - 1]
print(array[:i+1])
퀵 정렬
: 분할 정복 알고리즘. 추가적인 메모리 필요 없음. 대체로 빠른 속도. O(n log n)
def quick_sort(array):
if len(array) <= 1:
return array
pivot = len(array) // 2
front_arr, pivot_arr, back_arr = [], [], []
for value in array:
if value < array[pivot]:
front_arr.append(value)
elif value > array[pivot]:
back_arr.append(value)
else:
pivot_arr.append(value)
print(front_arr, pivot_arr, back_arr)
return quick_sort(front_arr) + quick_sort(pivot_arr) + quick_sort(back_arr)
병합 정렬
: 분할 정복과 재귀를 이용한 정렬. O(n log n)
def merge_sort(array):
if len(array) < 2:
return array
mid = len(array) // 2
low_arr = merge_sort(array[:mid])
high_arr = merge_sort(array[mid:])
merged_arr = []
l = h = 0
while l < len(low_arr) and h < len(high_arr):
if low_arr[l] < high_arr[h]:
merged_arr.append(low_arr[l])
l += 1
else:
merged_arr.append(high_arr[h])
h += 1
merged_arr += low_arr[l:]
merged_arr += high_arr[h:]
print(merged_arr)
return merged_arr
배열 정렬
: O(n^2)
1. list.sort() : 변수 자체를 수정. None 반환. key 설정 가능, reverse(내림차순) 가능.
2. sorted(list) : 원래 변수 수정X. 정렬된 배열이 반환됨. 새 변수에 저장 가능. key 설정 가능, reverse(내림차순) 가능.
힙 정렬
: 힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조(최소힙은 반대). 원소들의 상대적인 순서를 보존하지 않는 불안정 정렬이다.(= 같은 값이라도 순서가 달라질 수 있다.) O(n log n)
- 입력으로 들어온 배열을 최대 힙 형태로 구성한다. (Build Heap)
- 입력 배열을 처음부터 끝까지 순회하며, 각 원소를 힙에 삽입한다.
- 힙에 원소를 삽입할 때는 힙의 마지막 노드에 새 원소를 추가한 후, 부모 노드와의 비교와 교환을 반복한다. (Max Heapify)
- 최대 힙에서 가장 큰 원소(루트 노드)를 추출하여 정렬된 결과에 추가한다. (Extract Max)
- 루트 노드를 정렬된 결과에 추가한 후, 마지막 노드를 루트 노드로 가져온다.
- 힙을 다시 최대 힙 형태로 만들기 위해 힙 속성을 유지한다. (Max Heapify)
- 힙이 모두 빈 상태가 될 때까지 2단계를 반복한다.
def heapify(unsorted, index, heap_size): # 특정 인덱스의 노드를 최대 힙 형태로.
largest = index
left = 2 * index + 1
right = 2 * index + 2
if left < heap_size and unsorted[right] > unsorted[largest]:
largest = left
if right < heap_size and unsorted[right] > unsorted[largest]:
largest = right
if largest != index:
unsorted[largest], unsorted[index] = unsorted[index], unsorted[largest]
heapify(unsorted, largest, heap_size)
def heap_sort(unsorted): # 힙 정렬
n = len(unsorted)
for i in range(n // 2 - 1, -1, -1):
heapify(unsorted, i, n)
for i in range(n - 1, 0, -1):
unsorted[0], unsorted[i] = unsorted[i], unsorted[0]
heapify(unsorted, 0, i)
return unsorted
또는
def heapsort(iterable):
heap = []
result = []
for value in iterable:
heapq.heappush(heap, -value)
# print(heap)
# [-9, -8, -6, -5, -7, 0, -3, -1]
for i in range(len(heap)):
result.append(-heapq.heappop(heap))
return result
ALGORITHM CODE KATA
Ⅰ. Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다. Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.
def solution(brown, yellow):
n = brown + yellow # 전체 카펫 개수.
for w in range(1, n + 1): # w는 가로, h는 세로 길이.
if n % w == 0: # 가로길이가 전체 카펫 개수의 약수인 경우.
h = n // w
if (w - 2) * (h - 2) == yellow:
answer = [w, h]
return answer