📚 <이것이 코딩 테스트다> - 정렬

1. 기준에 따라 데이터를 정렬

정렬 : 데이터를 특정한 기준에 따라 순서대로 나열하는 것

선택 정렬

데이터가 무작위로 있을 때, 매번 가장 작은 것을 선택하여 앞으로 보내는 알고리즘

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] # swap

시간 복잡도 : O(N^2)
다른 정렬 알고리즘보다 비효율적이기는 하지만, 가장 작은 데이터를 찾는 과정은 코테에 많이 나오므로 익숙해질 필요가 있다.

삽입 정렬

특정한 데이터를 적절한 위치에 삽입한다는 의미
필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 훨씬 효율적임

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):
        if array[j] > array[j-1]:
            array[j], array[j-1] = array[j-1], array[j] # swap
        else: break

시간 복잡도 : O(N^2) -> 최선의 경우 O(N)

퀵 정렬

기준을 설정한 후 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 알고리즘
퀵 정렬에서는 피봇(pivot)이 사용됨 => 교환하기 위한 기준

리스트에서 첫 번째 데이터를 피봇으로 설정한다.
왼쪽과 오른쪽에서 이동하면서 두 수를 비교한 후 피봇보다 큰 수는 오른쪽, 작은 수는 왼쪽에 둔다.
두 값이 엇갈릴 때는 작은 데이터와 피봇의 위치를 서로 변경한다.
리스트의 개수가 1이 될 때까지 위 방식을 반복한다.

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

def quick_sort(array, start, end):
    if start >= end: 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]:
            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)

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] + quick_sort(right_side)

print(quick_sort(array))

퀵 정렬의 평균 시간복잡도 : O(NlogN) => 최악의 경우 O(N^2)
이미 데이터가 정렬되어 있는 경우 매우 느리게 동작 (삽입 정렬과 반대)
파이썬의 기본 정렬 라이브러리는 O(NlogN)을 보장한다.

계수 정렬

별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징
특정한 조건이 부합할 때만 사용할 수 있으나 매우 빠른 정렬 알고리즘
데이터의 개수가 N, 데이터 중 최댓값이 K일 때, 최악의 경우에도 O(N+K)를 보장한다.
단, 데이터의 크기 범위가 제한 되어 정수형태로 표현할 수 있을때만 사용 가능하다.
직접 데이터의 값을 비교한 뒤에 위치를 변경하며 정렬하는 방식이 아니다.

먼저 가장 큰 데이터와 작은 데이터의 범위가 모두 담길 수 있는 하나의 리스트를 생성한다.
데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 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=' ')

시간 복잡도 : O(N+K)
현존하는 정렬 알고리즘 중에서 기수 정렬과 더불어 가장 빠름
공간 복잡도 : O(N+K)
리스트의 크기가 100만을 넘지 않을 때가 좋다.

파이썬의 정렬 라이브러리

기본 정렬 라이브러리 : sorted() 함수, 리스트리 딕셔너리 등을 입력받아서 리스트로 반환함
정렬 알고리즘이 사용되는 경우
1. 정렬 라이브러리로 풀 수 있는 문제
2. 정렬 알고리즘의 원리에 대해 물어보는 문제 : 여러 정렬 알고리즘의 원리를 알고 있어야 한다
3. 더 빠른 정렬이 필요한 문제 : 기존 알고리즘의 구조적 개선 필요

2. 위에서 아래로

난이도 하

문제

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

해설

기본적인 정렬을 할 수 있는지 물어보는 문제이다. 기본 정렬 라이브러리를 이용하는 것이 효과적이다.

코드

n = int(input())
array = []

for i in range(n):
    array.append(int(input()))

array = sorted(array, reverse=True)
for i in array:
    print(i, end=' ')

3. 성적이 낮은 순서로 학생 출력하기

난이도 하

문제

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

해설

이 문제에서 학생 정보가 최대 10만개까지 입력되므로 계수 정렬을 이용하면 된다. 출력할 때는 이름만 출력하면 되므로 학생정보를 (점수, 이름)으로 묶은 뒤에 점수를 기준으로 정렬을 수행해야 한다.

n = int(input())
array = []

for i in range(n):
    input_data = input().split()
    array.append((input_data[0], input_data[1]))

array = sorted(array, key = lambda student: student[1])

for student in array:
    print(student[0], end=' ')

4. 두 배열의 원소 교체

난이도 하

문제

두 개의 배열 A, B는 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다. 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 A에 있는 원소 하나와 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다. 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이다.

N, K 그리고 배열 A, B의 정보가 주어졌을 때 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하시오.

해설

매번 배열 A에서 가장 작은 원소를 골라서 배열 B의 가장 큰 원소와 교체를 하는 것이다. 단, A의 가장 작은 원소가 B의 가장 큰 원소보다 작아야 한다. 이러한 과정을 K번 반복한다. 따라서 A는 오름차순, B는 내림차순으로 정렬한 후 첫 번째 인덱스부터 비교하면서 작을 때 교체를 수행한다. 최대 개수가 10만개이므로 O(NlogN)을 보장하는 정렬 알고리즘을 이용한다.

코드

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))