push swap - 퀵소트를 적용하기

slee2·2021년 9월 3일
42projectCSort
0

42Seoul

목록 보기
5/15
post-thumbnail

일단, 위의 퀵소트를 이용해 피봇을 하나 정하여 어떻게 이 프로젝트로 적용하는지 보겠습니다.

영역을 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_호출_횟수)

결론은 위와 같이 됩니다. 처음부터 순서대로 보겠습니다.

A to B

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( >= 4)
    • 8 5 6 7 4
  • B( < 4)
    • 3 1 2
  • 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_to_B(8)

    • A_to_B(5)

      • A_to_B(3)
      • B_to_A(2)

여기까지 진행 완료한 모습입니다.

  • A_to_B(8)

    • A_to_B(5)

      • A_to_B(3)
      • B_to_A(2)

    • B_to_A(3)

  • B_to_A(0)

이후 로직은 아래와 같습니다.

이 로직을 말로 설명드리기에는 재귀가 깊이 들어가므로, 그림을 통해 이해하도록 설명드렸습니다.

영역을 3개로 나눌때

본 서브젝트의 평가표를 보면 명령어의 개수를 보았을때 100개의 인자를 실행했을때 명령어가 700개 밑으로 나와야 만점입니다. 그런데 영역을 2개로 나누게 되면 700개가 넘게 나오게 됩니다. 영역 3개로 나눌때는 2개로 나눌때보다 명령어의 개수가 적게 나옵니다. 그 이유는 시간 복잡도와 관련이 있습니다.

​

시간복잡도

솔직히 시간복잡도라는 개념을 아직 잘 이해가 되지는 않습니다. 다만, 많이 나눌수록 더 효율적으로 동작을 할 수 있다. 정도만 알고 있습니다.

2개 영역, A_to_B(count)기준

피봇을 중간값으로 잡았을때

3개 영역, A_to_B(count)기준

피봇을 1/3, 2/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문은 이전과 같습니다. 이번에는 피봇이 2개입니다. 저는 전체 수들 중에서 rank를 매겨 등수가 1/3등 그리고 2/3등을 피봇으로 정했습니다.

for r개의 원소에 대해서
	if (스택A의 top) >= 피봇[큰것]
		ra명령으로 뒤로 넘긴다
		ra호출횟수++
	else
		pb명령으로 b로 보낸다
		pb호출횟수++
		if (스택B의 top) >= 피봇 [작은것]
			rb명령으로 뒤로 넘긴다
			rb호출횟수++

그림으로 보시면 이해가 더 쉬우실 것 같습니다.

처음에 A스택에 그림처럼 이것저것 섞여있는 상태겠죠? 2개의 피봇중에 큰놈을 큰피 작은놈을 작피라고 하겠습니다.

  • for문에서 큰피보다 큰 값들을 ra로 넘깁니다. 그 범위가 [3]입니다.
  • 그리고 큰피보다 작은 값들은 pb로 넘기는데 그중에 작피보다 크면 rb로 넘깁니다. 이 범위가 [2]입니다.
  • 그러면 작피보다 작은 값 [1]은 B스택의 앞자리를 차지하게 됩니다.

각 명령어의 횟수는 범위의 개수가 같습니다.

ra = [3] 개수
rb = [2] 개수
그리고 ([1] + [2]) 개수 = pb이므로,
pb - rb = [1]

for ra호출횟수, rb호출횟수
	rrr호출 #[3]과 [2]를 스택 앞으로 가져온다

for문의 목적은 [3]영역과 [2]영역을 맨 앞으로 가져오는 것입니다.
[3]의 개수와 [2]의 개수가 다를수도 있으므로, 그걸 위한 예외처리를 따로 해주셔야 합니다.(ra = 10, rb = 8이라면 rrr 8번 + rra 2번 이렇게 해줘야댐)

A_to_B(ra호출 횟수) #[3]
B_to_A(rb호출 횟수) #[2]
B_to_A(pb호출 횟수 - rb 호출 횟수) #[1]

위 그림은 A_to_B(ra호출 횟수)로 들어간 후에 그림입니다. 마지막에 A스택에 3개 이하가 남을때까지 재귀로 계속 들어갑니다. A스택에 3개 이하가 남게 되면, 적당히 정렬하고 종료조건으로 return하게 됩니다.

이후에 B_to_A(rb호출 횟수) 가 실행됩니다.

​

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]

[４] 영역을 [１][２][３] ３영역으로 나눴습니다.

rb = [1] 개수
ra = [2] 개수
pa -ra = [3] 개수

이후에 A_to_B([3])에서 다시한번 재귀로 정렬이 됩니다.([3] 개수가 3개 이하이고 정렬이 완료되었다고 가졍하겠습니다.)

그 후에 rrr을 거쳐가는 과정까지 위 그림이 되겠습니다.

이런식으로 B스택이 계속 쪼개지다가 3개 이하가 되면 종료 조건에 의해 정렬이 된 후에 pa로 A스택에 넘기게 됩니다. 그렇게 모든 값이 정렬되고 return이 계속되면 A스택에 전부 정렬됩니다.

글로 설명하기 어려워 그림을 활용했는데, 잘 설명했는지 모르겠습니다. 처음 보면 이해하기 어려울 수 있습니다. 그림을 직접 그려가며 고민해본다면 점점 이해가 되실 거라고 생각됩니다. 감사합니다.

참고
https://www.notion.so/push_swap-c15e62229b9541d78fadec4d6aae8b50

profile
slee2
이전 포스트

push swap - 퀵소트

다음 포스트

philosophers - 프로세스와 스레드 그리고 알고리즘

0개의 댓글