나는 (아마도 minckim님의 가이드로 가장 유명한) 빠른정렬 풀이로 push_swap을 해결했다. push_swap을 너무 재미있게 공부한 나머지, 스스로 막혔을 때 혹은 동료학습 과정에서 문제 해결의 실마리가 되어 준 몇 가지 아이디어를 되짚어 정리해보았다.
먼저 1~3번은 push_swap만의 '스택'이 배열과 어떻게 다른지 설명한다. 뒤이은 4~5번에서는 빠른정렬의 가장 큰 특징 중의 하나인 '재귀'를 보다 쉽게 이해하기 위한 방법을 다뤘다.
우리 스택의 정체는 무엇일까
(앞으로 push_swap에서 주어진 자료구조를 '우리 스택'이라고 부르겠다.)
1. 우리 스택은 큰 수부터 정렬해야 한다
하나의 정렬 방법도 자료구조에 따라 여러가지 모습이 될 수 있다는 걸 확인할 수 있다는 점은 이 과제의 큰 매력 중 하나다.
아래는 우리에게 익숙한 배열기반의 빠른정렬 함수와, 이 코드에 의해 정렬되는 배열의 모습이다.
1 void quicksort(arr[], left, right)
2 {
3 if (데이터가 1개)
4 //재귀 탈출!
5 pivot = partition(arr[], left, right);
6 quicksort(arr[], left, pivot - 1);
7 quicksort(arr[], pivot + 1, right);
8 }
이 코드와 배열은 모두, (코드의 경우 line 6과 line 7에 의해) 작은 수 먼저 정렬하고 있다. 왜 그런 걸까? 별 이유는 없다! 사실 배열은 어떤 데이터에든 아무 때나 인덱스로 접근할 수 있지 않은가. 때문에 line 6과 line 7의 순서가 바뀐다 해도 결과는 잘 나올 것이다.
반면에 우리 스택은 순서를 바꿀 수 있는 이동연산(push, swap)이 top에서만 가능하다는 큰 제한이 있다. 그림의 왼쪽을 우리 스택의 top, 오른쪽을 bottom이라고 치고 상상해보자. 중간에 깔려 있는 데이터들에 접근할 수 있는 명령어가 우리에겐 없음을 금방 알 수 있을 것이다.
이 때문에 우리 스택에서는 파티션한 후에 각 덩이들이 재귀함수에 들어가는 순서가 중요해진다. 1) 이동연산은 언제나 top에서만 가능하고, 2) 큰 수일 수록 아래로(즉 오름차순으로) 정렬해야 하기 때문에, 순서가 상관 없는 배열에서의 정렬과는 달리 line 7 -> line 6의 순서로 진행해야만 할 것이다.
2. 왜 하필 2 피봇일까?: 우리의 스택은 3개의 공간을 가지고 있다
push_swap을 빠른정렬로 풀다보면, 분할의 총 횟수를 줄이기 위해 한 번에 더 많은 덩이로 분할하고 싶어진다. (왜 그래야 하는지 모르겠을 땐 빠른정렬의 시간복잡도를 익히면 좋다.)
그리고 '배열'을 빠른정렬로 정렬할 때는 의식하지 못했지만, 사실 분할에는 항상 분할한 각 덩이들을 흐트러짐 없이, 순서대로 보관할 공간이 필요하다. (당연하다, 기껏 분류해두었는데 다시 섞이면 안 되니까.)
push_swap의 스택은 얼핏 보기에는 우리가 익히 알고 있는 스택, 즉 하노이의 탑 문제의 바닥이 막힌 기둥처럼 보이지만 rotate가 가능하다는 점이 다르다. stack A와 stack B를 2개보다 더 많은 공간으로 나누어 사용하기 위해 우리는 이 특징을 이용하게 된다.
좀더 설명하자면 이렇다. stack A와 stack B를 2개의 공간으로 사용할 때는, stack A에 있는 데이터들은 'stack A에 보관하기(ra)'와 'stack B에 보관하기(pb)'의 두 가지 동작에 의해 2개 덩이로 나눌 수 있다. 만약 stack A에 있는 데이터들을 3개 덩이로 나누고 싶다면? 기존의 'stack B에 보관하기(pb)' 대신, 'stack B의 위쪽에 보관하기(pb)'와 'stack B의 아래쪽에 보관하기(pb + rb)'의 두 개 동작을 사용한다면 stack B를 2개 공간인 것처럼 활용할 수 있다. 병에 담긴 물과 기름처럼.. 물론 실제로는 하나의 자료구조에 있는 것이기 때문에, 어디까지가 물이고 어디까지가 기름인지는 기억해 둬야 한다.
이렇게 하면 우리 스택을 최대 3개 공간으로 활용, 다시 말해 최대 2개 피봇으로 3분할 할 수 있게 된다.
3. 피봇은 주인공이 아니다: 피봇을 포함하여 분할해보자
우리에게 가장 익숙한 빠른정렬의 분할 알고리즘인 배열 기반의 로무토 파티션은, 한 번의 분할이 끝나면 피봇 데이터 한 개가 자기 자리를 찾는다(=정렬된다). 그런데 '피봇이 자기 자리를 찾았다!'는 사실에 현혹되면 안 된다. 빠른정렬이 빠른 이유는 '피봇을 제자리에' 두었기 때문이 아니라 '일을 분할'했기 때문임을 기억해야 한다.
우리가 배웠던 다음의 분할방법을, '피봇보다 작은 덩이' '피봇' '피봇보다 큰 덩이' 이렇게 3개 덩이로 나누는 것이라고 한 번 생각해보자.
void quicksort(arr[], left, right)
{
if (데이터가 1개)
//재귀 탈출!
pivot = partition(arr[], left, right); // 덩이1: 피봇. 정렬되었으므로 더이상 나눌 필요가 없다.
quicksort(arr[], left, pivot - 1); // 덩이2: 피봇보다 작은 수의 덩이
quicksort(arr[], pivot + 1, right); // 덩이3: 피봇보다 큰 수의 덩이
}이것이 가능한 이유는, (2에서도 이야기한 것처럼) 분할에는 분할한 각 덩이들을 그 위치에 그대로 보관할 공간이 필요하고, 그것은 정렬 완료된 피봇에도 해당하기 때문이다. 그리고 만약 이런 방식을 고수하면서 2개의 피봇을 사용하여 3분할하려고 한다면, 덩이는 2(피봇) + 3, 총 5개가 될 것이다.
그런데 우리 스택은 (2에서 본 것처럼) 최대 3개의 공간으로 활용할 수 있기 때문에 이 방법은 불가하다. 우리는 위 코드처럼 피봇에게 하나의 공간을 내어주며 2분할 할 것인지(1(피봇) + 2), 아니면 덩이에 피봇을 포함하는 대신 3분할 할 것인지 선택해야 한다. 전자의 경우 순회해야 하는 원소 수가 하나 줄어드는 장점이, 후자의 경우 분할을 더 많이 할 수 있는 장점이 있을 것이다.
만약 위 예시를, '피봇을 포함'하여 2분할하도록 한다면 다음과 같을 것이다.
void quicksort(arr[], left, right)
{
if (데이터가 1개)
//재귀 탈출!
pivot = partition(arr[], left, right);
quicksort(arr[], left, pivot); // 덩이1: 피봇보다 작거나 같은 덩이
quicksort(arr[], pivot + 1, right); // 덩이2: 피봇보다 큰 덩이
}물론 덩이1 대신 덩이2에 피봇이 포함되어도 상관 없다.
(+) 실제로는 1) '피봇을 포함하여 2분할'하거나 2) '피봇을 포함하여 3분할'하는 식으로 구현하는 경우가 대부분이고, 피봇을 포함하지 않는 경우는 고려되지 않는 것 같다.
(+) 왜 이렇게까지 했나 싶지만 어쩌다 보니..
재귀로 가는 징검다리
4. 재귀는 두괄식을 좋아한다: 함수 이름을 바꿔보자
재귀를 이해하기 어려울 때 해 볼 수 있는 잘 알려진 팁 중 하나는, 함수이름을 함수의 행동 자체가 아닌 행동의 결과로 개명해보는 것이다. 함수가 끝났을 때 우리가 되어 있기를 바라는 상태는 무엇인가?
push_swap 프로그램의 최종목적은 stack A에 들어온 모든 데이터를 오름차순으로 정렬하는 것이다. 그런데 그 일을 하는 함수를 가리켜 (파티션 과정에서 stack B로 이동하는 데이터들이 반 혹은 그 이상이라는 점을 살려) a_to_b()라고 이름짓는 경우가 많다.
void a_to_b(struct *stacks, int left, int right)
{
if (데이터가 1개)
//재귀 탈출!
// pivot 정하기
partition(stacks, left, right);//여기가 핵심!
a_to_b(stacks, pivot, right);
b_to_a(stacks, left, pivot);
}위와 같은 함수명의 단점은 이 함수의 목적이 무엇인지 짐작하기 어렵다는 것이다(리뷰어: '왜 stack A에서 stack B로 이동시킨다는 거지?'). 게다가 실제로 a_to_b()함수의 핵심인 partition() 함수에서는 stack A에서 stack B로 이동하는 데이터 뿐 아니라 stack B에서 stack A로 이동하는 데이터도 있으니 함수의 행동에 대한 정확한 설명도 아니다.
함수이름을 quicksort_stack_a() 혹은 sort_at_stack_a() 같은 식으로 바꿔보는 것은 어떨까.
void sort_stack_a(struct *stacks, int left, int right)
{
if (데이터가 1개)
//재귀 탈출!
partition(stacks, left, right);//여기가 핵심!
sort_stack_a(stacks, pivot, right);
sort_stack_b(stacks, left, pivot);
}a_to_b()가 끝났을 때 우리가 바라는 건 stack A에 있는 특정 구간(인자로 넣은 left ~ right)의 데이터들이 오름차순으로 정렬되어 있는 것이다. 마찬가지로 b_to_a()가 끝났을 때는 stack B의 특정 구간 데이터들이 완전히 정렬되어 있기를 바란다.
이 점을 살려 함수 이름을 짓는다면 중간과정에 주목하는 대신 결과부터 생각할 수 있다. 재귀함수가 생각하는 방식처럼 말이다.
5. 문제를 단순하게: a_to_b()만을 이용해서 정렬해보자
(4에서 설명한 이유로 앞으로 a_to_b()의 역할을 하는 함수는 sort_stack_a()로, b_to_a()의 역할을 하는 함수는 sort_stack_b()로 바꿔 부르기로 한다.)
사실 sort_stack_b()는 스택공간을 최대한 활용하려는 (=stack A와 stack B 모두를 파티션하는 거점으로 사용하기 위한) 목적에서 추가된 것일 뿐, 있으나 없으나 정렬이 되는 과정은 거의 비슷하다. 그런데 괜히 이 함수 때문에 머리가 더 복잡해지는 것 같다.
그렇다면 sort_stack_b() 함수 없이 sort_stack_a()만으로도 문제를 해결할 수 있을까?
1 void sort_stack_a(struct *stacks, int left, int right)
2 {
3 if (데이터가 1개)
//재귀 탈출!
5 partition(stacks, left, right); //큰 수는 stack a에, 작은 수는 stack b에
6 sort_stack_a(stacks, pivot, right); //stack a에 있는 수를 정렬
7 //partition()에서 pb한 만큼 다시 pa한다.
8 sort_stack_a(stacks, left, pivot); //stack b에 있다가 stack a에 도착한 나머지 수를 정렬
9 }위 코드와 같은 방법이라면 가능하다. 파티션하는 공간을 stack A로 한정하고, stack B는 일을 잠시 미뤄두는 보조공간으로만 쓴다고 생각하면 된다.
다시 말해,
line 6: 일단 stack A에 있는 데이터들을 모두 정렬하고,
line 7: 미뤄두었던 일을 stack A로 가져와서,
line 8: 마저 정렬하는 것이다.
그런데 line 7에서 아무 의미도 없이 그냥 도로 데이터를 가져오기만 하긴 좀 아쉽다. 오는 길에도 뭔갈 더 하면 좋겠다. stack A와 stack B가 거울 같은 공간이라고 생각하면, stack A가 stack B를 이용해 자신을 정렬하는 것처럼, stack B도 stack A를 이용해 자신을 정렬할 수 있지 않을까?
sort_stack_b()는 (아마도) 이런 과정을 통해 탄생했다. 결국 sort_stack_b()는 sort_stack_a()와 다를 바 없는 역할을 하고 있는 것이다.
퀵쏘트 예찬..
push_swap을 빠른정렬로 푸는 것은 약간 억지스럽게 느껴지기도 한다. 실제로 잘 알려진 빠른정렬을 응용한 풀이로 문제를 풀 경우, 미리 정렬하거나 미리 비교하는 식으로 여러 구간에서 추가적인 작업(최적화)을 해 주어야만 과제가 요구하는 명령어 개수를 충족(5점 만점 기준)시킬 수 있다.
그러나 그 덕분에 오히려 배울 수 있는 것이 많았다고 생각한다.
먼저 특이하게도 채점 조건에 비교연산은 고려되지 않으므로 비교할 수 있는 데선 주구장창 비교하게 되는데, 덕분에 비교연산과 이동연산의 비용에 대해, 내가 선택한 정렬알고리즘이 왜 이런 시간복잡도를 가지고 언제 비효율적인지에 관해 생각해 볼 수 있다.
또 최적화해야 하는 구간이 요기조기 많으니, 이건 안 해도 되지 않을까 하는 마음에 '미리 시간복잡도를 계산한 다음 예상하는 결과를 낼 때만 적용하는 방식'으로 프로그래밍 할 수 있는 기회(?)가 많이 주어진다. 덕분에 '일단' 해보는 대신 시간복잡도를 활용하는 것이 실제로 어떻게 좋은지 경험할 수 있었다.
적어도 나처럼 자료구조, 정렬 알고리즘, 시간복잡도 같은 개념이 완전히 처음인 카뎃이라면 (비록 이미 잘 알려진 해답을 흉내내는 것에 불과하더라도, 여전히) push_swap을 빠른정렬(을 포함한 몇몇의 기본 정렬 알고리즘)로 풀면서 많은 걸 얻어갈 수 있을 거라 생각한다.
게다가 빠른정렬은 이름 그대로 가장 빠른 시간복잡도를 가지는 대표적인 정렬방법이고, 특히 하드웨어적으로도 비교적 효율적인 방법(에 대한 재밌는 글 하나)이라 가장 많이 사용되는 정렬알고리즘이기도 하다..!
그러니 여러분, 빠른정렬을 포기하지 말아 주세요.
