Push_swap

본 프로젝트의 개요와 프로젝트를 진행하기 위한 개념 확립

프로젝트 소개

목표

Push_swap은 매우 간단하고 효과적인 알고리즘인 정렬에 관한 프로젝트이다. 정수값들의 집합, 2개의 스택, 그리고 두 스택을 조작하기 위한 명령어 집합이 주어진다. 목표는 입력 받은 정수 인자들을 정렬하는 push_swap 명령어를 사용하여 가장 작은 프로그램을 계산하고 표춘 출력에 출력하는 것이다. 요점은 다양한 유형을 알고리즘을 정밀하게 살펴보고 조작하여 최적화 된 데이터 정렬에 가장 적합한 솔루션을 선택하는 것이다. 여기서 그 기본 알고리즘의 복잡도라는 개념을 살펴보게 될 것이다.

허용 함수

• write
• read
• malloc
• free
• exit

규칙

a와 b라는 이름의 두 개의 스택을 가지고 인자를 스택 a에 오름차순으로 정렬한다.

게임은 다음과 같은 상태에서 시작한다 :

• a는 서로 중복되지 않는 음수 혹은 양수인 임의의 수를 가진다.
• b는 비어있다.

정렬하기 위해 다음 연산들을 수행할 수 있다 :

• sa : swap a - 스택 a의 가장 위에 있는 두 요소의 위치를 바꾼다. (요소가 하나도 없거나 한 개만 있을 경우 아무것도 수행하지 않음)
• sb : swap b - 스택 b의 가장 위에 있는 두 요소의 위치를 바꾼다. (요소가 하나도 없거나 한 개만 있을 경우 아무것도 하지 않음)
• ss : sa와 sb를 동시에 수행한다.
• pa : push a - 스택 b에서 가장 위에 있는 요소를 가져와서, 스택 a의 맨 위에 넣는다. (스택 b가 비어 있으면 아무것도 하지 않음)
• pb : push b - 스택 a에서 가장 위에 있는 요소를 가져와서, 스택 b의 맨 위에 넣는다. (스택 a가 비어 있으면 아무것도 하지 않음)
• ra : rotate a - 스택 a의 모든 요소를 1만큼 위로 이동시킨다. 첫 번째 요소는 마지막 요소가 된다.
• rb : rotate b - 스택 b의 모든 요소를 1만큼 위로 이동시킨다. 첫 번째 요소는 마지막 요소가 된다.
• rr : ra와 rb를 동시에 수행한다.
• rra : reverse rotate a - 스택 a의 모든 요소를 1만큼 아래로 이동시킨다. 마지막 요소는 첫 번째 요소가 된다.
• rrb : reverse rotate b - 스택 b의 모든 요소를 1만큼 아래로 이동시킨다. 마지막 요소는 첫 번째 요소가 된다.
• rrr : rra와 rrb를 동시에 수행한다.

예시

Init a and b:
2
1
3
6
5
8
_ _
a b

Exec sa:
1
2
3
6
5
8
_ _
a b

Exec pb pb pb:
6 3
5 2
8 1
_ _
a b

Exec ra rb (equiv. to rr):
5 2
8 1
6 3
_ _
a b

Exec rra rrb (equiv. to rrr):
6 3
5 2
8 1
_ _
a b

Exec sa:
5 3
6 2
8 1
_ _
a b

Exec pa pa pa:
1
2
3
5
6
8
_ _
a b

주의 사항

• push_swap이라는 이름의 프로그램을 작성해야 한다. 이 프로그램은 스택 a에 들어갈 값들을 정수 리스트의 형태로 포맷팅하여 인자로 받는다. 첫 번째 인자는 스택의 탑이 된다.
• 프로그램은 반드시 스택 a를 정렬하는데 가능한 가장 작은 개수의 명령어 리스트를 출력해야 한다.
• 명령어들은 \n으로만 구분되어야 한다.
• 목표는 가능한 적은 개수의 명령어 집합으로 스택을 정렬하는 것이다. 평가 도중에는 프로그램에서 도출한 명령어의 수와 허용된 최대 작업수를 비교한다. 프로그램에 너무 큰 리스트가 표시되거나 목록이 제대로 정렬되지 않은 경우 점수를 얻지 못한다.
• 에러의 경우에는, Error와 줄바꿈을 표준 에러에 출력해야 한다. 에러는 다음 예시들을 포함한다: 일부 인자가 정수가 아니거나, 정수 범위를 초과하거나, 중복이 있는 경우이다.
• checker_OS 프로그램이 KO를 출력하면, push_swap의 명령어 리스트가 정수 리스트를 정렬하지 못했음을 의미한다.