42 Seoul - 005_push_swap

🔄 push_swap : 제약(Constraints) 속에서 최적의 경로를 탐색하다

이 과제의 핵심은 알고리즘 맛보기라는 일이었다.

이전의 과제들이 C언어의 문법, 시스템과의 소통 방식을 익히는 과정이었다면, push_swap은 완전히 새로운 차원의 질문을 던진다: “엄격한 제약 조건 하에서, 어떻게 ‘최적(Optimal)’의 해를 찾아낼 것인가?”

이 과제는 단순히 주어진 숫자를 정렬하는 문제가 아니다. 두 개의 스택이라는 제한된 공간과 11개의 명령어(외부에 노출 될 수 있는 명령 갯수)라는 한정된 도구만을 사용하여, 가장 효율적인 데이터의 ‘이동 경로’를 설계해야 하는 복잡한 최적화 문제(Optimization Problem)이다.

Minitalk가 원시적인 신호 위에 통신 프로토콜을 쌓아 올리는 경험이었다면, push_swap은 혼돈(Unordered state) 속에서 질서(Sorted state)로 나아가는 가장 우아한 알고리즘적 여정을 찾아내는 과정이였다.

이는 정해진 답을 구현하는 것을 넘어, 문제의 본질을 꿰뚫고 자신만의 해결 전략, 즉 휴리스틱(Heuristic)을 창조하고 증명해야 하는, 진정한 의미의 문제 해결 능력에 대한 시험대였다.

🎲 문제 공간의 정의: 두 개의 스택과 11개의 연산자

push_swap의 세계는 다음의 공리(Axioms) 위에 세워져 있다.

1. 두 개의 스택 (a, b): 모든 연산의 주체이자 대상이 되는 유일한 데이터 구조. 이는 임의 접근(Random Access)이 불가능하고 오직 LIFO(Last-In, First-Out) 접근만 허용되는 근본적인 제약을 의미한다.
2. 11개의 연산자 (sa, pb, ra, rra 등): 스택의 상태를 변경할 수 있는 유일한 합법적인 행위. 각 연산자는 ‘1’이라는 비용(cost)을 가지며, 과제의 목표는 이 비용의 총합을 최소화하는 것이다.

이러한 제약은 퀵 정렬이나 병합 정렬과 같은 고전적인 효율적 정렬 알고리즘의 사용을 원천적으로 차단한다. 따라서 우리는 이 문제 공간의 특성에 맞는 새로운 전략을 수립해야만 했다.

💡 핵심 전략: LIS (최장 증가 부분 수열)를 이용한 문제 재정의

제일 처음 이 문제를 받았을 때, 머리가 하얗게 변하는 것을 느꼈다. 내가 할 일이 뭔지를 알겠고 구현은 했지만, 각 행동을 어떻게 알고리즘으로 엮어야 하지?

지금은 그래도 AI 로 접근은 되는 것이었지만, 핵심적인 연산자를 구현한걸 어떻게 엮어야 알고리즘의 방식을 적용을 해서 최적화 시키지? 이 문제는 계속 머리를 쥐어 뜯게 만들고, 뭘 얼마나 해야할 지에 대한 망설임을 만들었던 기억이 난다.

그렇게 어느정도 알고리즘에 대해 이해가 쌓이기 시작하고, 손을 델 수 있게 된 것은 “어떻게 움직임의 수를 최소화할 것인가?”라는 질문에 문제 자체를 재정의하는 것을 하면서 부터 조금씩 가능해지기 시작했다.

“모든 원소를 정렬하려 하지 말고, 이미 정렬된 것에 가까운 원소들은 그대로 둔 채, 흐름을 방해하는 최소한의 원소들만 옮기면 어떨까?”

이 접근법을 처음 알게 되고, 기존의 방법에서 해메던 도중이었고, 그 결과 나는 유레카를 불렀다. 이 방법이라면 뭔가 구현이 가능할 것으로 보이고, 내 이해도를 높이면서 최적화를 이룰 수 있을 것 같다는 감각적인 확신. 이러한 확신을 구현한 것이 바로 LIS (Longest Increasing Subsequence) 알고리즘, 한국어 명 최장증가수열 알고리즘이었다.

1. 기준점 설정 (LIS 탐색): 먼저 스택 a에 존재하는 숫자들 중에서 LIS, 최장 증가 수열을 찾는다. LIS에 속한 원소들은 최종적으로 정렬된 상태에서도 그 상대적 순서를 유지할 가능성이 높은 ‘앵커(Anchor)’ 그룹이다. 이들은 우리가 최소한으로 움직여야 할 대상, 즉 보존해야 할 가치가 가장 큰 원소들의 묶음이었다.
2. 문제의 분리: LIS 탐색 후, 문제는 두 가지 하위 문제로 분리된다.
   • LIS에 속하지 않는 원소들을 스택 b로 가장 효율적으로 이동시키는 문제.
   • 스택 b의 원소들을 다시 스택 a의 올바른 위치로 최소 비용으로 삽입하는 문제.

이처럼 LIS를 기준으로 문제를 재정의함으로써, ‘N개의 원소를 정렬하는 문제’는 ‘N-K개의 원소(K는 LIS의 길이)를 가장 효율적으로 이동시키는 문제’로 단순화된다. 이는 복잡한 문제에 직면했을 때, 불변의 기준을 찾아내고 이를 중심으로 문제를 분해하는 강력한 문제 해결 전략이며, 무엇보다 직관적이라는 장점은 기존의 만들어둔 기능들을 활용한 구현에서 아주 효과적이었다.

💃 탐욕 알고리즘(Greedy Algorithm)의 적용: 최적 삽입 경로 탐색

이렇게 LIS 그룹을 발견하고 나면, 이를 제외한 모든 원소가 스택 b로 옮겨진 후, 마지막 단계는 스택 b의 원소들을 다시 a로 돌려보내는 것이다.

이 과정은 매 순간 ‘지역적으로 최적인(Locally Optimal)’ 선택을 반복하는 탐욕 알고리즘의 아이디어를 기반으로 동작한다. 이때 핵심은 단순히 각각 스택으로 옮기는 방법도 있지만, 동시에 양쪽을 같이 움직이거나, 적절하게 오히려 거꾸로 순서를 정리하는 도구들을 얼마나 각 스텍에서 공통적으로 묶어서 동시에 실행하나에 달려 있었다.

• 비용 함수 정의: 스택 b의 특정 원소를 스택 a의 올바른 위치에 삽입하기 위해 필요한 ra, rra, rb, rrb 연산의 총 횟수를 ‘비용’으로 정의한다.
• 최적해 탐색: 스택 b의 모든 원소에 대해 이 비용을 계산하고, 그중 가장 비용이 낮은, 즉 가장 적은 연산으로 제자리를 찾아갈 수 있는 원소를 이번 턴에 이동시킬 대상으로 선택한다.
• 최적화: 만약 a와 b 스택이 같은 방향으로 회전해야 한다면(ra와 rb), 이를 rr이라는 단일 연산으로 통합하여 비용을 절감하는 최적화를 적용한다. 이와 반대의 경우엔 rrr을 사용한다.

이 과정을 스택 b가 빌 때까지 반복함으로써, 전체 이동 비용을 최소화하는 경로에 근사할 수 있다.

✨ 성찰 및 배운 점

이 과제는 체감상 printf 보다도 어렵고, 어쩌면 42서울 과정 중에서 상당히 길게 걸린, push_swap은 논리적 사고와 전략적 설계, 수학적 감각 등의 능력을 요구하는 과제였다. 나같은 문과생들에게는 정말 지옥과도 같았던 시간이라고(….), 그리고 동시에 그렇기에 진짜 수학을 왜 그리 열심히 배우는 지를 알 수 있었다.

그럼에도 이 과제를 마무리 함으로써

• 알고리즘적 사고로의 전환: ‘어떻게 구현할까’를 넘어 ‘어떤 전략이 가장 효율적일까’를 고민하게 만들었다. 이는 단순히 코드를 짜는 행위에서 문제를 분석하고 해결책을 설계하는 단계로의 성장을 의미했고, 특히나 왜 그렇게 ‘알고리즘’이라는 키워드에 개발자들이 강조하고, 이를 통해 얼마나 작업의 차이가 크게 나는지를 직접 눈으로 볼 수 있던 경험이라고 생각한다.
• 휴리스틱의 가치: 수학적으로 완벽한 최적해를 찾는 것은 매우 어렵거나(NP-hard) 비효율적일 수 있다. LIS라는 강력한 휴리스틱을 통해 ‘충분히 좋은(good enough)’ 해를 효율적으로 찾아내는 과정은, 현실 세계의 복잡한 문제를 해결하는 실용적인 접근법을 가르쳐주었다.
• 연산의 비용에 대한 감각: 모든 명령어에 ‘비용’이라는 개념이 존재함을 인지하게 되었다. 이는 “작동하는 코드”와 “효율적인 코드”의 차이를 명확히 구분하게 만들었으며, 성능 최적화에 대한 마인드셋을 심어주었다.

push_swap은 스택이라는 단순한 자료구조 위에서 펼쳐지는 한 편의 논리적인 왈츠였다. 이 프로젝트를 통해 나는 비로소 주어진 문제의 제약 조건을 이해하고, 그 안에서 최적의 해결책을 설계하는 ‘알고리즘 설계자’로서의 첫걸음을 뗄 수 있었다.