과제
이번 과제에서는 스택에 있는 데이터를 한정된 명령어를 이용하여 최대한 적은 횟수 내에 정렬하는 것을 목표로 합니다. 성공하기 위해서는 다양한 정렬 알고리즘을 조작해 보고, 최적화된 데이터 정렬에 가장 적합한 알고리즘을 선택하여야 합니다.
문제
스택 a와 b가 있습니다.
처음 시작할때 스택 a는 랜덤한 개수의 양의 정수들과 음의 정수들을 포함하며, 중복된 값은 포함되지 않습니다.
스택 b는 비어있습니다.
스택 a에 정수들을 오름차순으로 정렬하는것이 목표입니다.
명령어 목록
- sa(swap a) : 스택 a의 top에 위치한 두 개의 원소의 순서를 맞바꿉니다. 스택 a가 비어있거나 원소가 1개만 있을 때는 아무 동작도 하지 않습니다.
- sb(swap b) : 스택 b의 top에 위치한 두 개의 원소의 순서를 맞바꿉니다. 스택 b가 비어있거나 원소가 1개만 있을 때는 아무 동작도 하지 않습니다.
- ss(swap all) : sa와 sb를 동시에 수행합니다.
- pa(push a) : 스택 b의 top에 위치한 원소 한 개를 스택 a의 top으로 옮깁니다. 스택 b가 비어있을 경우에는 아무 동작도 하지 않습니다.
- pb(push b) : 스택 a의 top에 위치한 원소 한 개를 스택 b의 top으로 옮깁니다 스택 b가 비어있을 경우에는 아무 동작도 하지 않습니다.
- ra(rotate a) : 스택 a의 원소를 한 칸씩 위로 옮깁니다. 스택의 첫 번째 원소는 맨 마지막 원소가 됩니다.
- rb(rotate b) : 스택 b의 원소를 한 칸씩 위로 옮깁니다. 스택의 첫 번째 원소는 맨 마지막 원소가 됩니다.
- rr(rotate all) : ra와 rb를 동시에 수행합니다.
- rra(reverse rotate a) : 스택 a의 원소를 한 칸씩 아래로 옮깁니다. 스택의 마지막 원소는 맨 첫 번째 원소가 됩니다.
- rrb(reverse rotate b) : 스택 b의 원소를 한 칸씩 아래로 옮깁니다. 스택의 마지막 원소는 맨 첫 번째 원소가 됩니다.
- rrr(reverse rotate all) : rra와 rrb를 동시에 수행합니다.
스택(stack)
스택이란 후입선출의 특성을 가지는 자료구조이다 데이터가 들어오게되면 스택의 Top에 쌓이기되고 데이터를 출력할 때도 스택의 Top에서 빠지기 때문에 나중에 들어온 데이터가 먼저 나가게 된다
push 명령어는 스택에 새로운 데이터를 추가하는 명령이다 스택의 Top에 새로운 데이터를 추가해준다
pop 명령어는 스택의 Top에 있는 데이터를 출력해주는 명령이다 pop명령을 실행후 해당 데이터는 스택에서 빠지게 된다
문제에서의 스택
push_swap 과제에서 말하는 스택은 우리가 아는 스택과는 다른 구조를 가지고있다 push, swap 명령어는 top에서 실행되어 기존 스택 자료구조에서도 문제없이 동작이 가능하지만 rotate, reverse rotate 명령어는 스택의 top에 위치한 데이터를 bottom으로 옮겨야 되거나 스택의 bottom에 위치한 데이터를 top으로 옮겨야 되기 때문에 top에서부터 하나씩 데이터를 추출하는 스택 자료구조로 과제를 진행하기에는 부족함이있다
덱(deque)
덱 이란 양쪽 끝(top, bottom)에서 삽입과 삭제가 모두 가능한 자료구조이다 push_swap과제에서는 덱을 원형 양방향 연결리스트를 이용하여 구현한다
원형 양방향 연결 리스트
원형 양방향 연결 리스트의 구조는 각 노드가 prev 와 next 노드의 주소를 가지고있어서 연결리시트의 단점인 특정 데이터를 찾고싶을때 노드를 head부터 tail까지 전체를 순회해야 되는 단점을 개선한 방식이다 head의 prev는 tail이 되고 tail의 next는 head가 되게된다 이러면 궁금증이 보통 연결리스트는 tail의 next를 NULL포인터로 저장하여 연결리스트가 종료된것을 알려주는데 원형 리스트의 경우 tail의 다음 노드가 head로 연결되어 종료지점을 판단하기가 어렵다 이에 head구조체를 따로두어 size를 기록하게하고 size를 이용하여 연결리스트의 순회가 끝까지 이루어졌는지를 확인하게한다
- 원형 연결 리스트 : tail의 다음 노드가 head를 가리키는 연결리스트이다 원처럼 끝없이 순환한다고 하여 원형연결리스트 라고 한다
- 양방향 연결 리스트 : 연결리스트의 각 Node가 Next와 Prev를 가지고있는 자료구조이다
