push_swap - swap_push는 그다지 자연스럽지 않아서

들어가며

sa, rra, rra, sa

Push_Swap 과제를 성공적으로 해결하기 위한 첫걸음은 문제의 본질을 정확히 이해하는 것이다. 이 과제는 단순히 두 개의 스택을 이용해 데이터를 정렬하는 문제를 넘어, 제한된 명령어 집합으로 원형 리스트를 효율적으로 재배열하는 고유한 제약 조건을 가진 알고리즘 퍼즐이다.

 

핵심 과제 및 제약 조건

이 프로젝트의 공식 문서에 따르면, 목표는 명확하다: 주어진 정수들을 가장 적은 수의 명령어로 정렬하는 것이다[^1]. 이를 위해 반드시 준수해야 할 핵심 규칙과 제약 조건은 다음과 같다.

 

기본 구조: a와 b라는 두 개의 스택이 주어진다. 프로그램 시작 시, 모든 정수는 스택 a에 위치하며 스택 b는 비어 있다[^1].

오류 처리: 입력값에 중복이 있거나, 정수가 아닌 인자가 포함되거나, 정수 범위를 초과하는 경우, 표준 에러(standard error)에 "Error"를 출력하고 프로그램을 종료해야 한다[^1].

성능 벤치마크: 이 과제의 성패를 가르는 가장 중요한 요소는 명령어의 수다. 100개의 숫자를 정렬할 때는 700개 미만의 명령어를, 500개의 숫자를 정렬할 때는 5500개 이하의 명령어를 사용해야 최고점을 받을 수 있다. 이 기준을 충족하지 못하면 과제는 실패로 간주된다[^1].

 

이러한 제약 조건은 단순히 '정렬'이라는 목표를 넘어 '최적화'라는 핵심 과제를 부각시킨다.

 

도구 상자: 11개 명령어 심층 분석

과제에서 허용된 11개의 명령어는 문제 해결을 위한 유일한 도구다. 각 명령어의 기능을 정확히 이해하고, 이를 기능적으로 분류하는 것은 효율적인 전략 수립의 기반이 된다[^1].

 

1. 최상단 원소 교환 (s 계열: sa, sb, ss): 스택의 맨 위 두 원소의 위치를 바꾸는 지역적(local)인 연산이다. 스택 전체에 미치는 영향이 가장 적다.
2. 스택 간 데이터 전송 (p 계열: pa, pb): 한 스택의 최상단 원소를 다른 스택으로 옮기는 유일한 방법이다. 주 작업 공간(스택 a)과 보조 작업 공간(스택 b) 사이의 데이터 이동을 담당한다.
3. 전체 스택 회전 (r 및 rr 계열: ra, rb, rr, rra, rrb, rrr): 스택의 모든 원소를 한 칸씩 위 또는 아래로 이동시키는 가장 강력하고 복잡한 연산이다. 이 회전 연산의 효율적인 사용이 Push_Swap 알고리즘의 성능을 좌우한다.

 

예를 들어, 과제 설명서의 예시 2 1 3 6 5 8을 정렬하는 과정은 이러한 명령어들이 어떻게 조합되어 사용되는지를 보여준다[^1].

 

LIFO를 넘어서: '스택'이 오해를 부르는 이유

이 과제의 자료구조를 '스택'이라고 부르지만, 이는 전통적인 LIFO(Last-In, First-Out) 자료구조와는 근본적인 차이가 있다[^2]. 전통적인 스택은 오직 최상단 원소에만 접근이 가능하지만, Push_Swap에서는 회전 명령어(ra, rra 등)를 통해 사실상 모든 원소에 접근할 수 있다.

 

이것이 바로 첫 번째 핵심적인 관점의 전환이다. ra는 최상단 원소를 최하단으로 보내고, rra는 최하단 원소를 최상단으로 가져온다. 이는 스택의 양 끝이 연결된, 마치 양방향 원형 연결 리스트(doubly-linked circular list)나 덱(deque)과 유사한 구조를 만든다. 모든 원소에 접근은 가능하지만, 그 비용(명령어 수)이 양 끝으로부터의 거리에 따라 달라지는 것이다.

 

따라서 "스택으로 어떻게 정렬할까?"라는 질문에서 벗어나 "임시 저장 공간을 활용하여 원형 리스트를 어떻게 효율적으로 재배열할까?"라는 질문으로 문제를 재정의해야 한다. 이러한 사고의 전환은 회전 비용을 최소화하는 최적의 알고리즘을 설계하는 첫걸음이다.

 

일반적인 접근법의 한계: 그리디와 단순 청크 방식의 실패 원인 분석

내가 시도했던 그리디(Greedy) 및 청크 기반(Chunked-based) 알고리즘은 직관적이지만, Push_Swap의 엄격한 성능 벤치마크를 통과하기에는 근본적인 한계를 가진다. 이 섹션에서는 두 접근법이 왜 실패하는지 논리적으로 분석하고, 더 나은 전략이 필요한 이유를 제시한다.

 

그리디의 함정: 지역 최적해의 위험성

단순 그리디 알고리즘은 매 순간 가장 좋아 보이는 선택을 하는 전략이다. Push_Swap에서는 다음과 같이 구현될 수 있다:

 

1. 정렬된 상태에서 다음 순서에 와야 할 숫자(예: 현재 스택 a에 있는 가장 작은 수)를 찾는다
2. 해당 숫자를 스택 a의 최상단으로 가져오는 가장 저렴한 회전 명령어 조합을 계산하여 실행한다
3. pb를 이용해 스택 b로 옮긴다
4. 스택 a가 빌 때까지 이 과정을 반복한 후, 스택 b의 모든 원소를 pa로 다시 가져온다

 

이 방식은 작은 N에 대해서는 작동하는 것처럼 보이지만, 숫자의 개수가 늘어날수록 명령어 수가 기하급수적으로 증가한다. 100개의 숫자에 대해 약 2500개, 500개에 대해서는 약 60000개의 명령어를 사용하는 비효율적인 결과를 낳는다[^3].

 

그 이유는 명확하다. 그리디 알고리즘은 하나의 '올바른' 원소를 옮길 때마다 스택 a에 남아있는 다른 모든 원소들의 위치를 완전히 무작위로 섞어버린다. 하나의 작은 문제를 해결하는 동시에 N-1개의 새로운 위치 문제를 만들어내는 것이다. 이는 전형적인 지역 최적해(local optimum)에 빠지는 경우로, '지금 당장' 가장 저렴한 이동이 전체 해법에서는 거의 항상 최악의 선택이 된다. 성공적인 Push_Swap 알고리즘은 현재의 이동이 미래의 상태를 어떻게 더 쉽게 만들지를 고려하는 전역적인 전략을 가져야 한다.

 

개선이지만 해결책은 아닌: 청크(Quicksort-like) 방식

청크 방식은 그리디 알고리즘보다 한 단계 발전된 접근법이다. 전체 숫자 범위를 여러 개의 '청크(chunk)'로 나눈다(예: 100개의 숫자를 20개씩 5개의 청크로). 그런 다음 특정 청크에 속하는 모든 숫자를 스택 a에서 b로 옮기고, 정렬하여 다시 a로 가져오는 과정을 청크별로 반복한다[^4].

 

이 방법은 숫자들을 그룹으로 처리함으로써 순수한 그리디 방식의 무작위성을 일부 줄여주기 때문에 성능이 개선된다. 하지만 근본적으로 이 방식은 무엇일까? 이는 수동으로 버킷(bucket)을 나누는 것과 같다. "0부터 19 사이의 모든 숫자를 이 버킷(스택 b)에 넣어라"라고 명령하는 것과 같다. 이는 청크의 개수를 기수(base)로 하는 기수 정렬(Radix Sort)과 개념적으로 유사하다.

 

그러나 이 과정은 기계적으로 비효율적이다. 스택 a 전체에 흩어져 있는 특정 청크의 원소들을 찾아 b로 보내기 위해 수많은 회전이 필요하며, 정렬된 청크들을 다시 병합하는 과정 역시 비용이 많이 든다. 또한 최적의 청크 크기를 결정하는 것 자체가 어려운 휴리스틱 문제다[^5]. 사용자의 직관은 올바랐지만, 그 실행 방식이 비효율적이었던 것이다. 이는 더 체계적이고 덜 휴리스틱한 버킷팅 방법이 필요함을 시사하며, 다음 섹션에서 다룰 기수 정렬로 자연스럽게 연결된다.

 

표 1: 알고리즘 전략 비교

알고리즘	핵심 로직	강점	약점 / 실패 원인	명령어 수 (N=100)	명령어 수 (N=500)
그리디	매 단계에서 다음으로 정렬될 숫자를 찾아 가장 적은 비용으로 옮김	구현이 간단하고 직관적	지역 최적해에 빠짐. 하나의 이동이 나머지 원소들의 위치를 무작위화하여 장기적으로 비효율 초래	~2500[^3]	~60000[^3]
단순 청크	숫자 범위를 여러 조각(청크)으로 나누고, 청크 단위로 a에서 b로 옮겨 정렬	그리디보다 체계적이며, 그룹 단위 처리로 일부 비효율 감소	청크 내 원소를 찾는 비용이 높고, 청크 병합 과정이 복잡함. 청크 크기 결정이 어려움	~1500-2000	~12000-15000
기수 정렬	숫자를 비트(bit) 단위로 분해하여, 각 비트 값을 기준으로 정렬	전역적인 관점에서 체계적으로 정렬. N이 커져도 명령어 수가 효율적으로 증가	개념이 복잡하고, 데이터 정규화(Normalization) 과정이 선행되어야 함	<700[^1]	<5500[^1]

 

이 표는 현재 사용자의 접근법과 과제가 요구하는 성능 사이의 거대한 격차를 명확히 보여준다. 이 격차를 메우기 위해 왜 더 정교한 알고리즘이 필수적인지에 대한 강력한 동기를 부여한다.

728x90

추상화 계층: 데이터 정규화(랭킹)를 통한 문제 단순화

가장 효율적인 알고리즘을 적용하기 전에, 문제를 더 단순하고 예측 가능한 형태로 바꾸는 매우 중요한 준비 단계가 있다. 바로 데이터 정규화, 즉 랭킹(ranking)이다.

 

값의 무관성

Push_Swap 문제에서 -2147483648, 50, 101과 같은 실제 숫자 값은 정렬 로직 자체에는 아무런 영향을 미치지 않는다. 중요한 것은 오직 그들의 최종적인 상대적 순서뿐이다. {-10, 500, 0}을 정렬하는 것이나 {0, 2, 1}을 정렬하는 것이나 필요한 명령어의 순서와 종류는 동일하다.

 

랭킹 프로세스

정규화 과정은 입력된 숫자들을 0부터 N-1까지의 순위(rank)로 변환하는 작업이다. 이 과정은 다음과 같은 단계로 이루어진다[^3]:

 

1. 입력받은 숫자들을 임시 배열에 복사한다
2. 이 임시 배열을 오름차순으로 정렬한다
3. 원본 스택 a의 각 원소를 순회하면서, 정렬된 임시 배열에서 해당 숫자의 인덱스(위치)를 찾는다
4. 원본 스택의 숫자를 찾아낸 인덱스 값으로 대체한다

 

예를 들어, 입력이 {-10, 500, 0} 이라면, 정렬된 임시 배열은 {-10, 0, 500}이 된다.

 

• -10은 정렬된 배열에서 인덱스 0에 있으므로 0으로 변환된다
• 500은 인덱스 2에 있으므로 2로 변환된다
• 0은 인덱스 1에 있으므로 1로 변환된다

 

최종적으로 스택 a는 {0, 2, 1} 이라는 값을 갖게 된다.

 

고급 알고리즘과의 인과 관계

이 정규화 과정이 왜 그토록 중요할까? 그 이유는 정규화가 고급 알고리즘을 적용하기 위한 전제 조건이기 때문이다. 특히, 이 문제에 가장 효율적인 해결책인 이진 기수 정렬(Binary Radix Sort)은 숫자의 이진 표현(binary representation)을 기반으로 동작한다. 임의의 음수와 양수가 섞인 정수들에 이진 연산을 직접 적용하는 것은 매우 복잡하고 번거롭다.

 

하지만 입력을 0부터 N-1까지의 인덱스로 정규화함으로써, 우리는 비트 연산을 적용하기에 완벽한 데이터 집합을 만들 수 있다. 이제 문제는 "임의의 정수 정렬"에서 "0부터 N-1까지의 순열 정렬"이라는 훨씬 깨끗하고 예측 가능한 문제로 바뀌게 된다. 따라서 정규화는 단순한 최적화 기법이 아니라, 가장 효율적인 알고리즘을 간단하고 효과적으로 구현할 수 있게 해주는 필수적인 기반 작업이다[^6].

 

핵심 엔진: 이진 기수 정렬의 단계별 구현

데이터 정규화로 문제를 단순화했다면, 이제 이 과제를 위한 가장 강력한 정렬 엔진인 이진 기수 정렬을 구현할 차례다. 이 알고리즘은 숫자를 비트 단위로 체계적으로 정렬하여 높은 효율성을 달성한다.

 

기본 이론: 기수 정렬과 비트 논리

기수 정렬은 숫자를 각 자릿수별로 정렬하는 방식이다. 십진수에서는 일의 자리, 십의 자리 순으로 정렬하듯, 이진 기수 정렬에서는 가장 낮은 비트(최하위 비트, LSB)부터 가장 높은 비트(최상위 비트, MSB) 순으로 정렬한다. 이를 위해 C 언어의 비트 연산자에 대한 이해가 필요하다[^7].

 

• 오른쪽 시프트 (>>): (num >> i)는 num의 비트들을 오른쪽으로 i칸 이동시킨다. 이를 통해 i번째 비트를 가장 오른쪽(0번째) 위치로 가져올 수 있다.
• 비트 AND (&): (num >> i) & 1 연산은 오른쪽으로 시프트된 값에 1을 AND 연산하여 i번째 비트가 1이었는지(1 반환) 0이었는지(0 반환)를 확인한다.

 

Push_Swap 기수 정렬 알고리즘

Push_Swap에서의 기수 정렬은 스택 a와 b를 각각 '1' 버킷과 '0' 버킷으로 활용하여 진행된다. 정규화된 가장 큰 수(N-1)를 표현하는 데 필요한 비트 수만큼 다음 과정을 반복한다.

 

각 비트 i에 대하여 (i = 0부터 max_bits까지):

1. 현재 스택 a에 있는 모든 N개의 숫자를 대상으로 루프를 시작한다
2. 스택 a의 최상단에 있는 숫자(num)의 i번째 비트를 확인한다
3. 만약 (num >> i) & 1 == 0 이라면, 즉 i번째 비트가 0이라면, 이 숫자는 '0' 버킷에 속한다. pb 명령어를 실행하여 스택 b로 옮긴다
4. 만약 (num >> i) & 1 == 1 이라면, 즉 i번째 비트가 1이라면, 이 숫자는 '1' 버킷에 속한다. ra 명령어를 실행하여 스택 a의 맨 아래로 보낸다. 이는 숫자를 스택 a 안에 유지시키면서 현재 처리 대상에서 제외하는 효과를 가진다
5. N개의 모든 숫자에 대해 이 과정을 마치면, 스택 a에는 i번째 비트가 1인 숫자들만 남고, 스택 b에는 i번째 비트가 0인 숫자들만 모이게 된다
6. pa 명령어를 반복 실행하여 스택 b의 모든 숫자를 다시 스택 a로 가져온다. 이 시점에서 스택 a의 숫자들은 최하위 비트부터 i번째 비트까지 정렬된 상태가 된다

 

이 과정을 가장 낮은 비트부터 필요한 모든 비트에 대해 반복하면, 최종적으로 스택 a는 완벽하게 정렬된다[^6].

 

이 알고리즘이 작동하는 이유: 정렬의 안정성

기수 정렬이 올바르게 작동하기 위한 핵심 조건 중 하나는 안정성(stability)이다. 즉, 같은 자릿수 값을 가진 원소들의 기존 상대적 순서가 정렬 후에도 유지되어야 한다. Push_Swap 기수 정렬은 어떻게 이 안정성을 보장할까?

 

그 비밀은 ra와 pb 명령어의 선택에 있다. i번째 비트가 '1'인 숫자를 만났을 때 ra로 회전시키면, 이전 비트 패스에서 정렬되었던 '1' 그룹의 상대적 순서가 그대로 유지된다. 마찬가지로, '0'인 숫자들을 pb로 스택 b에 순서대로 쌓으면, 먼저 들어간 숫자가 b의 더 깊은 곳에 위치하게 되어 그들의 상대적 순서가 보존된다. 이들을 다시 pa로 가져올 때도 이 순서는 유지된다.

 

결론적으로, '1' 버킷에 ra를, '0' 버킷에 pb를 사용하는 것은 임의의 선택이 아니다. 이는 허용된 명령어들의 고유한 특성을 활용하여 안정 정렬을 구현하는 정교한 메커니즘이다. 이것이 바로 "무엇을 해야 하는가"를 넘어 "왜 그것이 작동하는가"에 대한 깊은 이해다.

 

디테일의 차이: 고성능 솔루션을 위한 고급 최적화

기수 정렬이라는 강력한 엔진을 갖췄다 하더라도, 프로젝트의 까다로운 벤치마크를 통과하기 위해서는 추가적인 최적화가 필수적이다. 이 섹션에서는 명령어 수를 극한까지 줄이는 핵심적인 미세 조정 기법들을 다룬다.

 

소수 예외 처리: 최적 해법 하드코딩

기수 정렬과 같은 범용 알고리즘은 숫자의 개수(N)가 매우 적을 때, 완벽하게 최적화된 하드코딩된 해법보다 비효율적일 수 있다. 따라서 작은 N에 대해서는 별도의 처리 로직을 구현하는 것이 현명하다.

 

• N=2: 정렬되어 있지 않다면 sa 한 번으로 해결된다.
• N=3: 3개의 숫자로 만들 수 있는 모든 순열(3!=6가지)은 최대 2개의 명령어로 정렬 가능하다. 각 경우에 대한 최적의 명령어를 미리 계산하여 하드코딩한다 (예: 2 1 0 -> sa, rra)[^3].
• N=4 및 N=5: 전략은 스택 a에서 1~2개의 원소를 b로 보내 3개짜리 문제로 축소시킨 후, 3개에 대한 최적 해법을 적용하고, 마지막으로 b의 원소들을 올바른 위치에 다시 병합하는 것이다. 5개 숫자 정렬의 최대 허용 명령어 수는 12개다[^8].

 

이는 재귀 알고리즘의 '기저 사례(base case)' 개념과 같다. 가장 작은 단위의 문제를 완벽하게 해결함으로써 전체 알고리즘의 성능을 향상시키는 것이다[^9].

 

회전의 미적분학: 이동 비용 최소화

이것은 어떤 알고리즘을 사용하든 보편적으로 적용 가능한 매우 중요한 최적화다. 특정 원소를 스택의 최상단으로 옮겨야 할 때, ra와 rra 중 어느 것이 더 저렴한지 반드시 계산해야 한다.

 

로직은 간단하다. 크기가 s인 스택에서 상단으로부터 i번째(0-indexed)에 위치한 원소를 옮기려 할 때:

 

• ra를 사용하는 비용은 i번의 연산이다
• rra를 사용하는 비용은 s - i번의 연산이다

 

알고리즘은 항상 이 두 값 중 최솟값을 선택해야 한다[^3]. 이 간단한 확인 로직을 프로그램 전체의 모든 회전 연산에 적용하는 것만으로도 회전 명령어의 수를 거의 절반으로 줄일 수 있으며, 고성능 솔루션을 위한 필수적인 최적화다.

 

5.3. 동기화된 움직임: rr과 rrr의 힘

가장 진보된 최적화는 한 수 앞을 내다보는 것이다. 스택 a와 b에 필요한 회전 연산을 독립적으로 계산하고 실행하는 대신, 두 스택의 움직임을 동시에 고려하여 비용을 절감할 수 있다.

 

이 기법은 주로 스택 b에서 a로 원소를 옮길 때, b의 특정 원소를 최상단으로 가져오는 비용과 그 원소를 a의 올바른 위치에 삽입하는 비용을 함께 계산하는 과정에서 빛을 발한다.

 

로직: a에 필요한 최적 회전 수를 cost_a(ra는 양수, rra는 음수), b에 필요한 회전 수를 cost_b라고 가정한다.

 

• 만약 cost_a와 cost_b가 모두 양수(둘 다 ra 계열)라면, min(cost_a, cost_b) 만큼 rr 명령어를 사용하고, 남은 회전은 단일 ra 또는 rb로 처리할 수 있다
• 만약 cost_a와 cost_b가 모두 음수(둘 다 rra 계열)라면, min(|cost_a|, |cost_b|) 만큼 rrr 명령어를 사용할 수 있다

 

이 기법은 알고리즘을 단순히 반응적인 것에서 예측적인 것으로 변모시킨다. Push_Swap이라는 제한된 환경 내에서 '병렬 처리'의 기회를 찾아내는 것으로, 최고 수준의 솔루션을 구별하는 특징이다[^5].

 

728x90

마치며

지금까지 논의된 모든 개념들을 종합하여, 프로젝트의 모든 요구사항을 충족시키는 일관되고 강력한 최종 전략을 제시한다.

 

하이브리드 알고리즘 설계도

1. 초기화: 인자를 파싱하고 유효성을 검사한다. 중복, 비정수 등의 오류를 명세에 따라 처리한다[^1].
2. 정규화: 입력된 정수들을 0부터 시작하는 순위(rank) 리스트로 변환한다 (섹션 3).
3. 분류(Triage): 전체 원소의 개수(N)를 확인한다.
   • N <= 5인 경우, 작은 숫자를 위한 특화된 하드코딩 정렬 로직을 실행한다 (섹션 5.1).
   • N > 5인 경우, 기수 정렬 구현으로 넘어간다.
4. 실행 (기수 정렬):
   • 섹션 4에서 설명한 비트 단위 기수 정렬을 구현한다.
   • 핵심적으로, 기수 정렬 루프 내에서 ra를 실행해야 할 때에도 항상 '회전의 미적분학' 로직(섹션 5.2)을 적용하여 rra가 더 저렴하지는 않은지 확인해야 한다. 이는 순수 기수 정렬 알고리즘을 Push_Swap의 제약 조건에 맞게 변형하는 중요한 과정이다.
5. 마무리: 기수 정렬이 완료되면 스택 a는 정렬된 상태가 된다. 마지막으로 가장 작은 원소(순위 0)가 스택의 맨 위에 오도록 스택 a를 한 번 더 회전시킨다. 이때도 역시 회전 비용 계산을 통해 가장 저렴한 방법(ra 또는 rra)을 선택한다[^10].

 

코드를 넘어서

Push_Swap 프로젝트는 단순한 정렬 연습 문제가 아니다. 이것은 주어진 문제의 고유한 제약 조건을 깊이 이해하고, 그 제약 조건을 역으로 활용하는 방법을 배우는 과정이다. 최고의 해결책은 일반적인 정렬 알고리즘을 C언어로 이식한 것이 아니라, Push_Swap 세계의 규칙으로부터 탄생한 맞춤형 알고리즘이다. 그리디 접근법에서 출발하여 최적화된 기수 정렬에 이르는 여정은, 개발자가 알고리즘적 성숙에 도달하는 과정을 완벽하게 보여주는 축소판과 같다.

---

참고문헌

[^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