퀵소트를 적용하기
먼저 https://www.notion.so/push_swap-c15e62229b9541d78fadec4d6aae8b50 이분 글을 훨씬 정리가 잘 되어있어서 이를 이용해서 해결했고, 이 글을 이해하는 느낌으로 작성하겠습니다.
일단, 위의 퀵소트를 이용해 피봇을 하나 정하여 어떻게 이 프로젝트로 적용하는지 보겠습니다.
영역을 2개로 나눌때
A_to_B
def A_to_B(범위의 크기r)
if r == 1 && r == 2 && r == 3
1은 return 2와 3은 적당히 정렬시키고 return
스택A의 r개의 원소 중에서 "적절한" 피봇을 선택한다
for r개의 원소에 대해서
if (스택A의 top) > 피봇
ra명령으로 뒤로 넘긴다
ra_호출_횟수++
else
pb명령으로 b로 보낸다
pb_호출_횟수++
for ra_호출 횟수
rra #ra로 넘어간 원소들을 다시 스택 상단으로 되감기
---------------------------------------------------------
A_to_B(ra_호출_횟수)
B_to_A(pb_호출_횟수)B_to_A
def B_to_A(범위의 크기r)
if r == 1 && r == 2 && r == 3
1은 pa 후에 return 2와 3은 적당히 정렬시키고 개수만큼 pa 후 return
스택B의 r개의 원소 중에서 "적절한" 피봇을 선택한다
for r개의 원소에 대해서
if (스택B의 top) > 피봇
rb명령으로 뒤로 넘긴다
rb_호출_횟수++
else
pa명령으로 a로 보낸다
pa_호출_횟수++
for ra_호출 횟수
rra #ra로 넘어간 원소들을 다시 스택 상단으로 되감기
--------------------------------------------------------------
A_to_B(pa_호출_횟수)
B_to_A(pb_호출_횟수)위 예시는 사이트에서 그대로 가져온 예시입니다. 차근차근 보겠습니다. - - - -는 그냥 보기 편하게 구분해놓은겁니다.
def A_to_B(범위의 크기r)
if r == 1 && r == 2 && r == 3
1은 return 2와 3은 적당히 정렬시키고 return
스택A의 r개의 원소 중에서 "적절한" 피봇을 선택한다if문은 나중에 다시 돌아올테니 일단 넘어가주세요. 여기에서 저는 피봇을 크기가 중간값인 친구를 피봇으로 정하겠습니다. 8 2 5 6 7 1 3 4 이면 피봇을 4로 정한다고 생각하시면 됩니다.
for r개의 원소에 대해서
if (스택A의 top) >= 피봇
ra명령으로 뒤로 넘긴다
ra_호출_횟수++
else
pb명령으로 b로 보낸다
pb_호출_횟수+
위 사진의 과정을 실행한다고 생각하면 됩니다. 처음에는 고정 부분이 없으니 큰수와 작은수로만 이루어져 있겠죠? 8 2 5 6 7 1 3 4 로 예시를 들자면
A - 8 5 6 7 4 >= 4
B - 3 1 2 < 4
ra 횟수 = 5
rb 횟수 = 3
여기서 중요한건 위 그림의 큰 수의 개수가 ra 횟수고 작은 수들의 개수는 rb의 횟수인 것입니다.
for ra 호출 횟수
rra #ra로 넘어간 원소들을 다시 스택 상단으로 되감기
A_to_B(ra 호출 횟수)
B_to_A(pb 호출 횟수)rra 를 ra 횟수만큼 한다면
큰 수의 개수들만큼 rra를 실행하여 위 그림처럼 돌아오게 됩니다. 물론 처음에는 rra를 하는게 의미가 없습니다만 나중에 계속 쪼개다 보면 저렇게 가운데에 건들면 안되는 공간이 생겨서 만들어둔 for문이라고 생각하면 될 것 같습니다.
그 후에 A_to_B를 가면 어떻게 되느냐
A - 8 5 6 7 4 >= 4
B - 3 1 2 < 4
ra 횟수 = 5
rb 횟수 = 3
A_to_B(5);
-------------------------------
pivot - 6 (8 5 6 7 4의 중간값)
A - 8 6 7 >= 6
B - 5 4 (3 1 2) < 6
이렇게 됩니다. 이 과정이
A_to_B(8)
{
A_to_B(5)
{
현재 여기
A_to_B(3)
B_to_A(2)
}
B_to_A(3)
}함수 안에 함수에 들어갔으니 현재 위 코드의 위치에 있습니다. 다시 위로 보면
def A_to_B(범위의 크기r)
if r == 1 && r == 2 && r == 3
1은 return 2와 3은 적당히 정렬시키고 return
스택A의 r개의 원소 중에서 "적절한" 피봇을 선택한다여기서 if문에 크기가 3개 들어올때는 적당히 정렬을 시킬 수 있습니다. 그러면
A - 6 7 8 >= 6
B - 5 4 (3 1 2) < 6
이렇게 정렬이 됩니다. 그 후에 B_to_A(2)에서 if문으로 인해 정렬 시키고 개수만큼 pa를 시킵니다.
A - 4 5 6 7 8
B - 3 1 2
이렇게 됩니다. 그러면 A_to_B 안에 있는 A_to_B(5)는 끝이났습니다. 그후에 A_to_B(3)에서 같은 방법을 실행하면 마지막에 A스택에 이쁘게 정렬이 됩니다.
B_to_A에서는 계속 A스택에 피봇보다 크거나 같은 수를 올리고 A_to_B를 시행하고, B스택에 피봇보다 작은수를 남기고 B_to_A를 시행합니다. 이렇게 서로 계속 맞물려 돌리면 마지막에 B_to_A나 A_to_B는 count개수가 3개 이하로 남을때까지 나누다가 마지막에 3개 이하에서 정렬되어 다시 빠져나오게 됩니다. (직접 예시를들어서 해보면 이해가 됩니다.)
영역을 3개로 나눌때
본 서브젝트의 평가표를 보면 명령어의 개수를 보았을때 100개의 인자를 실행했을때 명령어가 700개 밑으로 나와야 만점입니다. 그런데 영역을 2개로 나누게 되면 700개가 넘게 나오게 됩니다. 영역 3개로 나눌때는 2개로 나눌때보다 명령어의 개수가 적게 나옵니다. 그 이유는 시간 복잡도와 관련이 있습니다.
시간복잡도
솔직히 시간복잡도라는 개념을 아직 잘 이해가 되지는 않습니다. 다만, 많이 나눌수록 더 효율적으로 동작을 할 수 있다. 정도만 알고 있습니다.
2개 영역, A_to_B(count)기준
피봇을 중간값으로 잡았을때
3개 영역, A_to_B(count)기준
피봇을 1/3, 2/3로 각각 잡는다는 가정하에
시간복잡도 계산공식은
이 되기 때문에 3개로 영역을 나누는 경우가 더 효율적입니다.
A_to_B
def A_to_B(r)
if r <= 3
적절히 정렬
return
스택A 원소 중에서 "적절한" 피봇을 2개 선택한다
for r개의 원소에 대해서
if (스택A의 top) >= 피봇[큰것]
ra명령으로 뒤로 넘긴다
ra호출횟수++
else
pb명령으로 b로 보낸다
pb호출횟수++
if (스택B의 top) >= 피봇 [작은것]
rb명령으로 뒤로 넘긴다
rb호출횟수++
---------------------------------------------------
for ra호출횟수, rb호출횟수
rrr호출 #[3]과 [2]를 스택 앞으로 가져온다
---------------------------------------------------
A_to_B(ra호출 횟수) #[3]
B_to_A(rb호출 횟수) #[2]
B_to_A(pb호출 횟수 - rb 호출 횟수) #[1]B_to_A
def B_to_A(r)
if r <= 3
적절히 정렬/pa로 보내기
return
스택B 원소 중에서 "적절한" 피봇을 2개 선택한다
for r개의 원소에 대해서
if (스택B의 top) < 피봇[작은것]
rb명령으로 뒤로 넘긴다
rb호출횟수++
else
pa명령으로 a로 보낸다
pa호출횟수++
if (스택B의 top) < 피봇 [큰것]
ra명령으로 뒤로 넘긴다
ra호출횟수++
---------------------------------------------------
A_to_B(pa호출횟수 - ra호출횟수) #[3]
for ra호출횟수, rb호출횟수
rrr호출 #[1]과 [2]를 스택 앞으로 가져온다
---------------------------------------------------
A_to_B(ra호출횟수) #[2]
B_to_A(rb호출횟수) #[1]이해를 해봅시다.
def A_to_B(r)
if r <= 3
적절히 정렬
return
스택A 원소 중에서 "적절한" 피봇을 2개 선택한다if문은 아까처럼 3개 일때 알아서 정렬하고 리턴된다고 생각하시면 됩니다. 이번에는 피봇이 2개죠. 여기서 만든 분이 생각한것은 정확히 피봇을 기준으로 3 영역이 이쁘게 나눠지는 것입니다. 그러므로 저는 전체 수들 중에서 rank를 매겨 등수가 1/3등 그리고 2/3등을 피봇으로 정했습니다.
for r개의 원소에 대해서
if (스택A의 top) >= 피봇[큰것]
ra명령으로 뒤로 넘긴다
ra호출횟수++
else
pb명령으로 b로 보낸다
pb호출횟수++
if (스택B의 top) >= 피봇 [작은것]
rb명령으로 뒤로 넘긴다
rb호출횟수++
처음에 A스택에 그림처럼 이것저것 섞여있는 상태겠죠? 2개의 피봇중에 큰놈을 큰피 작은놈을 작피라고 하겠습니다. 위의 코드에서 큰피보다 큰 것을 ra로 넘깁니다. 그 크기를 [3]으로 부르겠습니다. 그리고 큰피보다 작은 것들은 pb로 넘기는데 그중에 작피보다 크면 rb로 넘깁니다. 즉, 큰피보다 작고 작피보다 큰 중간값[2]가 뒤로 넘어갑니다. 그러면 작피보다 작은 값[1]은 B스택의 앞자리를 차지하게 됩니다.
여기서 편하게 생각하겠습니다
ra = [3]
rb = [2]
그리고 [1] 개수 + [2] 개수 = pb횟수이므로,
pb - rb = [1]
for ra호출횟수, rb호출횟수
rrr호출 #[3]과 [2]를 스택 앞으로 가져온다
나중에는 건들면 안되는 고정영역들이 있어서 저렇게 for문이 있는데 저 for문의 목적은 [3]영역과 [2]영역을 맨 앞으로 가져오는 것입니다. 그러므로 저 [3]의 개수와 [2]의 개수가 다를수도 있겠죠? 그걸 위한 예외처리를 따로 해주셔야 합니다.(ra = 10, rb = 8이라면 rrr 8번 + ra 2번 이렇게 해줘야댐)
A_to_B(ra호출 횟수) #[3]
B_to_A(rb호출 횟수) #[2]
B_to_A(pb호출 횟수 - rb 호출 횟수) #[1]A_to_B
{
A_to_B(ra호출 횟수)
{
A_to_B(ra호출 횟수)
{
A_to_B(ra호출 횟수)
{
...
}
B_to_A(rb호출 횟수)
B_to_A(pb호출 횟수 - rb 호출 횟수)
}
B_to_A(rb호출 횟수)
B_to_A(pb호출 횟수 - rb 호출 횟수)
}
B_to_A(rb호출 횟수)
B_to_A(pb호출 횟수 - rb 호출 횟수)
}
위 그림은 A_to_B안에 A_to_B(ra호출 횟수)로 들어간 후에 그림입니다. 마지막에 A스택에 3개 이하가 남을때까지 계속 들어갑니다. 그 후에 A에서 정렬되고 리턴이 된다고 생각하시면 됩니다. 그러면 B스택에는 저렇게 각 영역 안에는 섞여있는 상태로 정렬이 되어있습니다.
B_to_A
def B_to_A(r)
if r <= 3
적절히 정렬/pa로 보내기
return
스택B 원소 중에서 "적절한" 피봇을 2개 선택한다for r개의 원소에 대해서
if (스택B의 top) < 피봇[작은것]
rb명령으로 뒤로 넘긴다
rb호출횟수++
else
pa명령으로 a로 보낸다
pa호출횟수++
if (스택B의 top) < 피봇 [큰것]
ra명령으로 뒤로 넘긴다
ra호출횟수++ 
현재 그림은 [４] 영역을 [１][２][３] ３영역으로 나눈 것입니다. 현재는 [1][2][3]이 저 공간에서 서로 섞여있는 상태입니다.
for문을 실행한 후 모습입니다.
현재 상황은
rb = [1]
ra = [2]
pa -ra = [3] 입니다.
A_to_B(pa호출횟수 - ra호출횟수) #[3]
for ra호출횟수, rb호출횟수
rrr호출 #[1]과 [2]를 스택 앞으로 가져온다
---------------------------------------------------
A_to_B(ra호출횟수) #[2]
B_to_A(rb호출횟수) #[1]A_to_B([3])에서 다시한번 재귀로 정렬이 시작됩니다. 그리고 마지막에 정렬이 되어서 나옵니다.
그 후에 rrr을 거쳐가면
이렇게 됩니다.
그 후에 A_to_B([2])를 합니다. [2]는 정렬된 [2]로 됩니다. 그럼 현재 정렬된 [2]와 정렬된 [3]이 있게 되고, 마지막에 B_to_A([1]) 을 실행합니다.
이런식으로 B스택이 계속 쪼개지다가 3개이하가 되면 조건에 의해 정렬이 된 후에 pa로 A스택에 넘기게 됩니다. 그렇게 모든 값이 정렬되고 return이 계속되면 A스택에 전부 정렬됩니다.
마지막으로 이 글은 처음에 말씀드렸듯이 다른분이 더 깔끔하게 정리된 글을 이해하는 방식으로 글을 작성했습니다.
Author And Source
이 문제에 관하여(퀵소트를 적용하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@seungju0000/pushswap-퀵소트를-적용하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
