- 이것이 취업을 위한 코딩테스다 with 파이썬(이코테 2021) 유튜브 영상을 보면서 공부한 자료입니다.
- https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC
정렬 알고리즘
- 정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다.
- 일반적으로 문제 상황에 따라서, 적절한 정렬 알고리즘이 공식처럼 사용된다.
선택 정렬
- 처리되지 않은 데이터 중에서, 가장 작은 데이터를 선택해, 맨 앞에 있는 데이터와 바꾸는 것을 반복하는 것을 말한다.
입력 예시
7 5 9 0 3 1 6 2 4 8
- 정렬하고자 하는 숫자 모음이 입력된다.
출력 예시
0 1 2 3 4 5 6 7 8 9
- 오름차순 정렬이 출력된다.
arr = list(map(int, input().split()))
for i in range(len(arr)):
min_idx = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
for a in arr:
print(a, end=' ')
선택 정렬의 시간 복잡도
- 선택 정렬은 N번 만큼, 가장 작은 수를 찾아서 맨 앞으로 보내야 한다.
- 전체 연산 횟수는 다음과 같다.
- 따라서
삽입 정렬
- 처리되지 않은 데이터를, 하나씩 골라 적절한 위치에 삽입한다.
- 선택 정렬에 비해, 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작한다.
입력 예시
7 5 9 0 3 1 6 2 4 8
- 정렬하고자 하는 숫자 모음이 입력된다.
출력 예시
0 1 2 3 4 5 6 7 8 9
arr = list(map(int, input().split()))
for i in range(1, len(arr)):
for j in range(i, 0, -1):
if arr[j - 1] > arr[j]:
arr[j - 1], arr[j] = arr[j], arr[j - 1],
else:
break
for a in arr:
print(a, end=' ')
삽입 정렬의 시간 복잡도
- 삽입 정렬의 시간 복잡도는 선택정렬과 마찬가지로 다음과 같다.
- 삽입 정렬은, 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.
퀵 정렬
- 기준 데이터를 설정하고, 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다.
- 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이다.
- 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다.
- 가장 기본적인 퀵 정렬은, 첫 번째 데이터를 기준 데이터(Pivot)으로 설정한다.
입력 예시
5, 7, 9, 0, 3, 1, 6, 2, 4, 8
출력 예시
0 1 2 3 4 5 6 7 8 9
- 파이썬의 장점을 활용하면, 다음과 같은 코드로 짤 수 있다.
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[0]
tail = arr[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)
arr = list(map(int, input().split(',')))
res = quick_sort(arr)
for r in res:
print(r, end=' ')
퀵 정렬의 시간 복잡도
- 평균의 경우 다음의 시간 복잡도를 갖는다.
- 최악의 경우 다음의 시간 복잡도를 갖는다. -> 이미 정렬된 배열에 대해서, 첫 번째 원소를 pivot으로 삼을 때 quick_sort
계수 정렬
- 특정한 조건이 부합할 때만 사용할 수 있지만, 매우 빠르게 동작하는 정렬 알고리즘이다.
- 계수 정렬은 데이터의 크기 범위가 제한되어, 정수 형태로 표현할 수 있을 때 사용 가능하다
- 데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때, 최악의 경우에도 수행 시간 O(N + K)를 보장한다.
입력 예시
7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2
출력 예시
0 0 1 1 2 2 3 4 5 5 6 7 8 9 9
arr = list(map(int, input().split(',')))
count = [0] * (max(arr) + 1)
for i in range(len(arr)):
count[arr[i]] += 1
res = []
for i in range(len(count)):
for j in range(count[i]):
res.append(i)
for r in res:
print(r, end=' ')
계수 정렬의 시간 복잡도
- 계수 정렬의 시간 복잡도와 공간 복잡도는 모두 다음과 같다.
- 계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용할 수 있다.
정렬 알고리즘 비교하기
- 대부분의 프로그래밍 언어에서 지원하는, 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN)을 보장하도록 설계되어 있다.
(오름차순 정렬 기준 설명)
- 선택 정렬: 처리되지 않은 데이터 중에서, 가장 작은 데이터를 선택해, 맨 앞에 있는 데이터와 바꾸는 것을 반복한다.
- 삽입 정렬: 처리되지 않은 데이터 중에서, index를 줄여가며 데이터 크기를 비교하여, 적절한 위치에 삽입한다.
- 퀵 정렬: 기준 데이터(pivot)를 설정하고, 그 기준보다 작은 데이터와 큰 데이터를 분류하는 방법을 재귀적으로 반복한다.
- 계수 정렬: 데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때, count 리스트를 생성하여, 각 숫자가 몇번 나오는지 계산한다.
<문제 1> 두 배열의 원소 교체
입력 예시
5 3
1 2 5 4 3
5 5 6 6 5
- 첫 번재 줄에 N, K가 공백을 기준으로 구분되어 입려된다.
- 두 번째 줄에 배열 A의 원소들이 공백을 기준으로 구분되어 입력된다.
- 세 번째 줄에 배열 B의 원소들이 공백을 기준으로 구분되어 입력된다.
출력 예시
26
- 최대 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]
else:
break
print(sum(a))
안녕하세요.