[코딩테스트] 정렬

JY·2022년 7월 1일

정렬 (Sorting)

: 연속된 데이터를 기준에 따라서 정렬하기 위한 알고리즘

정렬 알고리즘으로 데이터 정렬하면 이진 탐색이 가능 (이진탐색의 전처리 과정)
'알고리즘의 효율성' 이해 가능

선택 정렬

: 데이터가 무작위로 여러 개가 있을 때, 이 중 가장 작은 데이터를 선택해 맨 앞의 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복
=> 매번 '가장 작은 것'을 선택

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

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)

스와프: 특정 리스트가 주어졌을 때 두 변수의 위치를 변경하는 작업

#인덱스 0과 인덱스 1의 원소 교체하기
array = [3,5]
array[0], array[1] = array[1], array[0]

print(array)

선택 정렬의 시간 복잡도: $O(N^2)$
-> 2중 반복문 사용

삽입 정렬

: 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입
-> 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬 되어있다고 가정. 정렬 되어있는 데이터 리스트에서 적절한 위치를 찾은 뒤, 그 위치에 삽입

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)):
    for j in range (i, 0, -1): #인덱스의 i부터 1까지 감소하며 반복
        if array[j] < array [j-1]: 
            array[j], array[j-1] = array[j-1], array[j] #한 칸씩 왼쪽으로 이동
        else: #자기보다 작은 데이터를 만날 때
            break #그 위치에서 멈춤
    
print(array)

삽입 정렬의 시간 복잡도: $O(N^2)$
-> 2중 반복문 사용

퀵 정렬

: 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꿈

퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작 -> 피벗 사용
피벗: 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'
피벗을 어떻게 설정할 것인지에 따라 퀵 정렬 구분
퀵 정렬은 재귀 함수 형태로 작성했을 때 구현 간결
-> 퀵 정렬 끝나는 조건: 현재 리스트의 데이터 개수가 1개일 때
-> 이는 이미 정렬 되어있다고 간주, 분할 불가능

호어 분할 (Hoare Partition) : 리스트의 첫 번째 데이터를 피벗으로 설정
-> 왼쪽에서 부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터 찾기
-> 그 다음, 큰 데이터와 작은 데이터의 위치를 서로 교환
=> 이 결과는 피벗에 대한 정렬

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
    if start >= end:  #원소가 1개인 경우
        return  #종료
    pivot = start  #피벗은 첫 번째 원소
    left = start + 1
    right = end
    
    while left <= right:
        #피벗보다 큰 데이터를 찾을 때까지 반복
        while left <= end and array[left] <= array[pivot]:
            left += 1
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while right > start and array[right] >= array[pivot]:
            right -= 1
        if left > right: #엇갈렸다면
            array[right], array[pivot] = array[pivot], array[right] #작은데이터와 피벗 교체
        else: #엇갈리지 않았다면 
            array[left], array[right] = array[right], array[left]  # 작은데이터와 큰 데이터 교체
            
    #분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right-1)
    quick_sort(array, right+1, end)
    
quick_sort(array, 0, len(array)-1)
print(array)

python의 장점을 살린 퀵 정렬

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
    if len(array) <= 1:  #리스트가 하나 이하의 원소만을 담고 있다면
        return array  #종료
    pivot = array[0]  #피벗은 첫번째 원소
    tail = array[1:]  #피벗을 제외한 리스트 tail
    
    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)

print(quick_sort(array))

퀵 정렬의 시간 복잡도: $O(NlogN)$

계수 정렬

: 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘

계수 정렬의 시간 복잡도: $O(N +K)$ (데이터 개수: $N$ , 데이터 중 최댓값: $K$ )
계수 정렬의 공간 복잡도: $O(N +K)$
일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담음
먼저, 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트 생성
-> 처음에는 리스트의 모든 데이터가 0이 되도록 초기화
-> 그 다음 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킴
=> 결과적으로 리스트에는 각 데이터에 몇 번 등장했는지 횟수 기록

#모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5 ,9, 0, 3, 1, 6, 2, 9, 1, 4, 8,  0, 5, 2]
#모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
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=' ') #띄어쓰기를 구분으로 드앙한 횟수만큼 인덱스 출력

파이썬 정렬 라이브러리

sorted() : 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어짐
-> sorted() 함수는 리스트, 딕셔너리 자료형 등을 입력 받아 결과 출력

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

result = sorted(array)
print(result)

sort(): 리스트 변수가 하나 있을 때, 내부 원소 바로 정렬
-> 별도의 정렬된 리스트가 반환되지 않고, 내부 원소가 바로 정렬

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

array.sort()
print(array)

key 매개변수 활용
-> key 값으로 하나의 함수가 들어가야하며 이는 정렬의 기준

array = [('바나나', 2), ('사과', 5), ('당근', 3)]

def setting(data):
    return data[1]
    
result = sorted(array, key=setting)
print(result)

정렬 라이브러리 시간 복잡도: $O(NlogN)$

코딩테스트에서 정렬 알고리즘이 사용되는 경우

정렬 라이브러리로 풀 수 있는 문제: 단순히 정렬 기법을 알고 있는지 물어보는 문제로 기본 정렬 라이브러리의 사용 방법을 숙지하고 있으면 어렵지 않게 풀 수 있음

정렬 알고리즘의 원리에 대해서 물어보는 문제: 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 풀 수 있음

더 빠른 정렬이 필요한 문제: 퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용해서 문제에서 기존의 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있음

실전문제

Ex1) 위에서 아래로

하나의 수열에는 다양한 수가 존재한다. 이러한 수는 크기에 상관없이 나열되어 있다. 이 수를 큰 수부터 작은 수의 순서로 정렬해야 한다. 수열을 내림차순으로 정렬하는 프로그램을 만드시오.

sol) 기본적인 정렬 가능한지 묻는 문제, 수의 개수가 적기 때문에 어떠한 정렬 알고리즘 사용해도 무방 but 코드가 간결해지는 파이썬 기본 정렬 라이브러리 사용하는 것이 효과적

입력조건
- 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다. (1 $\leq$ N $\leq$ 500)
- 둘째 줄부터 N+1번째 줄까지 N개의 수가 입력된다. 수의 범위는 1 이상 100,000 이하의 자연수이다.

출력조건
- 입력으로 주어진 수열이 내림차순으로 정렬된 결과를 공백으로 구분하여 출력한다. 동일한 수의 순서는 자유롭게 출력해도 괜찮다.

n = int(input())  #N 입력 받기

array = []
for i in range(n):  #N개의 정수 입력 받아 리스트에 저장
    array.append((int(input())))
    
#파이썬 기본 정렬 라이브러리 이용하여 정렬 수행
array = sorted(array, reverse=True) 

for i in array:
    print(i, end=' ')  #정렬이 수행된 결과 출력

Ex2) 성적이 낮은 순서로 학생 출력하기

N명의 학생 정보가 있다. 학생 정보는 학생의 이름과 학생의 성적으로 구분된다. 각 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오.

sol) 학생의 정보가 최대 100,000개까지 입력될 수 있으므로 최악의 경우 $O(NlogN)$ 을 보장하는 알고리즘 또는 $O(N)$ 을 보장하는 계수정렬 이용
학생 정보를 (이름, 점수)로 묶은 뒤 점수를 기준으로 정렬 수행
-> 파이썬 튜플 문법 이용하여 파이썬 기본 정렬 라이브러리 이용하는 것이 효과적

입력조건
- 첫째 줄에 학생의 수 N이 입력된다. (1 $\leq$ N $\leq$ 100,000)
- 둘째 줄부터 N+1번째 줄에는 학생의 이름을 나타내는 문자열 A와 학생의 성적을 나타내는 정수 B가 공백으로 구분되어 입력된다. 문자열 A의 길이와 학생의 성적은 100 이하의 자연수이다.

출력조건
- 모든 학생의 이름을 성적이 낮은 순서대로 출력한다. 성적이 동일한 학생들의 순서는 자유롭게 출력해도 괜찮다.

n = int(input())  #N 입력 받기

array = []
for i in range(n):  #N명의 학생 정보 입력 받아 리스트에 저장
    input_data = input().split()
    #이름은 문자열 그대로, 점수는 정수형을 변환하여 저장
    array.append((input_data[0], int(input_data[1])))

#키를 이용하여 정수를 기준으로 정렬
array = sorted(array, key = lambda student: student[1])

for student in array:
    print(student[0], end=' ')  #정렬이 수행된 결과 출력

Ex3) 두 배열의 원소 교체

동빈이는 두 개의 배열 A, B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다. 동빈이는 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다. 동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이며, 여러분은 동빈이를 도와야한다.
N, K 그리고 배열 A, B의 정보가 주어졌을 때, 최대 K번 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하시오.

sol) 매번 배열 A에서 가장 작은 원소를 골라서, 배열 B에서 가장 큰 원소와 교체
-> 단, 배열 A에서 가장 작은 원소가 배열 B에서의 가장 큰 원소보다 작을 때에만 교체 수행 가능. 이러한 과정을 K번 반복
배열 A의 원소를 오름차순으로 정렬, 배열 B의 원소를 내림차순으로 정렬
->두 배열의 원소를 가장 첫 번째 인덱스부터 차례로 비교하여 A의 원소가 B의 원소보다 작을 때에만 교체 수행.
두 배열의 원소가 최대 100,000개까지 입력 가능
-> $O(NlogN)$ 보장하는 정렬 알고리즘 사용

입력조건
- 첫 번째 줄에 N, K가 공백으로 구분되어 입력된다. (1 $\leq$ N $\leq$ 100,000, 0 $\leq$ K $\leq$ N)
- 두 번째 줄에 배열 A의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수이다.
- 세 번째 줄에 배열 B의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수이다.

출력조건
- 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력한다.

n, k = map(int, input().split())  #N,K 입력 받기
a = list(map(int,  input().split())) #배열 A 모든 원소 입력 받기
b = list(map(int,  input().split())) #배열 B 모든 원소 입력 받기

a.sort()  #배열 A 오름차순 정렬
b.sort(reverse=True)  #배열 B 내림차순 정렬

for i in range(k): #첫번째 인덱스부터 두 배열의 원소를 최대 K번 비교
    if a[i] < b[i]: #A의 원소가 B의 원소보다 작을 경우
        a[i], b[i] = b[i], a[i] #두 원소 교체
    else: #A의 원소가 B의 원소보다 크거나 같을 때
        break  #반복문 탈출

print(sum(a))  #배열 A의 모든 원소의 합 출력

기출문제

Q23 국영수

도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어집니다. 이 때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오.

국어점수가 감소하는 순서로

국어 점수가 같으면 영어 점수가 증가하는 순서로

국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로

모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키코드에서 대문자는 소문자보다 작으므로 사전 순으로 앞으로 옵니다)

sol) 학생 정보를 튜플을 원소로 하는 리스트로 만들고 리스트를 정렬한다.
리스트의 원소를 정렬할 때 sort() 함수의 key 속성에 값을 대입하여 원하는 조건에 맞게 튜플 정렬 시킨다.
sort(key=lambda x: (-int(x[1]), int(x[2]), -int(x[3]), x[0]))

입력조건
- 첫째 줄에 도현이네 반의 학생 수 N이 입력됩니다. (1 $\leq$ N $\leq$ 100,000)
- 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어집니다.
- 점수는 1보다 크거나 같고, 100보다 작거나 같은 자연수입니다.
- 이름은 알파벳 대소문자로 이루어진 문자열이고, 길이는 10자리를 넘지 않습니다.

출력조건
- 문제에 나와 있는 정렬 기준으로 정렬한 후 첫째줄부터 N개의 줄에 걸쳐 각 학생의 이름을 출력합니다.

n = int(input())  #N 입력 받기
students = []  #학생 정보를 담을 리스트

for _ in range(n):  #모든 학생 정보를 입력받기
    students.append(input().split())

'''
[정렬기준]
1) 두 번쨰 원소를 기준으로 내림차순 정렬
2_ 두 번쨰 원소가 같은 경우, 세 번째 원소를 기준으로 오름차순 정렬
3) 세 번째 원소가 같은 경우, 네 번째 원소를 기준으로 내림차순 정렬
4) 네 번째 원소가 같은 경우, 첫 번째 원소를 기준으로 오름차순 정렬
'''
students.sort(key=lambda x: (-int(x[1]), int(x[2]), -int(x[3]), x[0]))

for student in students:
    print(student[0])

입력

12
Junkyu 50 60 100
Sangkeun 80 60 50
Sunyoung 80 70 100
Soong 50 60 90
Haebin 50 60 100
Kangsoo 60 80 100
Donghyuk 80 60 100
Sei 70 70 70
Wonseob 70 70 90
Sanghyun 70 70 80
nsj 80 80 80
Taehwan 50 60 90

출력

Donghyuk
Sangkeun
Sunyoung
nsj
Wonseob
Sanghyun
Sei
Kangsoo
Haebin
Junkyu
Soong
Taehwan