Push_swap

2 서클의 마지막 과제 push_swap을 시작해보자!!!

평가를 다니면서 많이 봤던 과제로 정렬을 하는데 2개의 stack에서 서로 상호작용을 하면서 여러 가지의 경우를 갖는다.

그리고 최적의 정렬 순서를 찾아 출력하는 것이 목표로 확인했다.

 

이제 자세히 알아보자!

 

---

 

1. subject 탐색
2. Algorithm
3. bonus

 

---

1. subject 탐색

MANDATORY PART

 

우리는 a, b의 stack을 갖고 있다.

 

먼저 a에 무작위의 수가 들어가 있고 b는 비어있다.

그리고 우리는 다음과 같은 11개의 연산을 할 수 있다.

 

• sa : stack a의 맨 위의 두 원소를 swap 한다.
• sb : stack b의 맨 위의 두 원소를 swap 한다.
• ss : sa, sb를 동시에 실행한다.
• pa : stack b의 맨 위의 원소를 stack a의 맨 위에 넣는다. (stack b가 비어있다면 X)
• pb : stack a의 맨 위의 원소를 stack b의 맨 위에 넣는다. (stack a가 비어있다면 X)
• ra : stack a의 맨 위의 원소를 맨 아래로 보낸다.
• rb : stack b의 맨 위의 원소를 맨 아래로 보낸다.
• rr : ra, rb를 동시에 실행한다.
• rra : stack a의 맨 아래의 원소를 맨 위로 보낸다.
• rrb : stack b의 맨 아래의 원소를 맨 위로 보낸다.
• rrr : rra, rrb를 동시에 실행한다.

우리는 프로그램을 실행하면 입력 인자를 받고 stack a에 넣는다. (입력 인자의 첫 번째가 stack의 맨 위)

출력되는 목록은 개행 문자(\n)로 구분되며 stack a를 최적 정렬방법의 목록을 출력해야 한다.

 

Error 상황

숫자 이외에 다른 문자가 입력되었을 때.

INT의 범위를 넘어간 숫자가 입력되었을 때.

입력된 문자에 중복된 숫자가 있을 때.

 

BONUS PART

 

위의 MANDATORY PART에서 만든 프로그램을 check 하는 프로그램 checker를 만든다.

 

checker 또한 정수의 리스트 형태로 된 stack a를 입력 인자로 받고 명령어들을 표준 입력으로 읽는다.

그리고 표준 입력으로 읽힌 문자들을 읽고 stack a를 명령대로 움직여서 정렬이 되어있는지 확인하고 stack b가 비어있다면 "OK" 정렬되지 않거나 stack b가 비어 있지 않다면 "KO"를 출력한다.

 

Error 상황

숫자 이외에 다른 문자가 입력되었을 때.

INT의 범위를 넘어간 숫자가 입력되었을 때.

입력된 문자에 중복된 숫자가 있을 때.

표준 입력으로 받은 명령어가 규정된 명령어가 아닐 때.

 

---

2. Algorithm

 

우리는 이미 여러 가지의 정렬 방식을 알고 있다.

예를 들어서 더블 소트, 퀵 소트, 선택 정렬, 삽입 정렬, 합병 정렬 등등...

하지만 우리는 단순히 정렬을 하는 것이 아니라 위의 11가지 방법을 이용하여 최적의 방법으로 정렬을 해야 한다.

 

자 우리는 그럼 어떤 식으로 접근을 해야 맞는 걸까?

문득, 이전 피신에서 했던 백트래킹이 생각난다.

 

뭔가 백트래킹은 조금 과정이 복잡할 거 같으면서 효율성이 떨어질 것 같은 느낌이다.

 

문득 검색하다 보니 Deque에 대한 이야기들이 나오는데 한번 알아보자!

 

Deque(Double Ended Queue)

즉, 이름과 같이 끝나는 곳이 두 개인 Queue인데 앞과 뒤에서 시작과 끝이 있다는 이야기인 듯하다.

 

구조체 선언은 아래와 같이 된다.

typedef struct	s_node
{
	int	Item;
  	t_node	*prev;
    	t_node	*next;
}		t_node;

typedef struct	s_deque
{
	t_node	*header;
  	t_node	*tailer;
}		t_deque;

이렇게 보면 전체적인 구성은 t_deque에 처음과 끝이 존재하고 header에는 prev가 NULL, tailer에는 next가 NULL이다.

그럼 이제 어디까지 손을 댈 수 있느냐 하면 prev와 next가 존재하니까 맨 앞 두 개, 맨 뒤 두 개까지 건드릴 수 있다는 뜻이다.

그럼 우리가 사용할 연산은 구현이 가능하다는 뜻이다.

 

일단은 입력 인자를 받고 숫자 외의 문자가 들어왔을 때, 중복된 숫자가 있을 때, INT의 범위를 넘어갔을 때의 로직을 짜 보자!

 

로직을 다 짰다.

그러고 나서 이제 오류가 없는 t_deque a이 존재하는데 이것을 어떤 알고리즘에 의해서 정렬을 시킬지가 의문인 것이다!

 

그전에 우리가 명령어를 먼저 만들어 보자.

 

크게 잡는다면 s, p, r, rr이 있는데 하나씩 생각해보자.

 

s의 경우는 맨 위가 그 아래의 원소를 swap 하는 것이다.

그렇다면 수정이 들어가야 하는 원소는 총 3개이다.

노드가 1=>2=>3라고 가정하면

1->next는 3을 가리키고 1->prev는 2를 가리킨다.

2->next는 1을 가리키고 2->prev는 NULL를 가리킨다.

3->prev는 2를 가리켜야 한다.

 

노드 2=>1=>3

 

p의 경우는 pa로 예시를 들면 b의 맨 위의 원소를 a의 맨 위로 옮기는 것이다.

a 헤더의 노드가 1=>2, b 헤더의 노드가 3=>4라고 가정하면

3->next는 1을 가리키고 3->prev는 NULL을 가리킨다.

1->prev는 3을 가리키고 4->prev는 NULL을 가리킨다.

 

a 헤더의 노드 3=>1=>2

b 헤더의 노드 4

 

r의 경우는 맨 위의 원소를 맨 아래로 보내는 것이다.

노드가 1=>2=>3=>4라고 가정하면

1->prev는 4를 가리키고 1->next는 NULL을 가리킨다.

4->next는 1을 가리키고 2->prev는 NULL을 가리킨다.

 

노드  2=>3=>4=>1

 

rr의 경우는 맨 아래의 원소를 맨 위로 보내는 것이다.

노드가 1=>2=>3=>4라고 가정하면

4->prev는 NULL을 가리키고 4->next는 1을 가리킨다.

1->prev는 4를 가리키고 3->next는 NULL을 가리킨다.

 

노드 4=>1=>2=>3

 

여기서 한 가지 더 집고 넘어가자면 입력 인수가 무조건 3개 이상이 여야 하는 것이 아니라

2개일 때의 경우가 3가지로 나뉜다.

./실행파일 숫자(1개)  =>   개행만 출력

./실행파일 문자(1개)  =>   에러 출력

./실행파일 "문자열"(1개)  => 문자열에서의 에러 체크 후 스플릿으로 나눈 뒤 정상출력

 

 

이제 정렬에 대한 것을 보자!

 

정렬은 많은 분들이 퀵 소트를 기본으로 진행했다.

퀵 소트를 간단히 설명하면 하나의 피봇을 잡고 피봇보다 큰 구역과 작은 구역으로 나눈다.

그리고 두 개의 구역에서 또 다른 피봇을 잡고 똑같이 진행한다.

이후 정렬이 구역의 수와 길이가 같다면 끝!

 

또 다른 정렬 중 머지 소트도 알아보자!

머지 소트는 전체 원소를 독립적으로 나누고 이를 각각의 대소를 따지면서 병합한다.

글로만 본다면 이해가 안 가니 위키를 참고하기로 하자...! 위키 최고

 

https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

퀵 정렬 - 위키백과, 우리 모두의 백과사전

https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

합병 정렬 - 위키백과, 우리 모두의 백과사전

 

왜 이 두 개의 정렬법을 사용했을까?

이는 시간 복잡도와 관련되어 있다.

시간 복잡도에 대해서 알아보자!

 

시간 복잡도는 말 그대로 "이 로직을 돌리는 데 시간이 얼마나 걸리느냐"라는 것이다.

우리가 코드 로직에서 하나의 반복문을 n번 돌린다면 시간 복잡도는 O(n)이다.

그리고 조건문이 있다면 조건문의 실행 시간을 전부 더한 것을 C라고 생각하면 시간 복잡도는 O(C*n)이다.

하지만 시간 복잡도는 상수를 무시한다. 즉, O(n)이다.

간혹 가다 log가 나오는데 이것은 보통 $log_2$이다.

몇 가지 수학적 지식이 들어가는데 그냥 2로 나누면서 반복문을 돌렸을 때 나온다?라고 생각하면 된다.

더 깊이 들어가기 싫다!!!!!!!!! 수학 멈춰!!!!!!!!!!!!!!!!!

 

시간 복잡도의 표현중에서도 표기법이 다르다.

"빅-오 표기법, 오메가 표기법, 세타 표기법"이 있는데 차례로 최악, 최상, 평균이다.

 

퀵 소트랑 머지 소트는 시간 복잡도가 어떻게 되는 걸까?

정렬 종류	평균	최선	최악
퀵소트	$O(nlogn)$	$O(nlogn)$	$O(n^2)$
머지소트	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$

자 위의 표를 보면 최대한 시간 복잡도가 좋은 것을 사용해야 최고의 방법을 찾지 않을까 한다.

 

퀵 소트에 대해 자세히 알아보자!

 

퀵 소트는 pivot을 기준으로 두 개의 구역으로 나눠서 pivot의 정확한 위치를 알게 하는 것이 첫 번째 목표이다.

많은 요소가 존재할 때를 생각해보면 처음에는 pivot을 1개로 잡고 분리 진행한 후 pivot을 정확한 위치에 존재하게 한다.

그리고 두 개의 구역으로 존재한 각각의 구역에서 각각의 pivot을 잡고 그 두 개의 pivot을 정확한 위치에 존재하게 한다.

이 과정을 반복한다면 마지막엔 결국 n개의 구역에 있는 원소가 1개가 되는데 이때 정렬이 완료가 된다.

 

우리가 이 부분에서 확실히 구현 가능한 부분은 pivot의 위치를 고정한다. 그리고 거의 마지막 과정(즉, 5개 이하의 원소가 남았을 때)에서는 정렬시킬 수 있다.

우리가 생각해봐야 할 것은 두 개의 deque으로 구현해야 하기 때문에 구현 과정은 거의 2 개의 서브 노드가 독립적인 이진트리와 같은 형상으로 구현되어야 한다는 것이다.

 

작성하는 걸 까먹었다... ㅋㅋ

 

전체적으로 진행되는 방법에 대해서만 쓰겠다.

 

 

1. 입력인자를 받아 에러 체크를 한다.
2. 입력인자들을 deque a에 차곡차곡 쌓는다.
3. 정렬된 배열 sorted를 quick sort로 생성한다.
4. deque a의 size를 판단하고 5개 이하면 내가 작성한 로직대로 진행한다.
5. 5개 이상이면 a_to_b로 가서 pivot 2개를 생성한다.(이때 pivot을 잡는 방법은 정해진 size에서 sorted에서 3등분을 해서 2개를 잡는다.)
6. a_to_b에서는 큰 pivot보다 크거나 같을 때 a의 뒤로 보낸다.
7. 작은 pivot보다 작거나 같으면 b로 보낸다.
8. 큰 pivot보다 작지만 작은 pivot보다 크다면 b로 보낸뒤 뒤로 보낸다.
9. 다 했다면 a, b에서 뒤로 보냈던 인자들을 복구한다.
10. 그리고 a_to_b, b_to_a, b_to_a로 선언한다.
11. b_to_a는 a_to_b와 같이 pivot을 2개 생성한다.
12. 작은 pivot보다 작거나 같으면 b의 뒤로 보낸다.
13. 큰 pivot보다 크다면 a로 보내고 뒤로 보낸다.
14. 작은 pivot보다 크고 큰 pivot보다 작거나 같으면 a로 보낸다.
15. a_to_b로 보낸다.
16. 다했다면 a, b에서 뒤로 보냈던 인자들을 복구한다.
17. a_to_b, b_to_a를 선언한다.
18. 이때 a_to_b와 b_to_a에서 size가 3개 이하라면 내가 따로 작성한 로직대로 진행하도록 한다.

이것이 끝이다.

여기서 조금 주의해야 할 것은 Error의 출력은 표준에러로 출력해야 한다는 점이다.

그리고 우리가 생각해봐야할 것은 rr, ss, rrr의 사용은 기본이지만 연속해서 나오는 명령어들이라는 것이다.

예를 들어 sa이후 sa가 나온다면 굳이 표시하지 않아도 된다. 이런 경우를 생각해봤을 때, 나는 내 로직에서 나오는 명령어들에서 r이후 rr의 명령어가 가장 많이 나오는 것으로 분석했고 ra 이후 rra가 나오거나 rb 이후 rrb가 나오는 경우에 명령어를 생략하기로 했다.

---

3.bonus

 

bonus는 제공하는 checker의 작성이다.

사실 checker의 로직에서는 특별히 사용될 함수는 read뿐이다.

즉, 우리가 push_swap에서 사용했던 함수를 조금 수정하고 get_next_line를 가져와서 사용하면 되는 것인다.

이번에 Norm의 버전이 바뀌어서 새로 작성하기로 했다.

시험에서의 get_nest_line과 유사하게 표준입력(fd=0)으로 받고 종료되었다면 끝내고 정렬이 되었는지 확인하는 것이다.

표준입력으로 받고 개행문자(\n)로 받았다면 그 이전까지 보내준다. 그리고 명령어들을 확인하고 수행해준다. 명령어중에 속한것이 없다면 Error를 표준에러로 출력한다.

끄읕~~~~~~~~~!