push_swap 기수 정렬 가이드

서론

이 글이 그리디와 모래 시계를 저 구석으로 몰아내고 기수 정렬이라는 새로운 유행을 불러올 수 있었으면 한다.

 

경고

현재 push_swap 과제를 막 시작한 상태라면 읽지 않는 것을 권장한다.

이 과제의 목적은 단순히 stack의 원소를 정렬하는 것이 아니다.

시간 복잡도와 여러 정렬 알고리즘에 대하여 공부한 후 자신만의 풀이를 구상해보자.

적어도 이 과제에 한해서는 일주일 정도 키보드에서 손을 떼고 연습장만 끄적이는 것을 권장한다.

다른 사람의 풀이를 참고할수록 얻어가는 것은 줄어들 것이다.

 

과제를 한 문장으로 설명하자면, 마법의 stack 2개를 이용해서 원소들을 정렬하는 것이다.

마법의 stack이라고 표현한 이유는, 실제 stack과 달리 rotate 기능이 추가되었기 때문이다.

이제부터는 마법의 stack 대신 단순히 배열이라는 용어를 사용하기로 한다.

그리고 모든 N은 원소의 개수를 의미한다.

 

시작은 단순하게

우선 N이 작은 경우부터 생각해보자.

N = 0 or N = 1인 경우 배열은 이미 정렬된 상태이므로 고려하지 않아도 된다.

 

N = 2인 경우 원소의 배치로 가능한 경우의 수는 2! = 2개이다.

• [1 2]: -
• [2 1]: sa

따라서 N = 2인 경우 최대 1개의 명령어로 배열을 정렬할 수 있다.

 

N = 3인 경우 원소의 배치로 가능한 경우의 수는 3! = 6개이다.

• [1 2 3]: -
• [1 3 2]: sa ra
• [2 1 3]: sa
• [2 3 1]: rra
• [3 1 2]: ra
• [3 2 1]: sa rra

따라서 N = 3인 경우 최대 2개의 명령어로 배열을 정렬할 수 있다.

 

자세히 보면 무언가 규칙이 보일 것이다.

시계 방향 배치와 반시계 방향 배치

 

원소의 배치를 시계 방향 배치 또는 반시계 방향 배치로 분류할 수 있다.

[1 2 3], [2 3 1], [3 1 2]는 시계 방향 배치이고 [1 3 2], [2 1 3], [3 2 1]은 반시계 방향 배치이다.

반시계 방향 배치에서 sa 명령을 한 번만 수행하면 시계 방향 배치가 된다.

• [1 3 2] -> [3 1 2]
• [2 1 3] -> [1 2 3]
• [3 2 1] -> [2 3 1]

시계 방향 배치에서는 ra 또는 rra 명령을 최대 한 번만 수행하면 정렬이 완료된다.

따라서 N = 3인 경우 if 문 3개로 정렬이 완료되는데 N = 2인 케이스도 동시에 처리할 수 있도록 구현할 수 있다.

 

N = 4인 경우 원소의 배치로 가능한 경우의 수는 4! = 24개이다.

• [1 2 3 4]: -
• [1 2 4 3]: ...
• ...

결론만 말하자면 N = 4인 경우 최대 5개의 명령어로 배열을 정렬할 수 있다.

하지만 경우의 수가 너무 커졌고 N이 커질수록 경우의 수는 폭발적으로 증가하기 때문에 더 이상 규칙을 구하기는 어려워 보인다.

N = 3인 경우의 풀이를 재귀적으로 이용해보자.

 

def simple_sort(stack a, stack b):

    if a.len < 4:

        위의 규칙에 따라 정렬

    else

        step 1: 적절히 ra 또는 rra를 하여 가장 큰 원소를 top으로 옮기고 pb

        step 2: simple_sort(a, b) // 재귀적으로 정렬

        step 3: pa, rra

 

step 1에서 ra 또는 rra 중 한 가지 명령만 사용하면 최대 N개의 명령어를 사용한다.

ra와 rra 중 적절한 명령어를 선택하면 최대 (floor(N / 2) + 1)개의 명령어를 사용하므로 더 효율적이다.

 

위와 같은 정렬 방법을 단순 정렬이라고 하자.

그리고 크기가 N인 배열을 단순 정렬할 때의 최대 명령어 개수를 simple[N]이라고 하자.

• simple[0] = simple[1] = 0
• simple[2] = 1
• simple[3] = 2
• simple[N] = floor(N / 2) + 1 + simple[N - 1] + 2    (N > 3)

simple[4] = 7, simple[5] = 12로 작은 N에 대해서는 괜찮은 성능을 보인다.

하지만 simple[100] = 2791, simple[500] = 63991로 N이 커질수록 명령어 개수는 빠르게 증가함을 확인할 수 있다.

 

simple[N]의 시간 복잡도를 분석해보자(N > 3).

simple[N] = simple[N - 1] + floor(N / 2) + 3

simple[N] <= simple[N - 1] + 2 * N

simple[N] = N^2 + N - 10 = O(N^2)

 

이제 O(N log N)의 성능을 보장하는 기수 정렬을 소개할 것이다.

(실제 기수 정렬의 시간 복잡도는 O(N * d)이며 아래에서 소개할 정규화를 수행하면 O(N log N)이 된다)

기수 정렬을 소개하기 전에 단순 정렬이라는 다소 느린 정렬 방법을 소개한 이유가 있다.

작은 N에 대해서는 단순 정렬이 기수 정렬보다 더 빠르게 작동한다.

두 알고리즘의 성능이 동일해지는 N을 임계값이라고 하는데 임계값 전후로 알고리즘의 성능 우위가 변화한다.

따라서 작은 N에 대해서는 단순 정렬을 수행하고 큰 N에 대해서는 기수 정렬을 수행하면 더 효율적으로 정렬이 가능하다.

 

기수 정렬의 도입

기수 정렬의 작동 방식을 잘 모른다면 먼저 이 문서를 공부하고 오자.

이 과제에서 기수 정렬을 사용하였을 때의 장점은 크게 두 가지가 있다.

첫 번째로 동일한 N에 대하여 동일한 명령어 개수를 보장한다(아래에서 소개할 정규화를 수행한 경우).

두 번째로 다른 O(N log N) 알고리즘에 비하여 구현이 매우 간단하다.

물론 단점도 있는데 아래에서 다시 언급하려고 한다.

 

이 과제에서는 배열(마법의 stack) 2개만 이용할 수 있다는 제약 때문에 10진수 기수 정렬을 그대로 수행할 수는 없다.

그 대신 2진수 기수 정렬을 도입할 수 있다.

마찬가지로 배열 2개의 제약 때문에 약간 다른 방법으로 수행할 것이다.

 

2진수 기수 정렬의 수행 과정은 다음과 같다.

• 각 자릿수에서 등장하는 숫자는 0 또는 1이다. 이를 기준으로 원소들을 0 그룹 또는 1 그룹으로 분류한다.
• 먼저 첫 번째 자릿수에 대하여 다음 과정을 수행한다.
• 0 그룹 원소는 pb를 하여 배열 B에 임시 저장한다.
• 1 그룹 원소는 ra를 하여 배열 A의 뒤로 보낸다.
• 모든 원소에 대하여 작업을 마치면 0 그룹 원소는 배열 B에, 1 그룹 원소는 배열 A에 위치하게 된다.
• 배열 B에 있는 0 그룹 원소들에 대하여 pa를 하여 배열 A로 보낸다.
• 모든 자릿수에 대하여 이 과정을 반복하면 정렬이 완료된다.

크기가 7인 배열 A = [7, 2, 4, 5, 1, 3, 6]을 2진수 기수 정렬 방법으로 정렬해보자.

배열 A를 2진수로 나타내면 A = [111, 010, 100, 101, 001, 011, 110]이다.

초기 상태

첫 번째 자릿수를 기준으로 0 그룹은 pb, 1 그룹은 ra

0 그룹 원소들을 배열 A로 복귀

두 번째 자릿수에 대해서도 반복

복귀

세 번째 자릿수에 대해서도 반복

정렬 완료

 

정렬이 완료되었다.

시간 복잡도를 분석하기 전에 기수 정렬의 단점을 알아보자.

정렬 과정을 살펴보면 기수 정렬의 수행 횟수는 원소의 최대 자릿수에 비례함을 알 수 있다.

따라서 원소들의 자릿수가 굉장히 크다면 수행 횟수 또한 증가하게 된다.

예를 들어, 배열 [1, 0]과 [2147483647, 2147483646]에서의 명령어 수행 횟수는 차이가 크다.

 

이를 해결하기 위하여 기존 원소들을 크기 순서대로 정규화할 수 있다.

구체적으로는 가장 작은 원소를 0으로, 그 다음 원소를 1로, ..., 가장 큰 원소를 (N - 1)로 대체하면 된다.

실제 입력값은 저장하고 있을 필요가 없고 이와 같은 정규화를 통해서 원소의 최대 자릿수를 최소한으로 줄일 수 있다.

위의 예제에서는 0을 사용하지 않았는데 별다른 이유는 없고 내가 사용한 visualizer가 0을 지원하지 않기 때문이다 :(

 

이제 시간 복잡도를 분석해보자.

• 0 그룹은 배열 B에 임시 저장한 후(pb) 배열 A로 복귀시킨다(pa).
• 1 그룹은 배열 A의 뒤로 보낸다(ra).

0 그룹은 2개의 명령어를 사용하고 1 그룹은 1개의 명령어를 사용하므로 평균 명령어 수행 횟수는 3/2 N이다.

이를 원소의 최대 자릿수 = ceil(log_2 N)회 반복하므로 시간 복잡도는 O(3/2 N * ceil(log_2 N))이 된다.

일반적으로 시간 복잡도 표기에서 상수는 생략하지만 이 과제에서는 상수 또한 중요하기에 상수도 표기하였다.

 

크기가 N인 배열을 2진수 기수 정렬할 때의 명령어 개수를 2radix[N]이라고 하자.

(단순 정렬과 다르게 '최대'라는 단어가 빠졌는데 이는 기수 정렬이 항상 동일한 명령어 수행 횟수를 보장하기 때문이다)

2radix[3] = 10, 2radix[5] = 25로 작은 N에 대해서는 단순 정렬에 비하여 느리지만,

2radix[100] = 1084, 2radix[500] = 6784로 큰 N에 대해서는 더 빠른 성능을 보여준다.

 

3진수 기수 정렬

2진수 기수 정렬의 성능도 괜찮지만 만족스러운 수준은 아니다.

이번에는 유사한 방법으로 3진수 기수 정렬을 수행해보자.

2진수 기수 정렬에서는 원소들을 2개의 그룹으로 분류하였다.

3진수 기수 정렬에서는 원소들을 3개의 그룹으로 분류하면 된다.

 

3진수 기수 정렬의 수행 과정은 다음과 같다.

• 각 자릿수에서 등장하는 숫자는 0, 1, 2 중 하나이다. 이를 기준으로 원소들을 0, 1, 2 그룹 중 하나로 분류한다.
• 먼저 첫 번째 자릿수에 대하여 다음 과정을 수행한다.
• 0 그룹 원소는 pb를 하여 배열 B의 앞으로 보낸다.
• 1 그룹 원소는 pb, rb를 하여 배열 B의 뒤로 보낸다.
• 2 그룹 원소는 ra를 하여 배열 A의 뒤로 보낸다.
• 모든 원소에 대하여 작업을 마치면 0 그룹 원소는 배열 B의 앞에, 1 그룹 원소는 배열 B의 뒤에 위치하게 된다.
• 2 그룹 원소는 배열 A에 위치하는데 pb를 하여 전부 배열 B의 앞으로 보낸다.
• 모든 자릿수에 대하여 이 과정을 반복하면 정렬이 완료된다.

눈치가 빠르다면 무언가 잘못되었다고 생각할 수 있는데 일단은 크게 신경 쓰지 말자.

 

크기가 8인 배열 A = [6, 7, 2, 4, 5, 8, 1, 3]을 3진수 기수 정렬 방법으로 정렬해보자.

배열 A를 3진수로 나타내면 A = [20, 21, 02, 11, 12, 22, 01, 10]이다.

 

초기 상태

첫 번째 자릿수를 기준으로 0 그룹은 pb, 1 그룹은 pb rb, 2 그룹은 ra

2 그룹 원소들을 배열 B로 보냄

 

이 부분이 2진수 기수 정렬과 상이하다.

2진수 기수 정렬에서는 어떠한 자릿수에 대하여 모든 명령을 수행하면 모든 원소가 배열 A에 위치하게 된다.

3진수 기수 정렬에서는 원소의 위치가 매번 뒤바뀐다(배열 A -> 배열 B, 배열 B -> 배열 A).

때문에 최대 자릿수가 홀수인 경우에는 배열 B에서 정렬이 끝나는데 이때는 pa 명령으로 모든 원소를 배열 A로 보내면 된다.

이번에도 무언가 잘못되었다고 생각할 수 있는데 일단은 크게 신경 쓰지 말자.

 

현재 모든 원소는 배열 B에 위치하고 있으므로 0 그룹은 pa, 1 그룹은 pa ra, 2 그룹은 rb와 같이 이전과 반대로 명령을 수행한다.

두 번째 자릿수를 기준으로 0 그룹은 pa, 1 그룹은 pa ra, 2 그룹은 rb

정렬 완료

 

이번에도 정렬이 완료되었다.

사진을 보면 제대로 정렬되지 않은 것처럼 보이지만 일단은 정렬된 상태라고 생각하자.

 

시간 복잡도를 분석해보자.

• 0 그룹은 배열 B의 앞으로 보낸다(pb).
• 1 그룹은 배열 B의 뒤로 보낸다(pb rb).
• 2 그룹은 배열 A의 뒤로 보낸 후 배열 B의 앞으로 보낸다(ra pb).

0 그룹은 1개의 명령어를 사용하고 1, 2 그룹은 2개의 명령어를 사용하므로 평균 명령어 수행 횟수는 5/3 N이다.

이를 원소의 최대 자릿수 = ceil(log_3 N)회 반복하므로 시간 복잡도는 O(5/3 N * ceil(log_3 N))이 된다.

 

크기가 N인 배열을 3진수 기수 정렬할 때의 명령어 개수를 3radix[N]이라고 하자.

원소의 최대 자릿수가 홀수인 경우 배열 B에 위치한 원소를 배열 A로 보내는 N개의 추가 명령어가 필요함에 유의하자.

3radix[3] = 8, 3radix[5] = 15로 작은 N에 대해서는 2진수 기수 정렬에 비하여 빠르고,

3radix[100] = 869, 3radix[500] = 4899로 큰 N에 대해서도 더 빠른 성능을 보여준다.

 

정렬이 실패한 이유

사실 정렬이 되었다는 것은 거짓말이고 실제로는 전혀 정렬되지 않았다.

크게 3가지 이유가 있는데 차례대로 알아보자.

 

첫 번째로 그룹을 순서대로 배치하지 않았다.

배열을 정렬하려면 0 그룹, 1 그룹, 2 그룹 순으로 배치해야 하는데 우리는 2 그룹, 0 그룹, 1 그룹 순으로 배치하였다.

때문에 배열이 절대 정렬될 수가 없는 상황이다.

해결 방법은 단순한데 각 그룹에 수행하는 명령어를 적절히 바꾸면 된다.

구체적으로는 0 그룹은 ra, 1 그룹은 pb, 2 그룹은 pb, rb를 수행하고 배열 A에 남은 0 그룹 원소들에 대하여 pb를 수행하면 된다.

이렇게 하면 0 그룹, 1 그룹, 2 그룹 순으로 배치가 가능하다.

 

해결 방법이 존재하지만 우리는 여전히 2 그룹, 0 그룹, 1 그룹 순서를 유지할 것이다.

잘 관찰해보면 모든 자릿수에 대하여 0 그룹의 크기는 다른 그룹의 크기보다 작을 수 없음을 알 수 있다.

따라서 0 그룹 원소에 대하여 단 하나의 명령어만 사용하도록 하면 명령어의 개수를 최적화할 수 있다.

정렬이 되지 않는다는 심각한 문제가 존재하지만 일단은 넘어가자.

 

두 번째로 0 그룹과 2 그룹은 매 자릿수마다 그룹 내의 정렬 순서가 반전된다.

pb 후 rb를 하는 1 그룹과 다르게 0 그룹과 2 그룹은 pb만 하기 때문에 그룹 내의 정렬 순서가 반전된다.

이를 해결하기 위한 규칙이 존재하지만 설명하기 복잡하므로 생략한다.

즉, 해결 방법은 존재하지만 해결하지 않을 것이다.

 

세 번째로 원소의 최대 자릿수가 홀수인 경우 배열의 정렬 순서가 반전된다.

이를 해결하기 위한 규칙 또한 존재하지만 설명하기 복잡하므로 생략한다.

즉, 해결 방법은 존재하지만 해결하지 않을 것이다.

 

작성자는 헛소리만 하면서 모든 문제를 해결하지 않겠다고 소리만 지르는 금쪽이의 모습을 보여주고 있다.

금쪽이는 이 상황을 어떻게 뒤집을 것인가.

 

두 번째 정규화와 마법의 배열

정렬이 되지 않은 것은 사실이지만 우리는 중요한 사실을 관찰할 수 있다.

크기가 N인 배열에서 원소의 순서를 재배치하더라도 우리가 얻는 결과 배열은 항상 동일하다는 것이다.

즉, 오름차순 정렬은 아니지만 무언가 특수한 기준으로 정렬되었다는 것이다.

 

앞의 예제에서 N = 8인 배열 A = [6, 7, 2, 4, 5, 8, 1, 3]을 정렬하였을 때 정렬 결과는 [7, 6, 8, 1, 2, 5, 3, 4]가 되었다.

배열 A의 원소를 임의로 재배치하고 3진수 기수 정렬을 수행하면 언제나 동일한 결과가 나오는 것을 확인할 수 있을 것이다.

이 정렬 결과는 오름차순으로 정렬된 배열 [1, 2, 3, 4, 5, 6, 7, 8]이 특수하게 변형된 형태이기 때문이다.

어떠한 3진수 기수 정렬의 정렬 결과 배열을 적절히 복구하면 오름차순으로 정렬된 배열이 만들어진다.

방금 언급한 정렬 결과 배열 [7, 6, 8, 1, 2, 5, 3, 4]를 예로 들어 보자.

• 마지막 자릿수를 기준으로 2 그룹 (7 6 8), 0 그룹 (1 2), 1 그룹 (5 3 4) 순으로 배치되었다.
• 그룹의 순서를 뒤바꾸면 [1, 2, 5, 3, 4, 7, 6, 8]이 된다.
• 또한 0 그룹과 2 그룹은 정렬 순서가 반전되었다.
• 0 그룹과 2 그룹의 정렬 순서를 반전시키면 [2, 1, 5, 3, 4, 8, 6, 7]이 된다.
• 각 그룹에 대하여 재귀적으로 복구를 수행하면 오름차순으로 정렬된 배열 [1, 2, 3, 4, 5, 6, 7, 8]을 얻을 수 있다.

이 과정을 반대로 생각해보면 크기가 N인 배열에 대하여 항상 동일한 정렬 결과를 얻을 수 있음을 알 수 있다.

이를 이용하면 우리가 그토록 바라던 오름차순 정렬을 수행할 수 있다.

위에서 언급하였듯이 N = 8인 배열 A = [6, 7, 2, 4, 5, 8, 1, 3]을 정렬하였을 때 정렬 결과는 [7, 6, 8, 1, 2, 5, 3, 4]가 되었다.

배열 A의 원소를 재배치하더라도 정렬 결과는 항상 [7, 6, 8, 1, 2, 5, 3, 4]가 된다는 사실에 주목하자.

 

우리는 1이 배열의 1번째 원소가 되기를 바란다.

하지만 정렬 결과 배열의 1번째 원소는 항상 7이 된다.

만약 우리가 1을 7로 대체한다면, 1은 우리가 바라던 대로 배열의 1번째 원소가 된다.

 

A = [6, 7, 2, 4, 5, 8, 1, 3] -> [6, 7, 2, 4, 5, 8, 7, 3]

 

우리는 2가 배열의 2번째 원소가 되기를 바란다.

하지만 정렬 결과 배열의 2번째 원소는 항상 6이 된다.

만약 우리가 2를 6으로 대체한다면, 2는 우리가 바라던 대로 배열의 2번째 원소가 된다.

 

A = [6, 7, 2, 4, 5, 8, 7, 3] -> [6, 7, 6, 4, 5, 8, 7, 3]

 

모든 원소에 대하여 이 작업을 반복하면 배열 A는 다음과 같이 변한다.

 

A = [6, 7, 2, 4, 5, 8, 1, 3] -> [5, 3, 6, 1, 2, 4, 7, 8]

 

이 배열에 3진수 기수 정렬을 수행하면 우리가 바라던 오름차순 정렬이 완료된다.

실제로 정렬이 잘 수행되는지 확인해보자.

정렬 결과 5는 배열의 6번째 원소가 되는데 5의 실제 값은 6이다.

정렬 결과 3은 배열의 7번째 원소가 되는데 3의 실제 값은 7이다.

...

금쪽이 폼 미쳤다.

 

이 작업을 두 번째 정규화라고 하고 정렬 결과 배열을 마법의 배열이라고 하자.

정규화라는 용어가 적절하지는 않은 것 같지만 바꿀 생각은 없다.

 

정리하자면, 우리의 정렬 알고리즘은 다음과 같다.

1. 입력 배열을 0 이상 N 미만의 정수로 정규화한다.
2. 3진수 기수 정렬을 수행하여 마법의 배열을 얻는다.
3. 마법의 배열을 이용하여 두 번째 정규화를 수행한다.
4. 3진수 기수 정렬을 다시 한 번 수행하여 실제로 수행해야 하는 명령어를 얻는다.

 

추가적인 최적화

그럭저럭 만족스러운 결과를 얻었지만 3radix[100] = 869로 약간 아쉬운 성능을 보여주고 있다.

기수 정렬의 단점은 원소의 최대 자릿수가 증가할수록 명령어의 개수도 증가한다는 것이다.

N = 100 = 81 + 19 = 3^4 + 19로 최대 5개의 자릿수를 사용하고 있다.

또한 자릿수가 홀수이기 때문에 배열 B에 위치한 원소들을 배열 A로 옮기기 위한 100개의 추가 명령어도 사용하고 있다.

 

잘 관찰해보면 특수한 형태의 N에 대하여 3진수 기수 정렬 2번을 4진수 기수 정렬 1번으로 대체할 수 있음을 알 수 있다.

N = 100인 경우 기존 알고리즘에서는 3진수 기수 정렬을 5번 수행해야 한다.

하지만 3진수 기수 정렬을 3번만 수행하고 마지막에 4진수 기수 정렬을 1번 수행하더라도 정렬을 완료할 수 있다.

모든 N에 대하여 가능한 것은 아니고 3 * 3^k < N <= 4 * 3^k를 만족하는 N에 대하여 이러한 최적화를 수행할 수 있다.

그리고 3 * 3^3 = 81 < N = 100 <= 4 * 3^3 = 108로, N = 100인 경우 4진수 기수 정렬 최적화가 가능하다.

이 최적화를 추가하면 N = 100일 때 688개의 명령어로 정렬이 가능해진다.

 

4진수 기수 정렬 방법을 떠올리기 어려울 수 있는데 전체적인 아이디어는 3진수 기수 정렬과 유사하다.

0 그룹과 1 그룹은 배열 B의 앞뒤로 보내고 2 그룹과 3 그룹은 배열 A의 뒤로 보낸다.

이렇게 하면 0 그룹과 1 그룹은 배열 B에서 앞뒤로 분리되어 있고 2 그룹과 3 그룹은 배열 A에 섞여 있게 된다.

여기서 2 그룹은 배열 B의 앞으로 보내고 3 그룹은 배열 B의 뒤로 보낸다.

정렬 순서가 2 그룹, 0 그룹, 1 그룹, 3 그룹 순이 되고 일부 그룹은 정렬 순서가 반전되지만 이전과 동일한 이유로 신경 쓰지 않아도 된다.

시간 복잡도는 O(2 N * ceil(log_4 N))이 되는데 4진수 기수 정렬을 주력으로 사용할 것은 아니기 때문에 중요하지는 않다.

 

구현은 쉬워요

글만 읽으면 어려워 보일텐데 핵심만 파악하면 쉬운 알고리즘이다.

그리디나 모래 시계 방법에 비하여 시간 복잡도도 뛰어나고 구현도 어렵지 않다.

유행이 바뀔 때가 되었다.

이해가 어렵거나 잘못된 내용이 있는 경우 댓글 부탁드립니다.

 

끝

끝