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=⎣⎢⎢⎢⎢⎢⎡⎣⎢⎢⎢⎢⎢⎡12345⎦⎥⎥⎥⎥⎥⎤⎣⎢⎡678⎦⎥⎤⎦⎥⎥⎥⎥⎥⎤
정렬된 stacks
어떤 stacks T이 정렬되어있다는 것은 T의 모든 요소(숫자)가 stack a에 오름차순으로 정렬되어있다는 것을 뜻한다.
동작(operation)
push_swap에서는 stacks의 요소(숫자)들의 위치 바꾸는 것을 '동작(operation)'이라고 한다.
push_swap에는 다음과 같은 11개의 동작(operation)들이 주어진다.
sasbsspapbrarbrrrrarrbrrr
ex) sa(⎣⎢⎢⎢⎢⎢⎡⎣⎢⎢⎢⎢⎢⎡12345⎦⎥⎥⎥⎥⎥⎤[]⎦⎥⎥⎥⎥⎥⎤)=⎣⎢⎢⎢⎢⎢⎡⎣⎢⎢⎢⎢⎢⎡21345⎦⎥⎥⎥⎥⎥⎤[]⎦⎥⎥⎥⎥⎥⎤
뿐만 아니라⎣⎢⎢⎢⎢⎢⎡⎣⎢⎢⎢⎢⎢⎡12345⎦⎥⎥⎥⎥⎥⎤[]⎦⎥⎥⎥⎥⎥⎤를 ⎣⎢⎡⎣⎢⎡251⎦⎥⎤[43]⎦⎥⎤로 바꾸는 동작도 있을 수 있다.
이제 동작의 특성을 설명한 건데, 동작의 특성은 함수의 특성과 유사하므로, 간략하게만 설명한다.
역동작(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 혹은 AB와 같이 나열하는 것으로 표현할 것이다.
모든 동작은 항상 주어진 11개의 동작(sasb...rrr) 중 하나이거나 주어진 동작들의 합성 동작이다.
(경우에 의한 증명과 수학적 귀납법으로 증명 가능하지만 생략한다.)
또한 어떤 동작 A가 되는 주어진 동작의 경우는 유일하지 않을 수 있고, 주어진 동작들을 합성하는 경우는 무수히 많다.
ex) T=[[12][]]일 때, (rra)(T)=(ra)(T)=(sa)(T)=[[21][]]
ex) T=⎣⎢⎢⎢⎢⎢⎡⎣⎢⎢⎢⎢⎢⎡12345⎦⎥⎥⎥⎥⎥⎤⎣⎢⎡678⎦⎥⎤⎦⎥⎥⎥⎥⎥⎤일 때, (rb×pb×rrb)(T)=(pb×sb)(T)=⎣⎢⎢⎢⎡⎣⎢⎢⎢⎡2345⎦⎥⎥⎥⎤⎣⎢⎢⎢⎡6178⎦⎥⎥⎥⎤⎦⎥⎥⎥⎤
합성 동작의 역동작
(A×B)−1=B−1×A−1 (합성 함수의 역함수를 생각해보자.)
교환 법칙
모든 동작 A와 B에 관해 A×B=B×A가 항상 성립하지는 않는다.
ex) T=⎣⎢⎢⎢⎢⎢⎡⎣⎢⎢⎢⎢⎢⎡12345⎦⎥⎥⎥⎥⎥⎤⎣⎢⎡678⎦⎥⎤⎦⎥⎥⎥⎥⎥⎤일 때, (pb×sa)(T)=⎣⎢⎢⎢⎡⎣⎢⎢⎢⎡3245⎦⎥⎥⎥⎤⎣⎢⎢⎢⎡1678⎦⎥⎥⎥⎤⎦⎥⎥⎥⎤=(sa×pb)(T)=⎣⎢⎢⎢⎡⎣⎢⎢⎢⎡1345⎦⎥⎥⎥⎤⎣⎢⎢⎢⎡2678⎦⎥⎥⎥⎤⎦⎥⎥⎥⎤
물론 성립할 때도 있다.
ex) T=⎣⎢⎢⎢⎢⎢⎡⎣⎢⎢⎢⎢⎢⎡12345⎦⎥⎥⎥⎥⎥⎤⎣⎢⎡678⎦⎥⎤⎦⎥⎥⎥⎥⎥⎤일 때, (ra×rb)(T)=(rb×ra)(T)=⎣⎢⎢⎢⎢⎢⎡⎣⎢⎢⎢⎢⎢⎡23451⎦⎥⎥⎥⎥⎥⎤⎣⎢⎡786⎦⎥⎤⎦⎥⎥⎥⎥⎥⎤
항등 동작 I
어떤 동작 A과 모든 stacks T에 관해, A(T)=T가 성립할 때,
라고 하고 I는 항등 동작이라고 한다.
역동작을 사용해 경우의 수를 늘려보자.
역동작을 사용해 어떤 알고리즘을 쓰든 경우의 수를 2배로 늘릴 수 있는 방법이다.
S를 정렬된 stacks ⎣⎢⎢⎢⎢⎢⎡⎣⎢⎢⎢⎢⎢⎡12345⎦⎥⎥⎥⎥⎥⎤[]⎦⎥⎥⎥⎥⎥⎤를 ⎣⎢⎢⎢⎢⎢⎡⎣⎢⎢⎢⎢⎢⎡15234⎦⎥⎥⎥⎥⎥⎤[]⎦⎥⎥⎥⎥⎥⎤로 만드는 동작이라고 하자.
그렇다면 동작 S의 역동작은 항상 존재하고,
S의 역동작 S−1는 ⎣⎢⎢⎢⎢⎢⎡⎣⎢⎢⎢⎢⎢⎡15234⎦⎥⎥⎥⎥⎥⎤[]⎦⎥⎥⎥⎥⎥⎤를 정렬된 stacks ⎣⎢⎢⎢⎢⎢⎡⎣⎢⎢⎢⎢⎢⎡12345⎦⎥⎥⎥⎥⎥⎤[]⎦⎥⎥⎥⎥⎥⎤로 만드는 동작이고
정렬된 stacks ⎣⎢⎢⎢⎢⎢⎡⎣⎢⎢⎢⎢⎢⎡12345⎦⎥⎥⎥⎥⎥⎤[]⎦⎥⎥⎥⎥⎥⎤를 ⎣⎢⎢⎢⎢⎢⎡⎣⎢⎢⎢⎢⎢⎡13452⎦⎥⎥⎥⎥⎥⎤[]⎦⎥⎥⎥⎥⎥⎤로 만드는 동작으로도 볼 수 있다.
더 풀어서 설명하자면 a만 봤을 때
S는 표에서 n 자리에 m이 오게 하는 동작이고, S−1는 m자리에 n이 오게 하는 동작이다.
n과 m의 관계를 해치지 않고, m을 오름차순으로 정렬하면 이런 표가 나온다.
따라서 S−1는 ⎣⎢⎢⎢⎢⎢⎡⎣⎢⎢⎢⎢⎢⎡12345⎦⎥⎥⎥⎥⎥⎤[]⎦⎥⎥⎥⎥⎥⎤를 ⎣⎢⎢⎢⎢⎢⎡⎣⎢⎢⎢⎢⎢⎡25431⎦⎥⎥⎥⎥⎥⎤[]⎦⎥⎥⎥⎥⎥⎤로 만드는 동작인 것이다.
우리는 알고리즘을 통해 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를 적용한 ⎣⎢⎢⎢⎢⎢⎡⎣⎢⎢⎢⎢⎢⎡15234⎦⎥⎥⎥⎥⎥⎤[]⎦⎥⎥⎥⎥⎥⎤를 삽입 정렬로 정렬해보자.
⎣⎢⎢⎢⎢⎢⎡⎣⎢⎢⎢⎢⎢⎡15234⎦⎥⎥⎥⎥⎥⎤[]⎦⎥⎥⎥⎥⎥⎤→ra×ra×pb×rra×pa×rra=⎣⎢⎢⎢⎢⎢⎡⎣⎢⎢⎢⎢⎢⎡12534⎦⎥⎥⎥⎥⎥⎤[]⎦⎥⎥⎥⎥⎥⎤→rra×rra×pb×rra×pa×rra×rra=⎣⎢⎢⎢⎢⎢⎡⎣⎢⎢⎢⎢⎢⎡12354⎦⎥⎥⎥⎥⎥⎤[]⎦⎥⎥⎥⎥⎥⎤→rra×pb×rra×pa×ra×ra=⎣⎢⎢⎢⎢⎢⎡⎣⎢⎢⎢⎢⎢⎡12345⎦⎥⎥⎥⎥⎥⎤[]⎦⎥⎥⎥⎥⎥⎤
총 20번으로 정렬되었다. 최적화를 잘 하면 ra×sa×ra×sa×ra×sa×ra×ra 8번으로 정렬 가능하다.
이번엔 정렬된 stacks에 동작 S−1를 적용한 ⎣⎢⎢⎢⎢⎢⎡⎣⎢⎢⎢⎢⎢⎡13452⎦⎥⎥⎥⎥⎥⎤[]⎦⎥⎥⎥⎥⎥⎤를 삽입 정렬로 정렬해보자.
⎣⎢⎢⎢⎢⎢⎡⎣⎢⎢⎢⎢⎢⎡13452⎦⎥⎥⎥⎥⎥⎤[]⎦⎥⎥⎥⎥⎥⎤→rra×pb×ra×pa×rra=⎣⎢⎢⎢⎢⎢⎡⎣⎢⎢⎢⎢⎢⎡12345⎦⎥⎥⎥⎥⎥⎤[]⎦⎥⎥⎥⎥⎥⎤
총 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이므로
⎣⎢⎢⎢⎢⎢⎡⎣⎢⎢⎢⎢⎢⎡15234⎦⎥⎥⎥⎥⎥⎤[]⎦⎥⎥⎥⎥⎥⎤→sa=⎣⎢⎢⎢⎢⎢⎡⎣⎢⎢⎢⎢⎢⎡51234⎦⎥⎥⎥⎥⎥⎤[]⎦⎥⎥⎥⎥⎥⎤→ra=⎣⎢⎢⎢⎢⎢⎡⎣⎢⎢⎢⎢⎢⎡12345⎦⎥⎥⎥⎥⎥⎤[]⎦⎥⎥⎥⎥⎥⎤
당연하게도 놀랍게도 정렬되는 것을 볼 수 있다.
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단계의 각 동작들이 역동작이 존재한다면 경우의 수를 최대 2n배로 늘릴 수 있다.
혹은 각 단계에서 더 적은 동작을 선택한다고 해보자.
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을 적용하면 정렬이 된다는 뜻이다.
다른 최적화 기법들은 다음 시간에 ^^...