정렬 알고리즘✍
정렬이란 특정 조건에 맞추어 주어진 데이터를 순서대로 나열하는 것을 의미한다. 우리에게 가장 익숙한 정렬이라면 아마 랜덤하게 주어진 숫자를 오름차순 혹은 내림차순으로 정리하는 정렬일 것이다. 정렬 알고리즘에는 정말 다양한 종류가 존재한다. 삽입정렬, 선택정렬, 퀵정렬, 계수정렬, 병합정렬, 힙정렬 등등.
- 선택정렬: 가장 작은 데이터를 찾아내어 현재 가르키고 있는 데이터와 자리를 바꾸어 나가면서 진행하는 정렬 방식. 시간복잡도는 O(N**2)에 해당한다.
- 삽입정렬: 현재 가르키고 있는 데이터를 앞서 이미 정렬된 데이터들 사이 올바른 위치에 삽입하여 정렬을 진행하는 방식. 시간복잡도는 O(N**2)으로 선택정렬과 같으나 선택정렬보다는 조금 빠르다. 또한 데이터들이 이미 정렬이 되어 있는 경우에는 O(N)에 해당하는 시간복잡도가 나타난다.
- 퀵정렬: 퀵정렬에는 pivot(기준값)이라는 개념이 도입된다. 대개 pivot은 정렬할 데이터들의 첫번째 값으로 지정된다. 정렬할 데이터들을 양방향에서 탐색하면서 오른쪽에서는 pivot보다 작은 값(x)을, 왼쪽에서는 pivot보다 큰 값(y)을 찾아 자리를 바꿔주는 과정을 반복하는 방식이다. 하지만 어느 순간 x와 y가 교차되는 경우가 발생하는데, 이때는 pivot과 x의 자리를 바꿔줘야 하고 비로소 분할이 이루어지게 된다. 분할이 이루어지면, pivot를 기준으로 왼쪽에는 pivot보다 작은 값들이, 오른쪽에는 큰 값들이 위치하기 때문에 각각을 독립적인 데이터셋으로 보고 다시 퀵정렬을 진행하면 된다. 그리고 데이터셋 내 데이터가 하나만 존재한다면, 그 데이터셋은 정렬이 끝났다고 이야기할 수 있다. 퀵정렬의 경우 평균시간복잡도가 O(NlogN)에 해당하는데, 삽입정렬과는 반대로 이미 정렬이 거의 진행된 데이터셋이 들어온다면 오히려 O(N**2)에 해당하는 시간복잡도가 발생하기도 한다.
- 계수정렬: 개인적으로 가장 색다른 방식의 정렬. 데이터의 범위가 한정되었을 사용할 수 있는 정렬방식으로 겹치는 데이터가 많을 때 좋다.
예를 들어 성적순으로 정렬한다고 하면 보통 0부터 100까지의 수들로 이루어져 있게된다. 그러면 인덱스 값이 0부터 100(최댓값K)까지 포함하는 하나의 리스트를 만들어서, 해당 점수가 들어오면 그 인덱스에 해당하는 리스트 값을 하나씩 증가시키는 방식이다. 모든 점수들을 적용하고 나면 그 리스트를 앞에서부터 탐색하여 값에 들어가있는 횟수만큼 인덱스를 반복하여 출력하면 결국 정렬이 되는 것이다.
해당 알고리즘은 사용할 수 있는 범위가 제한적이지만, 그 조건만 갖춘다면 O(N+K)로 앞서 언급된 정렬 알고리즘들에 비해 매우 적은 시간이 걸리는 알고리즘인 셈이다.
표준 라이브러리에서의 정렬 알고리즘
일반적으로 각 프로그래밍 언어에서 표준 라이브러리에서 사용되는 정렬알고리즘은 퀵정렬이나 병합정렬이라고 한다. 퀵정렬은 최악의 경우, 그 시간복잡도가 O(N** 2)이 되지만, 표준 라이브러리에서는 그 경우를 알아서 제어해서, 최악의 경우에도 O(NlogN)의 시간복잡도를 보장한다고 한다. 그렇기 때문에 문제 상에서 직접 정렬 알고리즘을 짜도록 유도하는 것이 아니라면 각 프로그래밍 언어에서 제공하는 정렬 메소드 등을 사용하는 것이 효율적이다.
파이썬에서의 정렬 메소드
파이썬에는 두 가지의 정렬 메소드가 존재한다. 하나는 sort()이고 하나는 sorted()인데 두 가지 메소드에는 공통점과 차이점이 모두 존재한다.
1. 공통점
- 기본값으로 오름차순 정렬을 제공한다. 하지만 reverse=True를 인자로 넘겨서 내림차순 정렬로 만들 수 있다.
- 인자로 key=특정 함수를 받아 key를 기준으로 정렬할 수 있다. 즉, 정렬할 기준을 마음대로 정할 수 있는 셈이다. 그리고 이 기능이 특정 조건에 맞추어 정렬을 진행하기 위한 핵심이기도 하다. 가장 많이 사용하는 방법은 lambda 함수를 '특정 함수' 부분에 삽입하는 것이다.
코드 해설: 여기서 key=lambda x:-x를 통해 a가 내림차순으로 정렬된 것을 확인할 수 있다 . 내림차순으로 정렬된 이유는 a의 각 데이터들에 대해 해당 값에 마이너스를 씌웠을 때를 기준으로 정렬했기 때문이다.a=[2,4,6,4,8,5,2] a.sort(key=lambda x:-x) print(a) >> [8, 6, 5, 4, 4, 2, 2]
2. 차이점
- sorted()의 겨우에는 원본을 바꾸지 않는다. 즉, 위의 a를 예시로 들자면 a.sorted()를 해도 a는 그대로 [2,4,6,4,8,5,2] 일 것이라는 말이다. 정렬된 결과물을 확인하기 위해서는 a.sorted()를 새로운 변수에 저장해줘야 한다. 다시 말해, b=a.sorted()와 같은 과정이 필요한 것이다. 그리고, sorted()의 경우에는 iterable한 데이터 타입에 대해서도(ex. 튜플, 사전) 사용이 가능하다.
- sort()는 sorted()의 반대라고 할 수 있다. sort()는 위의 예시에서 볼 수 있듯이 데이터 자체를 바꿔버린다. 즉, a.sort()를 하면 a에는 더이상 원본이 남아있지 않고, 정렬된 그 결과물이 자리하게 되는 셈이다. 그리고 iterable한 데이터 타입에는 사용이 불가능하다.
백준 10825번: 국영수📖
오늘은 정렬 알고리즘을 복습했다. 책을 먼저 읽고, 이코테 강의도 봤다. 그리고선 유형별 기출문제를 풀기 시작했는데 이 문제가 첫 번째 문제였다. 사실 이전에도 여러번 본 적 있는 문제였다. 다만 그때마다 정렬 조건이 너무 까다로워 보여서 번번히 넘겨버렸었다. 하지만 이젠 더 이상 넘길 수가 없어서 문제를 꼼꼼히 읽고 풀기 시작했다.
접근방식🤯
정말 막막했다. 도대체 어떻게 순차적으로 각 조건에 맞춰서 정렬을 해야 하는지 감이 잡히지 않았다. 특히 앞 점수가 동일할 경우라는 조건이 제일... 제일 싫었다. 그래도 풀어야겠다는 생각에 다음과 같은 코드를 작성했었다.
def sorting(a,b,start,index,scores):
while index<len(students):
if students[index][a]==students[index-1][a]:
scores.append(students[index])
else:
if b==2:
scores.sort(key=lambda score:score[b])
elif b==3:
scores.sort(reverse=True, key=lambda score:score[b])
students[start:start+len(scores)]=scores
scores.clear()
scores=[students[index]]
start=index
index+=1
if b==2:
scores.sort(key=lambda score:score[b])
elif b==3:
scores.sort(reverse=True, key=lambda score:score[b])
students[start:start+len(scores)]=scores
n=int(input())
students=[]
for i in range(n):
name,kor,eng,math=input().split()
students.append((name,int(kor),int(eng),int(math)))
students.sort(reverse=True, key=lambda score:score[1])
sorting(1,2,0,1,[students[0]])
sorting(2,3,0,1,[students[0]])-해당코드는 틀린코드입니다-
다시 봐도 참 복잡하다... 이 코드로 수학 점수까지 정렬하는 것은 성공했으나 도저히 국어, 영어, 수학 점수가 같을 때 이름을 정렬하는 것은 해결할수가 없었다. 그렇게 약 1시간 이상을 헤매었을까... 도저히 이러다간 저녁을 못 먹겠다 싶어서 해설을 펼쳤는데... 웬걸 너무 간단해서 허탈할 정도였다.
해설 내 핵심💡
이코테 책 내 국영수 해설에 따르면, 파이썬에서는 튜플을 원소로 하는 리스트가 있을 때, 그 리스트를 정렬하면 기본적으로 각 튜플을 구성하는 원소의 순서에 맞게 정렬된다는 특징이 있다는 것이다. 예까지 인용하자면 아래와 같다.
예를 들어 튜플이 3개의 원소로 구성된다면, 모든 원소가 첫 번째 원소의 순서에 맞게 정렬되고, 첫 번째 원소의 값이 같은 경우 두 번째 원소의 순서에 맞게 정렬되고, 거기에 두 번째 원소의 값까지 같은 경우 세 번째 원소의 순서에 맞게 정렬된다.
-이코테 책 인용-
즉 다시 말해, 이를 이용하면 첫 번째 원소의 값이 같은지 다른지를 비교할 필요가 없다는 것이다. 정말이지 너무 반가운 설명이었다. 이를 이용하고, 앞서 설명했던 것처럼 sort()함수에 key를 통해 특정 조건을 적용하여 정렬할 수 있다는 점을 이용하면 이 문제를 간단하게 풀 수 있는 셈이다. 이를 코드로 풀명 다음과 같다.
#백준 10825번 국영수 핵심코드
#학생들의 이름과 점수들을 튜플로 묶어서 students라는 리스트에 삽입했다고 가정하자.
students.sort(key=lambda x:(-x[1],x[2],-x[3],x[0]))마무리(주저리)👋
처음으로 공부한 걸 제대로 복기해보는 것 같다. 쓰다보디 괜히 욕심도 생격서 길게 쓰게 되었는데, 나름대로 만족스럽다. 정렬 알고리즘은 기본 중에 기본이라고 한다. 코딩테스트에는 정렬 알고리즘을 작성하는 문제보다는 활용하는 문제가 더 많이 나온다고 하지만(왜냐하면 다른 알고리즘에 필요한 경우가 많아서) 기술면접 등에서 잘 출제되는 문제라고 하니, 잘 새겨두어야겠다!
