나동빈님 유튜브의 '이것이 취업을 위한 코딩 테스트다'강의와 교재 내용을 공부하고, 그 내용을 정리해본다.
(내용의 출처는 모두 유튜브 동빈나, 그리고 책 '이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 저'임을 사전에 밝힙니다.)
이전 내용이었던 그래프 탐색 알고리즘 : DFS & BFS 내용이 궁금하다면 아래 링크를 참조하자.
https://jjuke-brain.tistory.com/49
Ch02. 그래프 탐색 알고리즘 : DFS & BFS (feat. 이것이 취업을 위한 코딩 테스트다)
나동빈님 유튜브의 '이것이 취업을 위한 코딩 테스트다'강의와 교재 내용을 공부하고, 그 내용을 정리해보자. (내용의 출처는 모두 유튜브 동빈나, 그리고 책 '이것이 취업을 위한 코딩 테스트다
jjuke-brain.tistory.com
영상은 다음과 같이 업로드한다.
https://www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=11
목차
0. Introduction
정렬 알고리즘이란, 데이터를 특정 기준에 따라 순서대로 나열하는 것이다.
일반적으로 문제 상황에 다라 적절한 정렬 알고리즘이 공식처럼 사용되므로, 다양한 문제를 풀어보며 유형을 익힐 필요가 있다.
데이터 개수가 적을 때 / 데이터의 개수는 많지만 데이터의 범위가 한정되어 있을 때 / 이미 데이터가 거의 정렬된 경우 등 많은 상황이 존재한다.
예를 들어, 다음과 같이 총 10개의 카드(데이터)가 있다고 가정해보자.
사람은 이 데이터를 보고 '아, 지금 데이터가 0부터 9까지 하나씩 있는 것을 보니 정렬 결과는 0 1 2 3 4 5 6 7 8 9 겠구나'라고 생각하겠지만, 컴퓨터 프로그램은 정렬 방법을 구체적 알고리즘으로 명시해주지 않으면 정렬을 수행할 수 없다.
1. 선택 정렬 (Selection Sort)
선택정렬은 처리되지 않은 데이터 중 가장 작은 데이터를 선택하여 맨 앞에 있는 데이터와 바꾸는 과정을 반복한다.
즉, 매번 현재 범위에서 가장 작은 데이터를 골라 제일 앞쪽으로 보내주는 것이다.
1) 선택 정렬 동작 예시
위에서 든 10개의 데이터 예시에 적용해보자.
[Step 0] 먼저, 처리되지 않은 데이터 중 가장 작은 '0'을 선택하여 가장 앞에 존재하는 '7'과 자리를 바꾼다.
[Step 1] 처리되지 않은 데이터 중 가장 작은 '1'을 선택하여 가장 앞에 존재하는 '5'와 자리를 바꾼다. (처리된 데이터 : 파란색)
[Step 2, 3, ...] 위와 같은 과정을 계속하여 반복한다.
참고로, 정렬되지 않은 데이터가 하나 남은 경우 처리하지 않아도 전체 데이터가 성공적으로 정렬된다.
동작 과정을 잘 살펴보면, 탐색 범위는 매 반복마다 하나씩 줄어들게 되고, 가장 작은 요소를 찾기 위해 탐색 범위만큼 데이터를 하나씩 확인하면서 가장 작은 데이터를 찾아야 하므로, 매번 선형 탐색을 수행하게 된다.
따라서 선택 정렬 구현을 위해서는 이중 반복문을 사용해야 한다.
(1) 선택 정렬 Python 코드
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(len(array)):
min_index = i # 가장 작은 원소의 idx
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)
실행 결과는
$$ [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] $$
로, 정렬이 완료된다.
파이썬에서는 위와 같이 별도의 라이브러리 없이 두 원소의 위치를 바꾸는 swap 연산을 한줄로 표현할 수 있다.
(2) 선택 정렬 C++ 코드
#include <bits/stdc++.h>
using namespace std;
int n = 10;
int target[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
int main(void) {
for (int i = 0; i < n; i++) {
int min_index = i;
for (int j = i + 1; j < n; j++) {
if (target[min_index] > target[j] {
min_index = j;
}
}
swap(target[i], target[min_index]);
}
for (int i = 0; i < n; i++) {
cout << target[i] << ' ';
}
return 0;
}
정렬을 수행하는 로직과 실행 결과는 파이썬에서와 같다.
단, swap()이라는 함수를 별도로 사용하는 것이 차이점이다.
2) 선택 정렬의 시간 복잡도
선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다.
구현 방식에 따라 조금의 오차는 있을 수 있으나, 전체 연산 횟수는 다음과 같다.
$$ N + (N - 1) + (N - 2) + ... + 2 $$
이는 등차수열 공식에 따라 \( (N^2 + N - 2) / 2 \)로 표현할 수 있는데, 빅오 표기법에 따라 \( O(N^2) \)로 표시한다.
2. 삽입 정렬 (Insertion Sort)
삽입 정렬은 처리되지 않은 데이터를 하나씩 골라서 적절한 위치에 삽입하면서 수행된다.
선택한 데이터 앞쪽에 있는 원소들은 이미 정렬되어있다 가정하고 뒤쪽의 원소들을 앞쪽에 있는 원소들의 위치 중 한 곳으로 들어가도록 한다. 즉, 데이터를 하나씩 확인하면서, 어느 위치에 들어가는 것이 맞는지 매번 계산하면서 적절한 위치에 들어가도록 정렬해주는 것이다.
선택 정렬에 비해 구현 난이도가 조금 더높지만, 일반적으로 더 효율적으로 동작한다.
1) 삽입 정렬 동작 예시
마찬가지로 예시를 통해 과정을 알아보자.
[Step 0] 첫 번째 데이터 '7'은 그 자체로 정렬되었다고 판단하고, 두 번째 데이터 '5'가 어떤 위치로 들어갈지 판단한다.
'7'의 왼쪽 또는 오른쪽으로 들어가는 두 경우만 존재한다. '5'는 '7'보다 작으므로 왼쪽 위치에 삽입될 것이다.
[Step 1] 이어서 다음 데이터인 '9'가 어떤 위치로 들어갈지 판단한다. '9'는 '5'와 '7'보다 크므로 현재 위치에 그대로 둔다.
[Step 2, 3, 4, ...] 이러한 과정을 반복하면 다음과 같이 정렬이 완료된다.
(1) 삽입 정렬 Python 코드
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): # index i부터 1까지 1씩 감소하며 반복함
if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동하며 비교
array[j], array[j - 1] = array[j - 1], array[j]
else: # 자신보다 작은 데이터를 만나면 그 위치에서 멈춤
break
print(array)
실행 결과는
$$ [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] $$
이다.
j는 삽입하고자 하는 원소의 위치를 의미하며, 왼쪽으로 하나씩 이동하며 값을 비교하게 된다.
(2) 삽입 정렬 C++ 코드
#include <bits/stdc++.h>
using namespace std;
int n = 10;
int target[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
int main(void) {
for (int i = 1; i < n; i++) {
for (int j = i; j > 0; j--) {
if (target[j] < target[j - 1]) {
swap(target[j], target[j - 1]);
}
else break;
}
}
for (int i = 0; i < n; i++) {
cout << target[i] << ' ';
}
return 0;
}
파이썬과 동일한 로직, 동일한 결과를 갖는다.
2) 삽입 정렬의 시간 복잡도
삽입 정렬의 시간 복잡도는 \( O(N^2) \)이다. 선택 정렬과 마찬가지로 반복문이 두 번 중첨되어 사용되기 때문이다.
단, 이중 for문이 실행된다고 해서 반드시 시간복잡도가 \( O(N^2) \)인 것은 아니다. 만약 for문 안에서 별도 함수가 추가된다면, 해당 함수의 시간복잡도까지 고려하여야 한다.
하지만, 삽입 정렬에서는 단순히 swap 연산만 진해오디기 때문에 시간 복잡도가 위와 같은 것이다.
삽입 정렬의 특징은 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다는 것이다.
예를 들어, 아래와 같이 이미 정렬이 된 데이터에 대해 삽입 정렬을 진행한다고 해보자.
이와 같은 경우, 삽입 정렬에서 각 원소가 들어갈 위치를 고를 때 매번 첫 과정(for j ... 부분)에서 바로 위치가 결정되어 이 과정이 굳이 반복문을 많이 돌지 않고도 바로 멈춰지므로 상수 시간이 걸리게 된다.
따라서 이때 삽입 정렬의 시간 복잡도는 \( O(N) \)이 된다.
3. 퀵 정렬 (Quick Sort)
퀵 정렬은 이름에서부터 알 수 있듯이, 빠른 정렬 알고리즘 중 하나이다.
일반적인 데이터 특성과 상관 없이 표준적으로 사용할 수 있는 정렬 알고리즘 중 하나로 볼 수 있다.
퀵 정렬 알고리즘은 기준 데이터를 설정하고, 그 데이터보다 큰 데이터와 작은 데이터의 위치를 바꾸면서 동작한다.
가장 기본적인 퀵 정렬은 단순히 첫 번째 데이터를 기준 데이터(Pivot)으로 설정한다.
또한 병합 정렬과 더불어 대부분 프로그래밍 언어의 정렬 라이브러리의 근간이 된다.
대표적으로 C언어, Java, Python의 표준 정렬 라이브러리도 모두 퀵 정렬 혹은 병합 정렬의 아이디어를 채택한 하이브리드 방식의 정렬 알고리즘을 사용하고 있다.
1) 퀵 정렬 동작 예시
다음과 같은 10개의 데이터가 있다고 가정하자.
[Step 0] 피벗의 값을 '5'로 둔다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하고, 오른쪽에서부터 '5'보다 작은 데이터를 선택한다. 예시 데이터의 경우, 큰 데이터는 '7', 작은 데이터는 '4'가 선택될 것이고, 이 둘의 자리를 바꿔준다.
[Step 1] 마찬가지로 왼쪽에서부터 피벗보다 큰 데이터를 선택하고('9'), 오른쪽에서부터 피벗보다 작은 데이터('2)를 선택하여 위치를 바꾼다.
[Step 2] 반복하여 진행하다가, 아래와 같이 왼쪽에서부터의 탐색과 오른쪽에서부터의 탐색이 엇갈린 경우, 피벗('5')과 작은 데이터('1')의 위치를 변경한다.
[분할 완료] 이제 처음 피벗이었던 '5' 왼쪽에는 모두 피벗보다 작은 값, 오른쪽에는 큰 값들이 존재하게 된다. 이와 같이 피벗을 기준으로 데이터 묶음을 나누는 작업을 분할(Divide) 또는 Partition이라 한다.
[왼쪽 데이터 묶음 정렬] 왼쪽에 있는 데이터에 대해 새로운 피벗 '1'에 대해 분할을 반복한다.
[오른쪽 데이터 묶음 정렬] 오른쪽에 있는 데이터에 대해 같은 작업을 반복한다.
이 과정을 재귀적으로 수행하면 모든 데이터가 정렬될 것이다.
2) 퀵 정렬의 시간복잡도
먼저, 퀵 정렬이 빠른 이유를 알아보자.
이상적인 경우, 분할이 절반씩 일어난다면 전체 연산 횟수는 \( O(N \log N) \)일 것이다. (∵ 너비 × 높이 = \(N \times \log N = N \log N \) )
물론 실제로는 피벗 값을 기준으로 왼쪽과 오른쪽으로 분할되지만, 단순히 위와 같이 분할된다고 보자.
데이터 범위가 절반씩 줄어들기 때문에 높이는 밑이 2인 \( \log N \)이다.
높이가 \(N\)이므로 이와 곱하여 전체 연산 횟수가 정해진다.
퀵 정렬은 평균의 경우 \( O(N \log N) \)의 시간 복잡도를 갖고, 최악의 경우 \( O(N^2) \)의 시간 복잡도를 갖는다. 이는 수학적으로 증명되었고, 여기서 따로 다루지는 않겠다.
이는 피벗 값을 어떻게 설정하느냐에 따라 위 사진에서와 같이 이상적으로 분할이 절반에 가깝게 일어나거나, 분할이 한쪽으로 치우쳐져 일어날 수 있기 때문이다.
아래 예시와 같이 이미 정렬된 배열의 경우, 첫 번째 원소를 피벗으로 삼을 때의 퀵 정렬을 생각해보자.
'0'을 피벗으로 삼아 왼쪽에서부터 큰 데이터는 바로 '1'로 정해지고, 오른쪽에서 부터 작은 데이터는 끝까지 와서 '0'으로 골라진다.
따라서 피벗 값 자기 자신에서 자기 자신의 위치로 변경되므로 분할이 이루어졌을 때 왼쪽 부분은 존재하지 않고 오른쪽 부분만 편향적으로 존재하게 되는 것이다.
이러한 방식으로 분할이 수행되는 횟수가 N과 비례하고, 분할을 하기 위해 매번 선형 탐색을 진행해야 하므로 전체 시간 복잡도가 \( O(N^2) \)이 되는 것이다.
따라서 다양한 프로그래밍 언어에서 표준 정렬 라이브러리가 퀵 정렬을 기반으로 작성되었다면, 조금 변형시켜 최악의 경우에도 \( O(N \log N) \) 의 시간복잡도를 보장할 수 있도록 구현한다.
(1) 퀵 정렬 Python 코드
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array, start, end):
if start >= end: # (분할된 데이터 묶음의) 원소가 1개인 경우 종료
return
pivot = start # 피벗을 첫 번째 원소로 설정
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): # 엇갈린 경우 피벗과 작은 데이터 swap
array[right], array[pivot] = array[pivot], array[right]
else: # 엇갈리지 않은 경우 작은 데이터와 큰 데이터 swap
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)
실행 결과는
$$ [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] $$
이다.
파이썬의 경우 다음과 같이 훨씬 간결하게 코드를 작성할 수 있다.
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))
list slicing, list comprehension으로 짧게 작성한 것이다.
tail이라는 피벗을 제외한 리스트를 따로 만들어 진행한다.
(2) 퀵 정렬 C++ 코드
#include <bits/stdc++.h>
using namespace std;
int n = 10;
int target[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
void quickSort(int* target, int start, int end) {
if (start >= end) return;
int pivot = start;
int left = start + 1;
int right = end;
while (left <= right) {
while (left <= end && target[left] <= target[pivot]) left++;
while (right > start && target[right] >= target[pivot]) right++;
if (left > right) swap(target[pivot], target[right]);
else swap(target[left], target[right]);
}
quickSort(target, start, right - 1);
quickSort(target, right + 1, end);
}
int main(void) {
quickSort(target, 0, n - 1);
for (int i = 0; i < n; i++) cout << target[i] << ' ';
return 0;
}
실행결과와 로직 모두 파이썬 코드와 같다.
4. 계수 정렬 (Counting Sort)
계수 정렬은 특정 조건이 부합할 때에만 사용할 수 있지만, 매우 빠르게 동작하는 정렬 알고리즘이다.
이때 특정 조건은 바로 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다는 것이다.
데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행시간 \( O(N + K)\)를 보장한다.
1) 계수 정렬 동작 예시
예를 들어,
$$ [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] $$
위와 같은 데이터를 정렬한다 해보자.
[Step 0] 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있도록 리스트를 생성하면 아래와 같다.
[Step 1] 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다. 이 과정은 상수 시간이 걸린다.
[Step 2, 3, 4, 5, ... , 15] 위 과정을 모든 데이터에 대해 반복하면 최종 리스트에는 각 데이터가 몇 번 등장했는지 횟수가 기록된다.
결과를 출력 시 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 반복하여 인덱스를 출력한다.
예시의 경우
idx 0 → [0, 0]
idx 1 → [0, 0, 1, 1]
idx 2 → [0, 0, 1, 1, 2, 2]
idx 3 → [0, 0, 1, 1, 2, 2, 3]
...
idx 9 → [0, 0, 1, 1, 2, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9] → 최종 결과!
이와 같이, 계수 정렬의 경우 가장 작은 데이터부터 가장 큰 데이터까지 모든 범위를 포함하는 크기의 배열을 만들어야 하기 때문에, 공간 복잡도는 상대적으로 높지만, 시간 복잡도는 조건만 만족한다면 퀵 정렬보다 더 빠르게 동작한다.
(1) 계수 정렬 Python 코드
# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (max(array) + 1) # 위 예시에서 0 ~ 9까지 10개
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=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력
실행 결과는
$$ 0, 0, 1, 1, 2, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9 $$
이다.
(2) 계수 정렬 C++ 코드
#include <bits/stdc++.h>
#define MAX_VALUE 9
using namespace std;
int n = 15;
int arr[15] = {7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2};
int cnt[MAX_VALUE + 1];
int main(void) {
for (int i = 0; i < n; i++) {
cnt[arr[i]] += 1;
}
for (int i = 0; i <= MAX_VALUE; i++) {
for (int j = 0; j < cnt[i]; j++) {
cout << i << ' ';
}
}
}
로직과 실행결과는 파이썬 코드와 같다.
2) 계수 정렬의 시간 복잡도
계수 정렬의 시간 복잡도와 공간 복잡도는 모두 \( O(N + K) \) 이다.
시간 복잡도의 경우
코드 상에서 각 데이터에 해당하는 인덱스의 값을 증가시키는 부분이 \( O(N) \) 이고,
원소 중에서 가장 큰 값(K) 만큼 각 인덱스를 확인하며 그 인덱스에 기록된 값만큼 출력을 수행하고, 중첩된(j) 반복문의 시간 복잡도가 \( O(N) \) 이므로 전체 이중 반복문의 시간 복잡도는 \( O(N + K) \)이다.
공간 복잡도의 경우
정렬을 수행할 데이터 갯수 N, 각 데이터의 등장 횟수를 세는 리스트의 원소 갯수가 K이므로 \( O(N + K) \) 이다.
계수 정렬의 경우 데이터의 범위를 잘 따져 효율성을 고려해주어야 한다.
특히, 데이터의 범위가 크지 않으면서 동일한 값을 갖는 데이터가 여러 개 등장할 때 효과적으로 사용할 수 있다.
다음 글에서 관련된 예제를 풀어보자.
최근댓글