Search
Duplicate
💯

[push_swap] 500개를 무조건 4000번 안에 정렬하는 방법

간단소개
O(n log n) 극강의 성능! push_swap
팔만코딩경 컨트리뷰터
ContributorNotionAccount
주제 / 분류
42cursus
태그
push_swap
Scrap
8 more properties
5달을 깎은 끝에 얻은 결론이지만, 과정을 설명하기에는 너무 길어 결과만 남겼습니다.

가능한가?

결론부터 말하자면, 이 방법으로 519개까지는 무조건 4000번 미만으로 정렬할 수 있습니다.

아이디어

이는 몇 가지 간단한 아이디어에서 시작합니다.

각 스택의 끝에서 끝으로 자유롭게 이동할 수 있다

스택 A의 top, 스택 A의 bottom, 스택 B의 top, 스택 B의 bottom, 이렇게 총 4가지 위치에서는 서로 다른 곳으로 이동할 수 있습니다.
시작 위치, 끝 위치
A top
A bottom
B top
B bottom
A top
-
ra
pb
pb + rb
A bottom
rra
-
rra + pb
rra + pb + rb
B top
pa
pa + ra
-
rb
B bottom
rrb + pa
rrb + pa + ra
rrb
-
그러므로 3분할 병합정렬, 퀵정렬이 가능합니다.

병합정렬, 퀵정렬, 18가지 방향, 다양한 방법

a + b + c = N개를 정렬하면서 이동하는 방법을 크게 병합정렬과 퀵정렬로 나눌 수 있습니다.
병합정렬
예시: (가)에서 (나)로 정렬
(가)에서 (나)로 a개를 정렬하면서 이동 (재귀적)
(가)에서 (다)로 b개를 정렬하면서 이동 (재귀적)
(가)에서 (가)로 c개를 정렬하면서 이동 (재귀적)
(가), (다), (라)에서 (나)로 병합
퀵정렬
예시: (가)에서 (가)로 정렬
(가)에서 크기에 따라 큰 것 a개를 (나), 작은 것 c개를 (라), 중간 b개를 (다)로 정렬하면서 이동
(나)에서 (가)로 a개를 정렬하면서 이동 (재귀적)
(다)에서 (가)로 b개를 정렬하면서 이동 (재귀적)
(라)에서 (가)로 c개를 정렬하면서 이동 (재귀적)
각 위치는 스택 A, B의 top, bottom일 수도 있고 top이면서 bottom일 수도 있습니다.
방향이 같아도 여러가지 방법이 있지만, 어떤 방법이 가장 효율적일지는 미리 알 수 없습니다.

개수와 방향에 따라 효율적인 정렬 방법/개수가 다르다

예를 들어 스택 A의 top에서 스택 A의 top으로 정렬하면서 이동하는 경우 아래 두 가지 방법이 있을 수 있습니다.
두번째 방법(#2)은 rr을 활용했습니다.
제가 찾은 방법은 6가지인데, 실제로 같은 방향이라도 개수에 따라 효율적인 방법이 달랐습니다.

방법

(ㄱ) - 우선 무차별 대입으로 몇 개까지는 항상 최적의 경로로 정렬되도록 하드코딩할 수 있습니다.
// 중략 "\2\2\2\2\5\13\5\10\5\10\1\1\1\1\6\6\6\6", // 9 8 7 6 5 4 2 3 1을 a의 top/bottom에서 a의 top/bottom으로 이동하려면 // pb pb pb pb ss rrr ss rr ss rr pa pa pa pa ra ra ra ra "\2\2\2\2\2\5\11\13\1\1\1\6\10\1\1\6\6\6", // 9 8 7 6 5 4 3 1 2을 a의 top/bottom에서 a의 top/bottom으로 이동하려면 // pb pb pb pb pb ss rra rrr pa pa pa ra rr pa pa ra ra ra "\2\2\2\2\2\3\13\13\5\1\1\1\10\1\1\6\6\6\6", // 9 8 7 6 5 4 3 2 1을 a의 top/bottom에서 a의 top/bottom으로 이동하려면 // pb pb pb pb pb sa rrr rrr ss pa pa pa rr pa pa ra ra ra ra // 후략
C
무차별 대입으로 찾은 하드코딩된 데이터 예시
(ㄴ) - 다음으로는 무차별 대입과 DP를 통해 개수와 방향에 따라 어떤 방법으로, 어디로 몇 개를 보내는 게 효율적일지도 몇 개까지는 하드코딩할 수 있습니다.
{ // 5000개를 정렬할 때 방향별로 어떤 방법을 써야 몇번만에 정렬이 완료될지 {{{1690, 2193, 1117}, 55845}, ps_solve_tst_merge_no_rotate_solve}, {{{1857, 2431, 712}, 53514}, ps_solve_txt_merge_twist_solve}, {{{1427, 519, 3054}, 57664}, ps_solve_tsb_merge_solve}, {{{1188, 1968, 1844}, 54224}, ps_solve_txb_merge_straightforward_solve}, {{{1631, 766, 2603}, 55779}, ps_solve_tot_merge_no_rotate_solve}, {{{878, 2358, 1764}, 53452}, ps_solve_tos_merge_solve}, {{{2849, 570, 1581}, 57387}, ps_solve_tob_merge_solve}, {{{1968, 712, 2320}, 54505}, ps_solve_sss_merge_solve}, {{{2088, 712, 2200}, 53565}, ps_solve_sxs_merge_straightforward_solve}, {{{736, 2355, 1909}, 54176}, ps_solve_sot_quick_solve}, {{{386, 2297, 2317}, 53784}, ps_solve_sob_quick_solve}, {{{519, 1427, 3054}, 57664}, ps_solve_bst_quick_solve}, {{{1256, 700, 3044}, 56586}, ps_solve_bxt_merge_twist_solve}, {{{2963, 1493, 544}, 58996}, ps_solve_bsb_merge_solve}, {{{296, 1415, 3289}, 56158}, ps_solve_bxb_quick_twist_solve}, {{{602, 1808, 2590}, 57387}, ps_solve_bot_merge_no_rotate_solve}, {{{599, 2335, 2066}, 55613}, ps_solve_bos_merge_solve}, {{{386, 1390, 3224}, 59369}, ps_solve_bob_merge_solve}, },
C
무차별 대입과 DP로 구한 개수/방향별 최적의 개수/방법 데이터 예시
이제 런타임에서는 이렇게 정해진 방법대로 정렬하면 됩니다.
일정 개수 (ㄱ) 이하는 하드코딩된 최적의 경로로, 또 일정 개수 (ㄴ) 이하는 최적의 개수/방법으로, 그 이상은 (ㄴ)의 마지막 비율대로…

마무리

저는 블랙홀이 부족해서 이 방법을 고안만 하고 구현은 아직 못 했습니다.
아마 이 방법대로 구현한다면 세계 1등일지도…?
생각하는 즐거움을 박탈하고 싶지 않아 최소한의 정보만 남겼습니다. 여러분도 한 번 생각해보세요!
그리고 혹시 더 빠르게 정렬할 방법을 찾으셨다면 댓글 남겨주시면 감사하겠습니다.