Push_swap ① Subject

Summary
이 프로젝트에서는 가능한 최소 작업 수를 사용하여 제한된 명령어 집합으로 스택의 데이터를 정렬할 수 있다. 이를 성공하기 위해서는 다양한 유형의 알고리즘을 조작하고 최적화된 데이터 정렬에 가장 적합한 솔루션을 선택해야 한다.

Objectives

정렬 알고리즘을 작성하는 것은 개발자의 여정에서 매우 중요한 단계이다. 보통 이 때 복잡성(알고리즘 분석)의 개념을 처음 접하게 된다.

• 알고리즘 분석 : 알고리즘을 실행하는데 필요한 자원의 수를 결정하는 것

정렬 알고리즘과 그 복잡성은 취업 면접에서 논의되는 고전적인 질문 중 하나이다. 이러한 개념은 언젠가는 직면해야 하기 때문에 지금 그 개념을 살펴보는 것은 좋은 시기일 것이다.
이 프로젝트의 학습 목표는 정밀함, C의 사용 및 기본 알고리즘의 사용이다. 특히 복잡성에 초점을 맞추고 있다.
값을 정렬하는 것은 간단하다. 가능한 가장 빠른 방법으로 분류하는 것은 덜 간단하다. 정수의 구성마다 가장 효율적인 정렬 솔루션이 다를 수 있기 때문이다.

Mandatory part

The rules

• a, b라는 이름의 두 개의 스택이 있다. (스택 : 요소를 더하고 빼는게 제일 위에만 가능한 자료구조)
• 시작할 때:
  • 스택 a에는 중복없는 양수 와/또는 음수가 임의의 개수만큼 있다.
  • 스택 b는 비어있다.
• 목표는 스택 a에 오름차순으로 수를 배열하는 것이다. 이를 위해 아래의 작업을 원하는 대로 수행해야 한다.
  • sa (swap a) : a의 제일 위 2개의 요소를 바꿈
  • sb (swap b) : b의 제일 위 2개의 요소를 바꿈
  • ss : sa와 sb를 동시에 진행
  • pa (push a) : b의 제일 위의 요소를 a의 제일 위로 이동. b가 비어있으면 아무것도 안함.
  • pb (push b) : a의 제일 위의 요소를 b의 제일 위로 이동. a가 비어있으면 아무것도 안함.
  • ra (rotate a) : a의 전체 요소를 위로 한 칸씩 올림. 제일 위에 있던 요소는 제일 아래로 이동.
  • rb (rotate b) : b의 전체 요소를 위로 한 칸씩 올림. 제일 위에 있던 요소는 제일 아래로 이동.
  • rr : ra와 rb를 동시에 진행
  • rra (reverse rotate a) : a의 전체 요소를 아래로 한 칸씩 내림. 제일 아래에 있던 요소는 제일 위로 이동.
  • rrb (reverse rotate b) : b의 전체 요소를 아래로 한 칸씩 내림. 제일 아래에 있던 요소는 제일 위로 이동.
  • rrr : rra와 rrb를 동시에 진행

The “push_swap” program

프로그램 이름	push_swap
제출 파일	Makefile, *.h, *.c
인자	stack a : 정수 리스트
외부 함수	read, write, malloc, free, exit, ft_printf를 포함해 본인이 작성한 코드
Libft 허용 여부	허용
설명	스택을 정렬함

프로젝트는 아래의 규칙을 준수해야 한다.

• 소스파일을 컴파일할 Makefile을 제출해야 한다. 이 Makefile은 리링크되어선 안된다.
• 전역변수는 금지된다.
• int형의 리스트로 이루어진 스택 a를 인자로 받는 push_swap이라는 프로그램을 작성해야 한다. 첫번째 인자는 제일 위에 위치하게 된다. (순서에 주의할 것)
• 프로그램은 스택 a를 작은 숫자가 제일 위로 가는 방식으로 만드는 가장 적은 수의 명령어 리스트를 표시해야 한다.
• 명령어는 '\n' 로만 구분되어야 한다.
• 목표는 스택을 가장 적은 동작으로 정렬하는 것이다. 평가 과정에서 너의 프로그램이 찾은 명령어의 수는 한도(용납될 수 있는 최대의 수)와 비교될 것이다. 프로그램이 한도를 넘거나 수를 제대로 정렬하지 못한다면 0점을 받을 것이다.
• 인자가 주어지지 않았다면 아무것도 표시하지 않고 프롬프트를 반환해야 한다.
• 에러가 발생하면 “Error“와 개행문자를 표준 에러로 표시해야 한다. 에러는 다음 경우에 발생한다.
  • 일부 인자가 int형이 아닌 경우
  • 일부 인자가 int형보다 큰 경우
  • 중복된 수가 있는 경우
• 평가 과정에서 프로그램을 체크하기 위해 바이너리가 제공된다.
• checker_OS가 KO를 표시하면 너의 push_swap이 수를 정렬하지 못했다는 것을 의미한다.

Bonus part

프로그램 이름	checker
제출 파일	*.h, *.c
인자	stack a : 정수 리스트
외부 함수	read, write, malloc, free, exit, ft_printf를 포함해 본인이 작성한 코드
Libft 허용 여부	허용
설명	스택을 정렬함

• 스택 a의 수를 인자로 받는 checker라는 이름의 프로그램을 작성해라. 인자가 주어지지 않는다면 프로그램은 종료되고 아무것도 표시하지 않는다.
• 그 다음 프로그램은 기다린 후 표준 입력의 명령어(각 명령어 다음엔 개행문자가 옴)를 읽어들인다. 명령어를 읽고 난 후, 프로그램은 인자에 입력받은 명령어를 실행시킨다.
• 이 명령어들을 실행시킨 후에 스택 a가 정렬되고 스택 b가 비었다면 프로그램은 “OK“와 뒤의 개행문자를 표준 출력으로 표시한다.
• 이 외에 모든 경우, 뒤에 '\n' 이 붙은 “KO“를 표준 출력으로 표시해야 한다.
• 에러가 발생한 경우 “Error“와 개행문자를 표준 에러로 표시해야한다. 에러는 다음의 경우 발생한다.
  • 일부 인자가 int형이 아닌 경우
  • 일부 인자가 int형보다 큰 경우
  • 중복된 수가 있는 경우
  • 명령어가 존재하지 않거나 제대로 포매팅되지 않은 경우