[42] push_swap 최적화

stack

push_swap에서는 stack $a$와 stack $b$, 2개의 stack을 사용한다.

여기서는 stack $a$와 stack $b$를 합친 자료구조를 stacks이라고 표현할 것이다.

또한 $a$에 1, 2, 3, 4, 5가 들어있고 $b$에 6, 7, 8가 들어있는 stacks $T$를 아래와 같이 표현할 것이다.

$T= \begin{bmatrix} \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \\ 5 \end{bmatrix} \begin{bmatrix} 6 \\ 7 \\ 8 \end{bmatrix} \end{bmatrix}$

정렬된 stacks

어떤 stacks $T$이 정렬되어있다는 것은 $T$의 모든 요소(숫자)가 stack $a$에 오름차순으로 정렬되어있다는 것을 뜻한다.

동작(operation)

push_swap에서는 stacks의 요소(숫자)들의 위치 바꾸는 것을 '동작(operation)'이라고 한다.

push_swap에는 다음과 같은 11개의 동작(operation)들이 주어진다.

$sa\quad sb\quad ss\quad pa\quad pb\quad ra\quad rb\quad rr\quad rra\quad rrb\quad rrr$

ex) $sa( \begin{bmatrix} \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \\ 5 \end{bmatrix} \begin{bmatrix} \end{bmatrix} \end{bmatrix} ) = \begin{bmatrix} \begin{bmatrix} 2 \\ 1 \\ 3 \\ 4 \\ 5 \end{bmatrix} \begin{bmatrix} \end{bmatrix} \end{bmatrix}$

뿐만 아니라$\begin{bmatrix} \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \\ 5 \end{bmatrix} \begin{bmatrix} \end{bmatrix} \end{bmatrix}$를 $\begin{bmatrix} \begin{bmatrix} 2 \\ 5 \\ 1 \end{bmatrix} \begin{bmatrix} 4 \\ 3 \end{bmatrix} \end{bmatrix}$로 바꾸는 동작도 있을 수 있다.

이제 동작의 특성을 설명한 건데, 동작의 특성은 함수의 특성과 유사하므로, 간략하게만 설명한다.

역동작(Inverse operation)

$A(T) = U$일 때 $A$의 역동작은 $A^{-1}$로 표기하고 $A^{-1}(U) = T$인 동작이다.

ex) $rb^{-1}=rrb$, $sa^{-1}=sa$, $pa^{-1}=pb$

$pa$, $pb$의 역동작이 존재하기 위해서는, 정의역과 공역을 줄여야 한다.

동작의 합성

$A$와 $B$를 합성한 동작 $C$는 $A$와 $B$의 합성 동작이라고 한다.

여기서는 편의를 위해 동작의 합성을 함수와 같이 $A\,∘\,B$같이 표현하는 것보다는
$A×B$ 혹은 $A\,B$와 같이 나열하는 것으로 표현할 것이다.

모든 동작은 항상 주어진 11개의 동작($sa\; sb\; ...\; rrr$) 중 하나이거나 주어진 동작들의 합성 동작이다.
(경우에 의한 증명과 수학적 귀납법으로 증명 가능하지만 생략한다.)

또한 어떤 동작 $A$가 되는 주어진 동작의 경우는 유일하지 않을 수 있고, 주어진 동작들을 합성하는 경우는 무수히 많다.

ex) $T= \begin{bmatrix} \begin{bmatrix} 1 \\ 2 \end{bmatrix} \begin{bmatrix} \end{bmatrix} \end{bmatrix}$일 때, $(rra)(T) = (ra)(T) = (sa)(T) = \begin{bmatrix} \begin{bmatrix} 2 \\ 1 \end{bmatrix} \begin{bmatrix} \end{bmatrix} \end{bmatrix}$

ex) $T= \begin{bmatrix} \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \\ 5 \end{bmatrix} \begin{bmatrix} 6 \\ 7 \\ 8 \end{bmatrix} \end{bmatrix}$일 때, $(rb×pb×rrb)(T) = (pb×sb)(T) = \begin{bmatrix} \begin{bmatrix} 2 \\ 3 \\ 4 \\ 5 \end{bmatrix} \begin{bmatrix} 6 \\ 1 \\ 7 \\ 8 \end{bmatrix} \end{bmatrix}$

합성 동작의 역동작

$(A×B)^{-1}=B^{-1}×A^{-1}$ (합성 함수의 역함수를 생각해보자.)

교환 법칙

모든 동작 $A$와 $B$에 관해 $A × B \not= B × A$가 항상 성립하지는 않는다.

ex) $T= \begin{bmatrix} \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \\ 5 \end{bmatrix} \begin{bmatrix} 6 \\ 7 \\ 8 \end{bmatrix} \end{bmatrix}$일 때, $(pb×sa)(T) = \begin{bmatrix} \begin{bmatrix} 3 \\ 2 \\ 4 \\ 5 \end{bmatrix} \begin{bmatrix} 1 \\ 6 \\ 7 \\ 8 \end{bmatrix} \end{bmatrix} \not= (sa×pb)(T) = \begin{bmatrix} \begin{bmatrix} 1 \\ 3 \\ 4 \\ 5 \end{bmatrix} \begin{bmatrix} 2 \\ 6 \\ 7 \\ 8 \end{bmatrix} \end{bmatrix}$

물론 성립할 때도 있다.

ex) $T= \begin{bmatrix} \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \\ 5 \end{bmatrix} \begin{bmatrix} 6 \\ 7 \\ 8 \end{bmatrix} \end{bmatrix}$일 때, $(ra×rb)(T) = (rb×ra)(T) = \begin{bmatrix} \begin{bmatrix} 2 \\ 3 \\ 4 \\ 5 \\ 1 \end{bmatrix} \begin{bmatrix} 7 \\ 8 \\ 6 \end{bmatrix} \end{bmatrix}$

항등 동작 $I$

어떤 동작 $A$과 모든 stacks $T$에 관해, $A(T) = T$가 성립할 때,

라고 하고 $I$는 항등 동작이라고 한다.

역동작을 사용해 경우의 수를 늘려보자.

역동작을 사용해 어떤 알고리즘을 쓰든 경우의 수를 2배로 늘릴 수 있는 방법이다.

$S$를 정렬된 stacks $\begin{bmatrix} \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \\ 5 \end{bmatrix} \begin{bmatrix} \end{bmatrix} \end{bmatrix}$를 $\begin{bmatrix} \begin{bmatrix} 1 \\ 5 \\ 2 \\ 3 \\ 4 \end{bmatrix} \begin{bmatrix} \end{bmatrix} \end{bmatrix}$로 만드는 동작이라고 하자.

그렇다면 동작 $S$의 역동작은 항상 존재하고,
$S$의 역동작 $S^{-1}$는 $\begin{bmatrix} \begin{bmatrix} 1 \\ 5 \\ 2 \\ 3 \\ 4 \end{bmatrix} \begin{bmatrix} \end{bmatrix} \end{bmatrix}$를 정렬된 stacks $\begin{bmatrix} \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \\ 5 \end{bmatrix} \begin{bmatrix} \end{bmatrix} \end{bmatrix}$로 만드는 동작이고

정렬된 stacks $\begin{bmatrix} \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \\ 5 \end{bmatrix} \begin{bmatrix} \end{bmatrix} \end{bmatrix}$를 $\begin{bmatrix} \begin{bmatrix} 1 \\ 3 \\ 4 \\ 5 \\ 2 \end{bmatrix} \begin{bmatrix} \end{bmatrix} \end{bmatrix}$로 만드는 동작으로도 볼 수 있다.

더 풀어서 설명하자면 $a$만 봤을 때

n	1	2	3	4	5
m	1	5	2	3	4

$S$는 표에서 n 자리에 m이 오게 하는 동작이고, $S^{-1}$는 m자리에 n이 오게 하는 동작이다.
n과 m의 관계를 해치지 않고, m을 오름차순으로 정렬하면 이런 표가 나온다.

n	1	3	4	5	2
m	1	2	3	4	5

따라서 $S^{-1}$는 $\begin{bmatrix} \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \\ 5 \end{bmatrix} \begin{bmatrix} \end{bmatrix} \end{bmatrix}$를 $\begin{bmatrix} \begin{bmatrix} 2 \\ 5 \\ 4 \\ 3 \\ 1 \end{bmatrix} \begin{bmatrix} \end{bmatrix} \end{bmatrix}$로 만드는 동작인 것이다.

우리는 알고리즘을 통해 $S×P1×P2×...×Pn=I$를 만족하는 $P1,P2,...,Pn$를 찾을 수 있다.

또한 $S^{-1}×Q1×Q2×...×Qm=I$를 만족하는 $Q1,Q2,...,Qm$도 찾을 수 있다.
($Pk(0<k≤n)$와 $Qk(0<k≤m)$는 주어진 동작 중 하나이다.)

$P1×P2×...×Pn=S^{-1}$, $Q1×Q2×...×Qm=S$가 만족하므로 $P1×P2×...×Pn=(Q1×Q2×...×Qm)^{-1}=Qm^{-1}×Qm-1^{-1}×...×Q1^{-1}$이다.

따라서 $P1,P2,...,Pn$과 $Q1,Q2,...,Qm$를 구하고 $m<n$이라면 $Qm^{-1}$, $Qm-1^{-1}$, $...$, $Q1^{-1}$을 출력하면 될 것이다.

예를 들어, 정렬된 stacks에 동작 $S$를 적용한 $\begin{bmatrix} \begin{bmatrix} 1 \\ 5 \\ 2 \\ 3 \\ 4 \end{bmatrix} \begin{bmatrix} \end{bmatrix} \end{bmatrix}$를 삽입 정렬로 정렬해보자.
$\begin{bmatrix} \begin{bmatrix} 1 \\ 5 \\ 2 \\ 3 \\ 4 \end{bmatrix} \begin{bmatrix} \end{bmatrix} \end{bmatrix}→ra×ra×pb×rra×pa×rra=\begin{bmatrix} \begin{bmatrix} 1 \\ 2 \\ 5 \\ 3 \\ 4 \end{bmatrix} \begin{bmatrix} \end{bmatrix} \end{bmatrix}→rra×rra×pb×rra×pa×rra×rra=\begin{bmatrix} \begin{bmatrix} 1 \\ 2 \\ 3 \\ 5 \\ 4 \end{bmatrix} \begin{bmatrix} \end{bmatrix} \end{bmatrix}→rra×pb×rra×pa×ra×ra=\begin{bmatrix} \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \\ 5 \end{bmatrix} \begin{bmatrix} \end{bmatrix} \end{bmatrix}$
총 20번으로 정렬되었다. 최적화를 잘 하면 $ra×sa×ra×sa×ra×sa×ra×ra$ 8번으로 정렬 가능하다.

이번엔 정렬된 stacks에 동작 $S^{-1}$를 적용한 $\begin{bmatrix} \begin{bmatrix} 1 \\ 3 \\ 4 \\ 5 \\ 2 \end{bmatrix} \begin{bmatrix} \end{bmatrix} \end{bmatrix}$를 삽입 정렬로 정렬해보자.
$\begin{bmatrix} \begin{bmatrix} 1 \\ 3 \\ 4 \\ 5 \\ 2 \end{bmatrix} \begin{bmatrix} \end{bmatrix} \end{bmatrix}→rra×pb×ra×pa×rra=\begin{bmatrix} \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \\ 5 \end{bmatrix} \begin{bmatrix} \end{bmatrix} \end{bmatrix}$
총 5번으로 정렬되었다. 최적화를 잘 하면 $rra×sa$ 단 2번으로 정렬 가능하다.

이것은 $P1 = ra$, $P2 = sa$, ..., $P8 = ra$이고 $Q1 = rra$, $Q2 = sa$인 상황이다.
아까 $Q2^{-1}×Q1^{-1}=S^{-1}$이라고 했으니, $S×Q2^{-1}×Q1^{-1}=I$인지 살펴보자.
$Q2^{-1}=sa^{-1}=sa$
$Q1^{-1}=rra^{-1}=ra$이므로
$\begin{bmatrix} \begin{bmatrix} 1 \\ 5 \\ 2 \\ 3 \\ 4 \end{bmatrix} \begin{bmatrix} \end{bmatrix} \end{bmatrix}→sa= \begin{bmatrix} \begin{bmatrix} 5 \\ 1 \\ 2 \\ 3 \\ 4 \end{bmatrix} \begin{bmatrix} \end{bmatrix} \end{bmatrix}→ra= \begin{bmatrix} \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \\ 5 \end{bmatrix} \begin{bmatrix} \end{bmatrix} \end{bmatrix}$

당연하게도 놀랍게도 정렬되는 것을 볼 수 있다.
$ra×sa×ra×sa×ra×sa×ra×ra$이 아닌 $sa×ra$를 출력해도 된다는 것이다.

$ra×sa×ra×sa×ra×sa×ra×ra$을 최적화해서 $sa×ra$가 될 수도 있기는 하지만, 주어진 동작을 많이 합성하는 경우에는 그럴 가능성이 매우 적다. 위에서 말했듯 어떤 동작 $A$가 되는 주어진 동작들을 합성하는 경우는 무수히 많기 때문이다.
편차가 적은 알고리즘일수록 효과가 적다. (알고리즘의 시간 복잡도를 big-Theta로 나타낼 수 있을 때) ex) merge sort, qucik sort

만약 정렬하는 $n$단계의 각 동작들이 역동작이 존재한다면 경우의 수를 최대 $2^{n}$배로 늘릴 수 있다.
혹은 각 단계에서 더 적은 동작을 선택한다고 해보자.
$S×A$ 혹은 $S^{-1}×B$로 1단계를 완성한다.
$B$보다 $A$가 동작이 더 적다면, $A$를 선택하고,
$S×A×C$ 혹은 $A^{-1}×S^{-1}×D$로 2단계를 완성한다.
$C$보다 $D$가 동작이 더 적다면, $D$를 선택하고,
$A^{-1}×S^{-1}×D×E$ 혹은 $D^{-1}×S×A×F$로 3단계를 완성한다.
$F$보다 $E$가 동작이 더 적다면, $E$를 선택하고, 정렬이 끝났다고 해보자.
그렇다면 $A^{-1}×S^{-1}×D×E=I$이다.
양변에 역을 취하면
$(A^{-1}×S^{-1}×D×E)^{-1}=I^{-1}$
합성 동작의 역동작의 성질로
$E^{-1}×D^{-1}×S×A=I$
양변에 동작을 합성
$D×E×(E^{-1}×D^{-1}×S×A)×E^{-1}×D^{-1}=D×E×I×E^{-1}×D^{-1}$
역함수의 정의에 의해
$S×A×E^{-1}×D^{-1}=I$
정렬된 stacks에 $S$가 적용된 상태에서, $A×E^{-1}×D^{-1}$을 적용하면 정렬이 된다는 뜻이다.

다른 최적화 기법들은 다음 시간에 ^^...