[ 이것이 코딩 테스트다 ] 4. 정렬

정렬 (Sorting)

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

다음 장에서 배울 이진 탐색의 전처리 과정이니 제대로 학습하자.

 

 

선택 정렬 (Selection Sort)

데이터 중에서 가장 작은 데이터를 선택해서 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다. 

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까지 감소하며 반복
		if array[j] < array[j-1]: # 한 칸씩 왼쪽으로 이동
			array[j], array[j-1] = array[j-1], array[j]
		else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
			break

print(array)

 

선택 정렬의 시간복잡도 : O(N**2) 

직관적으로, 2중 반복문이 사용되었기 때문이라고 볼 수 있다.

다른 알고리즘에 비해 매우 비효율적이지만, 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에 잦다.

 

 

삽입 정렬 (Inerstion Sort)

특정한 데이터를 적절한 위치에 삽입한다. 그리고 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 삽입 정렬이 이루어진 원소는 항상 오름차순을 유지한다.

# 삽입 정렬 예제
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]
    else:
      # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
      break

print(array)

 

삽입 정렬의 시간복잡도 : O(N**2) 

선택 정렬과 비슷한 시간이 소요되지만 삽입 정렬은 리스트의 데이터가 거의 정렬되어 있다면 매우 빠르게 작동한다. 최선의 경우 O(N)의 시간 복잡도를 가진다. 보통, 퀵 정렬보다 비효율적이지만 정렬이 거의 되어 있는 상황에서는 퀵 정렬 알고리즘보다 강력하다, 

 

 

퀵 정렬 (Quick Sort)

퀵 정렬과 병합 정렬 알고리즘은 가장 빠르고 많이 사용되는 정렬 라이브러리 근간이 되는 알고리즘이다.

맨앞의 값을 피벗으로 설정하고 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 그 다음 큰 데이터와 작은 데이터 위치를 서로 교환해준다. 만약, 왼쪽에서 찾는 값과 오른쪽에서 찾는 값의 위치가 엇갈렸다면 '작은 데이터'와 '피벗'의 위치를 서로 변경하고, 이를 반복한다.

array = [5, 7, 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)

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) 

앞의 두 정렬 알고리즘에 비해 매우 빠르다. 데이터 개수가 많을수록 차이는 극명해지고 데이터가 무작위로 입력된다면 일반적으로 퀵 정렬이 빠르게 동작할 확률이 높다. 하지만, 삽입 정렬과 반대로, 데이터가 정렬되어 있는 경우에는 매우 느리게 동작한다.

 

 

계수 정렬 (Count Sort)

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

다만, 데이터 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용할 수 있다. 계수정렬은 모든 범위를 담을 수 있는 리스트(배열)을 선언하기 때문이다. 예를 들어 0 이상 100 이하인 성적 데이터를 정렬할 때, 계수 정렬이 효과적이다. 

# 모든 원소의 값이 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(N+K) 

앞의 두 정렬 알고리즘에 비해 매우 빠르다. 데이터 개수가 많을수록 차이는 극명해지고 데이터가 무작위로 입력된다면 일반적으로 퀵 정렬이 빠르게 동작할 확률이 높다. 하지만, 삽입 정렬과 반대로, 데이터가 정렬되어 있는 경우에는 매우 느리게 동작한다.

 

 

정렬 라이브러리

파이썬의 기본 정렬 라이브러리 sorted() 함수는 병합 정렬을 기반으로 만들어졌는데, 퀵 정렬보다 느리지만 효율적이다.

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

 

 

코딩테스트 정렬 알고리즘 유형 3가지

1. 정렬 라이브러리로 풀 수 있는 문제

 

2. 정렬 알고리즘 원리 문제

선택, 삽입, 퀵 정렬 등의 원리를 알고 있어야 한다.

 

3. 더 빠른 정렬이 필요한 문제

퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며 계수 정렬 등 다른 정렬 알고리즘을 이용하거나 기존 알고리즘의 구조적인 개선을 통해 풀 수있다.

 

 

문제 1. 위에서 아래로

• 입력 받은 수열을 큰 수부터 작은 수의 순서로 내림차순 정렬해야 한다. 
• 첫째 줄에 수열 원소 개수를 입력된다.
• 둘째 줄부터 n+1번째 줄까지 n개의 수가 입력된다. 

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

# N개의 정수를 입력 받아 리스트에 저장
array = []
for i in range(n):
    array.append(int(input()))

# 파이썬 정렬 라이브러리를 이용하여 내림차순 정렬 수행
array = sorted(array, reverse=True)

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

 

수의 개수와 모든 수의 크기가 작으므로 어떠한 정렬 알고리즘을 사용해도 상관 없지만, 가장 코드가 간결해지는 파이썬의 기본 정렬 라이브러리를 이용하는 것이 효과적이다.

 

 

문제 2. 성적이 낮은 순서로 학생 출력하기

• n명의 학생 정보가 있고, 각 학생의 이름과 성적 정보가 주어졌을 때, 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오.
• 첫째 줄에 학생 수 n이 입력된다.
• 둘째 줄부터 n+1번째 줄에는 학생이름과 성적 점수가 입력된다.

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

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

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

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

 

학생의 최대 정보가 크기 때문에, 최악의 경우 O(NlogN)을 보장하는 알고리증을 이용하거나 O(N)을 보장하는 계수 정렬을 이용하면 된다. 또는 점수와 이름이 입력되지만 이름만 출력되기에 학생 정보를 (점수, 이름)으로 묶은 뒤에 정렬 라이브러리를 사용하는 것이 효과적이다.

 

 

문제 3. 두 배열의 원소 교체

• 배열 A, B 는 N개의 원소로 구성되어 있고, A 원소와 B 원소를 바꾸는 연산을 최대 K번 수행할 수 있다.
• 바꿔치기 연산을 수행하며 만들 수 있는 배열 A의 모든 원소 합의 최댓값을 출력하는 프로그램을 작성하시오.
• 첫 번째 줄에 N, K 가 입력된다.
• 두 번째 줄에 배열 A 원소들이 입력되고, 세 번째 줄에 배열 B 원소들이 입력된다.

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는 내림차순 정렬 수행

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

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

 

문제를 해결하기 위한 기본 아이디어는 매번 배열 A에서 가장 작은 원소와 B에서 가장 큰 원소를 교체하는 것이다. 단, A에서 가장 작은 원소가 B에서 가장 큰 원소보다 작을 때에만 교체를 수행한다. 따라서 배열 A,B 정보가 입력되면 A의 원소를 오름차순으로 정렬하고, B의 원소를 내림차순으로 정렬한다. 그리고 두 배열의 원소를 첫 번째 인덱스부터 비교하며 교체를 수행한다.