Subject

• 1. 문제 해석
• 2. 새로운 접근 - 선형 메모리
• 3. 결론 - locality

1. 문제 해석

1 - 1) push swap이란?

0을 포함한 양의 정수를 원소로 하는 두 스택 a, b에 대하여, 주어진 조작 방식 만을 활용하여 a의 원소를 모두 오름차순으로 정렬하는 문제이다. 이 때 최대한 적은 회수로 스택을 조작하여 정렬하는 것을 목표로 한다.

문제에서는 스택(stack)이라 칭하지만, 이후 소개할 내용에서 보면 스택의 top 뿐만 아니라 bottom에도 접근이 가능하므로, 사실상의 덱(deque)라 보아야 할 것이다.

1 - 2) command

문제에서는 제한된 방식으로만 스택을 조작할 수 있게 하는데, 이를 커맨드라 한다. 커맨드는 push(a, b), swap(a, b, all), rotate(a, b, all), reverse rotate(a, b, all)의 4부류, 총 11종이 존재한다. 이는 다음과 같다.

• push

• swap

  

• rotate

  

• reverse rotate

  

2. 새로운 접근 - 선형 메모리

2 - 1) 두 스택을 하나로

해당 문제의 어려움 중 하나는 비 직관성이다. 일반적인 환경에서의 정렬은 모두 선형, random access가능한 메모리를 대상으로 수행한다. 문제에서 요구하는 상황인 둘로 분절된, 심지어 특정 위치에만 접근 가능한 상황은 대단히 당황스럽다. 따라서 문제의 상황을 보다 이해하기 쉬운, 연속된 하나의 선형 메모리로 만들어보자.

두 스택 a, b에 대하여 서로의 top을 이어붙여서 하나의 메모리 덩어리로 만든다. 그 결과는 다음과 같다.