안녕하세요 이번 시간에는 코딩 테스트에서 사용되는 여러 정렬 알고리즘에 대해 알아보도록 하겠습니다.
정렬 알고리즘은 크게 단순하지만 비효율적인 방법(버블 정렬, 선택 정렬, 삽입 정렬)과 복잡하지만 효율적인 방법(퀵 정렬, 병합 정렬, 기수 정렬, 힙 정렬)로 나뉘어집니다.
먼저 버블 정렬이란 데이터의 인접 요소끼리 비교하고 스왑 연산을 수행하며 정렬하는 알고리즘입니다. 배열의 끝값부터 정렬되기 때문에 i는 0부터 N-1까지 탐색할 때 j는 0부터 N-1-i까지 탐색후 j 인덱스의 이웃한 값끼리 스왑을 진행합니다. 따라서 O(N^2)의 시간복잡도를 가집니다.
버블 정렬의 실제 구현 예시를 백준 2750(수 정렬하기)을 통해서 확인해보겠습니다. 위에서 설명한 방식대로 i는 0부터 N-1까지 탐색할 때 j는 0부터 N-1-i까지 탐색하며 j 인덱스를 기준으로 이웃한 값끼리 스왑합니다.
import java.util.*;
import java.io.*;
class Main{
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] map = new int[N];
for(int i=0;i<N;i++) map[i] = Integer.parseInt(br.readLine());
for(int i=0;i<N-1;i++){
for(int j=0;j<N-1-i;j++){
if(map[j] > map[j+1]){
int tmp = map[j];
map[j] = map[j+1];
map[j+1] = tmp;
}
}
}
StringBuilder sb = new StringBuilder();
for(int i=0;i<N;i++) sb.append(map[i]).append("\n");
System.out.println(sb);
}
}버블 정렬은 한 가지 특징을 가지고 있습니다. 바로 왼쪽으로 이동하는 경우는 1턴에 1칸이 최대라는 점입니다. 왜냐하면 버블 정렬 특성상 1턴에 1개씩 가장 뒤의 배열부터 채우기 때문에 뒤로 이동하는 경우는 충분히 많은 칸을 이동할 수 있으나 앞으로 이동하는 경우는 1개의 값만 뒤로 이동했을 때 상대적으로 1칸 앞으로 오기 때문입니다.
이를 응용할 수 있는게 백준 1377(버블 소트) 문제입니다. 주어진 프로그램에서 입력을 받았을 때의 출력을 구하는 문제, 즉 스왑이 한번도 일어나지 않은 루프가 언제인지, 몇 번 루프에서 정렬이 완료되는지를 구하는 문제입니다. 이 문제의 경우 버블 정렬로 탐색 시 시간 초과가 발생합니다. 따라서 버블 정렬의 특징인 왼쪽으로 이동하는 경우 1턴에 1칸이 최대라는 특징을 이용하여 배열 정렬 전 인덱스 값에서 정렬 후 인덱스 값을 뺀 값의 최댓값에 스왑이 일어나지 않는 반복문이 한번 더 실행되는 것을 감안하여 최댓값에 1을 더한 값이 구하고자 하는 결과값이 됩니다. 여기서 주의할 점은 값을 기준으로 배열을 만들어 배열에 인덱스 차를 저장할 경우 중복되는 값이 존재하는 배열에서 잘못된 결과를 리턴하기 때문에 클래스를 생성해서 인덱스 차이를 계산합니다.
선택 정렬의 경우 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 알고리즘입니다. 최솟값 또는 최댓값을 찾고 남은 정렬 부분의 가장 앞에 있는 데이터와 스왑합니다. 구현 방법이 복잡하고 시간복잡도도 O(N^2)로 효율적이지 않기 때문에 많이 사용하지 않습니다.
선택 정렬의 실제 구현 예시를 백준 1427(소트인사이드)를 통해 설명드리겠습니다. i는 0부터 N까지, j는 i+1부터 N까지 수행하며 j 범위에서 최댓값을 찾아 i의 값과 비교해서 스왑합니다.
import java.util.*;
import java.io.*;
class Main{
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
int N = str.length();
int[] map = new int[N];
for(int i=0;i<N;i++) map[i] = Integer.parseInt(String.valueOf(str.charAt(i)));
StringBuilder sb = new StringBuilder();
for(int i=0;i<N;i++){
int idx = i;
for(int j=i+1;j<N;j++){
if(map[j] > map[idx]) idx = j;
}
if(map[i] < map[idx]){
int tmp = map[i];
map[i] = map[idx];
map[idx] = tmp;
}
}
for(int i=0;i<N;i++) sb.append(map[i]);
System.out.println(sb);
}
}삽입 정렬이란 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 알고리즘입니다. 시간 복잡도는 O(N^2)로 버블 정렬과 선택 정렬과 같지만 최선의 경우 O(N)까지 줄어들 수 있다는 장점이 있습니다.
삽입 정렬을 백준 11399(ATM)을 통해서 구현해보겠습니다. 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 문제입니다. 그리디 방식으로 시간의 오름차순을 정렬한 후 누적합을 계산하면 됩니다. i를 0부터 N까지 탐색하고 j를 역순으로 탐색하면서 값이 더 큰 값이 다오면 인덱스를 저장 후 break, 이 후 해당 포인트 전까지 값을 이동시키고 빈 공간에 값을 추가합니다.
import java.util.*;
import java.io.*;
class Main{
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] map = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) map[i] = Integer.parseInt(st.nextToken());
for(int i=1;i<N;i++){
int idx = i;
int val = map[i];
for(int j=i-1;j>=0;j--){
if(map[j] < map[i]){
idx = j+1;
break;
}
if(j==0) idx = 0;
}
for(int j=i;j>idx;j--) map[j] = map[j-1];
map[idx] = val;
}
int[] sum = new int[N];
sum[0] = map[0];
for(int i=1;i<N;i++) sum[i] = sum[i-1] + map[i];
int res = 0;
for(int i=0;i<N;i++) res += sum[i];
System.out.println(res);
}
}퀵 정렬이란 기준값을 선정해 해당값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘입니다. 시간 복잡도가 O(nlogn)으로 빠른 편이며 재귀함수 형태로 구현합니다.
퀵 정렬을 백준 11004(K번째 수) 문제를 통해 구현해보겠습니다. 수를 오름차순 정렬했을 때 앞에서부터 K번째 있는 수를 구하는 문제입니다. 데이터가 대부분 정렬되어 있는 경우 앞쪽에 있는 수를 기준값으로 선택하면 불필요한 연산이 많아지기 때문에 중간값을 기준값으로 설정 후 계산의 편의를 위해 제일 앞값과 스왑합니다. 이 때 기준값이 K와 같을 경우 K번째 수를 찾은 것이므로 알고리즘을 종료하고, K보다 클 경우 기준값 기준 왼쪽에 K번째 수가 존재하기 때문에 기준값 기준 왼쪽을 정렬합니다. 반대로 K보다 작을 경우 오른쪽을 정렬합니다. 이후 기준값 이후의 시작지점과 끝점을 기준으로 끝점이 기준값보다 크다면 끝 인덱스를 줄이고 시작점이 기준값보다 작으면서 끝점보다 작은 경우 시작 인덱스를 증가시켜 두 인덱스가 만나는 위치와 기준값을 스왑합니다.
import java.util.*;
import java.io.*;
class Main{
static int N,K;
static int[] map;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
map = new int[N];
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) map[i] = Integer.parseInt(st.nextToken());
quickSort(0,N-1, K-1);
System.out.println(map[K-1]);
}
static void quickSort(int start, int end, int k){
if(start < end){
int pivot = partition(start,end);
if(pivot == k) return;
else if(k < pivot) quickSort(start,pivot-1,k);
else quickSort(pivot+1,end,k);
}
}
static int partition(int start, int end){
if(start+1 == end){
if(map[start] > map[end]) swap(start,end);
return end;
}
int M = (start+end)/2;
swap(start,M);
int pivot = map[start];
int i = start+1;
int j = end;
while(i<=j){
while(j>=start+1 && pivot < map[j]){
j--;
}
while(i<=end && pivot > map[i]){
i++;
}
if(i<=j) swap(i++,j--);
}
map[start] = map[j];
map[j] = pivot;
return j;
}
static void swap(int start, int end){
int tmp = map[start];
map[start] = map[end];
map[end] = tmp;
}
}병합 정렬은 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘입니다. 퀵 정렬과 마찬가지로 시간복잡도가 O(nlogn)으로 빠르며 재귀함수 형태로 구현됩니다. 퀵 정렬과의 차이점은 정렬할 그룹을 최소 길이로 나눈 후 각 그룹을 정렬하고 정렬된 그룹을 합쳐 다시 정렬하는 것을 반복하며 정렬을 진행합니다.
병합 정렬은 백준 2751(수 정렬하기 2)를 통해 구현해보겠습니다. 재귀 함수 형태로 중간지점을 기준으로 시작점과 중간점, 중간점과 끝점을 그룹으로 나누어 가장 작은 그룹이 될때까지 자기 자신을 호출합니다. 이 후 앞쪽 그룹의 시작점과 뒤쪽 그룹의 시작점을 비교하며 더 작은 수를 선택해서 배열에 저장하고 선택된 데이터의 인덱스 값을 오른쪽으로 이동합니다. 이 후 재귀 함수 특성 상 상위 그룹의 정렬이 진행되며 최종적으로 정렬이 완료됩니다.
import java.util.*;
import java.io.*;
class Main{
static int N;
static int[] map,tmp;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new int[N];
tmp = new int[N];
for(int i=0;i<N;i++) map[i] = Integer.parseInt(br.readLine());
mergeSort(0,N-1);
StringBuilder sb = new StringBuilder();
for(int i=0;i<N;i++) sb.append(map[i]).append("\n");
System.out.println(sb);
}
static void mergeSort(int start, int end){
if(end - start < 1) return;
int m = start + (end-start)/2;
mergeSort(start,m);
mergeSort(m+1,end);
for(int i=start;i<=end;i++) tmp[i] = map[i];
int k = start;
int s = start;
int e = m+1;
while(s <= m && e <= end){
if(tmp[s] > tmp[e]){
map[k] = tmp[e];
k++;
e++;
}
else{
map[k] = tmp[s];
k++;
s++;
}
}
while(s <= m){
map[k] = tmp[s];
k++;
s++;
}
while(e <= end){
map[k] = tmp[e];
k++;
e++;
}
}
}백준 1517(버블 소트) 문제의 경우 버블 정렬을 진행할 때 스왑이 몇 번 일어나는지 구하는 문제입니다. 버블 정렬을 진행 시 시간 초과가 발생하기 때문에 O(nlogn)의 시간복잡도의 정렬 알고리즘을 사용해야 합니다. 여기서 포인트는 버블 정렬의 특성과 함께 병합 정렬에서 병합 과정에서 앞으로 값이 추가되는 경우 앞으로 이동한 칸만큼 버블 정렬이 스왑된다는 것을 알 수 있습니다. 따라서 병합 정렬에서 앞으로 값이 추가되는 경우 이동한 값만큼 정답에 누적하여 더해주면 됩니다.
기수 정렬이란 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교하는 알고리즘입니다. O(kn), 여기서 k는 데이터의 자릿수를 의미하며 때에 따라서는 그 어떤 정렬 알고리즘보다 빠른 성능을 발휘할 수 있습니다. 최대 자릿수까지 반복하면서 현재 자릿수 기준으로 값을 순서대로 큐에 저장하여 작은 순서대로 새롭게 배열에 추가합니다.
기수 정렬을 백준 10989(수 정렬하기 3) 문제를 통해 구현해보겠습니다. N이 매우 크기 때문에 O(nlogn)보다 빠른 알고리즘이 필요하며, 숫자 자릿수가 최대 5자리이기 때문에 기수 정렬을 진행합니다. 현재 자릿수들의 분포의 개수를 누적합의 형태로 알려주는 배열을 설정하여 현재 자릿수를 기준으로 값을 배열에 카운트한 후 이전 배열의 값과 더해줍니다. 이렇게 하면 배열 내의 값이 실제 배열의 자릿수 별로 정렬되는 새로운 인덱스를 가리키게 되며 해당 인덱스의 위치에 기존 값을 새로운 배열에 추가하고 합 배열의 카운트를 감소시켜 다른 인덱스에 추가하는 방식으로 정렬을 반복합니다.
import java.util.*;
import java.io.*;
class Main{
static int N;
static int[] map;
static int MAX_RADIX = 5;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new int[N];
for(int i=0;i<N;i++) map[i] = Integer.parseInt(br.readLine());
radixSort();
StringBuilder sb = new StringBuilder();
for(int i=0;i<N;i++) sb.append(map[i]).append("\n");
System.out.println(sb);
}
static void radixSort(){
int[] output = new int[N];
int radix = 1;
int cnt = 0;
while(cnt != MAX_RADIX){
int[] bucket = new int[10];
for(int i=0;i<N;i++) bucket[(map[i]/radix)%10]++;
for(int i=1;i<10;i++) bucket[i] += bucket[i-1];
for(int i=N-1;i>=0;i--){
output[bucket[(map[i]/radix)%10]-1] = map[i];
bucket[(map[i]/radix)%10]--;
}
for(int i=0;i<N;i++) map[i] = output[i];
radix *= 10;
cnt++;
}
}
}힙 정렬의 경우 최소 힙 또는 최대 힙을 이용하여 정렬하는 알고리즘입니다. 힙은 완전 이진 트리 구조를 가지며 부모 노드는 자식 노드보다 항상 우선 순위가 앞선다(혹은 뒤쳐진다)는 조건을 만족시키며 채워나갑니다. 이렇게 되면 부모 노드는 항상 우선순위가 높은 노드가 들어가기 때문에 이를 이용하여 값을 정렬 시 부모 노드의 인덱스를 기준으로 스왑하여 정렬할 수 있습니다. 여기서 힙은 완전 이진 트리 구조를 가지기 때문에 노드 i의 부모 노드 인덱스는 i/2라는 특징을 가집니다.
백준 2220(힙 정렬) 문제의 경우 스왑 횟수가 최대가 되는 힙을 출력하는 문제입니다. 스왑 횟수가 최대가 되려면 1부터 N-1까지 최대 힙으로 넣어주고 배열의 가장 마지막에 1이 추가되는 경우입니다. 이를 노드 i의 부모 노드 인덱스는 i/2라는 특징을 이용하여 루트 노드에는 계속 최댓값을 넣어주고 나머지 원소를 하나씩 뒤로 미루는 방식으로 구현할 수 있습니다.
import java.util.*;
import java.io.*;
class Main{
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] map = new int[N+1];
for(int i=1;i<N;i++){
for(int j=i;j>1;j/=2) map[j] = map[j/2];
map[1] = i+1;
}
map[N] = 1;
StringBuilder sb = new StringBuilder();
for(int i=1;i<=N;i++) sb.append(map[i]).append(" ");
System.out.println(sb);
}
}