배열로 push_swap 해보자! (1)
“push_swap에 대하여”
글을 쓰기 전에 먼저 내 친구 현석이에게 감사를 표한다. 그가 없었다면 이 글이 세상에 존재할 일은 없었을 것이다. 이 글에서 보여주는 것들은 모두 현석이가 나에게 알려준 것들인데, 나만 알고 있기에는 아쉽다고 생각해 글로 남기게 되었다. 이 push_swap 글 시리즈는 과제를 해결하기 위한 알고리즘 자체에 대해서는 다루지 않는다는 사실을 미리 밝힌다.
알고리즘은 이미 좋은 글들이å많다…
개요
1. subject
- 본격적인 이야기를 시작하기 전에 과제에 대해 간략히 짚고 넘어가보자면,
* a와 b라는 스택이 있다.
* 시작할 때
- a는 중복되지 않는 임의의 수의 음수 혹은 양수를 포함하고
- b는 비어 있다.
* 목표는 숫자들을 오름차순으로 스택 a에 정렬시켜 놓는 것이다. 그것을 위해 아래 연산들을 사용할 수 있다.
(1) sa (swap a) : a의 top에 있는 두 원소를 바꾼다. a의 원소가 하나 이하라면, 아무런 행위도 하지 않는다.
(2) sb (swap b) : b의 top에 있는 두 원소를 바꾼다. b의 원소가 하나 이하라면, 아무런 행위도 하지 않는다.
(3) ss : sa와 sb를 동시에 행한다.
(4) pa (push a) : b의 top에 위치한 원소를 a의 top에 놓는다. b가 비어있다면, 아무런 행위도 하지 않는다.
(5) pb (push b) : a의 top에 위치한 원소를 b의 top에 놓는다. a가 비어있다면, 아무런 행위도 하지 않는다.
(6) ra (rotate a) : a의 원소들을 한 칸씩 옮긴다. 첫 번째 원소는 마지막 원소가 된다.
직선 배열 상에서 인덱스가 1씩 줄어든다. 0번째 원소는 배열의 size - 1번째 원소가 된다.
(7) rb (rotate b) : b의 원소들을 한 칸씩 옮긴다. 첫 번째 원소는 마지막 원소가 된다.
직선 배열 상에서 인덱스가 1씩 줄어든다. 0번째 원소는 배열의 size - 1번째 원소가 된다.
(8) rr : ra와 rb를 동시에 행한다.
(9) rra (reverse rotate a) : a의 원소들을 한 칸씩 옮긴다. 마지막 원소는 첫 번째 원소가 된다.
직선 배열 상에서 인덱스가 1씩 늘어난다. size - 1번째 원소는 배열의 0번째 원소가 된다.
(10) rrb (reverse rotate b) : b의 원소들을 한 칸씩 옮긴다. 마지막 원소는 첫 번째 원소가 된다.
직선 배열 상에서 인덱스가 1씩 늘어난다. size - 1번째 원소는 배열의 0번째 원소가 된다.
2. Example
- subject에서 친절하게도 예시를 보여준다.
Init a and b:
2 <- 2와 1 주목
1
3
6
5
8
_ _
a b
* sa 실행 시
1 <- 1과 2의 순서가 바뀜
2
3
6
5
8
_ _
a b
* pb 3번 실행 시
6 3
5 2
8 1 <- pb시 a의 top에서 b의 top으로 원소를 옮긴다.
_ _
a b
* ra, rb 실행 시 (rr과 동일)
5 2
8 1
6 3 <- 첫 번째 원소가 마지막 원소가 됨.
_ _
a b
* rra, rrb 실행 시 (rrr과 동일)
6 3 <- 마지막 원소가 첫 번째 원소가 됨
5 2
8 1
_ _
a b
* sa 실행 시
5 3 <- 스택 a의 top에 있는 두 원소의 순서 변동 (5, 6)
6 2
8 1
_ _
a b
* pa 3번 실행 시
1 <- pa시 b의 top에서 a의 top으로 원소를 옮긴다.
2
3
5
6
8
_ _
a b
=> 정렬 완료!!!
- 위 예시에는 흥미로운 부분이 있는데, 위의 예시대로라면 스택 a의 배열
2 1 3 6 5 8이sa pb pb pb ra rb rra rrb sa pa pa pa의 12번 연산 실행으로 정렬이 완료된 것인데, 위 연산은 예시에 적힌대로
sa pb pb pb rr rrr sa pa pa pa와 같이 줄일 수도 있고, rr 뒤에 rrr을 실행한 것은 결국 rr을 실행하기 전과 똑같은 상태가 되므로 결과적으로
sa pb pb pb sa pa pa pa로, 12번의 연산이 8번으로 줄게 된다(물론 예시에서는 ra, rb, rra, rrb, rr, rrr이 어떻게 작동하는지 보여주기 위해 연산을 행했을 것이다). 이 부분은 연산 수를 최적화할 때 참고가 될지도 모른다. 본인은 그리디 알고리즘을 사용했기 때문에 최적화의 의미가 크지 않아서 그냥 넘어갔는데, 그 외의 방법을 사용했다면 눈여겨 볼 만하지 않을까 생각한다.
연결 리스트 VS 배열
단도직입적으로 말하자면 본인은 배열로 스택을 구현했다. 그리고 이 시리즈 전체가 그것에 대해 이야기하는 장이 될 것이다.
중요한 것들을 나열하자면 다음과 같다.
1. 배열을 통한 원형 큐(Circular Queue)의 구현
- ra, rb, rra, rrb와 같은 명령어를 구현하기 위해서 rotate(혹은 reverse rotate)를 실행했을 때 첫 번째 원소가 마지막 원소가 되고, 마지막 원소가 첫 번째 원소가 되어야 한다. 구조체에 head와 tail을 담는 것으로 원형 큐(Circular Queue)를 구현할 수 있다(혹은 deque).
2. 가변 배열(Dynamic Array)의 구현
push, pop이 이루어지면서(pa, pb) 배열의 크기가 변하게 되는데, 이렇게 변하는 사이즈에 맞추어 배열의 사이즈를 계속해서 바꾸어주어야 한다. 구조체에 Size와 Capacity를 담는 것으로 연산량을 최적화하여 가변 배열을 구현할 수 있다.
대략 이런 모양의 구조체를 다루게 될 것이다. 이것으로 개요 설명을 마친다.
typedef struct s_deque { int *arr; int head; int tail; int size; int capacity; } t_deque;
