📕PUSH_SWAP
push_swap은 스택 2개를 이용해서 주어진 숫자들을 정렬하는 프로젝트이다.
시간복잡도를 고려해야하는 다른 알고리즘 문제와 다르게, 주어진 명령어를 최대한 적게 사용해서 정렬해야한다.
📚준비 과정
minitalk을 끝낸 뒤,
다음 과제를 push_swap으로 정하게 되었다.
먼저 나는 어떤 알고리즘으로 배열을 시킬지 고민을 했다.
퀵 소트, 병합 정렬 등 여러 효율적인 정렬 알고리즘이 있었지만 이 과제의 목적은 '빠르게' 정렬시키는 것이 아닌 sa, ra 등 '주어진 명령어를 최소한으로 사용하여' 정렬하는 것임으로 그리디 알고리즘이 적합하다고 생각해 그리디로 구현하게 되었다.
퀵 정렬도 고민해 보았지만 '최소한'의 명령어 사용이 보장될 것 같진 않았다. 그리고 나서 이를 어떻게 구현할지 고민을 꽤 오래 했던 것 같다. 고민한 내용들은 다음과 같다.
1. 스택
연결리스트? 배열?
2. 연결리스트라면 어떤 구조?
단일? 이중?
3. 파싱은 어떻게?
"32 1" 3 등과 같이 인자가 들어오면 어떻게 처리할 것인가📖 PUSH_SWAP 1일 차
원형 연결리스트로 스택 구현
일단 연결리스트로 스택을 구현했다.
typedef struct s_node
{
long long content;
struct s_node *next;
struct s_node *prev;
int flag;
} t_node;
typedef struct s_stack
{
int size;
t_node *top;
t_node *bottom;
} t_stack;
node를 만들고 그 노트의 맨 앞과 맨 뒤를 가지고 있는 스택이라는 구조체를 만들어 관리해 줬다.
여기서 실제로 노드의 맨 앞과 맨 뒤를 연결시켜 원형 연결리스트로 구현했는데 이렇게 했을 때의 장점은 예를 들어
a 스택에서 제일 큰 값 3개만 남겨놓고 다 b스택으로 push 해줄 때
별다른 명령어 없이도 마지막 노드에서 바로 첫 번째 노드로 넘어가기 때문에 관리가 쉽다.
단점도 있다. 연결리스트의 경우 리스트 전체의 노드를 살펴보는 반복문에 node == 0 일 경우가 마지막 노드까지 온 것이기 때문에 이를 탈출 조건으로 설정하면 되지만, 원형 연결리스트는 마지막 노드에서 next는 맨 처음 노드이기 때문에 위와 같이 설정이 불가능하다.
때문에 나는 스택 구조체에 size를 추가해서 이 단점을 해결했다.
그런데 이렇게 하면
int i;
i = 0;을 써줘야하기 때문에 2줄이 추가된다는 단점이 있다.
sa, ra, pa 등 명령어 구현
그다음에는 프로젝트에 주어진 명령어들을 구현했다.
stack 구조체의 주소값을 넘겨주는 식으로 다른 함수 안에서 실제 값이 변하도록 했다.
void sa(t_stack *st, int flag);
void sb(t_stack *st, int flag);
void ss(t_stack *a, t_stack *b);
void pa(t_stack *a, t_stack *b);
void pb(t_stack *a, t_stack *b);
void ra(t_stack *a, int flag);
void rb(t_stack *b, int flag);
void rrb(t_stack *b, int flag);
void rra(t_stack *a, int flag);
void r(t_stack *a, t_stack *b, int flag);
그리디 알고리즘 내에서 b 스택의 어떤 값을 a로 넘길 때
얼마나 명령어가 사용되는지 보는 과정이 있는데
이 과정에서도 위의 명령어가 사용되지만
그때에는 터미널에 실제로 sa가 출력이 되면 안 되기 때문에
flag를 설정해 print를 할지 말지 결정하도록 했다.
📖 2일차
PUSH_SWAP 파싱에 대한 고민
“10 12” 가 들어왔을 때 10 12로 나눠서 스택에 넣어야 할까?
나는 결론적으로 에러로 처리했다.
만약 10t12가 들어온다면 어떻게 해야할까?
주어진 프로젝트 파일에 의하면 error를 띄우고 종료하도록 처리를 해야한다.
인자로 integer를 받으라고 했기 때문이다.
나는 "10 12"와 "10t12"가 다를 바 없다고 생각해 동일하게 처리했다.
이렇게 처리했을 때 가장 문제가 되는 점은
A=“1 2 3 4”; ./push_swap $A이런식으로 인자를 받아오는 예시가 프로젝트에 있다는 것이다.
디펜스방법
bash 에서는 저렇게 입력해도 인자가
1, 2, 3, 4로 나눠서 들어오게 된다.
(zsh에서는 av[1] 에 “1 2 3 4”로 들어온다)
그리고 프로젝트에 예시의 '$'를 보면 bash에서 실행했다는 것을 알 수 있다.
정렬해야 하는 숫자가 2개, 3개일 경우 하드 코딩
2개일 경우, 3개일 떄는 경우의 수가 많지 않아 하드 코딩을 해줬다.
간단한 과정이니 별다른 설명없이 넘어가도록 하겠다.
checker 제작
체커는 만들기 어렵지 않았다.
이미 pa, sa 등 명령어는 다 구현했고
파싱 부분도 처리했기 때문에 코드를 그대로 가져와 명령어를 입력받을 수 있도록 만들어주면 된다.
ex) ./checker 3 2 1 이렇게 실행했을 때,
sa
rra
를 입력하고 ctrl + D 를 누르면
"OK"가 출력되어야 한다.
정렬이 제대로 안될 경우는 "KO",
인자로 이상한 값이 들어왔을 때는 표준 에러로 "Error"를 출력하면 된다.
✏️2일차에 완성 시킨 것
checker
3개 들어왔을 때 하드코딩
예외처리
이제 절반은 끝낸 느낌이다.
4개 이상의 숫자가 들어왔을 때 정렬시킬 그리디 알고리즘만 넣으면 끝난다!!
📖 3일차 push_swap 그리디
이제는 스택 구현, 명령어 구현, checker까지 끝냈고
정말로 알고리즘을 생각해볼 때다.
내가 일단 공부한 알고리즘은 2가지이다.
그리디와 퀵소트
결국 "그리디"로 정했다.
그리디 알고리즘은 항상 당장 최선의 경우를 선택하는 알고리즘이다.
자세한건 구글에 검색하면 나오니 넘기겠다.
그러면 정렬에 그리디 알고리즘이 적합한가?
시간 복잡도를 고려한다면 정렬에는 적절하지 않다.
하지만 본 과제는 시간이 아닌 “명령어의 최소 사용”이 목적임으로
항상 최선의 경우를 선택하는 그리디가 적절하다고 생각했다.
내가 짠 전체적인 코드의 알고리즘은 다음과 같다.
ex) ./push_swap 11 9 7 10 2 5 가 들어왔을 때
1.스택 A를 만든다.
11
9
7
10
2
5
ㅡ
A2. 인덱싱을 한다.
6
4
3
5
1
2
ㅡ
A인덱싱을 하는 이유
최대값을 나눈 숫자가 실제 배열의 1/n 지점이 되기 때문에 pivot을 설정하기 좋다.
최적의 pivot 설정을 위해 미리 정렬을 시키는 방식으로 푸는 분들도 계셨는데
그럴 필요 없이 최적의 pivot 설정이 가능하다.
그리고 맨 마지막에 제일 작은 숫자를 제일 위로 올리는 과정이 있는데,
그 때 다른 것을 신경 쓸 필요 없이 무조건 제일 작은 수인 1을 스택의 맨 위로 올리면 되서 편하다.
인덱싱을 해도 되는 이유
처음에 들어온 수 (예시에서는 9 7 10 2 5)를 다시 사용하지 않아도 무관하다. 이 프로그램에선 명령어만 출력하면 된다.
3. 제일 큰 숫자 3개만 남기고 스택 B로 넘긴다
6 2
4 1
5 3
ㅡ ㅡ
A B3개를 남기는 이유
- 스택 B에서 다시 A로 넘기는 과정에서 기준 값이 필요
- 숫자 3개를 정렬시키는 것은 하드 코딩을 앞서 했기 때문
최소 명령어 사용으로 정렬 가능하다. + 전에 썼던 코드 활용
4. A 스택에 있는 3숫자를 정렬한다. (3개 숫자는 전에 하드 코딩)
4 2
5 1
6 3
ㅡ ㅡ
A B5. B스택에서 최소로 명령어를 사용해 넘길 수 있는 숫자를 찾는다.
B 스택 전체를 돌며
A의 적당한 위치로 해당 숫자를 옮길 때 사용하는 명령어의 개수를 측정해 최소로 사용하는 숫자를 찾는다.
이 때 결국 pa는 B의 top에서 A의 top으로 이동시킨다는 것을 생각하면 쉽다.
= B스택에서 옮길 수를 B스택의 top으로 옮기고,
그 수의 다음으로 와야 하는 수를 A스택 안에서 찾아
A스택의 top으로 옮긴다. (이때 사용해야하는 명령어 수 측정)
위의 상황에서 이어 예시를 들면
B스택에 있는 2 1 3을 A로 넘길 때 써야하는 명령어 수를 측정한다.
2의 경우
4 2
5 1
6 3
ㅡ ㅡ
A B
그대로 pa해주면 됨으로 "1"
1의 경우
4 1
5 3
6 2
ㅡ ㅡ
A Brb, pa를 해야함으로 "2"
3의 경우도 마찬가지로 rra를 해줘야하기 때문에 "2"
6. 그 숫자를 스택 A로 넘긴다.
위 상황에서 2가 최소로 넘길 수 있다는 것을 알아냈기 때문에
2를 넘겨준다.
2
4
5 1
6 3
ㅡ ㅡ
A B7. B스택의 사이즈가 0이 될 때까지 5~6과정을 반복한다.
2
4
5 1
6 3
ㅡ ㅡ
A B1은 바로 넘기면 되지만
3은 숫자 3을 b의 top으로,
A스택에서 3의 다음 숫자가 4이기 때문에 ra를 해줘야하기 때문에 더 적은 명령어를 사용하는 1을 넘기게 된다.
1
2
4
5
6 3
ㅡ ㅡ
A B마지막으로 3을 넘기면 아래와 같은 상황이 된다.
3
4
5
6
1
2
ㅡ ㅡ
A B8. A스택의 top이 1이 되도록 한다.
위의 예시 상황에서는 ra보다 rra가 더 빠르므로
(원하는 수가 a size의 1/2 지점보다 아래에 있음)
rra
rra
를 해주면 정렬이 끝나게 된다.
1
2
3
4
5
6
ㅡ ㅡ
A B
여기까지가 기본적인 알고리즘이고 이제 최적화만 해주면 된다.
나는 다음과 같은 최적화를 해줬다.
⚙️ 최적화
1. r, rr 구분
top으로 옮기고 싶은 수가
해당 스택의 1 / 2 지점을 넘어가면 rra,
아니면 ra를 해줬다.
2. 청크 나누기
3의 과정에서 pivot을 설정해 청크를 나눠 B로 넘겨준다.
나는 전체 스택의 1/3 지점과 2/3 지점을 기준으로 (a size / 3, a size / 3 * 2)
pivot을 설정해 넘겨줬다.
청크를 2개로 나눌 수도 있고 그 이상으로 나눌 수도 있는데
어떤 경우가 제일 괜찮을지는 생각해보면 좋을 것 같다.
나는 3개로 나눴다.
3. ra, rb -> rr 로 바꾸기
ss, rr, rrr등 동시에 a, b스택에서 같은 동작을 하도록 하는 명령어를 사용해 줄일 수 있다.
그런데 나는 이건 처리를 따로 안해줬다.
쉽게 떠오를 만한 최적화는 여기까지...
나는 1, 2번 최적화만 해줬다.
📕 끝!
여기까지 진행했을 때 500개 기준
평균 4700개 정도의 명령어가 사용됐다.
만점 기준이 500개일 때 -> 명령어 5500개 임으로
널널하게 통과할 수 있다.
push swap 끝!!!
📚 이번 push_swap 과제를 하며 공부한 것들 목록
1. 여러 정렬 알고리즘 (퀵, 병합 등)
2. 시간 복잡도에 대한 이해
3. 그리디 알고리즘
4. C에서 동적할당 시 프로그램 종료 직전에 free를 명시적으로 해줘야 하는가?
-> mac등의 최신 os에서 안한다고 해서 당장 크게 문제될 건 없음
하지만 마찬가지로 명시적으로 해줘서 나쁠 것도 없음 (개인 선택의 문제 같다.)
free를 안해줬다고 무조건 leak은 아니라고 생각하게 되었다.
5. 메모리 leak 검사하는 방법
-> system("leaks push_swap");
6. 연결리스트 사용법
-> 이번 프로젝트에서 처음으로 제대로 연결리스트를 사용해봤다.
배열보다 사람이 이해하기 직관적이라는 장점이 있다.
7. atexit함수🗂️ push_swap 을 마무리 하며
처음 이 프로젝트를 시작할 때 사실 많이 막막했었다.
최소한의 명령어를 사용하라고 요구하는데 그냥 퀵 정렬같은 알고리즘을 쓰면 명령어 개수가 보장이 되려나?
어떻게 스택 2개에 그런 알고리즘을 정렬하지?
그리디를 정렬에 적용한다고?....
등 많은 고민을 했고 제대로 코드를 작성하기 시작하기 전 꽤 오랜 시간 고민 했던 기억이 난다.
하지만 때로는 고민만 하기 보다는 당장에 할 수 있는 부분들을 하는 것이 좋을 수 있겠다는 생각이 든다.
그렇게 할 수 있는 부분들을 채워나가다 보면
전혀 보이지 않던 길이 조금씩 보이기도 하는 것 같다.
여러모로 많이 배우고 발전할 수 있었던 프로젝트였고,
개인적으로 굉장히 재밌게 진행해서 만족스럽다.
끝!
