2022.04.02. push_swap 함수 구상하기

 

두개의 스택만을 이용해, 특정한 명령어들만 사용하여, 입력값을 오름차순으로 정렬하는 과제이다.

단, 최소의 움직임(명령어를 최소한)으로 정렬해야한다. 즉, 시간 복잡도는 별로 상관 없어 보인다.

피봇값을 기준으로 정렬하는 퀵정렬과, 굳이 따지자면 그리디 알고리즘에 가까운 방식으로 푸는 방법이 흔한 것 같다.

먼저 퀵정렬을 택해 구현을 해보자는 마음이 들었다.

퀵정렬을 택할 경우, 과제에서 요구하는 수준의 명령어 수 범위 내에서 정렬을 해내려면 최적화에 아주 힘써야한다고 하던데..!

일단 떠오르는 아이디어들을 적어가면서 구현 해보고, 안되겠다는 판단이 들면 다른 방식으로도 구현해보면서 정렬 알고리즘들에 가까워 지는 시간이 되었으면한다.(소중한 배움의 기회니까!) 

 

- 퀵정렬

먼저 퀵 정렬로 정렬을 해봐야겠다는 마음이 들자,

피봇값을 적절하게 정하는 것이 가장 관건이라는 생각이 들었다. 피봇 값은 들어온 값의 중간 값일 때가 가장 best인데, 중간 값에 가장 가깝도록 랜덤으로 표본을 뽑아 그 표본들의 평균을 내고, 그 평균값에 가장 가까운 값을 입력값에서 찾아서 피봇 값으로 사용해 볼까 하는 생각이 들었다. 그럼 이제 적절한 표본의 수를 생각해 봐야한다.

https://ko.surveymonkey.com/mp/sample-size-calculator/

표본 크기 계산기: 표본 크기 이해하기 | SurveyMonkey

위 사이트의 계산기를 사용해 신뢰 수준 90%를 유지하는 수준에서 적절한 표본크기를 정해봤다. 

17개 선에서 표본 집단 크기를 잡으면 적당하다고 생각이 들었다.

참고로 오차 한계는 15프로 정도로만 줄여도 모집단의 크기가 커질수록 표본 크기가 너무 커져버렸기 때문에..!

오차 한계를 20퍼센트로 해주면 모집단의 크기가 아무리 커져도 표본 크기가 17~18 수준에서 머물러서, 20프로의 오차한계를 감수하기로 했다. 

 

퀵정렬을 이용해 구현을 해야겠다고 맘을 먹고 생각하던중, 다른 아이디어가 생각이 났다.

위의 방법대로 표본을 뽑아 들어온 입력값의 평균값(근사치)에 가까운 값을 기준으로 스택 a와 스택 b에 나눠서 각각 오름차순, 내림차순으로 정렬한 뒤, 스택 b의 top에서 스택 a의 top으로 모두 옮기는 것이다.

단, 이번 과제는 명령어의 수를 최소화 해야하고, 과제에서 제시한 명령어 중에는 스택a와 스택b의 명령어를 한번에 합치는 명령어가 있으므로, 명령어 수 최소화를 하기위해 1."스택a에 정렬 명령어 1번 내리면 그다음엔 스택b에 명령을 내린다" or 2."순서가 바뀌어도 상관 없는 명령들에 대해서, 나중에 합친다." 중에 하나를 택해 구현해 보면 어떨까 하는 생각이 든것이다. 내일 일단 입력값 파싱부를 구현후, 이 방식으로 구현을 해보려고 한다.