2021. 4. 25. 14:12ㆍ카테고리 없음
※ 해당 포스팅은「이것이 취업을 위한 코딩테스트다(나동빈 저)」책 내용을 바탕으로 작성하였습니다.
📚 선택 정렬Selection Sort
매번 가장 작은 데이터를 선택해서 앞으로 보내는 과정을 반복 수행하여 전체 데이터를 정렬.
array = [7, 5, 9, 0, 3]
for i in range(len(array)):
min_index = i # 가장 작은 원소의 인덱스
for j in range(i+1, len(array)):
if array[min_index] > array[j]:
min_index = j
array[i], array[min_index] = array[min_index], array[i] # 스와프
print(array)
선택 정렬의 시간 복잡도 : O(N²)
📚 삽입 정렬Insertion Sort
데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에서 삽입하는 과정을 반복 수행하여 전체 데이터를 정렬.
삽입정렬은 선택정렬에 비해 실행 시간 측면에서 더 효율적이다. 특히 '데이터가 거의 정렬 되어 있을 때' 훨씬 효율적이다.
array = [7, 5, 9, 0, 3]
for i in range(1, len(array)):
for j in range(i, 0, -1):
if array[j] < array[j-1]: # 한 칸씩 왼쪽으로 이동
array[j], array[j-1] = array[j-1], array[j] # 스와프
else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
break
print(array)
삽입 정렬의 시간 복잡도 : O(N²)
리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작하기 때문에 최선의 경우 O(N) 의 시간복잡도를 가진다. 따라서 거의 정렬이 되어 있는 상태로 입력이 주어지는 입력이 주어지는 문제라면 퀵 정렬 등의 여타 정렬 알고리즘을 이용하는 것보다 삽입정렬을 이용하는 것이 더욱 효과적이다.
📚 퀵 정렬Quick Sort
기준(Pivot)을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작.
퀵 정렬은 정렬 알고리즘 중에 가장 많이 사용되는 알고리즘이다.
퀵 정렬에서는 피벗Pivot이 사용된다. 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'을 피벗이라고 표현한다.
1. 피벗을 설정한 뒤에 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.
2. 그 다음 큰 데이터와 작은 데이터의 위치를 서로 교환해준다.
이러한 과정을 반복하면 '피벗'에 대하여 정렬이 수행된다.
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(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] + right(side)
print(quick_sort(array))
퀵 정렬의 시간 복잡도 : O(NlogN)
최악의 경우 O(N²) 으로 데이터가 무작위로 입력되는 경우 퀵 정렬은 빠르게 동작할 확률이 높지만 '이미 데이터가 정렬되어 있는 경우'에는 매우 느리게 동작한다. (삽입정렬과 반대)
📚 계수 정렬Count Sort
별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는 알고리즘.
계수 정렬 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다.
'데이터의 크기 범위가 제한 되어 정수 형태로 표현할 수 있을 때' 만 사용할 수 있다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000 을 넘지 않을 때 효과적으로 사용할 수 있다.
1. 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성한다.
2. 처음에는 리스트의 모든 데이터가 0이 되도록 초기화한다.
3. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 계수정렬이 완료된다.
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
# 모든 범위를 포함하는 리스트 선언
count = [0] * (max(array) + 1)
for i in range(len(array)):
count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가
for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
for j in range(count[i]):
print(i, end = ' ')
N: 데이터 개수, K: 데이터 중 최댓값의 크기
계수 정렬의 시간 복잡도 : O(N + K)
계수 정렬의 공간 복잡도: O(N + K)
계수 정렬은 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리하며 항상 사용할 수는 없다.
⚡ [문제 1] 위에서 아래로
- 풀이시간: 10분
- 문제풀이
list = []
for _ in range(int(input())):
list.append(int(input()))
## 계수 정렬
def CountSort():
count = [0]* (max(list)+1)
for i in list:
count[i] += 1
for i in range(len(count)-1,0, -1):
for j in range(count[i]):
print(i, end=' ')
## 리스트 객체의 내장함수 sort()
def ListSort():
list.sort(reverse = True)
for i in list:
print(i, end = ' ')
## 파이썬 기본 정렬 라이브러리 sorted()
def SortLibaray():
global list
list = sorted(list, reverse = True)
for i in list:
print(i, end = ' ')
## 선택정렬
def SelectionSort():
for i in range(len(list)):
for j in range(i+1, len(list)):
if list[i] < list[j]:
list[i], list[j] = list[j], list[i]
for i in list:
print(i, end = ' ')
⚡ [문제 2] 성적이 낮은 순서로 학생 출력하기
- 풀이시간: 10분
- 문제풀이
## 파이썬 기본 정렬 라이브러리
n = int(input())
list = [(input().split()) for _ in range(n)]
def ScoreSort(list):
return int(list[1])
list = sorted(list, key = ScoreSort)
for i in list:
print(i[0], end = ' ')⚡ [문제 3] 두 배열의 원소 교체
- 풀이시간: 10분
- 문제풀이
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))
🐾 정리