Search
Duplicate
🔄

push_swap

Holy Graph
2Circle
간략한 내용
최적화된 알고리즘을 사용하여 데이터 정렬하기
적정 기간
60 hours
제작에 참여한 사람
진행 중인 사람
최종 편집일
Jun 22
통과한 사람
1 more property
그냥 퀵소트 쓰는게 편해요

0. push swap 과제 목표

주어진 스택에 대하여 제한된 명령어 집합을 가능한 한 적게 사용하여 정렬하기.
→ quick sort, merge sort ...

1. Instruction set

Search
명령어
Code
Instruction
Action
sb
스택 b의 가장 위에 있는 두 원소(혹은 첫 번쨰 원소와 두 번째 원소)의 위치를 서로 바꾼다.
ss
sa와 sb를 동시에 실행한다.
pa
스택 b에서 가장 위(탑)에 있는 원소를 가져와서, 스택 a의 맨 위(탑)에 넣는다. 스택 b가 비어 있으면 아무 것도 하지 않는다.
pb
스택 a에서 가장 위(탑)에 있는 원소를 가져와서, 스택 b의 맨 위(탑)에 넣는다. 스택 a가 비어있으면 아무 것도 하지 않는다.
ra
shifts all elements of stack a from bottom to top
rb
shifts all elements of stack b from bottom to top
rr
ra와 rb를 동시에 실행한다.
rra
스택 a의 모든 원소들을 아래로 1 인덱스 만큼 내린다. 마지막 원소(바텀)는 첫 번째 원소(탑)가 된다.
rrb
스택 b의 모든 원소들을 아래로 1 인덱스 만큼 내린다. 마지막 원소(바텀)는 첫 번째 원소(탑)가 된다.
rrr
rra와 rrb를 동시에 실행한다.

2. Quick Sort 란?

<예시>
void quicksort(int arr[], int left, int right) { int L; int R; int temp; int pivot; pivot = arr[(left + right) / 2]; L = left; R = right; while (L <= R) { while (arr[L] < pivot) L++; while (arr[R] > pivot) R--; if (L <= R) { if (L != R) { temp = arr[L]; arr[L] = arr[R]; arr[R] = temp; } L++; R--; } } if (left < R) quicksort(arr, left, R); if (L < right) quicksort(arr, L, right); }
C
복사

3. 랜덤값 돌려보기!

ARG=`ruby -e "puts (0..10).to_a.shuffle.join(' ')"`; ./push_swap $ARG
Shell
복사

4. 참고할만한 링크

의사 코드에 오타가 있으므로 제대로 이해하고 할것!