정렬 with 파이썬
1. 개요
정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나이다. 파이썬에서는 특정한 리스트의 원소를 뒤집는 메서드를 제공하기 때문에 내림차순 정렬은 오름차순 정렬을 수행한 뒤에 결과를 뒤집기하여 만들 수 있다. 리스트를 뒤집는 연산은 O(N)의 복잡도로 간단히 수행할 수 있다.
2. 선택 정렬
이 방법은 가장 원시적인 방법으로 매번 가장 작은 것을 선택해서 정렬한다는 의미에서 선택 정렬이다.
a = [7,5,9,0,3,1,6,2,4,8]
n =len(a)
for i in range(n-1):
min = i
for j in range(i+1,n):
if a[min]>a[j]:
min = j
a[i],a[min] = a[min],a[i]
print(a)
위와 같이 선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정을 n-1번 하면 정렬이 완료되는 것을 알 수 있다. 마지막은 자동으로 제자리를 찾아가기 때문이다.
시간 복잡도
선택 정렬은 n-1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야하고 매번 가장 작은 수를 찾기 위해 비교 연산이 필요하다. 따라서 연산 횟수는 N + (N-1) + …. +2 로 볼 수있으므로 O(N^2)이다. 직관적으로 이해하자면, 소스코드상 간단한 2중 반복문이 사용되었기 때문이라고 이해해도 좋다.
선택 정렬은 기본 정렬 라이브러리를 포함해 다른 알고리즘과 비교했을 때 매우 비효율적이므로 코딩 테스트에서 사용하기에는 적절치 못하다.
3. 삽입 정렬
삽입 정렬은 선택 정렬에 비해 구현 난이도가 약간 높지만 실행 시간 측면에서 더 효율적인 알고리즘으로 알려져 있다. 특히 삽입 정렬은 필요할 때만 위치를 바꾸므로 ‘데이터가 거의 정렬 되어 있을때’ 매우 효율적이다. 삽입 정렬은 두 번째 데이터부터 시작한다. 왜냐하면 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문이다.
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부터 1까지 1씩 감소하며 반복하는 문법
if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동
array[j], array[j - 1] = array[j - 1], array[j]
else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
break
print(array)
시간 복잡도
선택 정렬과 마찬가지로 반복문이 2번 중첩되어 있으므로 시간 복잡도는 O(N^2)이라고 직관적으로 이해할 수 있다. 여기서 꼭 기억해야할 내용은 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다는 점이다. 최선의 경우, 즉 이미 정렬이 되어있는 경우는 비교만 해보고 끝나므로 O(N)의 시간 복잡도를 가진다. 이미 정렬되어 있는 경우에는 퀵 정렬보다 더 강력하다는 것을 기억하자.
4. 퀵 정렬
퀵 정렬은 정렬 알고리즘 중에서 가장 많이 사용되는 알고리즘이다. 퀵 정렬과 비교할 만큼 빠른 알고리즘은 병합 정렬 알고리즘이 있다. 퀵 정렬은 피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러 가지 방식으로 구분되는데 가장 대표적으로는 호어 분할 방식이 있다. 호어 분할 방식은 피벗을 리스트의 첫 데이터로 설정하는 것이다.
a = [5,7,9,0,3,1,6,2,4,8]
def quick_sort(a):
if len(a)<=1:
return a
pivot = a[0]
tail = a[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)
# list(pivot) 은 불가능,, 원소가 하나인 것을 list로 형변환 불가능하다.
print(quick_sort(a))
위와 같이 코딩하면 시간 면에서는 조금 비효율적이나 직관적이고 이해하기 쉽다. 하지만 피벗설정으로 인한 최악의 경우 O(N^2)이 된다. 위와 같이 사용해도 좋지만 피벗 설정을 조금 다듬어 보자. 자세한 내용 클릭
a = [5,7,9,0,3,1,6,2,4,8]
def mid(a,idx1,idx2,idx3):
if a[idx1]>a[idx2] :
a[idx1],a[idx2] = a[idx2],a[idx1]
if a[idx1]>a[idx3] :
a[idx1],a[idx3]=a[idx3],a[idx1]
if a[idx2]>a[idx3] :
a[idx2],a[idx3]=a[idx3],a[idx2]
return idx2
def quick_sort(a):
def quick(a,left,right):
midx = mid(a,left,(left+right)//2,right)
a[midx],a[right-1]=a[right-1],a[midx]
pivot = a[right-1]
pl = left+1
pr = right -2
while pr>=pl:
while a[pl]<pivot:pl+=1
while a[pr]>pivot:pr-=1
if pl<=pr:
a[pl],a[pr]=a[pr],a[pl]
if left < pr: quick(a,left,pr) # left >=pr 이면 그 구간은 이미 정렬이 끝난 상태
if pl < right : quick(a,pl,right) # right <= pl이면 그 구간은 이미 정렬이 끝난 상태
n=len(a)
quick(a,0,n-1)
quick_sort(a)
print(a)
시간 복잡도
퀵 정렬의 평균 시간 복잡도는 O(NlogN)이고 최악의 경우 O(N^2)이다. 데이터가 무작위로 입력되는 경우 퀵 정렬은 빠르게 동작할 확률이 놓다. 하지만 피벗을 가장 왼쪽 데이터로 정한다고 가정했을 때 이미 정렬이 되어 있는 경우라면 매우 느리게 작동하게 된다. 삽입 정렬과는 반대의 양상을 보이게 된다.
5. 계수 정렬
계수 정렬 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다. 모든 데이터가 양의 정수인 상황을 가정해보자. 데이터의 개수가 N, 데이터 중 최댓값이 K일 때, 계수 정렬은 최악의 경우에도 O(N+K)를 보장한다. 다만, 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능하다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적이다. 왜냐하면 계수 정렬을 이용할 때는 모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언해야 하기 때문이다. 예를 들어 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000이라면 총 1,000,001개의 데이터가 들어갈 수 있는 리스트를 초기화 해야 한다. 계수 정렬은 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리하며 항상 사용할 수 없다는 것을 기억하자.
a = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
count = [0]*(max(a)+1)
for i in a:
count[i]+=1
for i in range(len(count)):
for _ in range(count[i]):
print(i,end=" ")
# 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9
시간 복잡도
모든 데이터가 양의 정수인 상황에서 데이터의 개수 N, 데이터 중 최댓값의 크기를 K라고 할 때, 시간 복잡도는 O(N+K)이다. 계수 정렬은 앞에서부터 데이터를 하나씩 확인하면서 리스트에서 적절한 인덱스의 값을 1씩 증가시킬 뿐만 아니라, 이후에 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최댓값의 크기만큼 반복을 수행해야하기 때문이다.
공간 복잡도
계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있다. 예를 들어 데이터가 0과 999,999 단 2개만 있다고 가정한다면 이 때 리스트의 크기가 100만 개가 되도록 선언해야 한다. 따라서 항상 사용할 수 있는 알고리즘이 아니며, 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하다. 예를 들면 학생들의 성적과 같이 말이다. 반면 앞서 설명한 퀵 정렬은 일반적인 경우에서 평균적으로 빠르게 동작하기 때문에 데이터의 특성을 파악하기 어렵다면 퀵 정렬을 이용하자.
6. 정렬 라이브러리
정렬 알고리즘의 경우 직접 구현해야하는 경우도 있지만 미리 만들어진 라이브러리를 이용하는 것이 효과적인 경우가 더 많다. 파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다. sorted()는 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어 졌는데, 병합 정렬은 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다는 특징이 있다. 이러한 sorted() 함수는 리스트, 딕셔너리 자료형 등을 입력받아서 정렬된 결과를 리스트 자료형으로 반환 한다. reverse=True 입력시 정렬 후 역순으로 반환한다.
a = [7,5,9,0,3,1,6,2,4,8]
result = sorted(a)
print(result) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
result = sorted(a,reverse=True)
print(result) # [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
리스트의 변수가 하나 있을 때 내부 원소를 바로 정렬할 수도 있다. 리스트 객체의 내장 함수인 sort()를 이용하는 것인데, 이는 별도의 정렬된 리스트가 반환되지 않고 내부 원소가 바로 정렬된다는 특징이 sorted()와 다른 점이다.
a = [7,5,9,0,3,1,6,2,4,8]
a.sort()
print(a) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sorted()나 sort()를 이용할 때에는 key 매개변수를 입력으로 받을 수 있다. key 값으로는 하나의 함수가 들어가야 하며 이는 정렬 기준이 된다. 예를 들어 리스트의 데이터가 튜플로 구성되어 있다면, 각 데이터의 두 번째 원소를 기준으로 정렬하는 경우는 다음과 같다.
a = [('바나나',2),('사과',5),('당근',3)]
result = sorted(a,key = lambda x:x[1])
print(result) # [('바나나', 2), ('당근', 3), ('사과', 5)]
sorted, sort함수 모두 기본적으로 오름차순을 기준으로 한다. reverse=True 를 사용하면 쉽게 내림차순으로 바꿀 수 있지만 섬세한 조정은 다음과 같이 쉽게 할 수 있다.
a = [(1, 3), (0, 3), (1, 4), (1, 5), (0, 1), (2, 4)]
result = sorted(a, key = lambda x : (x[0], -x[1]))
print(result)
# [(0, 3), (0, 1), (1, 5), (1, 4), (1, 3), (2, 4)]
첫 정렬은 첫 데이터로 오름차순, 두 번째 정렬은 두 번째 데이터로 내림차순
-부호를 붙이면 제일 큰 수는 제일 작은 수가 되므로 오름차순을 하면 내림차순이 된다.
시간 복잡도
정렬 라이브러리는 항상 최악의 경우에도 O(NlogN)을 보장한다. 사실 정렬 라이브러리는 이미 잘 작성된 함수이므로 우리가 직접 퀸 정렬을 구현할 때보다 더욱더 효과적이다. 따라서 문제에서 별도의 요구가 없다면 단순히 정렬해야 하는 상황에서는 기본 라이브러리를 사용하고, 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 할 때는 계수 정렬을 사용하자.
코딩 테스트의 정렬 알고리즘 유형은 다음과 같다.
- 정렬 라이브러리로 푸는 문제 : 단순히 정렬 기법을 알고 있는지 물어보는 문제로 기본 정렬 라이브러리 사용 방법만 숙지하고 있으면 풀 수 있다.
- 정렬 알고리즘 원리에 대해서 물어보는 문제 : 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 문제를 풀 수 있다.
- 더 빠른 정렬이 필요한 문제 : 퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있다.
7. 실전 문제
문제 : 위에서 아래로
하나의 수열에는 다양한 수가 존재하고 크기에 상관없이 나열되어 있다. 큰 수부터 작은 수의 순서로 정렬해야 할때 내림차순으로 정렬하는 프로그램을 만드시오.
입력 조건
- 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다 (1<= N <= 500)
- 둘째 줄부터 N+1번째 줄까지 N의 개수가 입력된다. 범위는 1이상 100,000이하의 자연수
출력 조건
- 입력으로 주어진 수열이 내림차순으로 정렬된 결과를 공백으로 구분하여 출력하며 동일한 수의 순서는 상관 없다.
입력 예시
3
15
27
12
출력 예시
27 15 12
풀이
N = int(input())
arr =[]
for i in range(N):
arr.append(int(input()))
arr.sort(reverse=True)
for i in range(N):
print(arr[i],end=" ")
문제 : 성적이 낮은 순서로 학생 출력하기
N명의 학생 정보가 있다. 학생 정보는 학생의 이름과 학생의 성적으로 구분된다. 각 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오.
입력 조건
- 첫 번째 줄에 학생의 수 N입력 (1~100,000)
- 두 번째 줄부터 N+1번째 줄에는 학생의 이름을 나타내는 문자열 A와 학생의 성적을 나타내는 정수 B가 공백으로 구분되어 입력된다. 문자열 A의 길이와 학생의 성적은 100이하의 자연수이다.
출력 조건
- 모든 학생의 이름을 성적이 낮은 순서대로 출력한다. 성적이 동일한 학생들의 순서는 자유롭게 한다.
입력 예시
2
홍길동 95
이순신 77
출력 예시
이순신 홍길동
풀이
N = int(input())
arr =[]
for i in range(N):
data = input().split()
arr.append((data[0],int(data[1])))
arr.sort(key=lambda x:x[1] )
for student in arr:
print(student[0],end=" ")
문제 : 두 배열의 원소 교체
캐릭터가 두 개의 배열 A,B를 가지고 있고 배열은 N개의 원소로 구성되며 모두 자연수이다. 캐릭터는 최대 K번의 바꿔치기 연산을 수행하여 배열 A의 모든 원소의 합이 최대값이 되도록 하려고 한다. 배열 A의 모든 원소 합의 최댓값을 출력하시오.
입력 조건
- 첫 번째 줄에는 N,K가 공백으로 구분되어 입력 (1<=N<=100,000 , 0<=K<=N)
- 두 번째 줄에 배열 A의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수이다.
- 세 번째 줄에 배열 B의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수이다.
출력 조건
- 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력한다.
입력 예시
5 3
1 2 5 4 3
5 5 6 6 5
출력 예시
26
풀이
import sys
input = sys.stdin.readline
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))
