push_swap
서브젝트 요약
최소한의 동작으로 스택의 데이터 정렬하기. 최적의 정렬 알고리즘을 찾아야 함.
두 스택 A, B가 주어진다. 처음에는 스택 A에 숫자들이 채워져있다. 스택 B는 비어있다.
적절한 연산을 통해 A의 숫자들을 정렬해야한다.
과제에서 사용할 수 있는 연산은 다음과 같다.
-> pa, pb, sa, sb, ss, ra, rb, rr, rra, rrb, rrr
checker , push_swap 두 개의 프로그램을 작성해야 한다.push_swap 프로그램 작성은 필수, checker 프로그램은 보너스 파트로 변경됨
checker : 표준입력으로 랜덤한 정수 리스트를 받아서 저장하고, 정렬되었는지 검사한다.
push_swap : 정수들을 정렬하기 위해서 몇 번의 움직임(명령)이 필요한지 계산하고, 해당 명령들을 표준출력으로 출력한다.
두 프로그램 모두 빈 문자열, 파라미터가 없는 경우, 숫자가 아닌 파라미터, 중복, 유효하지 않거나 존재하지 않는 명령 등을 에러처리해야한다.
General Instructions
-
42 Norm을 지켜야 한다. (C언어로 작성한 파일만)
-
write,read,malloc,free,exit을 사용할 수 있다. -
메모리 누수가 없어야 한다. 예상치 못한 방식으로 프로그램이 종료되어서는 안 된다. (seg fault, bus error, double free 등)
-
Makefile을 제출해야 함. 일반적인 rule을 포함해야한다. (all, clean, fclean, re, $(NAME))
-
libft 사용 가능
-
전역변수 사용 금지
-
디렉토리 구조, 파일 이름 등은 자유롭게. (뮬리넷 채점 x)
사전 지식
자료구조
스택은 양방향 연결리스트로 구현한다.
양방향 연결리스트로 구현하면 각 스택의 top과 bottom에 있는 원소에 가장 적은 움직임으로 접근할 수 있기 때문이다.
정렬 알고리즘
데이터를 정렬해야 하는 이유 : 효율적인 탐색을 위해서. (데이터가 정렬되어 있으면 이진탐색이라는 강력한 알고리즘을 사용할 수 있다. )
비교정렬 : 주어진 데이터들이 있을 때, 값들을 서로 비교해 순서에 맞게 자리를 바꿔주는 정렬 방법. 입력된 데이터의 크기가 n이라고 했을 때, n2번 만큼 비교를 해야 정렬이 된다. 현재는 대략 (nlgn)번 비교할 수 있도록 줄인 상태이고, 여기서 더 이상 줄일 수 없다고 증명되었다.
정렬 알고리즘은 이론과 달리 실제로 돌려봤을 때 의외의 결과가 나오는 경우가 종종 있다. 하드웨어 입출력에서 걸리는 시간에 차이가 있어서, 이론적으로는 더 느려야하는 알고리즘이 실제로는 더 빠르다던가 하는 식이다.
실제 응용에서는 상황에 따라 두 가지 이상의 정렬 방법을 사용하는 경우가 많다.
O(n log n)인 정렬 방법으로는 퀵 정렬(Quick sort), 병합정렬(Merge sort) 등이 있다.
1) 빠른정렬 (퀵정렬, Quick sort)
평균적인 상황에서 최고의 성능을 나타낸다. 컴퓨터로 가장 많이 구현된 정렬 알고리즘 중 하나.
적절한 원소 하나를 기준(피벗, pivot)으로 삼아 그보다 작은 것들을 앞으로 옮긴다.
피벗보다 작은 것, 큰 것으로 나눈 뒤 나누어진 각각에서 다시 피벗을 잡고 정렬해 각각의 크기가 0이나 1이 될 때까지 정렬한다.
이렇게 피벗을 잡고 이보다 작은 원소들을 왼쪽으로, 보다 큰 원소들을 오른쪽으로 나누는 걸 partition step(분할 알고리즘)이라고 한다.
분할을 어떻게 하느냐에 따라 성능에 차이가 날 수 있다.
가장 간단한 분할 알고리즘은 피벗을 맨 오른쪽 값을 기준으로 하는 것이다.
링크드 리스트는 퀵 정렬이 가능하다. 첫번째 노드 A를 피벗으로 놓고 나머지 노드들 중 피벗보다 작은 것들은 L1, 큰 것들은 L2로 연결한다. L1과 L2를 퀵정렬한 뒤 L1->A->L2 순으로 연결하면 정렬 완료.
시간복잡도 O(n log n) ~ O(n^2)
+) 정렬 알고리즘의 시간복잡도를 측정할 때, 비교연산은 세지 않는 이유 :
스왑 연산에는 메모리를 읽고 쓰는 과정이 포함되는데, 메모리를 읽고 쓰는 것은 캐시 메모리를 읽어들이는 것에 비해 훨씬 오래 걸린다. 그런데 연속된 메모리 공간을 순회하면서 비교하는 경우에는 높은 확률로 비교하려는 값들이 캐시메모리에 올라와 있을 것이다. 따라서 비교연산 횟수는 시간복잡도를 계산할 때 무시할만함.
원소의 갯수가 n이라고 할 때, 퀵소트는 분할에 드는 비용이 n에 비례한다. (k*n)
그리고 분할하는 횟수는 logn에 비례한다.
2) 병합정렬 (합병정렬, Merge sort)
대표적인 분할 정복 알고리즘. 더 이상 쪼갤 수 없을 때까지 분할하다가, 분할이 끝나면 정렬하면서 정복해나간다.
데이터 크기만한 메모리가 추가로 필요하며, 퀵 정렬보다 전반적으로 성능이 떨어지지만, 데이터의 상태에 별 영향을 받지 않는다는 장점이 있다.
push_swap 알고리즘
원소의 개수가 5개 이하일 때, 100개 이하일 때, 500개 이하일 때로 나눠서
정렬 알고리즘을 구현한다.
1) 중앙값 찾아서 나누기 -> 최댓값, 최솟값 찾아서 정렬하기
100개 이하일 때 :
중위값을 찾는다.
중위값보다 작은 수들을 스택 b에 넣는다.
스택 b에서 최댓값과 최솟값을 찾는다.
최댓값을 rotate up하는 것 vs 최솟값을 rotate down하는 것 중에서
더 움직임이 적은 쪽을 선택하고, 실행한다.
스택 a에 최댓값 (스택 b의 top)을 넣는다.
이렇게 하면, 숫자들이 이미 정렬된 상태로 스택 a에 담기게 된다.
그리고 나서 중위값보다 큰 수들을 스택 b에 넣어서 위 과정을 똑같이 반복한다.
500개 이하일 때 :
같은 방법을 사용하지만, 스택 a를 중앙값을 기준으로 2분의 1씩 나누는 대신,
4분의 1씩 나눴다.
2) 빠른정렬에서 각 분할의 중앙값 찾아서 피벗으로 사용하기 (내가 선택한 알고리즘)
스택 A에서 중앙값을 찾고, 중앙값을 기준으로 낮은 숫자를 스택 B로 옮기고,
높은 숫자를 스택 A에 그대로 두는 방식으로 분할한다.
분할이 한 번 이루어질 때마다 스택 B에 파티션을 둔다. (파티션 기준으로 아래에 있는 수 < 위에 있는 수)
스택 A에 3개 이하의 수가 남을 때까지 반복 분할한다.
스택 A에 3개 이하의 수가 남으면, 이 수들을 정렬한다.
다음으로, 스택 B에서 마지막 파티션 전까지의 숫자들 중에서 중위값을 찾는다.
스택 B의 다음 파티션에 도달할 때까지, 중위값보다 큰 값들을 스택 A에 push한다.
-
만약 3개 이하의 숫자를 스택 A에 넣었다면, swap과 rotation 명령어를 이용해 이 수들을 정렬한다. 그리고 스택 A의 끝에도 파티션을 둔다. (파티션 아래는 정렬된 상태)
스택 B의 숫자들은 이러한 방식으로 스택 A로 다시 옮겨진다.
-
만약 3개 이상의 숫자가 스택 A에 다시 push되었다면,
스택 A는 마지막 파티션 뒤에 있는 모든 숫자의 중위값을 중심으로, 반복적으로 분할하는 과정을 다시 수행한다. (높은 값은 그대로 스택 A에 두고 낮은 값은 B로 push하는 것)
스택 A가 정렬될 때까지 위의 모든 과정이 반복된다.
참고) 중앙값을 찾는 이유 :
{ 1,2,3,4,5,6 }과 같은 정렬된 상태의 배열이 있다.
이를 최좌측 값인 1을 pivot으로 하여 퀵정렬을 수행하면 아래와 같은 파티셔닝을 거친다.1단계: (1) (2, 3, 4, 5, 6) -> pivot = 2
2단계: (1)(2) (3, 4, 5, 6) -> pivot = 3
3단계: (1)(2)(3) (4, 5, 6) -> pivot = 4......즉, 피벗을 기준으로 좌측과 우측으로 이분하는 파티셔닝이 치우쳐서 진행되는 것이다.
이 파티셔닝이 최대한 같은 크기로 이분되어야
NlogN에 가깝게 실행이 될 수 있는데, 이렇게 치우치면N^2정렬들과 차이가 없다.
중간값 퀵정렬은 이렇게 이미 오름차순 또는 내림차순으로 정렬되어 있거나, 유사한 상황에서 중간 값으로 피벗을 선정하여, 피벗을 기준으로 최대한 비슷한 크기로 이분 파티셔닝을 하는 데 그 의의가 있다.
구현하기
checker 프로그램
-
스택 a의 인자들을 정수 리스트 형식으로 받는다. 첫번째 인자가 스택의 top에 있어야 한다. (순서에 주의할 것). 인자가 주어지지 않으면 checker는 멈추고 아무것도 출력하지 않는다.
-
checker는 다음으로, 표준 입력으로 명령을 입력받는다. 각 명령 다음에는 개행문자가 온다. 모든 명령이 읽혔다면, checker는 해당 명령들을 인자로 받은 스택에서 실행한다.
-
명령 실행이 끝난 후에, 스택 a가 정렬되어 있고 스택 b가 비어있다면, checker는 "OK\n"를 출력한다. 그렇지 않은 경우 "KO\n"를 출력한다.
-
에러가 발생한 경우, 표준 에러(standard error)에 "Error\n"를 출력해야한다.
에러 예시 : 숫자가 아닌 인자, 정수 범위보다 큰 수, 중복된 숫자, 존재하지 않거나 잘못된 형식의 명령 등
(checker 프로그램의 경우 내가 과제를 할 때는 Mandatory part에 있었지만 현재는 보너스 파트로 이동해서 필수 구현 항목이 아님. 구현이 비교적 간단하기 때문에 checker 보너스는 하는 것을 추천!)
push_swap 프로그램
-
스택 a의 인자들을 정수 리스트 형식으로 받는다. 첫번째 인자가 스택의 top에 있어야 한다. (순서에 주의할 것).
-
스택 a를 최소한의 명령을 사용해 정렬해야한다. 가장 작은 수가 스택의 top에 있어야한다.
-
각 명령은 개행문자로 구분된다.
-
에러가 발생한 경우, 표준 에러에 "Error\n"를 출력해야 한다.
에러 예시 : 숫자가 아닌 인자, 정수 범위를 벗어난 인자, 중복 등
팁
1) 다음과 같이 인자가 들어오는 경우
$>ARG="4 67 3 87 23"; ./push_swap $ARG | wc -l
6
$>ARG="4 67 3 87 23"; ./push_swap $ARG | ./checker $ARG
OK
$>위 예제는 bash 쉘에서만 정상적으로 실행된다.
bash는 "4 67 3 87 23" 과 같이 인자가 들어온 경우 내부적으로 파싱을 해서 4, 67, 3, ... 으로 인자를 받지만,
zsh에서는 "4 67 3 87 23" 을 하나의 인자(하나의 문자열)로 취급하기 때문에 argument error가 된다.
zsh에서도 이런 예제가 error가 나지 않고 정상적으로 실행되게 하려고 push_swap에 파싱 로직을 추가하는 경우가 있다.
서브젝트에 있는 예제이다보니.. 디펜스가 불안하면 파싱을 해도 되지만, 그냥 bash에서 실행하고 평가를 진행해도 된다.
(근데 개인적으로는 zsh에서 저런 인자가 들어오는 경우는 그냥 argument error 처리를 하는 게 맞는 것 같다. )
2) checker를 사용해 push_swap을 테스트하는 방법
zsh인 경우
> ./push_swap 1 4 3 2 | ./checker 1 4 3 2
OKpush_swap을 실행한 결과 (ra rb ... ) 가 checker에 들어가서
1, 4, 3, 2가 제대로 정렬되는지 확인해볼 수 있다.
bash인 경우
> ARG="1 4 3 2"
> ./push_swap $ARG | ./checker $ARG당연히 zsh에서처럼 직접 숫자를 입력해서 테스트해도 되고, 위와 같이 변수 (ARG)로 설정해놓고 사용해도 된다.
3) push_swap 명령어 갯수를 확인하는 방법
> ./push_swap 1 4 3 2 | wc -l
7wc -l 명령어를 통해 출력 라인 수를 확인할 수 있다.
4) 충족해야 하는 명령어 갯수
- 숫자 3개일 때 : 명령어 3개 이하 출력
- 숫자 5개일 때 : 명령어 12개 이하 출력
- 숫자 100개일 때 : 명령어 700개 이하 5점, 명령어 900개 이하 4점, 명령어 1100개 이하 3점, 명령어 1300개 이하 2점, 명령어 1500개 이하 1점
- 숫자 500개일 때 : 명령어 5500개 이하 5점, 7000개 이하 4점, 8500개 이하 3점, 10000개 이하 2점, 115000개 이하 1점
(변경 전 과제 기준이므로 지금은 다를 수도 있다)
참고 자료
