1.무엇을 하는 과제인가?
Stack A와 B가 있다고 가정하고, 최초에 Stack A에 숫자를 넣으면,
Stack A와 Stack B를 이용하여 Stack A에 "오름차순"으로 정렬을 하면 마무리 되는 과제이다.
횟수를 <가장 적게> 정렬하는 것이 이 과제의 포인트다.
2.주어진 명령어는 무엇일까?
- 스택의 "윗 부분"만 이동이나 바꾸기가 되고, 나머지는 각각의 스택을 돌리는 식으로 작동을 한다.(아래 그림 참조)
: 이 스택은 기존에 우리가 알고 있는 스택에서 조금 다르다고 생각하면 되고 컨셉은 스택과 비슷하다.
- Swap(sa, sb) : 각각 스택의 상단 2개의 위치를 바꾼다
- Push(pa, pb) : pa는 b의 최 상단의 값을 a의 최 상단으로 옮기는 것, pb는 그 반대
- Rotate(ra, rb) : 스택의 탑에 있는 값을 최 하단으로 한칸 내린다(돌린다고 생각하면 된다.)
: 예를 들어 (top) 5 / 10 / 30이었다면 (top) 10 / 30 / 5 순으로 바꾼다. - Reverse rotate(rra, rrb) : rotate의 반대방향으로 돌린다. 스택의 최 하단을 최 상단으로 한칸 올린다.
: 예를 들어 (top) 5 / 10 / 30 이었다면 (top) 30 / 5 / 10 순으로 바꾼다. - ss,rr,rrr은 각각 swap, rotate, rerotate를 a, b 각각 동시에 실행해주는 것을 말한다.
3.그래서 정렬을 어떻게 해야 할까?
-
다른 분들도 비슷하게 알고리즘을 만들었지만, 나의 경우는 들어온 숫자들을 크기별로 3개의 덩어리로 나누고 그게 또 크다면 다시 3개의 덩어리로 나누고 계속적으로 나누어 덩어리 내의 갯수가 3개 이하가 나올때까지 반복하는 작업을 한다.
: 3개나 나올때까지 나누는 이유는 3개가 되어야 정렬하기 수월해지기 때문이다. -
이렇게 하는 방법은 quick sort와 유사하다.
: 하지만 다른 것은 들어온 수를 미리 정렬을 한 뒤에 거기에서 1/3지점의 값, 2/3지점의 값을 미리 확인하고 3덩어리로 나눠준다.(이 과제는 시간 복잡도를 고려하는 과제가 아니라는 것을 알아야 한다. 물론 시간 복잡도가 좋으면 당연히 좋다, 이 과제는 시간 복잡도 보다 명령어의 횟수를 적게 하는 것이 목표이다.)
1.A에 있는 큰 덩어리를 미리 정렬해서 얻은 피벗(1/3지점의 값, 2/3지점의 값)의 기준으로 나눈다.(1번 그림)
: 그렇게 하면 1/3지점의 값보다 작은 값은 [1], 1/3~2/3지점의 구간은 [2], 2/3보다 큰 구간은 [3]이 된다.
: 예를 들면 1,2,3,4,5,6,7,8,9가 A스택에 들어왔으면
[1]의 구간은 1,2,3, [2]의 구간은 4,5,6 [3]의 구간은 7,8,9가 된다고 생각하면 된다.
: 위처럼 A에 [3] B에 [2][1]순서로 둔 것은 이 순서로 다시 a로 넘기면 오름차순의 형태이기 때문이다.
2.나눴는데도 [3]의 갯수가 많다면 또 1을 반복한다.(2번 그림)
3.[3]을 쪼갠 [3_3](3을 쪼갰는데 거기에서 또 가장 큰 영역)이 3개 이하면 정렬을 해준다.
4.3_3이 완료되었으면 b스택을 정리한다. (3번 그림)
: b스택을 나눌 때에는 정리된
[3_3]의 위쪽에 [3_2_3](3_2중 가장 큰 영역),
[3_3]의 아래쪽에 [3_2_2](3_2중 중간 영역),
b쪽에 [3_2_1](3_2중 가장 작은 영역)을 둔다.
만약 [3_2_3]영역이 정렬이 다 되면 [3_2_2]를 올려준다!
5.나누다 보면 다양한 케이스들이 발생되는데 (4번 그림)을 보면 [3_2_2]를 올려주려고 하는데
알고보니 b쪽에 아직 정리 되지 않은 [3_2_3]이 남아있는 경우가 발생이 된다.
: 이를 방지 하기 위해 [3_2_2]같은 대상들을 올려주기 전에 b쪽에 [3_2_2]이 있는 수보다 큰 수가 있으면 b쪽부터 정리를 하게끔 알고리즘을 짜두었다. 이는 간단하게 3_2_2의 가장 뒷수와 b스택의 상단을 비교만 하면 끝나는 일이다.
6.추가로 3개가 들어오는 케이스와 5개가 들어오는 케이스는 약간 하드 코딩을 해주었다.
: 3개는 그냥 하드코딩을 하면 된다.(쉽다)
: 5개의 경우 먼저 정렬을 하여 가장 중앙의 수를 찾은 후에 그 수보다 작은 수 두개를 b쪽으로 보내버리면 a쪽에 3개가 남게 되는데, 이때부터는 a에 있는 대상은 3개가 있는 것과 똑같이 생각을 하면 된다.
그 후에 3개 정렬했던 알고리즘을 적용하면 a쪽이 정리가 되고, 나머지 b에 남아있는 수를 처리해주면 간단히 처리가 된다.
7.이렇게 해서 나온 대상들을 나의경우는 하나하나 버퍼에 담아 주었고, 정렬이 다 끝나게 되면 이를 알고리즘 최적화 해주는 코드를 따로 해주었다.
8.알고리즘을 완료하게 되면 각각 수행하는 함수들은 각각 독립적이기 때문에 서로가 어떻게 명령어를 냈는지 알수가 없다. 하지만 나온 명령어들을 보면 우리는 최적화 할 수 있는 포인트들을 찾을수가 있다.
1) 예를들면 sa, sb는 ss로 ra, rb는 rr로 rra,rrb는 rrr로 명령어를 바꿀수 있고 2개 > 1개의 효과를 낳는다.
2) 추가로 ra,rra가 연달아 나온다면 돌리고 반대로 돌리고를 할 필요가 없어서 아예 삭제를 해주면 된다.
3) 1)의 경우 ra rb만 rr로 가능한것이 아니다. 예를 들어 ra rr rr rb가 있다면 이것도 rr rr rr로 바꿀수가 있다.
: 추가로 최적화 할 수 있는 포인트들이 있었지만 이 정도로만 해두었다.
9.이 알고리즘의 경우 최종적으로 아래와 같은 횟수가 나왔다.
case 3개 : 0~2개
case 5개 : 10개 이하
case 100개 : 680개 이하
case 500개 : 4600개 이하
4. 과제중 힘들었던 내용들
: 과제를 하면서 힘들었던 순간이나 헤맸던 순간을 적어놓았다.
1) 가장 큰 문제는 int malloc을 해주었는데 while문을 통과하기전에 i = size로 해두고 a[i] = 0 초기화를 한 사태가 있었다… 없는 곳에 접근을 한 셈이다.
: 예를 들어 a[4]까지만 초기화를 시켜줘야하는데 a[5]를 초기화 시켜주어서 프로그램이 돌때 다른 메모리를 접근해 버리는 상황이 나타났다. 가장 기초적인 것을 실수하는 바람에 모든 것이 삽질이 되었고 덕분에 1주일 이상은 날렸다.
: 하지만 이 사태로 인해서 기본이 얼마나 중요한 것인지 깨달은 계기가 되었다.
2) 상위의 스코프에서 현재 주소를 사용하는데 free를 해주어 문제가 발생된 상황
: 상위의 스코프에서 free해주는 부분의 주소를 사용하는 부분이 있었다. 이 부분에 대해서 아무것도 처리를 해주지 않아서 상위 스코프는 free된 곳을 계속 접근을 하여 프로그램이 이상하게 되었다. 향후에도 이 부분을 조심해서 접근해야 될듯.
: 상위 스코프에서 현재의 메모리를 사용한다면 꼭 주의하여 free를 해주어야 한다!
3)정렬이 되었는지 확인하는 부분을 적절하게 배치하지 못하여 예외상황이 많이 발생하였다.
4)leak잡기
: split으로 들어온 대상들을 분할 해준다음에 쓴 메모리를 해제해줘야하는데, 2중 포인터 인것을 착각해서 leak가 발생하였다. 이로 인하여 leak를 잡는데 시간을 많이 소모해주었다. 2중포인터이기 때문에 안에 있는 대상들도 해제를 따로 해주고 밖에 있는 대상도 해줘야한다.
: 필요 없는 부분들이 malloc해제되는지 체크할것.
: 한번은 다른곳에 char *을 말록 할당을 한뒤에 다시 또 할당을 해서 메모리 누수가 발생한 적도 있었다.
5.회고
-
약 3주간 과제를 하였는데 나름 정말 열심히 하였다. 3주내내 몰입해서 과제를 수행했던 것 같다. 중간에 삽질을 정말 많이 하였지만 그것으로 인해서 기본이 왜 중요한지에 대해서 많이 생각하게 되었고, 예외처리를 정말 많이 한 것 같다.
-
평가를 진행하려고 그림도 나름 그리고 준비를 하였지만 생각보다 처음 보신 분들에게 설명을 해주는 것이 쉽지는 않았다. 다음 평가때는 더 쉽게 설명을 해보도록 해야겠다.
-
이론 공부를 많이 해보려고 했으나, 생각보다 많이 하지는 못하였다. 알고리즘 책은 향후에 다시 빌려서 다시 공부를 해야겠다.
-
오랜만에 피신때의 느낌이 들어서 좋기도 했고, 힘들긴 했지만 재밌었던 과제였었다. 많은 아쉬움과 애정이 남는 과제로 남을 것 같다.
