push_swap 공부하기
By kkimkkimkkim
42Seoul/push_swap
2021. 3. 4. 00:05

    Push_Swap 과제 해석

    !!!

    오역/의역으로 꽉 찬 내용입니다.

    Push_Swap

    Swap_Push는 자연스럽지 않으니까요.. ㅎ



    요약: 

    이 프로젝트는 당신이 한정된 명령어를 이용하여 최소한의 작업만으로 스택의 값을 정렬할 수 있도록 해줄 겁니다. 성공하기 위해선 다양한 자료형과 알고리즘들을 조작할 줄 알고, 가장 적합한 방법을 선택해야 합니다.


    목차

    I 머리말
    II 소개
    III 목표
    IV 일반적인 지침
    V 필수 파트
      V.1   게임 규칙
      V.2   예제
      V.3   "체커" 프로그램
      V.4   "Push_Swap" 프로그램
    VI 뽀오너스 파트
    VII 제출 및 동료 수집(?)


    Chapter I : 머리말

    C언어

    #include	<stdio.h>

int			main(void)
{
	printf("hello, world\n");
	return (0);
}

    어셈블리어

    cseg segment
assume cs:cseg, ds:cseg
org 100h
main proc
jmp debut
mess db 'Hello world!$'
debut:
mov dx, offset mess
mov ah, 9
int 21h
ret
main endp
cseg ends
end main

    LOLCODE

    HAI
CAN HAS STDIO?
VISIBLE "HELLO WORLD!"
KTHXBYE

    PHP

    <?php
	echo "Hello world!";
?>

    BrainFuck

    ++++++++++[>+++++++>++++++++++>+++>+<<<<-]
>++.>+.+++++++..+++.>++.
<<+++++++++++++++.>.+++.------.--------.>+.>.

    닉값 오지네

    C#

    using System;

public	class				HelloWorld
{
	public	static void		Main ()
	{
		Console.WriteLine("Hello world!");
	}
}

    닉값 오지네

    HTML5

    <와 >로 넣어도 깨져버리네요.

    YASL

    "Hello world!"
print

    OCaml

    let main () =
print_endline "Hello world !"
let _ = main ()


    Chapter II : 소개

    Push_Swap 프로젝트는 간단하면서도 알고리즘을 공부하는데 매우 효과적입니다.

    데이터를 정렬해야 하니까요.

    두 스택을 모두 조작할 수 있는 일련의 int 값, 2개의 스택 및 지침을 마음대로 사용할 수 있습니다.

      아, 당신의 목표요?

    입력받은 정수 매개변수를 정렬하고 표준 출력에 표시하는 push_swap이라는 프로그램을 만드세요. (당연히 C언어로)

    쉬워 보이나요?

    두고 보자구요...



    Chapter III : 목표

    정렬 알고리즘을 작성하는 건 보통 복잡성의 개념을 처음 경험하는 일이기에,

    프로그래며에게 있어 매우 중요한 단계입니다.

    정렬 알고리즘과 복잡성에 관한 문제는 면접에서 나오는 고전적인 질문 중 하나기도 하죠.

    이런 개념을 한 번에 사용해야 하기 때문에, 배우기에 좋은 타이밍일 겁니다.

    이 프로젝트의 학습목표는 엄격함, C 사용, 기본적인 알고리즘 사용입니다.

    여러번 말했듯이, 알고리즘의 복잡성을 공부해야 합니다. (대충 강조)


    값을 정렬하는 건 간단합니다.

    다만.. 그걸 빠르게 하는 것은 덜 간단합니다.

    특히 정수의 구성 마다 효율적인 알고리즘이 다를 수 있기 때문입니다.



    Chapter IV : 일반적인 지침


    - 이 프로젝트는 사람에 의해서만 평가됩니다. (기계평가 없음)

       : 따라서 자유롭게 파일을 구성하고 이름지을 수 있겠지만, 평가자를 존중하는것도 잊지 마세요.


    - 실행 파일의 이름은 push_swap이 되어야 합니다.


    - Makefile을 제출해야 합니다.

       : Makefile은 프로젝트를 컴파일하며, 일반적인 규칙을 포함합니다.

       : 필요하다면 프로젝트를 재컴파일 할 수 있습니다.


    - 영리하다면 당신의 프로젝트에 라이브러리를 사용하고,

       : libft와 자체 Makefile을 포함하는 libft 폴더도 제출 할 수 있습니다.

       : 이럴 때 당신의 Makefile은 라이브러리를 컴파일한 후 프로젝트를 컴파일해야 합니다.


    - 전역 변수 금지!


    - 당신의 프로젝트는 규범에 따라 C언어로 작성되어야 합니다.


    - 오류를 민감하게 처리하세요. Segfault, BusError, DoubleFree 등 금지


    - 프로그램에 메모리 누수가 있어서는 안됩니다!


    - 필수 파트를 처리함에 있어 다음 기능을 사용할 수 있습니다.

       : write
       : read
       : malloc
       : free
       : exit


    - Forum, Slack에 편하게 질문하세요 ㅎㅎ



    필수 파트

    V.1 게임 규칙

    - A와 B라는 2개의 스택으로 구성됩니다.


    - 시작하기:

       : A에는 양수 또는 음수의 "난수"가 포함됩니다. (중복 없음)

       : B는 비어 있습니다.


    - 목표는 스택A에 오름차순 번호를 정렬하는 것입니다.


    - 이걸 하기 위해 수행할 수 있는 작업들:

    sa (swap A) 스택A의 맨 위에 있는 처음 2개 요소를 교체합니다.
    (요소가 하나만 있거나 없는 경우, 아무 작업도 하지 않습니다.)
    sb (swap B) 스택B의 맨 위에 있는 처음 2개 요소를 교체합니다.
    (요소가 하나만 있거나 없는 경우, 아무 작업도 하지 않습니다.)
    ss (swap A and B both) sa와 sb를 동시에 실행합니다.
    pa (push A) 스택B 상단에 있는 첫 번째 요소를 가져와 A의 상단에 배치합니다.
    (B가 비어 있는 경우, 아무 작업도 하지 않습니다.)
    pb (push B) 스택A 상단에 있는 첫 번째 요소를 가져와 B의 상단에 배치합니다.
    (A가 비어 있는 경우, 아무 작업도 하지 않습니다.)
    ra (rotate B) 스택A에 있는 모든 요소를 1만큼 위로 이동합니다.
    첫 번째 요소가 마지막 요소가 됩니다!
    rb (rotate A) 스택B에 있는 모든 요소를 1만큼 위로 이동합니다.
    첫 번째 요소가 마지막 요소가 됩니다!
    rr (rotate A and B both) ra와 rb를 동시에 실행합니다.
    rra (reverse_rotate A) 스택A에 있는 모든 요소를 1만큼 아래로 이동합니다.
    마지막 요소가 첫 번째 요소가 됩니다!
    rrb (reverse_rotate B) 스택B에 있는 모든 요소를 1만큼 아래로 이동합니다.
    마지막 요소가 첫 번째 요소가 됩니다!
    rrr (reverse_rotate A and B both) rra와 rrb를 동시에 실행합니다.

    V.2 예시

    앞의 명령들을 설명하기 위해 임의의 정수 목록을 정렬해 보겠습니다.

    여기서는 두 스택이 모두 오른쪽에서 확장되고 있음을 고려합니다.


    --------------------------------------------------------------------
스택 A, B 초기화:
2
1
3
6
5
8
_ _
A B
--------------------------------------------------------------------
sa 실행:
1
2
3
6
5
8
_ _
A B
--------------------------------------------------------------------
pb pb pb 실행:
6 3
5 2
8 1
_ _
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
6 2
8 1
_ _
A B
--------------------------------------------------------------------
pa pa pa 실행:
1
2
3
5
6
8
_ _
A B
--------------------------------------------------------------------

    지금 보여드린 예시는 정수를 12번의 연산을 통해 정렬한 것입니다. 더 낫게 할 수 있나요?

    V.3 "push_swap" 프로그램

    - 정수로 구성된 스택을 매개변수로 받는 push_swap이라는 프로그램을 작성해야 합니다.

       첫 번째 인수는 스택의 맨 위입니다. (순서 주의!)


    - 스택 A를 정렬할 수 있는 "가장 적은" 명령어 목록을 표시해야하며,

       가장 작은 숫자가 맨 위에 있어야 합니다.


    - 지침들은 "\n"으로 구분되어야 하고, 다른 내용은 없어야 합니다.


    - 저희의 목표는 최소한의 작업 수로 스택을 정렬하는 겁니다.

       디펜스하는 동안 프로그램이 찾은 실행수와 허용되는 최대 실행수를 비교합니다.

       실행수가 너무 많거나 정렬이 되지 않을 경우 점수를 얻지 못합니다..


    - 오류 발생 시 "Error\n"을 표시하여야 합니다.

       일부 인수가 정수가 아니거나, 일부 인수가 정수보다 크거나 중복이 있는 경우가 에러입니다.

    $>./push_swap 2 1 3 6 5 8
sa
pb
pb
pb
sa
pa
pa
pa

$>./push_swap 0 one 2 3
Error
$>

    - 디펜스 동안 프로그램에 대해 제대로 확인하기 위해 바이너리를 제공합니다.

       다음과 같이 동작합니다:

    $>ARG="4 67 3 87 23"; ./push_swap $ARG | wc -l
	6
$>ARG="4 67 3 87 23"; ./push_swap $ARG | ./checker_OS $ARG
OK
$>

    - check_OS 프로그램이 KO를 표시한다면 당신의 push_swap이 목록을 정렬하지 않았음을 의미합니다.

       check_OS 프로그램은 intra.42.fr의 프로젝트 리소스에 있으니 마음껏 사용하세요.

       보너스 섹션에서 작동 방식에 대한 설명을 찾을 수 있습니다.

    Chapter VI. 보너스 파트

    티스토리툴바