22.04.28. push_swap - 정렬 알고리즘 최적화

 

이제 push_swap과제에서 남은 부분은  1. 최적화 2.정렬되었는지 확인-> 되어있으면 아무것도 출력 안하고 끝내기 3.리팩토링 이다.

 

정렬을 할 수 있는 프로그램이 되긴 했지만, 이번 과제의 중점은 "명령을 최소한으로 내려서" 정렬 하는 것에 있다.

따라서 정렬을 다 했다고 끝이 아니라, 과제에서 요구하는 수준 까지 최적화를 해야 한다.

일단 앞서 push_swap과제를 완료하신 동료 카뎃분들의 이야기를 들어보니, 다음과 같은 수준을 만족해야한다고 한다.

현재 50개의 input 값을 정렬한 내 알고리즘이 내린 명령어 수는 다음과 같다.

50개 인풋에 851개의 명령어를 썼다면, 100개의 input에서는 더한 비효율을 보일것으로 예상 된다..! 50개의 input을 더 추가해, 알고리즘을 돌려보니 1700개쯤으로 나오겠거니 했으나 2199라는 수가 나왔다.

흔하게 기준이 되는 중간값의 갯수를 늘려서 (흔히 피봇값을 2개 이상으로) 최적화를 하거나, 갯수가 적을 경우를 최소한의 명령어로 정렬할 수 있게끔(보통 정렬할 값이 5개 이하 일때) 하드 코딩을 하는 식으로 문제를 해결 하는 것 같다.

 + 위의 input이 알고보니 102개의 input 을 넣은거라, 다시 100개 input으로 고치고 넣어보니 2146개의 명령어로 확인되었다.

나름대로, k와 i 값이 1밖에 차이 나지 않을 때는 sa, sb 등의 명령어로 써보는 건 어떨까하고 시도해 봤는데, 100개 일 시에 필요한 명령어의 수는 2146으로 동일 했다. 기존에 ra, rra로 정렬할 때에도 명령어의 수는 똑같기 때문인것 같다.

따라서 좀더 근본적인 부분을 바꿔야 겠다는 생각이 번뜩 들었다.

현재 구현한 a_stack과 b_stack 모두 count로 들어간 입력값의 반절 값이 저장되어있다.(input이 100개일때, a_stack엔 50개, b_stack에도 50개) 이를 이용해서, count / 2 값을 기준으로 상단부와 하단부를 나누어서 정렬해 보면 어떨까 하는 생각이 들었다.

이 부분을 구현하기 위해서는, 1. "처음 b_stack으로 50 이하의 값을 보낼 때 a_stack의 상단부, 하단부를 나누는 방법" 과 2. "a_stack의 정렬을 하면서 자연스럽게 나누어 보는 방법" 이 있다.

 

먼저 처음 b_stack으로 50 이하의 값을 보낼 때 a_stack의 상단부, 하단부를 나누는 방법이 명령어를 최소화 시키기에 후자보다 좋다고 생각해, 시도해 보려고 한다.

 

먼저, b_stack으로 middle 보다 큰 값을 보내는 경우, 240~241줄을 추가해서, 75 이상의 인덱스를 가지는 값은 b_stack의 하단부로 모이게 했다.

이 처리를 했는데도 100개 input에 대한 정렬 명령어의 갯수는 1도 변화없이 동일했는데, 뒷쪽 50개를 추가 할 때 1씩 증가하는 수를 넣었기 때문인거  같아, 50개 인풋에 대해서도 진행했는데,

50개 인풋에 대한 명령어 값도 여전히 동일 했다.

다시 한번 코드를 보던 중, b_stack은 내림 차순정렬이라는 것을 잠깐 잊어버려서, 239줄의 부등호 방향을 잘못 설정 했다는 것을 깨닫고 의도한 바에 따라서 뒷부분에 들어갈 숫자들을 b_stack의 tail 부분으로 몰았다.

그랬더니 되려 input값에 대한 명령어 숫자가 증가했다..!

일단 최적화 과정중에 있으니 좀더 진행을 해보려고 한다.

a_stack에서 전체 input 개수 / 4 로 기준 값을 남기기가 여전히 힘들어서, 전처리 과정을 조금 더 바꿔보기로 했다.

이렇게 로직을 손으로 써보면서 정리해보니 위에서 왜 명령어가 증가 했는지 알 수 있었다. 순간 b_stack에서 정렬되는 구간이 ㄷ, ㄹ 구간이라고 착각했기 때문이었다. ㄴ구간(25~50 사이)을 먼저 b_stack의 바닥구간에 몰아야 함으로,

239 라인의 부등식의 부등호 방향과 크기 비교의 기준 값을 변경했다.

이에 따라 다시 명령어의 수가 증가했는데, 이는 현재의 알고리즘이, 뒤쪽에 현재 값과 비슷한 값이 있을 경우에 rra 명령어를 통해 빠르게 가져오던 이점이 없어진 것에서 온 것으로 보인다. 일단 정리해 본 로직 대로 수정 후에 다시 기존의 방식과 최종비교를 해보기로 한다.

먼저 노란 형광색을 친 부분처럼 239~240 라인을 통해 인덱스 ㄴ구간을 b_stack의 tail에 가까운 구간에 위치 시켰다. (참고로 input 100개는 스택을 출력했을 때 길이가 너무 길어서 값을 확인하기가 어려워, 모니터링하는 input을 50개 인풋으로 잠시 변경했다.)