문제 출처
23881번 알고리즘 수업 - 선택 정렬 1
23882번 알고리즘 수업 - 선택 정렬 2
풀이
선택 정렬
선택 정렬
가장 작은 것을 선택해서 제일 앞으로 보내거나,
제일 큰 것을 선택해서 제일 뒤로 보내거나
li = [3, 4, 10, 9, 2, 1, 5]
index = -1
for i in range(0, len(li)):
min = 9999
for j in range(i, len(li)):
if min > li[j]:
min = li[j]
index = j
temp = li[i]
li[i] = li[index]
li[index] = temp
print(li) # [1, 2, 3, 4, 5, 9, 10]
23881번 풀이
range(시작, 끝, 간격)
0~i까지의 최대값을 찾아서 저장하고, 변경해준다.
변경할 때마다 cnt를 체크해서 k와 같아지면 끝내준다.
for문을 다 돌았는데도 안 끝났다면 -1을 출력해준다.
import sys
sys.stdin = open("input.txt", "r")
input = sys.stdin.readline
n, k = map(int, input().split())
l = list(map(int, input().split()))
cnt = 0
for i in range(n - 1, 0, -1):
index = l.index(max(l[:i + 1]))
if index != i:
l[index], l[i] = l[i], l[index]
cnt += 1
if cnt == k:
print(l[index], l[i])
exit()
print(-1)
23882번 풀이
리스트 요소를 한줄에 한번에 출력하고 싶으면 print(*list)
import sys
sys.stdin = open("input.txt", "r")
input = sys.stdin.readline
n, k = map(int, input().split())
l = list(map(int, input().split()))
cnt = 0
for i in range(n - 1, 0, -1):
index = l.index(max(l[:i + 1]))
if index != i:
l[index], l[i] = l[i], l[index]
cnt += 1
if cnt == k:
print(*l)
exit()
print(-1)
버블 정렬
옆에 있는 값과 비교해서 더 작은 값을 반복적으로 앞으로 보내는 정렬 방법.
정렬 알고리즘 중 가장 비효율적인 알고리즘이다.
li = [3, 4, 10, 9, 2, 1, 5]
for i in range(0, len(li)):
# 뒤에서부터 큰 값들을 채워 나가므로
# j는 전부 도는 게 아니라 len - i -1 까지만 반복한다.
for j in range(0, len(li) - i - 1):
if li[j] > li[j + 1]:
temp = li[j]
li[j] = li[j + 1]
li[j + 1] = temp
print(li)삽입 정렬
각 숫자를 적절한 위치에 삽입하는 방식으로 정렬하는 알고리즘.
앞선 선택 정렬, 버블 정렬은 무조건 위치를 바꾸는 방식이었다면, 삽입 정렬은 필요할 때만 위치를 바꾼다.
삽입 정렬은 최악의 경우 O(n^2)이지만,
데이터가 거의 이미 정렬되어 있는 경우 그 어떤 알고리즘보다도 빠르다.
왜냐하면 필요할 때만 삽입을 진행하기 때문이다.
li = [3, 4, 10, 9, 2, 1, 5]
for i in range(0, len(li) - 1):
j = i
while j >= 0 and li[j] > li[j + 1]:
temp = li[j]
li[j] = li[j + 1]
li[j + 1] = temp
j -= 1
print(li)퀵 정렬
대표적인 분할 정복 알고리즘으로, 평균 시간복잡도가 O(N * logN)이다.
퀵 정렬은 하나의 문제를 두 개의 작은 문제로 분할하는데, 정확히는 특정한 값(pivot)을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤 배열을 반으로 쪼갠다. 보통 첫번째 원소를 pivot으로 설정하고 시작한다.
기본적으로 N번씩 탐색하되, 반으로 쪼개 들어가므로 logN을 곱한 게 시간 복잡도가 된다.
퀵 정렬은 이미 정렬되어 있는 데이터의 경우 최악의 시간 복잡도인 O(n^2)를 보여준다. 삽입 정렬과 반대되는 특징을 갖는 것이다.
li = [3, 4, 10, 9, 2, 1, 5]
def quick_sort(list, start, end):
if start >= end:
return
key = start
i = start + 1
j = end
while i <= j:
while i <= end and list[i] <= list[key]: # pivot보다 큰 값의 index를 찾고
i += 1
while j > start and list[j] >= list[key]: # pivot보다 작은 값의 index를 찾아서
j -= 1
if i > j: # pivot보다 큰 값의 index인 i가 pivot보다 작은 값의 index인 j보다 크면,
# 이미 큰 값의 index인 i는 놔두고, pivot이 list[j] 보다 크니까 교환해준다.
temp = list[j]
list[j] = list[key]
list[key] = temp
else:
# 아닌 경우라면, 큰 값인 list[i]가 list[j]보다 앞에 있다는 거니까 뒤로 보내준다.
temp = list[i]
list[i] = list[j]
list[j] = temp
# 분할 정복
quick_sort(list, start, j - 1)
quick_sort(list, j + 1, end)
quick_sort(li, 0, len(li) - 1)
print(li)혹은 이렇게도 가능
[알고리즘] 퀵 정렬 - Quick Sort (Python, Java)
- 파이썬의
list.sort()는 퀵 정렬을 기본으로 한다. - 일반적으로 원소의 개수가 적어질수록 나쁜 중간값이 선택될 확률이 높아지기 때문에, 원소의 개수에 따라 퀵 정렬에 다른 정렬을 혼합해서 쓰는 경우가 많다.
- 병합 정렬과 퀵 정렬은 분할 정복과 재귀 알고리즘을 사용한다는 측면에서는 유사해보이지만, 내부적으로 정렬을 하는 방식에서는 큰 차이가 있다.
- 병합 정렬은 항상 정 중앙을 기준으로 단순 분할 후 병합 시점에서 값의 비교 연산이 발생하는 반면, 퀵 정렬은 분할 시점부터 비교 연산이 일어나기 때문에 그 이후 병합에 들어가는 비용이 매우 적거나 구현 방법에 따라서 아예 병합을 하지 않을 수도 있다.
def quick_sort(arr):
def sort(low, high):
if high <= low:
return
mid = partition(low, high)
sort(low, mid - 1)
sort(mid, high)
def partition(low, high):
pivot = arr[(low + high) // 2]
while low <= high:
while arr[low] < pivot:
low += 1
while arr[high] > pivot:
high -= 1
if low <= high:
arr[low], arr[high] = arr[high], arr[low]
low, high = low + 1, high - 1
return low
return sort(0, len(arr) - 1)