Search
๐Ÿ’ฑ

push_swap

Created
2021/06/21
tag
42์„œ์šธ
42Seoul
push_swap
Quick Sort
Stack Sort
Algorithm

Subjects

โ€ข

1. ๋“ค์–ด๊ฐ€๊ธฐ ์ „์—

์ด๋ฒˆ ๊ธ€์€ ์ด์ „ ๊ธ€๋“ค๊ณผ ์กฐ๊ธˆ ๋‹ค๋ฅธ ์„ฑ๊ฒฉ์œผ๋กœ, ํŠน์ • ์ง€์‹์˜ ์ „๋‹ฌ๋ณด๋‹ค๋Š” ํ”„๋กœ์ ํŠธ ํ’€์ด๋ฅผ ์œ„ํ•ด ํ–ˆ๋˜ ์ƒ๊ฐ๋“ค์„ ์œ„์ฃผ๋กœ ์ „๋‹ฌํ•  ์˜ˆ์ •์ด๋‹ค. ๋”ฐ๋ผ์„œ ๋ฌธ์ œ ํ•ด๊ฒฐ์„ ์œ„ํ•œ ๋ชจ๋“  ๋ฐฉ๋ฒ•์ด ์•„๋‹Œ ํŠน์ • ๋ฐฉ๋ฒ•๋งŒ ์†Œ๊ฐœ๋  ์˜ˆ์ •์ด๋ฉฐ, ๊ธ€ ์ „์ฒด์ ์œผ๋กœ ์ฃผ๊ด€์ ์ธ ์„ฑ๊ฒฉ์ด ๊ฐ•ํ•˜๋ฏ€๋กœ ์ด๋ฅผ ์ฐธ๊ณ ํ•˜๊ณ  ์ฝ๋Š” ๊ฒƒ์„ ์ถ”์ฒœํ•œ๋‹ค. ํ’€์ด๋ฅผ ์œ„ํ•ด ์–ด๋–ค ํ๋ฆ„์œผ๋กœ ์ƒ๊ฐ์„ ํ–ˆ๋Š”์ง€ ์ •๋„๋ฅผ ๋ณด๋ฉด ์ข‹์„ ๊ฒƒ ๊ฐ™๋‹ค.
๋˜ํ•œ ๋Œ€์ถฉ ์–ด๋Š ์ •๋„์˜ ๊ฐ’์ด ๋‚˜์˜ฌ์ง€ ์˜ˆ์ธก์€ ๋˜๋Š”๋ฐ, ์ˆ˜์‹์œผ๋กœ ์ •๋ฆฌํ•˜๋ ค๊ณ  ๋ณด๋‹ˆ ์ž˜ ์•ˆ ๋˜์—ˆ๋‹ค. ์‹œ๊ฐ„ ๋ณต์žก๋„ ๊ณ„์‚ฐ์— ์žˆ์–ด์„œ ์–ผ๋งˆ๋‚˜ ๋ฌด๋Šฅํ•œ์ง€ ์•Œ ์ˆ˜ ์žˆ์—ˆ๋‹ค. ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ๋ฅผ ํ‘ผ๋‹ค๋“ ๊ฐ€, ์–ด๋–ค ๊ฒƒ์— ๋Œ€ํ•ด์„œ ์ฝ”๋”ฉ์„ ํ•  ๋•Œ ์ง€๊ธˆ๋ณด๋‹ค๋„ ๋” ๊ผผ๊ผผํ•˜๊ฒŒ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ํ™•์ธํ•˜๊ณ  ์ฆ๋ช…ํ•˜๋Š” ์Šต๊ด€์„ ๋“ค์—ฌ์•ผ๊ฒ ๋‹ค๋Š” ์ƒ๊ฐ์„ ๋งŽ์ดํ•˜๊ฒŒ ๋˜์—ˆ๋‹ค.
์ด๋ฒˆ ๊ณผ์ œ์˜ ๊ฒฝ์šฐ์—๋„ ๊ฒฐ๊ณผ์ ์œผ๋กœ๋Š” n2n^2๊ณผ ๊ฐ™์€ ํ˜•ํƒœ๋กœ ์ฝ”๋“œ๋ฅผ ์ž‘์„ฑํ–ˆ๋Š”๋ฐ, ์ˆœ์ˆ˜ํ•˜๊ฒŒ n2n^2์œผ๋กœ ๋Œ์ง€ ์•Š๋Š”๋‹ค๋Š” ํ™•์‹  ํ•˜๋‚˜๋งŒ์œผ๋กœ ๊ฒฐ๊ณผ๋ฅผ ๋‚ด๋ณด์•˜๋‹ค. ํ”„๋กœ์ ํŠธ์—์„œ ์ข‹์€ ์ ์ˆ˜๋ฅผ ๋ฐ›์„ ๋งŒํผ์˜ ๊ฒฐ๊ณผ๊ฐ€ ๋‚˜์™”๊ณ  ์ด๋Š” ์–ผ์ถ” ์˜ˆ์ธกํ•œ ๋ฒ”์œ„ ๋‚ด์—์„œ ๋‚˜์™”์Œ์—๋„, ์ œ์‹œ๋œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด nlognnlogn์˜ ์ •๋ ฌ๊ณผ ๋น„์Šทํ•˜๊ฑฐ๋‚˜ ์กฐ๊ธˆ ๋” ์ข‹์€ ๊ฒฐ๊ณผ๋ฅผ ๋‚ด๋Š” ๊ฒƒ์— ๋Œ€ํ•ด์„œ ์ •ํ™•ํ•œ ์ˆ˜์‹์œผ๋กœ ์ฆ๋ช…ํ•˜์ง€ ๋ชปํ–ˆ๋‹ค. ๋ฐ˜์„ฑํ•ด์•ผํ•  ๋ถ€๋ถ„์ด๋ผ๊ณ  ์ƒ๊ฐํ•˜๊ณ , ์ƒ๋‹นํžˆ ๋ถ€๋„๋Ÿฝ๊ฒŒ ๋Š๊ปด์ง„๋‹ค.
๋‹ค์‹œ ๊ณต๋ถ€ํ•ด์•ผ ํ•  ๊ฒƒ ๊ฐ™๋‹ค ใ…Žใ…Ž..

2. Approach

1) ์ค‘๋ณต ๊ฒ€์‚ฌ

push_swap์—์„œ๋Š” ์ˆซ์ž๋กœ ๋˜์–ด ์žˆ๋Š” ์ธ์ž๋งŒ ๋ฐ›์„ ์ˆ˜ ์žˆ์œผ๋ฉฐ, ์ธ์ž ๊ฐ’์€ ์ค‘๋ณต์œผ๋กœ ๋ฐ›์„ ์ˆ˜ ์—†๋‹ค. ๋”ฐ๋ผ์„œ ์ค‘๋ณต๋œ ๊ฐ’์œผ๋กœ ์ธ์ž๊ฐ€ ๋“ค์–ด์™”์„ ๋•Œ, ์ด๋ฅผ ํ™•์ธํ•˜๊ณ  ์ ์ ˆํ•˜๊ฒŒ ์—๋Ÿฌ๋ฅผ ๋‚ด์ค˜์•ผ ํ•œ๋‹ค.
์ •๋ ฌ์„ ์ˆ˜ํ–‰ํ•˜๋Š” ๋กœ์ง์„ ์–ด๋–ป๊ฒŒ ๋‘์ง€ ์ •ํ•˜์ง€ ์•Š์€ ์ƒํƒœ์ด๋”๋ผ๋„, ํ‰๊ฐ€ ๊ธฐ์ค€์— ๋ถ€ํ•ฉํ•˜๋Š” ๊ฒฐ๊ณผ๋ฅผ ๋‚ด๊ธฐ ์œ„ํ•ด์„  ํ‰๊ท ์ ์œผ๋กœ O(nlogn)O(nlogn)์˜ ์„ฑ๋Šฅ์ด ๋ณด์žฅ๋˜์–ด์•ผ ํ•œ๋‹ค. ์ •๋ ฌ์—์„œ์˜ ํ‰๊ท  ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ O(nlogn)O(nlogn)์„ ๋งŒ์กฑํ•˜๋”๋ผ๋„ ์ค‘๋ณต ๊ฒ€์‚ฌ๋ฅผ ์ˆ˜ํ–‰ํ•  ๋•Œ ์ธ์ž๋“ค์„ ์ผ์ผ์ด ํ™•์ธํ•˜๊ฒŒ ๋œ๋‹ค๋ฉด O(n2)O(n^2)์ด ๋˜์–ด๋ฒ„๋ฆฐ๋‹ค. ์šด์ด ์ข‹๋‹ค๋ฉด O(n2)O(n^2)๊นŒ์ง€ ๊ฑธ๋ฆฌ์ง€ ์•Š๊ฒ ์ง€๋งŒ, ์ด๋Š” ์–ด๋””๊นŒ์ง€๋‚˜ ์ค‘๋ณต๋œ ์ธ์ž๊ฐ€ ๋“ค์–ด๊ฐ„ ๊ฒฝ์šฐ์—๋งŒ ํ•ด๋‹น๋œ๋‹ค. ์ฆ‰, ์ค‘๋ณต๋œ ์ธ์ž๊ฐ€ ๋“ค์–ด์˜ค์ง€ ์•Š๊ณ  ์ •์ƒ์ ์œผ๋กœ ์ •๋ ฌ ๋กœ์ง์„ ์ˆ˜ํ–‰ํ•˜๊ฒŒ ๋œ๋‹ค๋ฉด ์ด๋ฏธ ํ™•์ •์ ์œผ๋กœ O(n2)O(n^2)์„ ์ˆ˜ํ–‰ํ•˜๋Š” ๊ฒƒ์ด ๋˜๋ฏ€๋กœ ์ค‘๋ณต ๊ฒ€์‚ฌ์— ์กฐ๊ธˆ ๋” ํšจ์œจ์ ์ธ ๋ฐฉ์‹์ด ํ•„์š”ํ•˜๋‹ค.
์ค‘๋ณต ๊ฒ€์‚ฌ๋ฅผ ์œ„ํ•œ ๋ฐฉ๋ฒ•์€ ํฌ๊ฒŒ 3๊ฐ€์ง€๊ฐ€ ๋– ์˜ฌ๋ž๋‹ค.
1.
๊ฐ ์ธ์ž ๋ณ„๋กœ ๋‹ค๋ฅธ ์ธ์ž๋“ค์„ ์ผ์ผ์ด ๋น„๊ตํ•˜๋Š” ๋ฐฉ๋ฒ• Brute Force
2.
์‚ฌ์šฉ๋œ ์ธ์ž๋“ค์„ ํ…Œ์ด๋ธ”์— ๊ธฐ๋กํ•˜๋Š” ๋ฐฉ๋ฒ• Memoization
3.
์ง‘ํ•ฉ Set
๊ฐ€์žฅ ์‰ฌ์šด ๋ฐฉ๋ฒ•์€ 1๋ฒˆ์ด์ง€๋งŒ, ์œ„์—์„œ ์–ธ๊ธ‰ํ•œ ๊ฒƒ์ฒ˜๋Ÿผ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ๋งŒ์กฑํ•˜๊ธฐ ์œ„ํ•ด์„œ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋Š” ๋ฐฉ๋ฒ•์€ ์•„๋‹ˆ์—ˆ๋‹ค. nn์ด ์ปค์งˆ์ˆ˜๋ก ์ค‘๋ณต ๊ฒ€์‚ฌ๋ฅผ ์œ„ํ•ด ์†Œ์š”๋˜๋Š” ์‹œ๊ฐ„์ด ์ปค์ง€๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.
๊ฐ€์žฅ ์‹œ๊ฐ„์ด ์ ๊ฒŒ ๊ฑธ๋ฆฌ๋Š” ๋ฐฉ๋ฒ•์€ 2๋ฒˆ์ด์—ˆ์ง€๋งŒ, ์ด ์—ญ์‹œ๋„ ์‚ฌ์šฉํ•  ์ˆ˜๋Š” ์—†๋Š” ๋ฐฉ๋ฒ•์ด์—ˆ๋‹ค. Memoization ๋ฐฉ์‹์€ ์‚ฌ์šฉํ•˜๋ ค๋Š” ์ธ์ž๋“ค์˜ MAXโˆ’MIN+1MAX - MIN + 1 ๋งŒํผ์˜ ๊ณต๊ฐ„์„ ํ• ๋‹นํ•ด๋‘์–ด, xx๋ผ๋Š” ๊ฐ’์ด ์‚ฌ์šฉ๋˜์—ˆ์œผ๋ฉด ํ• ๋‹น ๋ฐ›์€ ๊ณต๊ฐ„์˜ xx๋ฒˆ์งธ index์— ํ•ด๋‹นํ•˜๋Š” ๊ณณ์— ๋งˆํ‚น์„ ํ•ด๋‘๋Š” ๋ฐฉ์‹์ด๋‹ค. ์ผ๋ฐ˜์ ์ธ ๋กœ์ง ํ…Œ์ŠคํŠธ๋ฅผ ์œ„ํ•ด ์ธ์ž๋“ค์˜ Interval์ด 1์ธ ํ˜•ํƒœ๋กœ ์ž…๋ ฅ์ด ๋“ค์–ด์˜ค๋Š” ๊ฒฝ์šฐ์—๋Š” ๋ฌธ์ œ ์—†์ด ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ์ง€๋งŒ, Interval์ด ๋ฌด์ž‘์œ„ ํ•˜๊ฒŒ ์ธ์ž๋“ค์ด ๋“ค์–ด์˜ค๋Š” ๊ฒฝ์šฐ์—๋Š” ์ค‘๋ณต ๊ฒ€์‚ฌ๋ฅผ ์œ„ํ•œ ๊ณต๊ฐ„์ด ๊ต‰์žฅํžˆ Sparseํ•  ์ˆ˜ ์žˆ๋‹ค๋Š” ๊ฒƒ์ด ๊ฐ€์žฅ ํฐ ๋ฌธ์ œ์ด๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด 1 2 3 4 5์™€ ๊ฐ™์€ ํ˜•ํƒœ๋กœ ์ธ์ž๋ฅผ ๋ฐ›๊ฒŒ ๋˜๋ฉด ํ• ๋‹น ๋ฐ›์€ 5๊ฐœ์˜ ๊ณต๊ฐ„์„ ๋ฌธ์ œ ์—†์ด ์ด์šฉํ•  ์ˆ˜ ์žˆ์ง€๋งŒ, -2147483648 1 2 3 4 5์™€ ๊ฐ™์€ ํ˜•ํƒœ๋กœ ์ธ์ž๋ฅผ ๋ฐ›์œผ๋ฉด ํ• ๋‹น ๋ฐ›์€ ๊ณต๊ฐ„์„ Sparseํ•˜๊ฒŒ ์ด์šฉํ•˜๊ฒŒ ๋˜๋Š” ๊ฒƒ์ด๋‹ค. ํ•ด๋‹น ๊ฒฝ์šฐ์— ์‚ฌ์šฉํ•˜๋Š” ์ธ์ž๋Š” 6๊ฐœ์ง€๋งŒ, -2147483647 ~ 0๊นŒ์ง€์˜ ๊ณต๊ฐ„์€ ๋‚ญ๋น„ํ•˜๊ฒŒ ๋œ๋‹ค.
๋”ฐ๋ผ์„œ ๊ณต๊ฐ„์„ ๋‚ญ๋น„ ์—†์ด ํšจ์œจ์ ์œผ๋กœ ์‚ฌ์šฉํ•˜๋ฉด์„œ O(n2)O(n^2)๋ณด๋‹ค ์ ์€ ์‹œ๊ฐ„ ๋‚ด์— ์›ํ•˜๋Š” ๊ฒฐ๊ณผ๋ฅผ ์–ป๊ธฐ ์œ„ํ•ด ๋– ์˜ฌ๋ฆฐ ๊ฒƒ์ด Set์ด์—ˆ๋‹ค. Red-Black Tree๋กœ ๊ตฌํ˜„๋œ Set์€ 1๊ฐœ์˜ ์š”์†Œ๋ฅผ ์‚ฝ์ž…ํ•  ๋•Œ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„์ด O(logn)O(logn)์ด๋ฉฐ ํƒ์ƒ‰์ด ํฌํ•จ๋˜์–ด ์žˆ๊ธฐ ๋•Œ๋ฌธ์—, ์‚ฝ์ž… ์—ฐ์‚ฐ๋งŒ์œผ๋กœ ์ค‘๋ณต ๊ฒ€์‚ฌ๋ฅผ ์ˆ˜ํ–‰ํ•  ์ˆ˜ ์žˆ๋‹ค. ์ฆ‰, nn๊ฐœ์˜ ์š”์†Œ๋ฅผ ์‚ฝ์ž…ํ•  ๋•Œ๋Š” O(nlogn)O(nlogn)์ด ์š”๊ตฌ๋˜๋ฉฐ ์ด ๊ณผ์ •์—์„œ ์ค‘๋ณต ์ธ์ž๊ฐ€ ๋“ค์–ด์™”๋Š”์ง€ ํŒ๋ณ„์ด ๊ฐ€๋Šฅํ•ด์ง„๋‹ค.
Red-Black Tree? Red-Black Tree๋Š” ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ์˜ ํ•œ ์ข…๋ฅ˜์ด๋‹ค. ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ์˜ ํŠน์„ฑ ์ƒ Balance๋ฅผ ์ž˜ ์œ ์ง€ํ•˜์ง€ ๋ชปํ•˜๋ฉด O(n)O(n)์— ๊ทผ์ ‘ํ•œ ์„ฑ๋Šฅ์ด ๋‚˜์˜ค๊ฒŒ ๋˜๋Š”๋ฐ, Red-Black Tree๋Š” ์‚ฝ์ž… ์—ฐ์‚ฐ ํ›„ Balance๊ฐ€ ์œ ์ง€๋  ์ˆ˜ ์žˆ๋„๋ก ์ž์ฒด์ ์œผ๋กœ ๊ท ํ˜•์„ ์กฐ์ •ํ•˜์—ฌ ์‚ฝ์ž…, ์‚ญ์ œ, ํƒ์ƒ‰์˜ Worst Case์— ๋Œ€ํ•ด์„œ๋„ ํ•ญ์ƒ O(logn)O(logn)์˜ ์„ฑ๋Šฅ์„ ๋ณด์žฅํ•œ๋‹ค. ๊ท ํ˜•์„ ์กฐ์ •ํ•  ๋•Œ๋Š” ์ƒํ™ฉ์— ๋”ฐ๋ผ Left Rotation ํ˜น์€ Right Rotation์„ ์ˆ˜ํ–‰ํ•˜์—ฌ ๋‚ด๋ถ€์— ์œ ์ง€ ์ค‘์ธ Node๋“ค์„ ํšŒ์ „์‹œํ‚จ๋‹ค. ์ƒ๋Œ€์ ์œผ๋กœ AVL Tree ๋ณด๋‹ค๋Š” ๊ท ํ˜•์— ๋Œ€ํ•œ ๊ธฐ์ค€์ด ์—„๊ฒฉํ•œ ํŽธ์€ ์•„๋‹ˆ์–ด์„œ Worst Case์— AVL Tree๋ณด๋‹ค ์ ์€ Rotation์„ ์ˆ˜ํ–‰ํ•˜๋ฏ€๋กœ ๊ณ ์ •๋œ O(logn)O(logn)์˜ ์„ฑ๋Šฅ์„ ๋ณด์žฅํ•  ์ˆ˜ ์žˆ๋Š” ๊ฒƒ์ด๋‹ค.
๋ ˆ๋“œ-๋ธ”๋ž™ ํŠธ๋ฆฌ - ์œ„ํ‚ค๋ฐฑ๊ณผ, ์šฐ๋ฆฌ ๋ชจ๋‘์˜ ๋ฐฑ๊ณผ์‚ฌ์ „
๋ ˆ๋“œ-๋ธ”๋ž™ ํŠธ๋ฆฌ(Red-black tree)๋Š” ์ž๊ฐ€ ๊ท ํ˜• ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ(self-balancing binary search tree)๋กœ์„œ, ๋Œ€ํ‘œ์ ์œผ๋กœ๋Š” ์—ฐ๊ด€ ๋ฐฐ์—ด ๋“ฑ์„ ๊ตฌํ˜„ํ•˜๋Š” ๋ฐ ์“ฐ์ด๋Š” ์ž๋ฃŒ๊ตฌ์กฐ๋‹ค. 1978๋…„ ๋ ˆ์˜ค ๊ท€๋ฐ”์Šค(Leo J. Guibas)์™€ ๋กœ๋ฒ„ํŠธ ์„ธ์ง€์œ…์ด 1972๋…„ ๋ฃจ๋Œํ”„ ๋ฐ”์ด์–ด๊ฐ€ ์ฐฝ์•ˆํ•œ "๋Œ€์นญํ˜• ์ด์ง„ B-ํŠธ๋ฆฌ"๋ฅผ ๋ฐœ์ „์‹œ์ผœ ๋งŒ๋“ค์—ˆ๋‹ค. ๋ ˆ๋“œ-๋ธ”๋ž™ ํŠธ๋ฆฌ๋Š” ๋ณต์žกํ•œ ์ž๋ฃŒ๊ตฌ์กฐ์ง€๋งŒ, ์‹ค ์‚ฌ์šฉ์—์„œ ํšจ์œจ์ ์ด๊ณ , ์ตœ์•…์˜ ๊ฒฝ์šฐ์—๋„ ์ƒ๋‹นํžˆ ์šฐ์ˆ˜ํ•œ ์‹คํ–‰ ์‹œ๊ฐ„์„ ๋ณด์ธ๋‹ค: ํŠธ๋ฆฌ์— n๊ฐœ์˜ ์›์†Œ๊ฐ€ ์žˆ์„ ๋•Œ O(log n)์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋กœ ์‚ฝ์ž…, ์‚ญ์ œ, ๊ฒ€์ƒ‰์„ ํ•  ์ˆ˜ ์žˆ๋‹ค.

2) Stack

์ฒ˜์Œ์— ํ›„๋ณด๋กœ ๋‘์—ˆ๋˜ Stack์˜ ์ž๋ฃŒ๊ตฌ์กฐ๋Š” ๋ฐฐ์—ด, ๋ฑ, ๋ฆฌ์ŠคํŠธ๋กœ ์ด 3๊ฐœ์˜€๋‹ค.
์ด์šฉํ•˜๋ ค๋Š” ์ธ์ž์˜ ์ˆ˜๋งŒํผ์„ ๊ณต๊ฐ„์„ ํ• ๋‹น ๋ฐ›์•„ ๋ฐฐ์—ด์„ ์ด์šฉํ•œ๋‹ค๊ณ  ํ–ˆ์„ ๋•Œ ์ƒ๊ฐ๋‚ฌ๋˜ ๋ฌธ์ œ์ ์€ 2๊ฐœ์˜€๋‹ค. push ์—ฐ์‚ฐ์„ ๋ฐ˜๋ณตํ–ˆ์„ ๋•Œ ๋‚จ๋Š” ๊ณต๊ฐ„์ด ๋งŽ์•„์ง€๋Š” ๋ฌธ์ œ์™€ rotation ์—ฐ์‚ฐ์„ ๋ฐ˜๋ณตํ–ˆ์„ ๋•Œ ์ธ์ž๋ฅผ ์ ์ ˆํžˆ ์œ„์น˜์‹œํ‚ค๊ธฐ ์œ„ํ•ด์„œ ๋ชจ๋“  ์ธ์ž๋“ค์„ ์•ž ํ˜น์€ ๋’ค๋กœ ํ•œ ์นธ์”ฉ ๋ฐ€์–ด์ค˜์•ผ ํ•œ๋‹ค๋Š” ๋ฌธ์ œ๊ฐ€ ์žˆ๋Š”๋ฐ ์ด๋ฅผ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์–ด์•ผ ํ–ˆ๋‹ค. ์ฒซ ๋ฒˆ์งธ ๋ฌธ์ œ๋Š” ๊ทธ๋ƒฅ ์‹ ๊ฒฝ ์“ฐ์ง€ ์•Š๊ณ  ๊ตฌํ˜„ํ•˜๋”๋ผ๋„ ๋‘ ๋ฒˆ์งธ ๋ฌธ์ œ๋งŒํผ์€ ์ฐจ๋ผ๋ฆฌ ๋ฆฌ์ŠคํŠธ๋ฅผ ์ด์šฉํ•˜๋Š” ๊ฒƒ์ด ๋” ๋‚ซ๊ฒ ๋‹ค๋Š” ์ƒ๊ฐ์ด ๋“ค์—ˆ๊ธฐ ๋•Œ๋ฌธ์— ๋ฐฐ์—ด์€ ํ›„๋ณด์ง€์—์„œ ์ œ์™ธ์‹œ์ผฐ๋‹ค.
๋ฑ์˜ ๊ฒฝ์šฐ์—๋Š” ๊ฐ„๋‹จํ•˜๊ฒŒ ๋ฐฐ์—ด์„ ๋ณด์œ ํ•˜๊ณ  ์žˆ๋Š” ๋ฆฌ์ŠคํŠธ๋“ค์˜ ์—ฐ๊ฒฐ๋กœ ๊ตฌํ˜„ํ•  ๊ณ„ํš์œผ๋กœ ์‹ค์ œ ๋ฑ์˜ ๋ธ”๋ก ๊ตฌ์กฐ์™€ ์ตœ๋Œ€ํ•œ ๋น„์Šทํ•˜๊ฒŒ ์ƒ๊ฐ์„ ํ–ˆ์—ˆ๋‹ค. ์ด๋ ‡๊ฒŒ ๊ตฌํ˜„์„ ํ•˜๊ฒŒ ๋˜๋ฉด ์œ„์—์„œ ์ œ์‹œํ•œ rotation ์—ฐ์‚ฐ์œผ๋กœ ์ธ์ž์˜ ์•ž ๋’ค๋กœ ๋ถ™์ด๊ณ  ๋ฏธ๋Š” ๊ณผ์ •์ด ํ•„์š” ์—†๊ณ  ๊ทธ์ € ์ด์ „ ์ธ๋ฑ์Šค์— ํ•ด๋‹นํ•˜๋Š” ๊ณต๊ฐ„์— ๊ฐ’์„ ๊ธฐ๋กํ•˜๊ธฐ๋งŒ ํ•˜๋ฉด ๋˜๋ฏ€๋กœ ๋ฌธ์ œ๊ฐ€ ๋˜์ง€ ์•Š๋Š”๋‹ค. ํ•˜์ง€๋งŒ ์—ฌ์ „ํžˆ push ์—ฐ์‚ฐ์œผ๋กœ ์ธํ•œ ๋‚จ์€ ๊ณต๊ฐ„์— ๋Œ€ํ•œ ๋‚ญ๋น„๊ฐ€ ์žˆ๋‹ค๋Š” ์ ์€ ํ•ด๊ฒฐ๋˜์ง€ ์•Š์„ ๊ฒƒ ๊ฐ™์•˜๋‹ค. ๋”๊ตฐ๋‹ค๋‚˜ ๋ฑ์€ ๋ธ”๋ก์ด๋ผ๋Š” ๊ตฌ์กฐ ๋•Œ๋ฌธ์— ์ผ๋ฐ˜์ ์ธ ์ž๋ฃŒ๊ตฌ์กฐ๋ณด๋‹ค ๋” ํฐ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์ฐจ์ง€ํ•˜๋ฉฐ ์‹œ๊ฐ„ ์ƒ์˜ ๋“์„ ๋ณด๋Š” ๊ตฌ์กฐ์ด๋ฏ€๋กœ ๋‹จ์ˆœํžˆ ์ •ํ•ด์ง„ ํฌ๊ธฐ์˜ ๊ณต๊ฐ„๋งŒ ๋‚ญ๋น„ ๋˜๋Š” ๊ฒƒ์ด ์•„๋‹ˆ๋ผ ์‚ฌ์šฉํ•˜๊ณ  ์žˆ๋Š” ๊ณต๊ฐ„ ์™ธ์˜ ๋‚˜๋จธ์ง€ ๊ณต๊ฐ„์— ๋Œ€ํ•ด ์†Œ๋ชจ๊ฐ€ ์žˆ์„ ์ˆ˜ ์žˆ์–ด์„œ ํ›„๋ณด์ง€์—์„œ ์ œ์™ธ์‹œ์ผฐ๋‹ค.
๊ฒฐ๊ณผ์ ์œผ๋กœ ์ผ๋ฐ˜์ ์ธ Stack์„ ๊ตฌํ˜„ํ•˜๋Š” ๊ฒƒ์ฒ˜๋Ÿผ ๋ฆฌ์ŠคํŠธ๋ฅผ ์ด์šฉํ•˜๊ธฐ๋กœ ํ–ˆ๋‹ค. rotation ์—ฐ์‚ฐ์„ ๊ณ ๋ คํ•ด์„œ ์ˆœํšŒ ๊ตฌ์กฐ๋กœ ๊ตฌํ˜„ํ•  ๊ณ„ํš์ด์—ˆ๊ณ , ๊ฐ Node๋ฅผ Single๋กœ ์—ฐ๊ฒฐํ• ์ง€ Double๋กœ ์—ฐ๊ฒฐํ• ์ง€๋งŒ ์ •ํ•˜๋ฉด ๋˜์—ˆ๋‹ค. ๊ฒฐ๊ณผ์ ์œผ๋กœ๋Š” Double๋กœ ๊ตฌํ˜„์„ ํ–ˆ๋Š”๋ฐ, ์ƒ๊ฐํ•ด๋ณด๋ฉด Single๋กœ๋„ ์ถฉ๋ถ„ํ–ˆ์„ ๊ฒƒ ๊ฐ™๋‹ค.
๊ตฌํ˜„ ์ดˆ๊ธฐ์—๋Š” Single๋กœ ๋‘๊ณ  ์ง„ํ–‰ํ–ˆ์ง€๋งŒ, ์ฝ”๋“œ๋ฅผ ์ž‘์„ฑํ•˜๋Š” ๊ณผ์ •์—์„œ ๋กœ์ง์„ ๋งŽ์ด ๋’ค์—Ž๋‹ค๋ณด๋‹ˆ Double๋กœ ๋ฐ”๊พธ์—ˆ๋‹ค๊ฐ€ Single๋กœ ๋ฐ”๊พธ์—ˆ๋‹ค๊ฐ€ ํ•˜๋Š” ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•˜๊ฒŒ ๋˜์—ˆ๋‹ค. ์–ด๋–ค ๋กœ์ง์œผ๋กœ ๊ฒฐ๊ณผ๋ฅผ ๋‚ผ์ง€ ๋ชจ๋ฅด๋Š” ์ƒํ™ฉ์ด์–ด์„œ Double๋กœ ์ง„ํ–‰์„ ํ–ˆ๋‹ค๊ฐ€ ์ด ํ˜•ํƒœ ๊ทธ๋Œ€๋กœ ๋†”๋‘๊ฒŒ ๋˜์—ˆ๋‹ค. ํ”„๋กœ์ ํŠธ๋ฅผ ๋งˆ์นœ ํ›„์— ๋ณด๋‹ˆ Single๋กœ ํ•ด๋„ ๋ฌด๋ฐฉํ•œ ๋กœ์ง์ด์—ˆ๋˜ ๊ฒƒ ๊ฐ™์€๋ฐ Double๋กœ ํ•œ ๊ฒƒ์ด ๋งŽ์ด ์•„์‰ฌ์› ๋‹ค.

3) Sorting

1. Divide and Conquer (ver. 1)

๊ธฐ๋ณธ์ ์œผ๋กœ ํ‰๊ฐ€ ๊ธฐ์ค€์—์„œ ์ œํ•œํ•˜๋Š” ๋ช…๋ น์–ด์˜ ์ œํ•œ์„ ๋งž์ถ”๊ธฐ ์œ„ํ•ด์„  O(n2)O(n^2)์˜ ๋ฐฉ๋ฒ•์œผ๋กœ๋Š” ๋งž์ถœ ์ˆ˜ ์—†๊ธฐ ๋•Œ๋ฌธ์— O(nlogn)O(nlogn)์˜ ๋ฐฉ๋ฒ•์„ ์ฐพ์•„๋ณด์•„์•ผ ํ•œ๋‹ค. O(nlogn)O(nlogn)์€ nn๊ฐœ์˜ ์ธ์ž๋“ค์— ๋Œ€ํ•œ ๊ฒฐ๊ณผ์ด๋ฏ€๋กœ ๊ฐ„๋‹จํ•˜๊ฒŒ ์ƒ๊ฐํ•ด์„œ 1๊ฐœ์˜ ์ธ์ž๋Š” lognlogn ์ •๋„๋กœ ์ฒ˜๋ฆฌ ๋˜์–ด์•ผ ํ•จ์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค.
๋”ฐ๋ผ์„œ ๊ฐ€์žฅ ๋จผ์ € ๋– ์˜ฌ๋ฆฐ ๋ฐฉ์‹์€ Divide and Conquer (๋ถ„ํ•  ์ •๋ณต)์ด์—ˆ๋‹ค. ์ ˆ๋ฐ˜์„ ๋‚˜๋ˆ„์–ด B Stack์œผ๋กœ ๋ฐ€๊ณ  ๋‚จ์€ ์ ˆ๋ฐ˜์„ A Stack์—์„œ ์ •๋ ฌํ•˜๊ณ , A Stack ์ •๋ ฌ์„ ์œ„ํ•ด ๋‹ค์‹œ ์ ˆ๋ฐ˜์„ ๋‚˜๋ˆ„์–ด B Stack์œผ๋กœ ๋ฐ€๊ณ  ๋‚จ์€ ์ ˆ๋ฐ˜์„ A Stack์—์„œ ์ •๋ ฌํ•˜๊ณ ... ํŠน์ • ๊ฐœ์ˆ˜๊ฐ€ ๋˜์–ด ์ •๋ ฌ์„ ํ•  ์ˆ˜ ์žˆ์„ ๋•Œ๊นŒ์ง€ ์žฌ๊ท€์ ์œผ๋กœ ์ •๋ ฌ ํ•จ์ˆ˜๋ฅผ ํ˜ธ์ถœํ•˜๋Š” ์‹์œผ๋กœ ๊ตฌ์ƒ์„ ํ–ˆ๋‹ค.
์œ„์™€ ๊ฐ™์€ ๋ฐฉ์‹์œผ๋กœ ์ž‘์„ฑ์„ ํ–ˆ์„ ๋•Œ, ์ƒ๋‹นํžˆ ๋งŒ์กฑ์Šค๋Ÿฝ์ง€ ๋ชปํ•œ ๊ฒฐ๊ณผ๊ฐ€ ๋‚˜์™”๋‹ค. 100๊ฐœ์งœ๋ฆฌ ์ธ์ž์™€ 500๊ฐœ์งœ๋ฆฌ ์ธ์ž์—์„œ ์•„์˜ˆ ์ ์ˆ˜๋ฅผ ๋ชป ๋ฐ›์„ ๋งŒํผ์ด์—ˆ๋˜ ๊ฒƒ์œผ๋กœ ๊ธฐ์–ตํ•œ๋‹ค. ์ตœ์ ํ™”๋ฅผ ํ•˜๋ฉด ์กฐ๊ธˆ ๋” ๋‚˜์„ ์ˆ˜ ์žˆ๊ฒ ์ง€๋งŒ, ์ตœ์ ํ™” ์ „๋ถ€ํ„ฐ ๋„ˆ๋ฌด ํฐ ์ฐจ์ด๋ฅผ ๋ณด์—ฌ ๋‹ค๋ฅธ ๋ฐฉ๋ฒ•์„ ๋– ์˜ฌ๋ ธ๋‹ค.

2. Divide and Conquer (ver. 2)

๋‹ค์Œ์œผ๋กœ ์ƒ๊ฐํ•œ ๊ฒƒ์ด ์ •ํ™•ํžˆ ์ ˆ๋ฐ˜์œผ๋กœ ๋‚˜๋ˆ„์–ด ํ•จ์ˆ˜๋ฅผ ํ˜ธ์ถœํ•˜๋Š” ๊ฒƒ๋ณด๋‹ค๋Š” ๊ฐ€์žฅ ๋งŽ์ด ์ •๋ ฌ์ด ๋˜์–ด ์žˆ๋Š” ๊ฐ’์„ ๊ธฐ์ค€์œผ๋กœ ์‚ผ์•„ ๋ฐ˜์„ ๋‚˜๋ˆ„๋Š” ์‹์œผ๋กœ ์žฌ๊ท€์ ์œผ๋กœ ํ•จ์ˆ˜๋ฅผ ํ˜ธ์ถœํ•˜๊ฒŒ ๋˜๋ฉด ์กฐ๊ธˆ ๋” ๋‚˜์„ ๊ฒƒ์ด๋ผ๊ณ  ์ƒ๊ฐํ–ˆ๊ณ , ์ด์ „์— ์ž‘์„ฑํ–ˆ๋˜ ๋กœ์ง์—์„œ B Stack์œผ๋กœ ๋„˜๊ธฐ๋Š” ๊ฐ’๋“ค์„ ์ด ๋ฐฉ๋ฒ•์œผ๋กœ ์ˆ˜์ •ํ–ˆ๋‹ค. ์ „๋ฐ˜์ ์œผ๋กœ ๋ช…๋ น์–ด ๋ฐ˜๋ณต ํšŸ์ˆ˜๊ฐ€ ์ค„์—ˆ์ง€๋งŒ, ์ด ์—ญ์‹œ๋„ ๋งŒ์กฑ์Šค๋Ÿฌ์šด ๊ฒฐ๊ณผ๋ฅผ ๋‚ด์ง€ ๋ชปํ–ˆ๋‹ค. ์ •ํ•ด์ง„ ๊ทœ์น™์— ๋งž์ถฐ์„œ ๋‚˜๋ˆ„๋Š” ๊ฒƒ์ด ์–ด์จŒ๋“  ์ข‹์€ ๋ฐฉํ–ฅ์œผ๋กœ ๊ฐ€๋Š” ๊ฒƒ ๊ฐ™์•„์„œ ์กฐ๊ธˆ ๋” ์ข‹์€ ๋ฐฉ๋ฒ•์„ ๊ณ ๋ฏผํ•ด๋ณด์•˜๋‹ค.

3. Divide and Conquer (ver. 3)

์ด์ „๊ณผ ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ ๊ฐ€์žฅ ๋งŽ์ด ์ •๋ ฌ๋˜์–ด ์žˆ๋Š” ๊ฐ’์„ ๊ธฐ์ค€์œผ๋กœ ์‚ผ๋Š” ๊ฒƒ์€ ๋™์ผํ•˜์ง€๋งŒ ๋ฐ˜์„ ๋‚˜๋ˆ„๋Š” ๊ฒƒ์ด ์•„๋‹ˆ๋ผ 3๋ถ„ํ• ์„ ์ƒ๊ฐํ•ด๋ƒˆ๋‹ค. ์ด์ „ ๋ฐฉ๋ฒ•์€ ์ •๋ ฌ๋˜์–ด ์žˆ๋Š” ๊ฐ’์„ ๊ธฐ์ค€์œผ๋กœ ํฐ ๊ฐ’ ํ˜น์€ ์ž‘์€ ๊ฐ’์„ ์ด์šฉํ•˜์—ฌ ์ง„ํ–‰ํ–ˆ์—ˆ๋Š”๋ฐ, ๋‘ ๊ฐ’ ์–ด๋Š ๊ฒƒ์„ ์ด์šฉํ•ด๋„ ๋ฐ˜์„ ๋‚˜๋ˆ„๋Š”๋ฐ๋Š” ๋ช…๋ น์–ด ํšŸ์ˆ˜๊ฐ€ ๋น„์Šทํ•œ ๊ฒƒ์„ ๋ณผ ์ˆ˜ ์žˆ์—ˆ๋‹ค. ์ด๋ฒˆ์—๋Š” ์ด ๋‘ ๊ฐ’์„ ๋™์‹œ์— ์ด์šฉํ•ด๋ณด๋Š” ๊ฒƒ์€ ์–ด๋–จ๊นŒํ•˜๋Š” ์ƒ๊ฐ์ด ๋“ค์—ˆ๋‹ค. ์ด ๋ฐฉ๋ฒ•์€ minckim๋‹˜๊ป˜์„œ ์ž‘์„ฑํ•˜์‹  ๋ฐฉ๋ฒ•๊ณผ ๊ทธ ๋ฐฉ๋ฒ•์ด ๋Œ€์ฒด์ ์œผ๋กœ ๊ต‰์žฅํžˆ ๋น„์Šทํ•˜๋‹ค.
3๋ถ„ํ• ์„ ํ•ด๋†“์€ chunk๋“ค์ด ์ •๋ ฌ๋˜๊ธฐ ์œ„ํ•ด์„  ๊ฐ€์žฅ ํฐ chunk๋ฅผ A Stack์— ๋‘๊ณ , ์ด๋ฅผ ์ •๋ ฌํ•˜๊ธฐ ์œ„ํ•ด ์žฌ๊ท€๋ฅผ ํ˜ธ์ถœํ•˜๋Š” ๋ฐฉ์‹์ด ๋œ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ์žฌ๊ท€๋ฅผ ๋ฐ˜๋ณตํ•˜๊ฒŒ ๋˜๋ฉด ์ค‘๊ฐ„ chunk๋ฅผ B Stack์˜ ๋’ค์— ๋‘๊ณ , ๊ฐ€์žฅ ์ž‘์€ chunk๋ฅผ B Stack์˜ ์•ž์— ๋‘๋„๋กํ•˜์—ฌ ์Œ“์ด๊ฒŒ ๋œ๋‹ค. ์ดํ›„์— A Stack์— ์ •๋ ฌ์„ ๋งˆ์น˜๊ฒŒ ๋˜๋ฉด Call-Tree์—์„œ ํ˜ธ์ถœ์„ ํšŒ์ˆ˜ํ•˜๋ฉด์„œ B Stack์— ์Œ“์ธ chunk๋“ค์„ A Stack์œผ๋กœ ์˜ฎ๊ฒจ์ฃผ์–ด์•ผ ํ•˜๊ณ , ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ ์ •๋ ฌ์ด ๋œ chunk๋ฅผ A Stack์œผ๋กœ ์˜ฎ๊ธฐ๊ฑฐ๋‚˜ A Stack์œผ๋กœ ์˜ฎ๊ธด ๋’ค์— ํ•ด๋‹น chunk๋ฅผ ์ •๋ ฌํ•˜๋Š” ๊ณผ์ •์ด ํ•„์š”ํ•˜๋‹ค. ์ด๋ ‡๊ฒŒ ์˜ฎ๊ฒจ์ง„ chunk๊ฐ€ ์ •๋ ฌ์ด ๋˜์—ˆ๋‹ค๊ณ  ํ•ด์„œ A Stack ์ „์ฒด๊ฐ€ ์ •๋ ฌ์ด ๋œ ํ˜•ํƒœ๋Š” ์•„๋‹ ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ, A Stack ์ „์ฒด๋ฅผ ๋‹ค์‹œ ์ •๋ ฌํ•˜๊ธฐ ์œ„ํ•ด ์žฌ๊ท€๋ฅผ ํ˜ธ์ถœํ•˜๋Š” ๊ตฌ์กฐ๋ฅผ ๊ฐ€์ ธ์•ผ ํ•œ๋‹ค.
์ด์ „ ๋ถ„ํ•  ์ •๋ณต๊ณผ ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ ๋ช…๋ น์–ด ํšŸ์ˆ˜์— ํฐ ์ฐจ์ด๋Š” ์—†์—ˆ๋‹ค. ์ „์ฒด์ ์œผ๋กœ ์ •๋ ฌ์ด ๋˜์–ด ์žˆ๋Š”์ง€ ํ™•์ธํ•˜๋ฉด์„œ ์ถ”๊ฐ€์ ์œผ๋กœ ์žฌ๊ท€๋ฅผ ํ˜ธ์ถœํ•˜๋Š” ํšŸ์ˆ˜๊ฐ€ ๋งŽ์•˜๊ณ , ์ด์— ๋”ฐ๋ผ ๋ถˆํ•„์š”ํ•˜๊ฒŒ ํ˜ธ์ถœ๋˜๋Š” push์™€ swap๋“ค์ด ๋งŽ์•˜๋‹ค. ์ถ”๊ฐ€์ ์ธ ์ตœ์ ํ™”๋ฅผ ํ•˜๋ฉด ๋ช…๋ น์–ด๊ฐ€ ๋งŽ์ด ์ค„์–ด๋“ค๊นŒ ์‹ถ์€ ์ƒ๊ฐ์ด ๋“ค์—ˆ๋Š”๋ฐ, ๊ฒฐ๊ตญ์—๋Š” ํฌ๊ธฐํ•˜๊ณ  ๋‹ค๋ฅธ ๋ฐฉ๋ฒ•์„ ์ฐพ์•„๋‚˜์„ฐ๋‹ค.
์ด ๋ฐฉ๋ฒ•์œผ๋กœ ๋ช…๋ น์–ด๋“ค์„ ์ •ํ•ด์ง„ ํšŸ์ˆ˜์— ๋งŒ์กฑ์‹œํ‚ค๋„๋ก ์ฝ”๋“œ๋ฅผ ์ž‘์„ฑํ•œ ๋ถ„๋“ค๊ป˜์„œ๋Š” ์ตœ์ ํ™”๋ฅผ ๊ต‰์žฅํžˆ ์ž˜ํ•œ ๊ฒƒ์ด๋ผ๊ณ  ์ƒ๊ฐ์ด ๋“œ๋Š”๋ฐ, ์–ด๋–ป๊ฒŒ ์ตœ์ ํ™” ํ–ˆ๋Š”์ง€ ๊ฐœ์ธ์ ์œผ๋กœ ๋ฌด์ฒ™ ๊ถ๊ธˆํ•˜๋‹ค.
์ด์™€ ๊ฐ™์€ ์ฆ์ƒ์ด ๋ฐœ์ƒํ–ˆ๋˜ ์ด์œ ๋ฅผ ์•Œ๊ฒŒ ๋˜์—ˆ๋‹ค. Pivotting์— ๋ฌธ์ œ๊ฐ€ ์žˆ์—ˆ๋˜ ๊ฒƒ์ด๋‹ค. 13\frac{1}{3}, 23\frac{2}{3} ์ง€์ ์— ๋ฐ”๋กœ Pivotting์„ ํ•˜๋Š” ๊ฒƒ๋ณด๋‹ค, ์ •๋ ฌํ•˜๋ ค๋Š” ๊ตฌ๊ฐ„์˜ ์ •๋ ฌ๋œ ๊ฐ’์— ๋Œ€ํ•ด์„œ 13\frac{1}{3}, 23\frac{2}{3} ์ง€์ ์„ Pivotting์„ ํ•˜๋ฉด ๋ถˆํ•„์š”ํ•œ push์™€ swap๋“ค์„ ์ •๋ง ๋งŽ์ด ์—†์•จ ์ˆ˜ ์žˆ์—ˆ๋‹ค. Pivotting์˜ ์ค‘์š”์„ฑ์„ ๋‹ค์‹œ ํ•œ ๋ฒˆ ๊นจ๋‹ฌ์„ ์ˆ˜ ์žˆ์—ˆ๋‹ค. ์ดˆ๋ฐ˜์—๋Š” ์™œ ์ •๋ ฌ๋œ ์ƒํƒœ์˜ ์ง€์  ๊ฐ’์„ ์ด์šฉํ•  ์ƒ๊ฐ์„ ์•ˆํ–ˆ๋Š”์ง€ ๋ชจ๋ฅด๊ฒ ๋‹ค ใ…Žใ…Ž...

4. Predicate

๋ฆฌํ”„๋ ˆ์‰ฌ๋ฅผ ํ•  ๊ฒธ ์—ฌ๋Ÿฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜๋“ค์„ ์ฐพ์•„๋ณด๋‹ค๊ฐ€ ๊ฒฐ๊ตญ์— Quick Sort์˜ ํŠน์„ฑ์„ ๋‹ค์‹œ ํ•œ ๋ฒˆ ์ƒ๊ฐํ•ด๋ณด๊ฒŒ ๋˜์—ˆ๋‹ค.
Quick Sort๋Š” ๋‹ค๋ฅธ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ ๋‹ฌ๋ฆฌ ๊ณ ์ •์ ์œผ๋กœ O(nlogn)O(nlogn)์ด๋ผ๋Š” ์„ฑ๋Šฅ์„ ๋ณด์žฅํ•˜์ง€ ์•Š๊ณ , ํ‰๊ท ์ ์œผ๋กœ O(nlogn)O(nlogn)์˜ ์„ฑ๋Šฅ์„ ๋‚ธ๋‹ค. ์ฆ‰, Worst Case์—๋Š” O(n2)O(n^2)์ด ๋˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ผ๋Š” ๊ฒƒ์ด๋‹ค. ๊ทธ๋Ÿผ์—๋„ Quick Sort๊ฐ€ ์ถฉ๋ถ„ํžˆ ๋น ๋ฅธ ์ •๋ ฌ์ธ ์ด์œ ๋Š” ๋‹ค๋ฅธ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜๋“ค์ฒ˜๋Ÿผ ๊ณ ์ •๋œ ๋ฐฉ์‹์œผ๋กœ ์ •๋ ฌ์„ ์ˆ˜ํ–‰ํ•˜๋Š” ๊ฒƒ์ด ์•„๋‹ˆ๋ผ, ์ •๋ ฌ์„ ์ˆ˜ํ–‰ํ•˜๋ ค๋Š” ๊ฐ’๋“ค์— ์˜์กดํ•˜๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค. ์ •๋ ฌ์„ ์ˆ˜ํ–‰ํ•˜๋ ค๋Š” ๊ฐ’๋“ค์ด ์–ผ๋งŒํผ ์ •๋ ฌ์ด ๋˜์–ด ์žˆ๋Š”์ง€๊ฐ€ ํฐ ์˜ํ–ฅ์„ ๋ผ์น˜๊ฒŒ ๋œ๋‹ค.
๋˜ ๋‹ค๋ฅธ ํŠน์„ฑ์œผ๋กœ๋Š” Quick Sort ์ž์ฒด๊ฐ€ Stack์„ ์ด์šฉํ•˜์—ฌ ์ •๋ ฌ์„ ์ˆ˜ํ–‰ํ•˜๊ฒŒ ๋˜๊ณ  ์ด ๋•Œ ์‚ฌ์šฉ๋˜๋Š” ์—ฐ์‚ฐ๋“ค์ด ์ด๋ฒˆ ํ”„๋กœ์ ํŠธ์—์„œ ์‚ฌ์šฉ๋˜๋Š” ์—ฐ์‚ฐ๋“ค๊ณผ ๋Œ€์ฒด์ ์œผ๋กœ ์œ ์‚ฌํ•˜๋‹ค๋Š” ๊ฒƒ์ด์—ˆ๋‹ค. Quick Sort์—์„œ ์‚ฌ์šฉํ•˜๋Š” Stack์ด ์ผ๋ฐ˜์ ์ธ Stack์ด ์•„๋‹ˆ๋ผ ์‚ฌ์šฉ์ž๊ฐ€ ์ •์˜ํ•œ Stack์„ ์ด์šฉํ•˜์—ฌ ๊ตฌํ˜„ํ•œ ๊ฒฝ์šฐ์—๋Š” ์กฐ๊ธˆ ๋” ๋‚˜์€ ์„ฑ๋Šฅ์„ ๋ณด์ผ ์ˆ˜ ์žˆ๋‹ค๋Š” ์–˜๊ธฐ๊ฐ€ ๋– ์˜ฌ๋ผ, ์ด๋ฒˆ ๊ณผ์ œ๊ฐ€ ์ •๋ง ํฐ ํ‹€ ์•ˆ์—์„œ Quick Sort์™€ ๋‹ค๋ฅผ ๊ฒƒ์ด ์—†๊ตฌ๋‚˜ ์‹ถ์—ˆ๋‹ค. push_swap์—์„œ๋Š” ํŠน์ • ๋ช…๋ น์–ด๋ฅผ ์ˆ˜ํ–‰ํ•  ์ˆ˜ ์žˆ๋Š” ์‚ฌ์šฉ์ž ์ •์˜ Stack์ด ์žˆ์œผ๋ฏ€๋กœ, ์ด๋ฅผ ์ด์šฉ ํ–ˆ์„ ๋•Œ ์—ฐ์‚ฐ์ด ๋†’๊ฒŒ ๋‚˜์˜ฌ๋งŒํ•œ ์›์ธ์„ ์ฐพ์•„๋ณด๊ฒŒ ๋˜์—ˆ๋‹ค. ์ด์ „๊นŒ์ง€์˜ ๊ตฌํ˜„ ๋ฐฉ๋ฒ•๋“ค์„ ๋ณด๋ฉด, push์™€ swap์„ ์ด์šฉํ–ˆ์„ ๋•Œ ๋Œ€์ฒด์ ์œผ๋กœ ๊ฐ Stack์ด Mess-Up๋˜์–ด ๋‹ค์‹œ ์žฌ๊ท€๋ฅผ ํ˜ธ์ถœํ•˜๊ณ  ๊ทธ ํ˜ธ์ถœ ํšŸ์ˆ˜๊ฐ€ ๋งŽ์•„์ง€๋Š” ๋Š๋‚Œ์„ ๋งŽ์ด ๋ฐ›์•˜์—ˆ๋‹ค.
์–ผ๋งŒํผ ์ •๋ ฌ์ด ๋˜์–ด ์žˆ๋Š”๊ฐ€์™€ ๋ช…๋ น์–ด ํšŸ์ˆ˜๋ฅผ ๋†’๊ฒŒ ๋งŒ๋“œ๋Š” ๋ช…๋ น์–ด๋ฅผ ๊ณ ๋ คํ•ด์„œ ๋กœ์ง์„ ๋– ์˜ฌ๋ ค๋ณด๊ธฐ๋กœ ํ–ˆ๋‹ค. ๊ทธ๋ ‡๊ฒŒ ๋– ์˜ค๋ฅธ ๋ฐฉ์‹์ด ์ˆ˜ํ–‰ํ•˜๊ฒŒ ๋  ๋ช…๋ น์–ด๊ฐ€ ๊ฐ€์žฅ ์ ์€ ๊ฐ’์„ ์ด์šฉํ•˜๋Š” ๋ฐฉ์‹์ด์—ˆ๋‹ค.
๊ฐ€์žฅ ๋งŽ์ด ์ •๋ ฌ์ด ๋˜์–ด ์žˆ๋Š” ๊ตฌ๊ฐ„์„ ์ฐพ์•„๋‚ด๊ณ , ๊ทธ ๊ตฌ๊ฐ„์„ A Stack์˜ ๋ฐ”๋‹ฅ์— ์œ„์น˜ํ•  ์ˆ˜ ์žˆ๋„๋ก rotation์„ ์ˆ˜ํ–‰ํ•œ๋‹ค. ์ด ๋•Œ CW (clock-wise)๋กœ ๋Œ๋ฆด์ง€, CCW (counter clock-wise)๋กœ ๋Œ๋ฆด์ง€๋Š” ์ ์ ˆํžˆ ํŒ๋‹จํ•˜์—ฌ ์ˆ˜ํ–‰ํ•  ์ˆ˜ ์žˆ๋„๋ก ๋งŒ๋“ ๋‹ค. ์ด์™€ ๊ฐ™์ด ์ •ํ•ด์ง„ ์œ„์น˜์˜ ๊ฐ’์„ A Stack์˜ ๊ฐ€์žฅ ์•„๋ž˜์— ๊น”์•„๋‘๋Š” ๊ณผ์ •์„ Correction์ด๋ผ ํ•˜๊ฒ ๋‹ค. Correction์„ ๊ฑฐ์น˜๊ฒŒ ๋˜๋ฉด ์œ„ ๊ทธ๋ฆผ์ฒ˜๋Ÿผ ๊ฐ€์žฅ ๋งŽ์ด ์ •๋ ฌ๋˜์–ด ์žˆ๋Š” ๊ตฌ๊ฐ„์€ ์•„๋ž˜๋กœ ๊น”๋ฆฌ๊ณ  ๋‚˜๋จธ์ง€ ๊ฐ’๋“ค์€ A Stack์˜ ์œ„์— ์œ„์น˜ํ•˜๊ฒŒ ๋˜๋Š”๋ฐ, ๊ทธ ๋‹ค์Œ์—๋Š” ๊ตฌ๊ฐ„ ์™ธ์˜ ๊ฐ’๋“ค์„ ๋ชจ๋‘ B Stack์œผ๋กœ ๋„˜๊ธฐ๋Š” A to B๋ฅผ ์ˆ˜ํ–‰ํ•œ๋‹ค.
์ด์ œ๋Š” A to B๋กœ ๋„˜์–ด์˜จ ์ธ์ž๋“ค์„ ํ•˜๋‚˜ ํ•˜๋‚˜ A Stack์œผ๋กœ ๋„˜๊ฒจ์ฃผ๋Š” ๊ณผ์ •์ด ํ•„์š”ํ•œ๋ฐ, ์ด๋ฅผ B to A๋ผ๊ณ  ํ•ด๋ณด์ž. ์ด ๋•Œ B Stack์— ์œ„์น˜ํ•œ ๊ฐ’๋“ค์ด A Stack์˜ ์ œ ์œ„์น˜๋กœ ์ฐพ์•„๊ฐ€๊ธฐ ์œ„ํ•œ ๋ช…๋ น์–ด ํšŸ์ˆ˜๋ฅผ ๋ฏธ๋ฆฌ ๊ณ„์‚ฐํ•ด๋ณด๊ณ  ๊ฐ€์žฅ ์ ๊ฒŒ ์†Œ์š”๋˜๋Š” ์ธ์ž๋ฅผ A Stack์— ์˜ฎ๊ธฐ๋„๋ก ๋งŒ๋“ ๋‹ค. ์ด๋ฅผ B Stack์— ์žˆ๋Š” ๊ฐ’๋“ค์ด ์—†์–ด์งˆ ๋•Œ๊นŒ์ง€ ๋ฐ˜๋ณตํ•˜๋ฉด ๋œ๋‹ค. ์—ฌ๊ธฐ์„œ B Stack์˜ ๊ฐ ์ธ์ž๋“ค์ด ์‚ฌ์šฉํ•  ๋ช…๋ น์–ด ํšŸ์ˆ˜ ๋“ฑ์˜ ์ •๋ณด๋ฅผ ๊ณ„์‚ฐํ•œ ๊ฒƒ์„ Predicate์ด๋ผ ํ•œ๋‹ค.
์ด์™€ ๊ฐ™์ด ํ•˜๋ฉด A Stack์— ์ •๋ ฌ๋˜์–ด ์žˆ๋Š” ๊ฐ’๋“ค์ด xx๊ฐœ๋ผ๊ณ  ํ–ˆ์„ ๋•Œ pa์™€ pb๋ฅผ ํ˜ธ์ถœํ•˜๋Š” ํšŸ์ˆ˜๋Š” 2(nโˆ’x)2(n - x)๊ฐ€ ๋˜๊ณ , ๊ฐ’์„ ํ™•์ •์ ์œผ๋กœ ์˜ฎ๊ธธ ๋•Œ ์™ธ์—๋Š” push๋Š” ์‚ฌ์šฉ๋˜์ง€ ์•Š๋Š”๋‹ค. ๋˜ํ•œ ์ ์€ ์ธ์ž๋ฅผ ์ •๋ ฌํ•˜๋Š” ๊ฒƒ์ด ์•„๋‹ˆ๋ผ๋ฉด ์ด์™€ ๊ฐ™์€ ์ผ๋ฐ˜์ ์ธ ์ธ์ž๋“ค์„ ์ •๋ ฌํ•  ๋•Œ๋Š” ๋ณ„๋„์˜ swap์ด ์‚ฌ์šฉ๋˜์ง€ ์•Š๋Š”๋‹ค. ๋”ฐ๋ผ์„œ ์ˆœ์ˆ˜ํ•˜๊ฒŒ rotation๋งŒ์œผ๋กœ ์ •๋ ฌ์„ ์ˆ˜ํ–‰ํ•˜๊ฒŒ ๋˜๊ณ , ์ด๋Š” rotation ์ˆ˜ํ–‰ ์ „์— ๋ช…๋ น์–ด๋ฅผ ํŒŒ์•…ํ•  ๋•Œ cw ํ˜น์€ ccw ์ค‘ ๋” ์ž‘์€ ๊ฐ’์œผ๋กœ ๋ช…๋ น์–ด๋ฅผ ์ˆ˜ํ–‰ํ•  ์ˆ˜ ์žˆ๊ฒŒ ๋œ๋‹ค. ๋”ฐ๋ผ์„œ rotation์— ๋Œ€ํ•ด์„œ๋Š” ๋ณ„๋„์˜ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ํ• ๋‹น๋ฐ›๊ณ  ํ›„์ฒ˜๋ฆฌ๋ฅผ ํ•˜๋Š” ์‹์œผ๋กœ ์ตœ์ ํ™”๋ฅผ ํ•˜์ง€ ์•Š์•„๋„ ๋œ๋‹ค.
ํƒ์ƒ‰ ๋ฐฉ์‹์€ 1ํšŒ์ฐจ์—๋Š” (nโˆ’x)(n - x)๋ฒˆ, 2ํšŒ์ฐจ์—๋Š” (nโˆ’xโˆ’1)(n - x - 1)๋ฒˆ, ... , nโˆ’xn - xํšŒ์ฐจ์—๋Š” 1๋ฒˆ์ด ๋˜์–ด Big-O Notation์œผ๋กœ๋Š” O(n2)O(n^2)์ด ๋˜์ง€๋งŒ, ์‹ค์ œ๋กœ๋Š” ์ˆœ์ˆ˜ํ•œ n2n^2 ๋ณด๋‹ค๋Š” ์ ์€ ์—ฐ์‚ฐ์ด ๋Œ์•„๊ฐ€๋ฉด์„œ A Stack ๋‚ด์˜ ์ธ์ž๋“ค์ด ๋งŽ์ด ์ •๋ ฌ์ด ๋˜์–ด ์žˆ์„์ˆ˜๋ก ๋” ์ ์€ ์‹œ๊ฐ„์ด ์†Œ์š”๋œ๋‹ค. ๋ช…๋ น์–ด ์ˆ˜ํ–‰ ์ธก์ •์—๋Š” ํƒ์ƒ‰ ๊ณผ์ •์ด ํฌํ•จ๋˜์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ์— ๋ช…๋ น์–ด ์ˆ˜ํ–‰ ํšŸ์ˆ˜๋ฅผ ๋”ฐ๋กœ ์ƒ๊ฐํ•˜์—ฌ n2n^2์ฒ˜๋Ÿผ ๋™์ž‘ํ•˜๋Š”์ง€ ์ƒ๊ฐํ•ด๋ด์•ผ ํ•˜๋Š”๋ฐ ์ด ์—ญ์‹œ๋„ n2n^2์— ๋ฏธ์น˜์ง€ ์•Š๋Š”๋‹ค๋Š” ๊ฒƒ์„ ๋– ์˜ฌ๋ฆด ์ˆ˜ ์žˆ๋‹ค. ์˜์‚ฌ ์ฝ”๋“œ๋Š” ์•„๋ž˜์™€ ๊ฐ™๋‹ค.
// pseudo-code func do_before_sort() { // ๊ฐ€์žฅ ๊ธธ๊ฒŒ ์ •๋ ฌ๋˜์–ด ์žˆ๋Š” ๊ตฌ๊ฐ„์„ ์ฐพ๋Š”๋‹ค. find_longest_sort() // ์ฐพ์€ ์œ„์น˜๋ฅผ ํ† ๋Œ€๋กœ ํ•ด๋‹น ๊ตฌ๊ฐ„์ด A Stack ๊ฐ€์žฅ ์•„๋ž˜์— ์œ„์น˜ํ•  ์ˆ˜ ์žˆ๋„๋ก rotation์„ ์ˆ˜ํ–‰ํ•œ๋‹ค. // rotation์€ ๊ตฌ๊ฐ„์˜ ๋ index + 1์ด A Stack ์ ˆ๋ฐ˜๋ณด๋‹ค ํฐ ์ง€ ์ž‘์€ ์ง€ ํŒ๋ณ„ํ•˜์—ฌ cw, ccw๋ฅผ ์ˆ˜ํ–‰ํ•œ๋‹ค. stack_correction() // Stack Correction ์ดํ›„์— ๊ฐ€์žฅ ๊ธธ๊ฒŒ ์ •๋ ฌ๋˜์–ด ์žˆ๋Š” ๊ตฌ๊ฐ„์˜ index๊ฐ€ ๋ฐ”๋€Œ์–ด ์žˆ์„ ์ˆ˜๋„ ์žˆ๋‹ค. // ๋”ฐ๋ผ์„œ ๊ตฌ๊ฐ„ ๊ฒ€์ƒ‰์„ ๋‹ค์‹œ ํ•œ ๋ฒˆ ํ•ด์ฃผ์–ด a_to_b ํ˜ธ์ถœ ์‹œ ์ด๋ฏธ ์ •๋ ฌ๋˜์–ด ์žˆ๋Š” ๊ฐ’์ด B Stack์œผ๋กœ ๊ฐ€์ง€ ์•Š๋„๋ก ํ•œ๋‹ค. find_longest_sort() } func a_to_b() { while A Stack์˜ ๋ชจ๋“  lst์— ๋Œ€ํ•ด์„œ if current lst index < ์ •๋ ฌ๋˜์–ด ์žˆ๋Š” ๊ตฌ๊ฐ„์˜ ์‹œ์ž‘ index do pb } func b_to_a() { do ์ž„์‹œ predicate ์ดˆ๊ธฐํ™” while B Stack์˜ lst๊ฐ€ ์กด์žฌํ•˜์ง€ ์•Š์„ ๋•Œ๊นŒ์ง€ { do ์ตœ์†Œ predicate ์ดˆ๊ธฐํ™” while B Stack์˜ ๋ชจ๋“  lst์— ๋Œ€ํ•ด์„œ { do current lst์— ๋Œ€ํ•ด ์†Œ์š”๋˜๋Š” ๋ช…๋ น์–ด ํšŸ์ˆ˜๋ฅผ ์ž„์‹œ predicate์— ๊ธฐ๋ก if ์ตœ์†Œ predicate > ์ž„์‹œ predicate ์ตœ์†Œ predicate := ์ž„์‹œ predicate } do predicate์— ๊ธฐ๋ก๋œ ํšŸ์ˆ˜๋งŒํผ A Stack๊ณผ B Stack์„ rotation do pa } } func sort_3() { // do_before_sort์—์„œ ์ด๋ฏธ ์ตœ์†Œ 2๊ฐœ๋Š” ์ •๋ ฌ์ด ๋˜์–ด ์žˆ๋‹ค. // ๋”ฐ๋ผ์„œ do_before_sort ๊ณผ์ • ์ดํ›„์—๋„ ์ •๋ ฌ์ด ์•ˆ ๋˜์–ด ์žˆ๋Š” ๊ฒฝ์šฐ๋Š” ์ด 2๊ฐ€์ง€๋‹ค. // 2 1 3 -> sa ์ˆ˜ํ–‰ if current lst val > next lst val && current lst val < next next lst val do sa // 3 1 2 -> ra ์ˆ˜ํ–‰ else if current lst val > next next val do ra } func sort_5() { // A Stack์˜ ๊ธธ์ด๊ฐ€ 4์ธ ๊ฒฝ์šฐ์—๋Š” do_before_sort์—์„œ ์ฐพ์€ ๊ตฌ๊ฐ„์˜ ํฌ๊ธฐ๊ฐ€ 2, 3์ด ๋œ๋‹ค. // A Stack์˜ ๊ธธ์ด๊ฐ€ 5์ธ ๊ฒฝ์šฐ์—๋Š” do_before sort์—์„œ ์ฐพ์€ ๊ตฌ๊ฐ„์˜ ํฌ๊ธฐ๊ฐ€ 2, 3, 4๊ฐ€ ๋œ๋‹ค. // 3๊ฐœ์งœ๋ฆฌ ์ •๋ ฌ ๋กœ์ง์ด ์žˆ์œผ๋ฏ€๋กœ ํ˜„์žฌ ํ•จ์ˆ˜์—์„œ ์ตœ๋Œ€ํ•œ 3๊ฐœ์งœ๋ฆฌ ์ •๋ ฌ ๋กœ์ง์„ ํ™œ์šฉํ•œ๋‹ค. // ๊ตฌ๊ฐ„์˜ ํฌ๊ธฐ๊ฐ€ 2์ธ ๊ฒฝ์šฐ์—๋Š” A Stack์— ์ธ์ž๋ฅผ 3๊ฐœ๊ฐ€ ๋˜๋„๋ก ๋งŒ๋“ค๊ณ  ์ด๋ฅผ ์ •๋ ฌํ•œ๋‹ค. if ์ •๋ ฌ๋œ ๊ตฌ๊ฐ„์˜ ํฌ๊ธฐ < 3 { do A Stack์— 3๊ฐœ๋งŒ ๋‚จ๊ธฐ๊ณ  B Stack์œผ๋กœ push sort_3() } // ๊ตฌ๊ฐ„์˜ ํฌ๊ธฐ๊ฐ€ 3์ด์ƒ์ธ ๊ฒฝ์šฐ์—๋Š” ๊ตฌ๊ฐ„์— ํ•ด๋‹นํ•˜์ง€ ์•Š๋Š” ๊ฐ’์„ B Stack์œผ๋กœ ๋„˜๊ธฐ๋Š” ํ•จ์ˆ˜๋ฅผ ํ˜ธ์ถœํ•œ๋‹ค. else a_to_b() // ์ด ํ›„์—๋Š” A Stack์—๋Š” ์ตœ์†Œ 3๊ฐœ ์ด์ƒ์ด ์ •๋ ฌ๋˜์–ด ์žˆ๋Š” ์ƒํƒœ๊ณ  ๋‚˜๋จธ์ง€๋Š” B Stack์— ์œ„์น˜ํ•œ๋‹ค. // ๋”ฐ๋ผ์„œ b_to_a๋ฅผ ํ˜ธ์ถœํ•˜์—ฌ B Stack์˜ ์ธ์ž๋“ค์ด A Stack์— ์ œ ์œ„์น˜์— ์žˆ๋„๋ก ๋งŒ๋“ค์–ด์ค€๋‹ค. b_to_a() // B Stack์˜ ์ธ์ž๋“ค์„ A Stack์œผ๋กœ ์˜ฎ๊ธด ํ›„์—๋Š” ์ตœ์†Œ ์ธ์ž๊ฐ€ ๊ฐ€์žฅ ์•ž์— ์™€์žˆ์ง€ ์•Š์„ ์ˆ˜ ์žˆ๋‹ค. // ๋”ฐ๋ผ์„œ A Stack์—์„œ ๊ฐ€์žฅ ์ž‘์€ ๊ฐ’์„ ์ฐพ์•„ Stack Correction์„ ์ˆ˜ํ–‰ํ•œ๋‹ค. stack_correction() } func sort_others() { a_to_b() b_to_a() stack_correction() } func yield() { // do_before_sort์—์„œ ๊ฐ€์žฅ ๊ธธ๊ฒŒ ์ •๋ ฌ๋œ ๊ตฌ๊ฐ„์„ ์ฐพ๋Š”๋‹ค. // ์ฐพ์€ ๊ตฌ๊ฐ„์œผ๋กœ Stack Correction์„ ๊ฑฐ์น˜๋ฏ€๋กœ ์ตœ์†Œ 2๊ฐœ์˜ ์ธ์ž๋Š” ์ •๋ ฌ์ด ๋˜์–ด ์žˆ๊ฒŒ ๋œ๋‹ค. do_before_sort() if A Stack์˜ ๊ธธ์ด < 2 return else if A Stack์˜ ๊ธธ์ด == 3 sort_3() else if A Stack์˜ ๊ธธ์ด <= 5 sort_5() else sort_others() }
C

5. ํŠน์ • ๊ฐœ์ˆ˜ ์ดํ•˜์˜ ์ •๋ ฌ

2๊ฐœ์งœ๋ฆฌ๋Š” ๊ฐ€์žฅ ๊ธธ๊ฒŒ ์ •๋ ฌ๋˜์–ด ์žˆ๋Š” ๊ตฌ๊ฐ„์„ ์ฐพ๊ณ  Correction์„ ํ•˜๋Š” ๊ณผ์ •์—์„œ ์ด๋ฏธ ์ •๋ ฌ์ด ๋˜์–ด๋ฒ„๋ฆฌ๊ณ , 3๊ฐœ์งœ๋ฆฌ๋Š” Correction ํ›„ sa ํ˜น์€ ra๋งŒ์œผ๋กœ ๋๋‚˜๊ฒŒ ๋œ๋‹ค.
4๊ฐœ์งœ๋ฆฌ์™€ 5๊ฐœ์งœ๋ฆฌ๋Š” Correction ํ›„์— A Stack์— 3๊ฐœ๋งŒ ๋‚จ๊ธฐ๊ณ  ๋‚˜๋จธ์ง€๋ฅผ B Stack์œผ๋กœ ์˜ฎ๊ธด๋‹ค. ๊ทธ๋ฆฌ๊ณ  A Stack์„ 3๊ฐœ์งœ๋ฆฌ ์ •๋ ฌ ๋ฐฉ์‹์œผ๋กœ ์ •๋ ฌ ํ›„, B Stack์— ์žˆ๋Š” ๊ฐ’์„ Predicate ๋ฐฉ์‹์„ ์ด์šฉํ•˜์—ฌ ์ •๋ ฌํ•œ๋‹ค.

3. Testing Script

checker ๋ถ€๋ถ„๊ณผ push_swap ๋ถ€๋ถ„์œผ๋กœ ๋‚˜๋ˆ„์–ด ์ž‘์„ฑํ•˜์˜€๊ณ , Makefile์— test๋ผ๋Š” Rule์„ ์ถ”๊ฐ€ํ•˜์—ฌ ํ…Œ์ŠคํŠธ๋ฅผ ์ˆ˜ํ–‰ํ•˜์˜€๋‹ค. test๋ผ๋Š” Rule์—๋Š” checker_test์™€ push_swap_test๋ผ๋Š” Rule์ด ์˜์กด์„ฑ์œผ๋กœ ์กด์žฌํ•˜๊ณ , ๊ฐ Rule์ด checker์™€ push_swap์— ํ•ด๋‹นํ•˜๋Š” ์Šคํฌ๋ฆฝํŠธ๋ฅผ ์‹คํ–‰ํ•˜๋„๋ก ์ž‘์„ฑํ–ˆ๋‹ค.
์Šคํฌ๋ฆฝํŠธ ๋‚ด๋ถ€์—๋Š” ํ…Œ์ŠคํŠธ์— ์‚ฌ์šฉ๋  ์ธ์ž๋“ค์„ ์ˆ˜๊ธฐ๋กœ ์ž‘์„ฑํ•œ ๊ฒƒ๋“ค๋„ ์žˆ์—ˆ๊ณ , ์ž‘์„ฑํ•œ Sorting Algorithm์— ๋Œ€ํ•ด์„œ ํ‰๊ท ์ ์ธ ์„ฑ๋Šฅ์„ ์ธก์ •ํ•ด๋ณด๊ธฐ ์œ„ํ•ด ๋ฌด์ž‘์œ„ ๋‚œ์ˆ˜๋ฅผ ์ƒ์„ฑ ํ›„ ํŠน์ • ํšŸ์ˆ˜๋งŒํผ ๋ฐ˜๋ณตํ•˜์—ฌ ๊ฒฐ๊ณผ๋ฅผ ์ธก์ •ํ•˜๋Š” ์‹์œผ๋กœ ์ž‘์„ฑํ•ด๋‘์—ˆ๋‹ค. ์ž‘์„ฑ ์ดˆ๊ธฐ์—๋Š” C++์„ ์ด์šฉํ•˜์—ฌ ๋ณ„๋„์˜ ์‹คํ–‰ ํŒŒ์ผ์„ ๋งŒ๋“ค์–ด์„œ ๋‚œ์ˆ˜๋ฅผ ์–ป์—ˆ๋Š”๋ฐ, ํ‰๊ฐ€ ํ™˜๊ฒฝ ๋ฐ ์ž‘์—… ํ™˜๊ฒฝ์ด Mac OS X๋ฏ€๋กœ ๊ธฐ๋ณธ์ ์œผ๋กœ ์„ค์น˜๋˜์–ด ์žˆ๋Š” ruby๋ฅผ ๊ทธ๋Œ€๋กœ ์ด์šฉํ•ด๋„ ์ข‹๊ฒ ๋‹ค๋Š” ์ƒ๊ฐ์ด ๋งŽ์ด ๋“ค์—ˆ๋‹ค. ๊ฒฐ๊ณผ์ ์œผ๋กœ๋Š” ruby์˜ ์˜ต์…˜์„ ํ†ตํ•ด์„œ ๋‚œ์ˆ˜๋ฅผ ์ƒ์„ฑํ•˜๋„๋ก ๋‘์—ˆ๋‹ค.
๊ทธ ์™ธ์—๋Š” Makefile์—๋Š” ํ‘œ์ค€ ์—๋Ÿฌ๋กœ ๋‚˜์˜ค๋Š” ์ถœ๋ ฅ์— ๋Œ€ํ•ด์„œ๋Š” false๋กœ ์ธ์‹ํ•˜์—ฌ ์˜ค๋ฅ˜๋กœ ์ฒ˜๋ฆฌํ•˜๋ฏ€๋กœ, ํ‘œ์ค€ ์—๋Ÿฌ์˜ ์ถœ๋ ฅ์„ ๊ฒ€์ฆํ•  ๋•Œ false๊ฐ€ ๋‚˜์˜ค์ง€ ์•Š๋„๋ก ์‹ ๊ฒฝ ์จ์ฃผ์—ˆ๋‹ค.
์•„๋ž˜ ํ•ญ๋ชฉ์— ๊ธฐ์žฌ๋œ ๋งํฌ์—๋Š” ์†Œ์Šค ์ฝ”๋“œ๋“ค์ด ์žˆ๋‹ค. ์†Œ์Šค ์ฝ”๋“œ์—์„œ test๋ผ๋Š” ๋””๋ ‰ํ† ๋ฆฌ์— ์žˆ๋Š” ์Šคํฌ๋ฆฝํŠธ๋“ค์„ ์‹คํ–‰ํ•˜๋Š” ๋ฐฉ์‹ ๊ทธ๋Œ€๋กœ ํ™œ์šฉํ•ด๋„ ์ข‹๊ณ , Makefile์— Rule์„ ๋‘๋Š” ์‹์œผ๋กœ ํ™œ์šฉํ•ด๋„ ์ข‹์œผ๋ฏ€๋กœ ํ•„์š”ํ•˜๋‹ค๋ฉด ๊ฐ€์ ธ๋‹ค ์‚ฌ์šฉํ•ด๋„ ์ข‹๋‹ค.

4. Code of Jseo