Push_Swap - Mandatory
PUSH_SWAP
Because Swap_push isn’t as natural
Swap_push라는 이름은 그다지 자연스럽지 않으니까요
Summary: This project will make you sort data on a stack, with a limited set of instructions, using the lowest possible number of actions. To succeed you’ll have to manipulate various types of algorithms and choose the one (of many) most appropriate solution for an optimized data sorting.
요약: 이번 과제에서는 스택에 있는 데이터를 한정된 명령어를 이용하여 최대한 적은 횟수 내에 정렬하는 것을 목표로 합니다. 성공하기 위해서는 다양한 정렬 알고리즘을 조작해 보고, 최적화된 데이터 정렬에 가장 적합한 알고리즘을 선택하여야 합니다.
The Push_swap project is a very simple and highly straightforward algorithm project: data must be sorted.
Push_swap 프로젝트는 아주 간단하고 꽤나 중요한 알고리즘 프로젝트입니다. 이 프로젝트에서는 데이터를 정렬하여야 합니다.
You have at your disposal a set of int values, 2 stacks and a set of instructions to manipulate both stacks.
과제에서는 정렬해야 하는 int 값들과 두 개의 스택, 그리고 이 스택을 조작하는 명령어 집합이 주어집니다.
Your goal ? Write a program in C called push_swap which calculates and displays on the standard output the smallest program using Push_swap instruction language that sorts the integer arguments received.
여러분의 목표는 C언어로 Push_swap이라는 프로그램을 작성하시는 겁니다. Push_swap 프로그램은 최소한의 Push_swap 명령어들을 이용하여 정수형 인자를 정렬하는 방법을 계산하고, 최종적으로 사용된 명령어들을 표준 출력해야 해요.
Easy?
쉬워보이죠?
We’ll see about that...
두고보세요...
개요
push_swap은 2 써클 과제 중 가장 어려운 과제에 속하는 것 같습니다. Libft와 Get_next_line에서 다룬 연결 리스트 공부만 열나게 했지, 수많은 해결 알고리즘을 접했지만 가장 직관적인 알고리즘으로 구현하다 보니 많이 얻어간 느낌은 없는 그런 과제였습니다.
최적의 명령어 수로 해결해 보았지만, 시간이 굉장히 오래 걸렸습니다. 평가를 많이 다녀서 공부를 많이 해야겠습니다. 통과하고 나니 개운한 느낌만 들고 다신 만나고 싶지 않은 과제군요.. 풀이가 마음에 들지 않은 적은 ft_printf이후 또 겪어 봅니다.
해당 과제에서 여러 자료 구조와 알고리즘을 수도 없이 찾아보실 것이고 적용하려고 시도할 겁니다. 과제의 구절을 인용하면 쉽지 않습니다. 두고 봐야 합니다.
목표
Writing a sorting algorithm is always a very important step in a developer’s journey. It is often the first encounter with the concept of complexity.
정렬 알고리즘을 작성하는 것은 개발자의 여정에서도 꽤나 중요한 비중을 차지하는 부분입니다. 대개 복잡도의 개념을 여기서 처음 마주하게 되거든요.
Sorting algorithms and their complexities are part of the classic questions discussed during job interviews. It’s probably a good time to look at these concepts because you’ll have to face them at one point.
정렬 알고리즘과 복잡도는 기업 면접에서 자주 질문하는 문항이기도 합니다. 언젠가는 마주할 내용이기 때문에, 이번 기회에 개념을 잘 다지는 것도 좋은 방법이겠지요.
The learning objectives of this project are rigor, use of C, and use of basic algorithms. Especially focusing on their complexity.
이번 과제의 목표는 엄격함, C언어의 사용과 기본적인 알고리즘의 사용입니다. 특히 복잡도에 대해 면밀히 살펴보세요.
Sorting values is simple. To sort them the fastest way possible is less simple, especially because from one integers configuration to another, the most efficient sorting algorithm can differ.
값을 정렬하는 건 꽤나 간단합니다만, 가능한 한 빠르게 정렬하는 것은 조금 복잡합니다. 어떤 정수 집합을 정렬하는지에 따라 최적의 알고리즘이 달라지거든요.
과제의 요구 조건을 살펴봅시다.
1. 스택 a에는 랜덤 개수의 정수가 존재하며, 값은 중복되지 않습니다. 스택 b는 비어있습니다.
2. 스택 a에 정수들을 오름차순으로 정렬하는 것이 목표입니다. 정렬 명령어는 sa, sb, ss, pa, pb, ra, rb, rr, rra, rrb, rrr를 사용할 수 있습니다.
3. 정렬하는데 소요되는 시간보다 사용한 명령어의 개수를 줄이는 것이 높은 점수를 받을 수 있습니다.
4. 정수와 중복 조건을 포함하여, 입력 인수가 잘못되었다고 판단하면 처리해 주어야 합니다.
5. 매개 변수가 지정되지 않은 경우, 프로그램은 프롬프트를 반환해야 합니다.
6. 복잡도의 개념을 묻고 있습니다.
7. 사용 가능한 외부 함수: read, write, malloc, free, exit, ft_printf
구현 전 사전 지식
1. 자료구조(스택)
2. 알고리즘 선택(복잡도)
3. exit
1. 자료구조
스택은 선입후출 자료구조로, 과제의 스택 a, b는 알고리즘에 등장하는 것과 달리 회전하고 1, 2번 자료를 섞을 수도 있습니다. 스택 a에 무작위로 있는 정수들을, 비어있는 스택 b와 명령어를 이용하여 다시 스택 a에 오름차순으로 정렬해야 합니다.
저는 양방향 순환 연결 리스트를 사용했습니다. 연결 리스트가 가장 익숙하고 사용할 함수들도 이전 과제에서 만들어 놨기 때문에 구현에 가장 적합하다고 생각했습니다. 정적 배열은 특정 인덱스에 가시적으로 접근하기 쉬워 보였으나, 명령어의 사용(특히 회전)이 어렵다고 판단해 사용하지 않았습니다.
구조체를 만들어서 값을 저장할 변수, 이전과 다음 구조체를 가리킬 포인터를 선언하여 양방향 연결 리스트를 구현했습니다.
2. 알고리즘 선택(복잡도)
자료구조를 선택해서 정렬 직전까지 구현하는 것은 오래 걸리지 않습니다. 이제 어떤 알고리즘으로 최소한의 명령어 정렬을 수행할 수 있는지 생각해 봐야 합니다. 자신이 선택한 자료구조에 원활하게 수행할 방법이면서, 이해하고 설명하기 적합한 알고리즘이 좋습니다.
복잡도의 개념은 평가를 위해 다져 놓읍시다. 시간 복잡도를 위해 알고리즘을 최적으로 구현하고 공간 복잡도를 위해 최적의 자료구조를 선택해 봅시다. 정해진 답이 있는 것은 아니므로 자신이 무얼 사용하고 있는지만 알고 있으면 된다고 생각합니다.
제가 사용한 방법은 그리디로, 가능한 경우를 모두 탐색해서 최소의 명령어가 나오면 그것을 수행하도록 했습니다. 또 ss, rr, rrr은 2개를 하나로 줄여주는 명령어이므로 자주 사용하면 좋습니다. 이러면 수행 시간은 오래 걸리지만 명령어를 적게 사용하여 정렬할 수 있습니다.
스택 a에 수를 오름차순으로 정렬해야 하는데, 스택 b에 수를 내림차순으로 정렬할 수 있다면 pa 명령어로 옮기기만 해도 자연스럽게 스택 a는 오름차순으로 정렬이 됩니다.
3. exit()
함수 원형: void exit(int status) - stdlib.h
exit 함수는 메모리를 해제하고 프로그램을 종료합니다. 그리고 운영체제에 인자값을 반환합니다. 메모리를 해제해 주기 때문에, 그동안 할당했던 메모리를 free 하지 않고 그냥 exit으로 끝내버리도록 코드를 작성하는 경우가 있습니다. 이는 좋지 못한 방법입니다. exit이 메모리 해제에 실패하는 경우가 존재하기 때문입니다.
코드 작성자의 실수가 아닌 예상치 못한 상황으로 컴퓨터가 그냥 해제를 못하는 경우가 있을 수 있습니다. 하지만 이는 잘 일어나지 않는 방법이므로 그리 고려할 필요가 없다고 할 수 있는데, 문제가 되는 부분은 코드 작성자의 실수로 exit 함수가 메모리 해제를 할 수 없다는 것입니다.
간단한 예시인데요, Get_next_line 과제에서 찾아볼 수 있습니다. 우리는 메모리를 해제할 때 free 함수의 인자로 포인터를 넘겨줍니다. 우리는 할당한 메모리를 포인터로 찾았습니다. 할당한 메모리를 가리키는 포인터가 다른 주소를 가리키도록 해버리면 할당 메모리를 다시 찾을 수가 없습니다. gnl과제에서 버퍼를 갱신할 때 임시 포인터를 사용한 이유입니다. 추측건데, exit은 포인터를 탐색하며 메모리를 해제하는 것 같습니다. 할당 메모리를 가리키는 포인터가 존재하지 않을 때 exit 함수가 해제에 실패한 경우를 찾을 수 있었습니다.
구현
code
char **input_check(int ac, char *av[])
{
char **str_array;
char *array_oneline;
skip_space_check_value(ac, av);
array_oneline = make_str(ac, av);
str_array = ft_split(array_oneline, ' ');
if (!check_integer(str_array) || !duplicate_check(str_array))
print_error();
return (str_array);
}프로그램 인수를 통해 입력값을 받습니다. 정확히 말하면 문자 배열을 받는 겁니다. input_check 함수는 문자 배열을 반환합니다. 그다음 atoi로 스택을 구성할 겁니다. 하지만, 입력값을 확인해야 합니다.
skip_space_check_value 함수는 빈 문자열을 확인합니다. 입력 예시로 ./push_swap "", ./push_swap " "와 같은 경우를 에러 처리합니다. 빈 입력, 공백 문자만 존재하는 입력을 처리합니다.
make_str 함수는 문자 배열을 하나의 문자열로 만듭니다. 입력된 인자는 공백 문자로 구분되기 때문에 split 함수가 잘 작동할 수 있도록 재구성하는겁니다. ./push_swap "1 2 3" 4 5 "6 7" 이렇게 입력이 되었다면 문자열이 "1 2 3456 7"로 만들어 질 것입니다. 따라서 strjoin을 사용하여 문자 배열을 문자열로 만들 때 공백을 일부러 하나 삽입합니다. 인자가 공백으로 구분되어 있다면, 공백이 몇 개이든 split이 구분자를 잘 제거해 줄 것입니다.
check_integer, duplicate_check 함수는 정수와 중복을 확인하고 에러처리 합니다. 정수의 범위를 넘어섰거나 중복된 수가 등장하면 처리합니다."1 2 3" 4 5 "6 7" 입력은 수가 7개지만 문자열은 4개입니다. make_str 함수로 하나의 문자열을 만들었고, 다시 split을 통해 잘라주었기 때문에 이젠 문자열과 인자의 개수가 동일합니다.
void make_stack(t_node **lst, char **str)
{
t_node *node;
while (*str != NULL)
{
node = lstnew(ft_atoi(*str));
lstadd_back(lst, node);
str++;
}
(*lst)->prev = lstlast(*lst);
lstlast(*lst)->next = *lst;
}이제 올바른 입력값임이 분명하므로 atoi를 사용하여 연결 리스트를 구성합니다. 문자 배열의 문자열을 atoi로 바꾸어 노드를 생성하고 연결을 해줍니다. 연결은 양방향으로 진행합니다. lstadd_back 함수에서 앞뒤로 연결됩니다. 마지막으로 맨 뒤와 맨 앞을 연결합니다.
Algorithm
예시로 구성된 a에서 b로 옮겨가며 내림차순으로 정렬을 시작하겠습니다.
묻고 따지지 말고 b에 2개를 그냥 옮깁니다. 이러면 b에서 최댓값과 최솟값이 정의됩니다. 그리고 a를 보는 것입니다. a에서 하나의 값이 b로 올 때 내림차순으로 정렬되려면 명령어를 몇 개로 최소 사용하게 될 것인지를 확인해야 합니다.
짚고 넘어가야 할 것은 스택이 양방향 순환 연결 리스트라는 것과 회전 치환입니다.
이 스택은 절대적인 시작 지점이 존재하지 않습니다. 무슨 말이냐 하면, b는 오름차순으로 보이지만, 내림차순으로 볼 수 있습니다. 2번째 노드부터 읽는다면 5 -> 2로 읽히기 때문입니다. 따라서 특정 노드부터 읽었을 때 내림차순으로 읽히기만 하면 내림차순 정렬로 판단할 수 있습니다. 최상단부터 읽을 필요가 없다는 뜻입니다.
회전 치환은 정회전과 역회전이 치환될 수 있다는 것입니다. r명령어는 rr명령어로도 사용할 수 있습니다. 10개의 노드가 존재하는 스택에서 정회전을 4번 하는 것은 역회전을 6번 하는 것과 동일한 결과를 보입니다. 따라서 스택을 회전해야 하는 상황일 때 어떤 회전 방향이 더 적은 명령어를 사용할 것인지 계산해야 합니다.
7: a의 탑 노드인 '7'이 이동된다고 생각해 봅시다. 그냥 '7'을 옮겨버리면 어디서부터 읽든 내림차순이 될 수 없습니다. 따라서 b를 조정해야 합니다. 최상단 노드를 '5'로 바꿔주고 '7'을 옮긴다면 '7 5 2'로 구성되어 내림차순이 가능합니다. 사용된 명령어(이후부터 비용이라 지칭합니다.)는 2개(rb 혹은 rrb + pb) 입니다.
1: a에서 '1'은 탑 노드가 아니기 때문에 '7'보다 비용을 하나 더 소모해야 합니다. ra로 '7'을 ra로 내려주어야 '1'이 최상단 노드가 되고 pb로 옮길 수 있기 때문입니다. 그런데 정작 '1'을 b로 옮기려면 b를 회전해야 합니다. 더 생각할 필요가 없습니다. 비용은 2를 넘을 것입니다.
6: a의 최상단인 '7'부터 최하단인 '8'까지 볼 때, 다음 노드를 고려할수록 비용은 1씩 추가됩니다. 이미 '7'은 비용 2를 기록했고 '1' 또한 비용 2를 넘었기 때문에 '6' 이후부터는 설명하지 않아도 됩니다.
다시 a의 모든 노드를 탐색하여 최소 비용을 계산합니다.
1: 명확합니다. 그냥 옮기면 내림차순 정렬이 됩니다. b에서 '1 7 5 2'로 보이지만 '7'부터 읽으면 됩니다. 비용은 1.
6: '7' 다음에 올 수밖에 없습니다. 따라서 '7'을 내리고 '6'을 옮겨야 합니다. 비용은 2. 다음 수들은 설명할 필요가 없습니다.
반복하면 이렇게 정렬 됩니다.
스택 a에 3개만 남기는 이유는 3개를 정렬할 때 경우의 수가 1 혹은 2개기 때문입니다.
이제 b에서 a로 옮기면서 오름차순으로 정렬될 수 있도록 합니다.
a to b 방식대로, b to a를 진행합니다.
code
void sort_algorithm(t_node **alst)
{
t_node *blst;
int idx;
blst = NULL;
if (lstsize(*alst) == 2)
swap_a(alst);
else
{
blst = setting_blst(alst);
alst = setting_alst(alst, &blst);
idx = find_idx(*alst, lst_min(*alst));
if (idx < lstsize(*alst) - idx)
{
while ((*alst)->value != lst_min(*alst))
rotate_a(alst);
}
else
{
while ((*alst)->value != lst_min(*alst))
rotate_reverse_a(alst);
}
}
}스택 b에 내림차순으로 정렬한 뒤, 스택 a에 옮겨 오름차순으로 정렬할 겁니다. 노드의 개수가 2개라면 swap 명령어로만 해결되므로 예외로 처리합니다.
setting_blst 함수는 a에서 노드 3개만 남겨두고 전부 b로 옮겨 내림차순 정렬합니다. 그다음 a로 옮기면서 오름차순 정렬합니다.
그리고 find_idx 함수에서 현재 최상단 노드가 무엇인지 확인한 다음, 정회전, 역회전 중 가장 적은 비용이 발생하는 회전을 진행합니다.
동료 평가
1. 입력값 처리를 어떻게 했는지 설명해야 합니다.
2. 사용한 자료구조와 알고리즘에 대해서 이해하고 설명해야 합니다.
마치며
과제가 많이 어렵지만, 동료평가 디펜스는 어려울 부분이 딱히 없습니다. 테스터와 비주얼라이져가 깃헙에 많이 있기 때문에 자신의 코드가 어떻게 작동하는지 확인하기 쉽습니다. 많이 찾아보시고 해결하시길 바랍니다. 보너스는 정말 간단하므로 따로 리뷰하지 않겠습니다.