<aside> ⚠️ 5달을 깎은 끝에 얻은 결론이지만, 과정을 설명하기에는 너무 길어 결과만 남겼습니다.

</aside>

가능한가?

결론부터 말하자면, 이 방법으로 519개까지는 무조건 4000번 미만으로 정렬할 수 있습니다.

아이디어

이는 몇 가지 간단한 아이디어에서 시작합니다.

각 스택의 끝에서 끝으로 자유롭게 이동할 수 있다

스택 A의 top, 스택 A의 bottom, 스택 B의 top, 스택 B의 bottom, 이렇게 총 4가지 위치에서는 서로 다른 곳으로 이동할 수 있습니다.

시작 위치, 끝 위치 A top A bottom B top B bottom
A top - ra pb pb + rb
A bottom rra - rra + pb rra + pb + rb
B top pa pa + ra - rb
B bottom rrb + pa rrb + pa + ra rrb -

그러므로 3분할 병합정렬, 퀵정렬이 가능합니다.

병합정렬, 퀵정렬, 18가지 방향, 다양한 방법

a + b + c = N개를 정렬하면서 이동하는 방법을 크게 병합정렬과 퀵정렬로 나눌 수 있습니다.

각 위치는 스택 A, B의 top, bottom일 수도 있고 top이면서 bottom일 수도 있습니다.

방향이 같아도 여러가지 방법이 있지만, 어떤 방법이 가장 효율적일지는 미리 알 수 없습니다.

개수와 방향에 따라 효율적인 정렬 방법/개수가 다르다

예를 들어 스택 A의 top에서 스택 A의 top으로 정렬하면서 이동하는 경우 아래 두 가지 방법이 있을 수 있습니다.

두번째 방법(#2)은 rr을 활용했습니다.

Untitled

Untitled

제가 찾은 방법은 6가지인데, 실제로 같은 방향이라도 개수에 따라 효율적인 방법이 달랐습니다.

방법