[42경산 push_swap] 11개 명령어로 정렬하기: 순위 변환, 비용 계산, 이진 기수 정렬
TL;DR (세 줄 요약)
- push_swap은 스택 두 개와 명령어 11개만으로 정수를 정렬하는 42 과제입니다. 최고점 기준은 숫자 100개를 700회 미만, 500개를 5,500회 이하의 명령어로 정렬하는 것입니다.
- 숫자를 0부터 N-1까지의 순위로 바꾸면 문제가 단순해집니다. 이진 기수 정렬은 구현하기 쉽지만, 계산하면 100개에 1,084회, 500개에 6,784회가 필요해서 최고점 기준에는 미치지 못합니다.
- 명령어를 줄이려면 회전 방향(
ra와rra) 가운데 횟수가 적은 쪽을 고르고,rr과rrr로 두 스택을 함께 돌려야 합니다. 제 구현은 이 비용 계산을 쓰는 그리디 방식입니다.
이 글은 42경산의 push_swap 과제를 풀면서 정리한 내용입니다. 과제의 규칙, 명령어 11개, 숫자를 순위로 바꾸는 방법, 이진 기수 정렬, 명령어 수를 줄이는 방법을 순서대로 설명합니다.

1. push_swap은 어떤 과제인가요?
과제 문서에 따르면 목표는 주어진 정수들을 가장 적은 수의 명령어로 정렬하는 것입니다[1]. 스택은 나중에 넣은 것을 먼저 꺼내는 자료구조입니다. 규칙은 세 가지입니다.
- 기본 구조:
a와b라는 스택 두 개가 주어집니다. 프로그램이 시작할 때 모든 정수는 스택a에 있고, 스택b는 비어 있습니다[1]. - 오류 처리: 입력에 중복된 값이 있거나, 정수가 아닌 인자가 있거나, 정수 범위를 넘는 값이 있으면 표준 에러(오류 메시지를 내보내는 출력 통로)에 "Error"를 출력하고 프로그램을 끝내야 합니다[1].
- 성능 기준: 점수는 명령어의 수로 정해집니다. 최고점을 받으려면 숫자 100개를 700개 미만의 명령어로, 숫자 500개를 5,500개 이하의 명령어로 정렬해야 합니다[1].
그래서 이 과제는 "정렬하기"보다 "명령어 수 줄이기"가 핵심입니다.
2. 명령어 11개는 무엇인가요?
과제에서 쓸 수 있는 명령어는 11개뿐입니다[1]. 하는 일에 따라 네 묶음으로 나눌 수 있습니다.
| 묶음 | 명령어 | 하는 일 |
| 교환 | sa, sb, ss | 스택 맨 위의 두 원소를 서로 바꿉니다. ss는 sa와 sb를 함께 실행합니다. |
| 이동 | pa, pb | 한 스택의 맨 위 원소를 다른 스택의 맨 위로 옮깁니다. 두 스택 사이에서 원소를 옮기는 방법은 이것뿐입니다. |
| 회전 | ra, rb, rr | 맨 위 원소를 맨 아래로 보냅니다. 나머지 원소는 한 칸씩 위로 올라갑니다. rr은 두 스택을 함께 돌립니다. |
| 역회전 | rra, rrb, rrr | 맨 아래 원소를 맨 위로 가져옵니다. 나머지 원소는 한 칸씩 아래로 내려갑니다. rrr은 두 스택을 함께 돌립니다. |
교환은 맨 위의 두 원소만 바꾸므로 스택 전체에 주는 영향이 가장 작습니다. 회전은 스택의 모든 원소를 한 칸씩 움직입니다. 회전을 얼마나 적게 쓰는지가 명령어 수를 좌우합니다. 과제 설명서에는 2 1 3 6 5 8을 정렬하는 예시가 실려 있습니다[1].
3. 왜 스택을 원형 리스트처럼 생각해야 하나요?
과제에서는 자료구조를 "스택"이라고 부릅니다. 하지만 보통의 스택과는 다릅니다[2]. 보통의 스택은 LIFO(Last-In, First-Out) 구조라서 맨 위의 원소에만 접근할 수 있습니다. push_swap에서는 회전 명령어(ra, rra 등)를 쓰면 모든 원소를 맨 위로 가져올 수 있습니다.
ra는 맨 위 원소를 맨 아래로 보냅니다.rra는 맨 아래 원소를 맨 위로 가져옵니다.
이 두 명령어 때문에 스택의 위쪽 끝과 아래쪽 끝이 이어진 것처럼 동작합니다. 이런 구조는 양방향 원형 연결 리스트(doubly-linked circular list)나 덱(deque)과 비슷합니다. 덱은 양쪽 끝에서 원소를 넣고 뺄 수 있는 자료구조입니다. 모든 원소에 접근할 수 있지만, 필요한 명령어 수는 그 원소가 양 끝에서 얼마나 떨어져 있는지에 따라 달라집니다.
그래서 질문을 바꿔야 합니다. "스택으로 어떻게 정렬할까?"가 아니라 "임시 공간 하나를 써서 원형 리스트를 어떻게 적은 회전으로 다시 배열할까?"로 생각합니다.
4. 가장 작은 수부터 옮기는 방법은 왜 명령어가 많이 드나요?
가장 먼저 떠오르는 방법은 매번 가장 작은 수를 찾아서 옮기는 것입니다. 그리디(Greedy)는 매 순간 가장 좋아 보이는 선택을 하는 방식을 말합니다. 이 방법의 순서는 다음과 같습니다.
- 스택
a에 남아 있는 수 가운데 가장 작은 수를 찾습니다. - 그 수가 스택
a의 맨 위에 오도록 회전합니다. pb로 스택b에 옮깁니다.- 스택
a가 빌 때까지 반복합니다. 그다음 스택b의 모든 원소를pa로 다시 가져옵니다.
숫자가 적을 때는 이 방법도 쓸 만합니다. 하지만 숫자가 많아지면 명령어 수가 빠르게 늘어납니다. 숫자 하나를 맨 위로 가져오는 데 회전이 최대 스택 크기의 절반만큼 필요합니다. 이 일을 숫자 개수만큼 반복합니다. 그래서 전체 회전 횟수는 숫자 개수의 제곱에 비례해서 늘어납니다.
이 방법은 "지금 옮길 수 하나"만 봅니다. 지금의 이동이 다음 이동을 쉽게 만드는지는 따지지 않습니다. 이렇게 눈앞의 선택만 좋은 답을 지역 최적해(local optimum)라고 부릅니다. 명령어 수를 줄이려면 두 스택의 회전을 함께 따지는 계산이 필요합니다. 그 방법은 10번에서 설명합니다.
5. 청크 방식은 무엇이 다른가요?
청크(chunk) 방식은 전체 숫자 범위를 여러 조각으로 나누는 방법입니다. 예를 들어 숫자 100개를 20개씩 5개의 청크로 나눕니다. 그다음 한 청크에 속하는 숫자를 스택 a에서 b로 옮기고, 정렬해서 다시 a로 가져오는 일을 청크마다 반복합니다[4].
- 나아지는 점: 가장 작은 수 하나를 찾는 대신, 청크에 속하는 수 가운데 가까이 있는 것을 옮기면 됩니다. 그래서 수를 찾으려고 하는 회전이 줄어듭니다.
- 남는 문제: 옮긴 수를 다시 순서대로 가져오는 데 회전이 필요합니다. 청크를 몇 개로 나눌지도 정해진 답이 없어서 여러 번 시험해 봐야 합니다[5].
6. 왜 숫자를 순위로 바꾸나요?
push_swap에서 -2147483648, 50, 101 같은 실제 값은 정렬 방법에 영향을 주지 않습니다. 중요한 것은 수들 사이의 순서뿐입니다. {-10, 500, 0}을 정렬하는 명령어와 {0, 2, 1}을 정렬하는 명령어는 같습니다.
그래서 입력된 숫자를 0부터 N-1까지의 순위(rank)로 바꿉니다. 이 작업을 정규화라고 부릅니다. 순서는 다음과 같습니다[3].
- 입력받은 숫자들을 임시 배열에 복사합니다.
- 임시 배열을 오름차순으로 정렬합니다.
- 스택
a의 원소마다, 정렬된 임시 배열에서 그 숫자가 몇 번째에 있는지(인덱스) 찾습니다. - 스택의 숫자를 찾아낸 인덱스 값으로 바꿉니다.
예를 들어 입력이 {-10, 500, 0}이면 정렬된 임시 배열은 {-10, 0, 500}입니다.
| 원래 값 | 정렬된 배열에서의 위치 | 바뀐 값 |
| -10 | 0번째 | 0 |
| 500 | 2번째 | 2 |
| 0 | 1번째 | 1 |
스택 a는 {0, 2, 1}이 됩니다. 이렇게 바꾸면 문제가 "임의의 정수 정렬"에서 "0부터 N-1까지의 수 정렬"로 바뀝니다. 음수가 없어지고 값의 범위가 정해지므로, 청크를 나누거나 비트를 확인하는 계산이 쉬워집니다[6].
7. 이진 기수 정렬은 어떻게 동작하나요?
기수 정렬(Radix Sort)은 숫자를 자릿수별로 정렬하는 방식입니다. 십진수라면 일의 자리, 십의 자리 순서로 정렬합니다. 이진 기수 정렬은 숫자를 2진수로 보고, 가장 낮은 비트(LSB)부터 가장 높은 비트(MSB)까지 차례로 정렬합니다. 비트는 2진수의 한 자리입니다. 이때 C 언어의 비트 연산자 두 개를 씁니다[7].
- 오른쪽 시프트(>>):
(num >> i)는num의 비트들을 오른쪽으로 i칸 옮깁니다. i번째 비트가 가장 오른쪽 자리로 옵니다. - 비트 AND(&):
(num >> i) & 1은 i번째 비트가 1이면 1을, 0이면 0을 돌려줍니다.
push_swap에서는 스택 a를 "비트가 1인 수를 두는 곳"으로, 스택 b를 "비트가 0인 수를 두는 곳"으로 씁니다. 순위로 바꾼 가장 큰 수(N-1)를 나타내는 데 필요한 비트 수만큼 다음 과정을 반복합니다.
비트 i마다(가장 낮은 비트부터) 하는 일:
- 스택
a에 있는 숫자 N개를 하나씩 확인합니다. - 스택
a의 맨 위에 있는 숫자num의 i번째 비트를 확인합니다. ((num >> i) & 1) == 0이면 i번째 비트가 0입니다.pb로 스택b에 옮깁니다.((num >> i) & 1) == 1이면 i번째 비트가 1입니다.ra로 스택a의 맨 아래로 보냅니다. 숫자는 스택a에 남고, 다음 숫자가 맨 위로 올라옵니다.- N개를 모두 확인하면 스택
a에는 i번째 비트가 1인 숫자만, 스택b에는 i번째 비트가 0인 숫자만 있습니다. pa를 반복해서 스택b의 모든 숫자를 스택a로 다시 가져옵니다. 이제 스택a는 가장 낮은 비트부터 i번째 비트까지 기준으로 정렬된 상태입니다.
필요한 모든 비트에 대해 이 과정을 반복하면 스택 a가 정렬됩니다[6].
왜 이 방법으로 정렬이 되나요?
기수 정렬이 올바르게 동작하려면 안정성(stability)이 필요합니다. 안정성은 같은 자릿수 값을 가진 원소들의 순서가 정렬한 뒤에도 그대로 유지되는 성질입니다. push_swap의 기수 정렬은 ra와 pb로 이 성질을 지킵니다.
- i번째 비트가 1인 숫자를
ra로 돌리면, 그 숫자들끼리의 순서가 그대로 유지됩니다. - i번째 비트가 0인 숫자를
pb로 차례로 쌓으면, 먼저 옮긴 숫자가 스택b의 더 아래에 놓입니다.pa로 다시 가져오면 원래의 순서로 돌아옵니다.
8. 이진 기수 정렬은 명령어를 몇 번 쓰나요?
이진 기수 정렬의 명령어 수는 입력 순서와 상관없이 정해져 있습니다. 비트 하나를 처리할 때 숫자 N개마다 ra나 pb를 한 번씩 쓰고, pb로 옮긴 만큼 pa를 씁니다. 0부터 N-1까지의 순위에 대해 계산하면 다음과 같습니다.
| 숫자 개수 | 필요한 비트 수 | ra | pb | pa | 합계 | 최고점 기준 |
| 100개 | 7 | 316 | 384 | 384 | 1,084 | 700 미만 |
| 500개 | 9 | 2,216 | 2,284 | 2,284 | 6,784 | 5,500 이하 |
이진 기수 정렬은 규칙이 단순해서 구현하기 쉽습니다. 하지만 이 방법만으로는 최고점 기준에 미치지 못합니다. 최고점 기준을 맞추려면 10번에서 설명하는 회전 비용 계산이 필요합니다.
9. 숫자가 적을 때는 어떻게 정렬하나요?
숫자의 개수(N)가 아주 적을 때는 미리 정해 둔 명령어를 쓰는 편이 명령어 수가 적습니다.
- N=2: 정렬되어 있지 않으면
sa한 번으로 끝납니다. - N=3: 숫자 3개로 만들 수 있는 순서는 6가지(3!)입니다. 모든 경우를 최대 2개의 명령어로 정렬할 수 있습니다. 경우마다 쓸 명령어를 미리 정해 둡니다(예:
2 1 0은sa,rra)[3]. - N=4와 N=5: 스택
a에서 원소 1~2개를b로 보내서 3개짜리 문제로 줄입니다. 3개를 정렬한 뒤,b의 원소를 올바른 자리에 다시 넣습니다. 숫자 5개를 정렬할 때 허용되는 명령어는 최대 12개입니다[8].
가장 작은 크기의 문제를 정확히 풀어 두면, 큰 문제를 풀 때도 마지막 단계에서 이 방법을 다시 쓸 수 있습니다[9].
10. 회전 비용은 어떻게 줄이나요?
ra와 rra 가운데 횟수가 적은 쪽을 고릅니다
어떤 원소를 스택의 맨 위로 가져와야 할 때는 ra와 rra 가운데 어느 쪽이 횟수가 적은지 계산해야 합니다. 크기가 s인 스택에서 위에서부터 i번째(0부터 셈)에 있는 원소를 맨 위로 가져온다고 하겠습니다.
ra를 쓰면 i번이 필요합니다.rra를 쓰면 s - i번이 필요합니다.
둘 가운데 작은 값을 고릅니다[3]. ra만 쓰면 평균 s/2번이 필요하고, 작은 쪽을 고르면 평균 s/4번 정도가 필요합니다. 평균 회전 횟수가 절반 정도로 줄어듭니다.
rr과 rrr로 두 스택을 함께 돌립니다
스택 a와 b에 필요한 회전을 따로 계산해서 따로 실행하지 않고, 두 스택의 회전을 함께 계산합니다. 이 방법은 스택 b의 원소를 a로 옮길 때 씁니다. b의 원소를 맨 위로 가져오는 비용과, 그 원소가 들어갈 a의 자리를 맨 위로 가져오는 비용을 함께 봅니다.
a에 필요한 회전 수를 cost_a, b에 필요한 회전 수를 cost_b라고 하겠습니다. ra 방향은 양수, rra 방향은 음수로 적습니다.
- cost_a와 cost_b가 모두 양수이면, min(cost_a, cost_b)번만큼
rr을 씁니다. 남은 회전은ra나rb로 처리합니다. - cost_a와 cost_b가 모두 음수이면, min(|cost_a|, |cost_b|)번만큼
rrr을 씁니다.
rr과 rrr은 명령어 한 개로 두 스택을 함께 돌리므로, 겹치는 횟수만큼 명령어가 줄어듭니다[5].
11. 제 구현은 어떤 순서로 정렬하나요?
제가 제출한 구현은 기수 정렬을 쓰지 않습니다. 10번의 회전 비용 계산을 쓰는 그리디 방식입니다. 순서는 다음과 같습니다.
- 입력 검사: 인자를 읽고 검사합니다. 중복된 값이나 정수가 아닌 값이 있으면 과제 문서대로 오류를 처리합니다[1].
- 순위 변환: 입력된 정수를 0부터 시작하는 순위로 바꿉니다(6번).
- 개수에 따라 방법 고르기: 이미 정렬되어 있으면 아무 명령어도 출력하지 않습니다. 3개 이하이면 가장 큰 수의 위치를 보고 회전을 한 번 하고, 필요하면
sa를 한 번 씁니다. - 비용 기반 그리디: 4개 이상이면 스택
a에 3개만 남기고 나머지를b로 옮깁니다. 옮길 때마다 비용이 가장 적은 원소를 고릅니다. 남은 3개를 정렬합니다. 그다음b의 원소 가운데a의 올바른 자리에 넣는 비용이 가장 적은 것부터a로 옮깁니다. - 청크: 500개 이상이면 순위 범위를 청크로 나누고, 청크 순서대로
b로 옮깁니다.a로 되돌릴 때는 4번과 같은 방법을 씁니다. - 마무리: 가장 작은 수(순위 0)가 맨 위에 오도록 스택
a를 회전합니다. 이때도ra와rra가운데 횟수가 적은 쪽을 고릅니다[10].
여기서 비용은 두 스택에 필요한 회전 횟수를 합친 값입니다. 두 스택이 같은 방향으로 돌면 rr이나 rrr로 겹칠 수 있어서, 겹치는 만큼 비용이 줄어듭니다.
push_swap은 일반적인 정렬 알고리즘을 C 언어로 옮기는 과제가 아닙니다. 명령어 11개라는 규칙 안에서 회전 횟수를 줄이는 방법을 찾는 과제입니다.
자주 묻는 질문 (FAQ)
Q1. 이진 기수 정렬만으로 최고점 기준을 맞출 수 있나요?
맞출 수 없습니다. 이진 기수 정렬은 숫자 100개에 1,084회, 500개에 6,784회의 명령어를 씁니다. 최고점 기준은 100개 700회 미만, 500개 5,500회 이하입니다. 기준을 맞추려면 회전 비용을 계산해서 옮길 원소를 고르는 방식이 필요합니다.
Q2. 왜 숫자를 순위로 바꿔야 하나요?
정렬에 필요한 명령어는 실제 값이 아니라 수들 사이의 순서로만 정해지기 때문입니다. 순위로 바꾸면 음수가 없어지고 값이 0부터 N-1까지로 정해집니다. 청크를 나누거나 비트를 확인하는 계산을 그대로 쓸 수 있습니다.
Q3. ra와 rra 가운데 어느 쪽을 써야 하나요?
횟수가 적은 쪽을 씁니다. 크기가 s인 스택에서 위에서 i번째 원소를 맨 위로 가져올 때 ra는 i번, rra는 s - i번이 필요합니다. 두 값을 비교해서 작은 쪽을 고릅니다.
수정 안내
이 글은 2026년 11월 22일에 다시 썼습니다. 고친 내용은 다음과 같습니다.
- 이전 판은 이진 기수 정렬이 100개에 700회 미만, 500개에 5,500회 미만을 쓴다고 적었습니다. 계산하면 1,084회와 6,784회이므로 고쳤습니다.
- 그리디 방식(약 2,500회, 약 60,000회)과 청크 방식(약 1,500~2,000회, 약 12,000~15,000회)의 명령어 수는 근거를 확인할 수 없어서 지웠습니다.
- "기준을 충족하지 못하면 과제는 실패"라는 문장은 지웠습니다. 700회와 5,500회는 최고점 기준입니다.
- 기수 정렬 안에서
rra를 고른다는 설명과 기수 정렬 뒤의 마지막 회전 설명은 기수 정렬의 동작과 맞지 않아서 지웠습니다. - 비트를 확인하는 식에 괄호를 더했습니다. C 언어에서는
==가&보다 먼저 계산되기 때문입니다. - 마지막 절은 제 저장소의 실제 구현 순서로 바꿨습니다. 구현의 명령어 수는 원문에 잰 기록이 없어서 적지 않았습니다.
참고문헌
[1] push_swap.pdf - 42 School Push_Swap Project 공식 문서
[2] [자바] 후입선출(LIFO, Last In First Out)의 자료구조 - 스택(Stack) - HyuniPad
[3] Push_swap: what is the most efficient way to sort given values using a limited set of instructions on two rotatable stacks? - Stack Overflow
[4] [42Seoul] - Push_swap - velog
[5] How to Over-optimize an Algorithm : Push_Swap (42 School Project) - Kilfen Baridon, Medium
[6] Push_Swap Tutorial - Medium (nerd-for-tech)
[7] madebypixel02 / push_swap - GitLab
[8] Push_swap ③ 구현 과정 - Justnote
[9] [push_swap] 5. 최적화 - foufou
[10] My implementation of the 42 — push_swap project - Dan SYLVAIN
참고 자료
같은 주제의 다른 글: [42경산/C언어] Libft 구현 가이드: 표준 C 함수 다시 만들기와 주의점, [42경산/C언어] Get Next Line 가이드: read와 static 변수, 메모리 해제, [42경산 ft_printf] 가변 인자(va_list)로 printf 직접 구현하기, [42경산 Born2beRoot] Rocky Linux 서버 구축: LVM·SSH·SELinux, [42경산 FDF] 와이어프레임 구현 가이드: 등각 투영과 선 그리기