[알고리즘 대비 - 이코테] 5. 정렬

정렬(Sorting)

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

선택 정렬(Selection Sort)

• 가장 작은 것을 선택해서 앞으로 보내는 과정을 반복 수행하는 방법

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

print(array)

시간복잡도

$$
O(N^2)
$$

 

---

삽입 정렬(Insertion Sort)

• 특정한 데이터를 적절한 위치에 삽입하는 방법
• 삽입을 수행하려는 데이터의 이전 데이터들은 모두 정렬되어 있다고 가정

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

# index 0은 이미 정렬되어있다고 가정(원소 수 1개)
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^2)
$$

• 현재의 데이터가 거의 정렬되어 있는 상태라면 최선의 경우 $O(N)$의 시간 복잡도를 가진다!

 

---

퀵 정렬(Quick Sort)

• 기준(pivot)을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방법

1. 피벗을 설정한다.
2. 일반적으로 첫 번째 원소를 피벗으로 지정
3. 왼쪽에서 부터 피벗보다 큰 데이터를 찾고, 오른쪽에서 피벗보다 작은 데이터를 찾는다.
4. 이후 큰 데이터와 작은 데이터의 위치를 서로 교환한다.

직관적 형태의 퀵 정렬

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

def quick_sort(array, start, end):
    if start >= end:  # 원소가 1개인 경우 종료
        return
    # left, right, pivot : 인덱스
    pivot = start  # 피벗은 첫 번째 원소
    left = start + 1
    right = end

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

 

파이썬 기반 퀵 정렬

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(N^2)
$$

-시간복잡도의 정의가 최악의 복잡도를 나타낸다.

• 평균적인 시간복잡도

$$
O(NlogN)
$$

분할 정복(Divide and Conque) 방법으로 문제를 해결하기 때문에 평균적으로는 $O(NlogN)$의 시간복잡도가 나온다.

 

📢 분할 정복? → 문제를 작은 문제로 쪼개어서 해결하는 것

퀵 정렬에서는 작은 문제로 쪼갤 경우 1/2로 줄어든다.

• 최악의 시간복잡도가 나오는 경우
  • 이미 정렬된 데이터(오름차순, 내림차순)에 대해 퀵 정렬을 수행할 때 발생
  • ∴ 이미 정렬된 데이터를 또 정렬할 경우에는 삽입 정렬을 이용하는 게 좋다!

 

---

계수 정렬(Count Sort)

• 특정한 조건이 부합할 때만 사용할 수 있는 매우 빠른 정렬 방법
• 데이터의 크기 범위가 제한 되어 정수 형태로 표현할 수 있을 때만 사용 가능
• 파이썬에서는 일반적으로 범위가 1,000,000 이하인 경우 효과적으로 작동
• 동일한 값을 가지는 데이터가 여러개 등장할 때 적합
• 비교 기반 정렬 알고리즘 ❌
  • 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다.

🌟 데이터의 크기가 한정적이고 크기가 많이 중복되어 있을 경우 유리하다!

1. 모든 범위를 담을 수 있는 크기의 리스트를 생성한다.
2. 데이터를 순회하며 모든 데이터들의 개수를 센다.
3. 마지막에 저장된 개수를 토대로 데이터들을 모두 출력한다.

# 모든 원소의 값이 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=' ')

시간복잡도

$$
O(K + N)
$$

 

---

Q1. 위에서 아래로

문제 설명

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

입력 조건

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

출력 조건

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

풀이

from sys import stdin
n = int(stdin.readline())
arr = []
for _ in range(n):
    arr.append(int(stdin.readline())) # arr에 정수를 입력받아, 저장

[print(i, end=' ') for i in sorted(arr, reverse=True)]

• sorted() 메서드를 이용해서 정렬 수행
  • 이때 파라미터 값으로 reverse = True 을 지정하여 역순으로 정렬한다.

 

---

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

문제 설명

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

입력 조건

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

출력 조건

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

풀이

from sys import stdin
n = int(stdin.readline())
arr = []
for _ in range(n):
    # arr에 이름, 점수를 입력받아 저장
    arr.append(stdin.readline().split())
    arr[-1][1] = int(arr[-1][1]) # 점수는 int 형으로 바꿔서 저장

[print(i[0], end=' ') for i in sorted(arr, key=lambda x: x[1])]

• sorted() 메서드의 파라미터 값으로 key=lamda x : x[1] 을 지정하여 점수순으로 정렬을 수행한다.

 

---

Q3. 두 배열의 원소 교체

문제 설명

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

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

예를 들어 N = 5, K = 3이고 배열 A와 B가 다음과 같다고 하자.

• 배열 A = [1, 2, 5, 4, 3]
• 배열 B = [5, 5, 6, 6, 5]

이 경우, 다음과 같이 세 번의 연산을 수행할 수 있다.

• 연산 1) 배열 A의 원소 ‘1’과 배열 B의 원소 ‘6’을 바꾸기
• 연산 2) 배열 A의 원소 ‘2’와 배열 B의 원소 ‘6’을 바꾸기
• 연산 3) 배열 A의 원소 ‘3’과 배열 B의 원소 ‘5’를 바꾸기

세 번의 연산 이후 배열 A와 배열 B의 상태는 다음과 같이 구성될 것이다.

• 배열 A = [6, 6, 5, 4, 5]
• 배열 B = [3, 5, 1, 2, 5]

이때 배열 A의 모든 원소의 합은 26이 되며, 이보다 더 합을 크게 만들 수는 없다. 따라서 이 예시의 정답은 26이 된다.

입력 조건

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

출력 조건

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

풀이

from sys import stdin
n, k = map(int, stdin.readline().split())

arr_A = list(map(int, stdin.readline().split()))
arr_B = list(map(int, stdin.readline().split()))

arr_A.sort()
arr_B.sort(reverse=True)

for i in range(k):
    if arr_A[i] > arr_B[i]:
        break
    arr_A[i], arr_B[i] = arr_B[i], arr_A[i]

print(sum(arr_A))

• 배열 A와 배열 B를 각각 입력받아 정렬 수행
  • 배열 A는 오름차순 정렬 sort()
  • 배열 B는 내림차순 정렬 sort(reverse=True)
• 반복문을 돌며 배열 A와 배열 B 비교
  • 배열 A의 원소가 배열 B의 원소보다 클 경우 반복문을 빠져나온다.
  • ∵ 더 이상 바꿔치기 연산을 수행할 필요가 없기 때문

 

 

---

해당 포스팅의 내용은

저)나동빈님의 『이것이 취업을 위한 코딩 테스트다 with 파이썬』을

통해 공부한 내용을 토대로 작성하였습니다.

이것이 취업을 위한 코딩 테스트다 with 파이썬

저자 | 나동빈

출판 | 한빛미디어

발매 | 2020.08.05.