42Seoul - Push_swap

 

 

이번 과제는 Push_Swap이라는 과제를 진행하였습니다.

알고리즘에 약한 저로써는 처음에 많이 힘들었지만 과제를 하면서 많이 배운 것 같습니다.

퀵 소트, 시간복잡도, 최적화하기 등등 좋은 스킬들을 많이 얻었습니다.

그럼 Push_Swap의 전체적인 진행과정에 대해서 설명드리겠습니다.

 

❗ 과제 목표

2개의 Stack A(중복되지 않는 양수, 음수인 난수들), B(빈 스택)를 이용하여 A Stack을 오름차순으로 정렬하는 것.

 

🔑 허용 함수

write, read, malloc, free, exit만 사용할 수 있습니다.

 

🧲 허용 액션

sa(swap a)

스택 A의 가장 위의 두 원소를 바꾸는 동작.

sb(swap b)

스택 B의 가장 위의 두 원소를 바꾸는 동작.

ss(swap a and swap b)

위의 sa,sb를 동시에 실행시키는 동작.

pa(push a)

스택 B의 가장 위 원소를 가져와 스택 A의 맨 위에 놓는 동작. 스택 B가 비었을 경우는 동작X.

pb(push b)

스택 A의 가장 위 원소를 가져와 스택 B의 맨 위에 놓는 동작. 스택 A가 비었을 경우는 동작X.

ra(rotate a)

스택 A의 모든 원소를 위로 한 칸 씩 이동한 후, 첫 번째 원소는 제일 밑으로 이동.

rb(rotate b)

스택 B의 모든 원소를 위로 한 칸 씩 이동한 후, 첫 번째 원소는 제일 밑으로 이동.

rr(rotate a and rotate b)

ra와 rb를 동시에 동작.

rra(reverse rotate a)

스택 A의 모든 원소들을 아래로 1씩 이동한 후, 제일 밑의 원소를 제일 위로 이동.

rrb(reverse rotate b)

스택 B의 모든 원소들을 아래로 1씩 이동한 후, 제일 밑의 원소를 제일 위로 이동.

rrr(reverse rotate a and reverse rotate b)

rra, rrb를 동시에 실행시키는 동작.

 

 

🧭 유의 사항

입력을 받을 때 처음 입력 받은 숫자가 제일 위에 위치해야합니다.

프로그램은 가장 작은 명령어로 Stack A를 정렬 할 수 있어야합니다.

명령어들은 '\n'로 구분합니다.

에러의 경우는 "Error" + '\n'을 출력해야합니다.

에러의 경우에는, Error와 줄바꿈을 표준 에러에 출력해야 합니다. 에러는 다음 예시들을 포함합니다.

일부 인자가 정수가 아니거나, 정수 범위를 초과하거나, 중복이 있는 경우입니다.

 

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

<Error>

숫자가 아닌 것으로 구성되어있는 경우 : Error출력

같은 인자가 들어가있는 경우 : Error출력

인자가 int범위내가 아닌 경우 : Error출력

인자가 안 들어오는 경우 : 아무것도 출력하면 안됨.

인자가 순서대로 들어오는 경우 : 아무것도 출력하면 안됨.

 

 

자 이제 위의 내용들을 확인하셨다면 제가 어떻게 위의 문제들을 해결해 나갔는지 설명드리겠습니다.

 

이것을 어떻게 만들까요? 일단은 Stack이라는 자료구조를 만들어야합니다.

Stack은 양방향 링크드리스트로 구현하면됩니다. 링크드리스트의 특징은 링크를 참조해주세요.

왜 링크드리스트로 해야할까요? 일단 그냥 배열로 했을 경우에는 엄청나게 비효율적입니다.

예를 들면 위의 sa,sb,pb,pa.... 기능들을 실행하는데 원소들을 바꿔줘야합니다.

근데 한 개의 원소가 빠질 경우 배열 같은 경우는 모든 원소들이 이동해야합니다.

그러나 양방향 링크드리스트는 next가 가리키는 노드만 바꿔주고 서로 연결해주면 끝입니다.

물론 단점은 중간 값들을 조회하는데 어렵습니다.

그러나 그런 기능은 현재 쓰지 않으므로 양방향 링크드리스트가 가장 적당하다고 생각합니다.

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

typedef struct s_stack
{
	int	size;
	t_node	*top;
	t_node	*bottom;
}		t_stack;

이제 자료구조를 정했으니 알고리즘을 선택해야합니다.

 

알고리즘 순서

Stack A에서 제일 작은 숫자를 찾습니다.

Stack A의 제일 위로 찾은 숫자를 올립니다.

Stack B로 옮깁니다.

Stack A가 비워질때까지 1~3번과정을 반복합니다.

Stack B에 담겨진 숫자들을 차례로 Stack A로 옮깁니다.

 

그러나 이러한 방식은 정렬이 가능하지만 비효율적입니다. 어떻게해야 더 효율적일까요?

바로 "퀵 소트(Quick sort)"방식을 이용하는 것입니다. 퀵 소트 알고리즘에 대해 알아보겠습니다.

일단 피벗이라는 개념을 알아야합니다.

피벗은 기준을 뜻하면서 이것을 기준으로 왼쪽 요소들은 피벗보다 작은 수, 오른쪽 요소들으 피벗보다 큰 수를 뜻합니다.

이 피벗이 프로그램의 성능을 결정하게됩니다. 크게 퀵 소트방식은 세 가지로 나뉩니다.

 

분할

피벗을 기준으로 2개의 부분 배열로 분할합니다.

정복

부분 배열을 정렬합니다. 부분 배열이 원하는 만큼 작지 않으면 순환 호출을 합니다.

결합

정렬된 부분 배열들을 하나의 배열에 병합합니다.

 

그럼 스택 A,B를 가지고있는 저희는 어떻게 해야할까요? 스택 A에서 적당한 피봇을 설정해줍니다.

그 다음은 만약 스택 A의 제일 위 숫자가 피봇보다 작으면 스택B(PB)로

스택 A제일 위 숫자가 피봇보다 크면 스택 A의 제일 밑으로(RA)이동시켜 분리시킵니다.

그러나 위의 알고리즘은 평균 NlogN의 복잡도를 가지고 최악은 N^2의 복잡도를 가지게 됩니다.

그리고 평가지의 통과기준에 부합하지 않은 방식입니다. 그럼 어떻게 해야할까요?

바로 "더블 피봇"을 이용합니다. 2개의 피봇을 설정하여 3개의 구간으로 나눠 정렬합니다.

이 방법은 링크를 참고하였습니다. 더블 피봇방식으로 20개의 원소를 정렬하는 경우를 그림으로 표현해봤습니다.

20개 이상은 원소를 해야 b_to_a()재귀함수가 적용되게 됩니다.

 

위의 그림은 꼭 손으로 한번 그려보시길 추천드립니다. 3번 정도 그리고나니 완전히 이해했습니다.

재귀함수가 많이 쓰이기 때문에 눈으로하면 많이 헷갈리게 됩니다.

자세한 동작에 대해서는 위의 42PUSH_SWAP가이드 링크를 참고하시기 바랍니다.

이제 여기까지 오셨으면 거의 모든 작업을 끝냈습니다. 이제 대망의 최적화만 해주면 끝납니다.

위의 상황에서 프로그램을 돌려보면 5개와 100개의 인자를 넣었을 경우 에러가나게 됩니다.

그래서 저는 5개 부분은 아예 함수를 만들어 따로 처리해줬고 100개 rrr명령과 위에서 보시듯이

처음에 a스택에 되돌리기를 하는 것은 의미가 없습니다. B_TO_A가 한 번은 실행되어야 그 때부터

기능을 하기때문에 B_TO_A를 한번도 안 들어갔을 경우에는 b스택만 되돌리기를 하도록 하였습니다.

 

ARG 5개 처리

void	arg_five(t_stack *a, t_stack *b)
{
	int	pb;
	int	mid;

	pb = 0;
	mid = get_mid_value(a->top);
	while (1)
	{
		if (a->top->value < mid)
		{
			push(a, b, 'B');
			pb++;
		}
		else
			one_stack_rotate(a, 'A');
		if (pb == 2)
			break ;
	}
	three_a(a);
	two(a, b, 'B');
}

5개의 인자가 있을 경우에는 중간 값을 구해 A스택에 3개 B스택에 2개를 각각 나누어 정렬하고

그 후 다시 B스택에 2개를 A스택으로 보내게하는 알고리즘을 구성하였습니다.

 

되돌리기 명령 최소화

우리는 더블 피봇을 사용하기 때문에 되돌리기 기능이 따로 필요했습니다.

그러나 처음에 A_TO_B를 들어가서 스택B로 보내고 제일 숫자가 큰 그룹은 A스택에 남아있습니다.

ra명령을 사용해 뒤로 넘겨지는데 분할이 다 끝나고 나서 되돌리기 기능을 수행하면 전 후 상태가

똑같은 모습을 보실 수 있습니다. 그리고 이 명령은 숫자가 크면클수록 더 비효율적이기 때문에

B_TO_A함수에 들어가기 전까지는 스택 B만 되돌리기를 하도록했습니다.

res_cnt변수를 줘서 B_TO_A에 들어가면 무조건 더해주는 방향으로 하였습니다.

A_TO_B의 되돌리기에서는 res_cnt를 인식하여 0이상이면 무조건 rrr,rra,rrb를 수행하도록 했습니다.

 

 

이렇게 더블 피봇과 최적화하기를 통하여 평가표내의 통과 기준을 통과하였습니다.

 

 

💵 Bonus

체커 프로그램을 직접 구현하는 과제입니다.

인수가 주어지지 않으면 검사기가 중지되고 아무것도 표시하지 않습니다.

Checker는 표준입력을 기다렸다가 표준입력을 읽고  입력에따라 정렬하게 됩니다.

정렬이 잘 된 경우는 "OK\n", 정렬이 잘 되지 않았을 경우는 "KO\n"를 출력해야합니다.

위의 Push_Swap프로그램과 매우 비슷합니다.

다른 점은 명령에 따라서 정렬을 하고 sa,ss..등의 출력은 안해도 되는 것입니다.

그리고 파이프라인으로 앞의 명령들을 받아올때는 GNL을 이용하여 "\n"기준으로 명령을 받아와 수행합니다.

거의 Push_Swap을 복사한 느낌이라 위의 설명을 이해하셨으면 쉽게 구성할 수 있을 것이라 생각합니다.

 

이렇게 Push_Swap과제를 진행해봤습니다.

물론 처음에는 문제를 이해하는데만 2일 정도 걸렸던 것 같습니다.

특히 알고리즘 부분이 재귀함수가 많은 탓에 이해하기가 힘들었습니다.

그 때 카뎃분이 직접 손으로 2번 정도 그려보면 알고리즘이 이해가 쉬울 것이라고 말해줬습니다.

그래서 손으로 직접 20개를 정렬해봤습니다. 2시간 정도 걸렸던 것 같습니다.

그렇게하고 나니 정말로 이해가 빠르게되었습니다. 더블 피봇이 어려우신 분들이라면 꼭 추천드립니다.

긴 글 읽어주셔서 감사합니다.