Subjects
1. ๋ค์ด๊ฐ๊ธฐ ์ ์
์ด๋ฒ ๊ธ์ ์ด์ ๊ธ๋ค๊ณผ ์กฐ๊ธ ๋ค๋ฅธ ์ฑ๊ฒฉ์ผ๋ก, ํน์ ์ง์์ ์ ๋ฌ๋ณด๋ค๋ ํ๋ก์ ํธ ํ์ด๋ฅผ ์ํด ํ๋ ์๊ฐ๋ค์ ์์ฃผ๋ก ์ ๋ฌํ ์์ ์ด๋ค. ๋ฐ๋ผ์ ๋ฌธ์ ํด๊ฒฐ์ ์ํ ๋ชจ๋ ๋ฐฉ๋ฒ์ด ์๋ ํน์ ๋ฐฉ๋ฒ๋ง ์๊ฐ๋ ์์ ์ด๋ฉฐ, ๊ธ ์ ์ฒด์ ์ผ๋ก ์ฃผ๊ด์ ์ธ ์ฑ๊ฒฉ์ด ๊ฐํ๋ฏ๋ก ์ด๋ฅผ ์ฐธ๊ณ ํ๊ณ ์ฝ๋ ๊ฒ์ ์ถ์ฒํ๋ค. ํ์ด๋ฅผ ์ํด ์ด๋ค ํ๋ฆ์ผ๋ก ์๊ฐ์ ํ๋์ง ์ ๋๋ฅผ ๋ณด๋ฉด ์ข์ ๊ฒ ๊ฐ๋ค.
๋ํ ๋์ถฉ ์ด๋ ์ ๋์ ๊ฐ์ด ๋์ฌ์ง ์์ธก์ ๋๋๋ฐ, ์์์ผ๋ก ์ ๋ฆฌํ๋ ค๊ณ ๋ณด๋ ์ ์ ๋์๋ค. ์๊ฐ ๋ณต์ก๋ ๊ณ์ฐ์ ์์ด์ ์ผ๋ง๋ ๋ฌด๋ฅํ์ง ์ ์ ์์๋ค. ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ๋ฅผ ํผ๋ค๋ ๊ฐ, ์ด๋ค ๊ฒ์ ๋ํด์ ์ฝ๋ฉ์ ํ ๋ ์ง๊ธ๋ณด๋ค๋ ๋ ๊ผผ๊ผผํ๊ฒ ์๊ฐ ๋ณต์ก๋๋ฅผ ํ์ธํ๊ณ ์ฆ๋ช
ํ๋ ์ต๊ด์ ๋ค์ฌ์ผ๊ฒ ๋ค๋ ์๊ฐ์ ๋ง์ดํ๊ฒ ๋์๋ค.
์ด๋ฒ ๊ณผ์ ์ ๊ฒฝ์ฐ์๋ ๊ฒฐ๊ณผ์ ์ผ๋ก๋ ๊ณผ ๊ฐ์ ํํ๋ก ์ฝ๋๋ฅผ ์์ฑํ๋๋ฐ, ์์ํ๊ฒ ์ผ๋ก ๋์ง ์๋๋ค๋ ํ์ ํ๋๋ง์ผ๋ก ๊ฒฐ๊ณผ๋ฅผ ๋ด๋ณด์๋ค. ํ๋ก์ ํธ์์ ์ข์ ์ ์๋ฅผ ๋ฐ์ ๋งํผ์ ๊ฒฐ๊ณผ๊ฐ ๋์๊ณ ์ด๋ ์ผ์ถ ์์ธกํ ๋ฒ์ ๋ด์์ ๋์์์๋, ์ ์๋ ์๊ณ ๋ฆฌ์ฆ์ด ์ ์ ๋ ฌ๊ณผ ๋น์ทํ๊ฑฐ๋ ์กฐ๊ธ ๋ ์ข์ ๊ฒฐ๊ณผ๋ฅผ ๋ด๋ ๊ฒ์ ๋ํด์ ์ ํํ ์์์ผ๋ก ์ฆ๋ช
ํ์ง ๋ชปํ๋ค. ๋ฐ์ฑํด์ผํ ๋ถ๋ถ์ด๋ผ๊ณ ์๊ฐํ๊ณ , ์๋นํ ๋ถ๋๋ฝ๊ฒ ๋๊ปด์ง๋ค.
๋ค์ ๊ณต๋ถํด์ผ ํ ๊ฒ ๊ฐ๋ค ใ
ใ
..
2. Approach
1) ์ค๋ณต ๊ฒ์ฌ
push_swap์์๋ ์ซ์๋ก ๋์ด ์๋ ์ธ์๋ง ๋ฐ์ ์ ์์ผ๋ฉฐ, ์ธ์ ๊ฐ์ ์ค๋ณต์ผ๋ก ๋ฐ์ ์ ์๋ค. ๋ฐ๋ผ์ ์ค๋ณต๋ ๊ฐ์ผ๋ก ์ธ์๊ฐ ๋ค์ด์์ ๋, ์ด๋ฅผ ํ์ธํ๊ณ ์ ์ ํ๊ฒ ์๋ฌ๋ฅผ ๋ด์ค์ผ ํ๋ค.
์ ๋ ฌ์ ์ํํ๋ ๋ก์ง์ ์ด๋ป๊ฒ ๋์ง ์ ํ์ง ์์ ์ํ์ด๋๋ผ๋, ํ๊ฐ ๊ธฐ์ค์ ๋ถํฉํ๋ ๊ฒฐ๊ณผ๋ฅผ ๋ด๊ธฐ ์ํด์ ํ๊ท ์ ์ผ๋ก ์ ์ฑ๋ฅ์ด ๋ณด์ฅ๋์ด์ผ ํ๋ค. ์ ๋ ฌ์์์ ํ๊ท ์๊ฐ ๋ณต์ก๋๋ฅผ ์ ๋ง์กฑํ๋๋ผ๋ ์ค๋ณต ๊ฒ์ฌ๋ฅผ ์ํํ ๋ ์ธ์๋ค์ ์ผ์ผ์ด ํ์ธํ๊ฒ ๋๋ค๋ฉด ์ด ๋์ด๋ฒ๋ฆฐ๋ค. ์ด์ด ์ข๋ค๋ฉด ๊น์ง ๊ฑธ๋ฆฌ์ง ์๊ฒ ์ง๋ง, ์ด๋ ์ด๋๊น์ง๋ ์ค๋ณต๋ ์ธ์๊ฐ ๋ค์ด๊ฐ ๊ฒฝ์ฐ์๋ง ํด๋น๋๋ค. ์ฆ, ์ค๋ณต๋ ์ธ์๊ฐ ๋ค์ด์ค์ง ์๊ณ ์ ์์ ์ผ๋ก ์ ๋ ฌ ๋ก์ง์ ์ํํ๊ฒ ๋๋ค๋ฉด ์ด๋ฏธ ํ์ ์ ์ผ๋ก ์ ์ํํ๋ ๊ฒ์ด ๋๋ฏ๋ก ์ค๋ณต ๊ฒ์ฌ์ ์กฐ๊ธ ๋ ํจ์จ์ ์ธ ๋ฐฉ์์ด ํ์ํ๋ค.
์ค๋ณต ๊ฒ์ฌ๋ฅผ ์ํ ๋ฐฉ๋ฒ์ ํฌ๊ฒ 3๊ฐ์ง๊ฐ ๋ ์ฌ๋๋ค.
1.
๊ฐ ์ธ์ ๋ณ๋ก ๋ค๋ฅธ ์ธ์๋ค์ ์ผ์ผ์ด ๋น๊ตํ๋ ๋ฐฉ๋ฒ Brute Force
2.
์ฌ์ฉ๋ ์ธ์๋ค์ ํ
์ด๋ธ์ ๊ธฐ๋กํ๋ ๋ฐฉ๋ฒ Memoization
3.
์งํฉ Set
๊ฐ์ฅ ์ฌ์ด ๋ฐฉ๋ฒ์ 1๋ฒ์ด์ง๋ง, ์์์ ์ธ๊ธํ ๊ฒ์ฒ๋ผ ์๊ฐ ๋ณต์ก๋๋ฅผ ๋ง์กฑํ๊ธฐ ์ํด์ ์ฌ์ฉํ ์ ์๋ ๋ฐฉ๋ฒ์ ์๋์๋ค. ์ด ์ปค์ง์๋ก ์ค๋ณต ๊ฒ์ฌ๋ฅผ ์ํด ์์๋๋ ์๊ฐ์ด ์ปค์ง๊ธฐ ๋๋ฌธ์ด๋ค.
๊ฐ์ฅ ์๊ฐ์ด ์ ๊ฒ ๊ฑธ๋ฆฌ๋ ๋ฐฉ๋ฒ์ 2๋ฒ์ด์์ง๋ง, ์ด ์ญ์๋ ์ฌ์ฉํ ์๋ ์๋ ๋ฐฉ๋ฒ์ด์๋ค. Memoization ๋ฐฉ์์ ์ฌ์ฉํ๋ ค๋ ์ธ์๋ค์ ๋งํผ์ ๊ณต๊ฐ์ ํ ๋นํด๋์ด, ๋ผ๋ ๊ฐ์ด ์ฌ์ฉ๋์์ผ๋ฉด ํ ๋น ๋ฐ์ ๊ณต๊ฐ์ ๋ฒ์งธ index์ ํด๋นํ๋ ๊ณณ์ ๋งํน์ ํด๋๋ ๋ฐฉ์์ด๋ค. ์ผ๋ฐ์ ์ธ ๋ก์ง ํ
์คํธ๋ฅผ ์ํด ์ธ์๋ค์ Interval์ด 1์ธ ํํ๋ก ์
๋ ฅ์ด ๋ค์ด์ค๋ ๊ฒฝ์ฐ์๋ ๋ฌธ์ ์์ด ์ฌ์ฉํ ์ ์์ง๋ง, Interval์ด ๋ฌด์์ ํ๊ฒ ์ธ์๋ค์ด ๋ค์ด์ค๋ ๊ฒฝ์ฐ์๋ ์ค๋ณต ๊ฒ์ฌ๋ฅผ ์ํ ๊ณต๊ฐ์ด ๊ต์ฅํ Sparseํ ์ ์๋ค๋ ๊ฒ์ด ๊ฐ์ฅ ํฐ ๋ฌธ์ ์ด๋ค. ์๋ฅผ ๋ค์ด 1 2 3 4 5์ ๊ฐ์ ํํ๋ก ์ธ์๋ฅผ ๋ฐ๊ฒ ๋๋ฉด ํ ๋น ๋ฐ์ 5๊ฐ์ ๊ณต๊ฐ์ ๋ฌธ์ ์์ด ์ด์ฉํ ์ ์์ง๋ง, -2147483648 1 2 3 4 5์ ๊ฐ์ ํํ๋ก ์ธ์๋ฅผ ๋ฐ์ผ๋ฉด ํ ๋น ๋ฐ์ ๊ณต๊ฐ์ Sparseํ๊ฒ ์ด์ฉํ๊ฒ ๋๋ ๊ฒ์ด๋ค. ํด๋น ๊ฒฝ์ฐ์ ์ฌ์ฉํ๋ ์ธ์๋ 6๊ฐ์ง๋ง, -2147483647 ~ 0๊น์ง์ ๊ณต๊ฐ์ ๋ญ๋นํ๊ฒ ๋๋ค.
๋ฐ๋ผ์ ๊ณต๊ฐ์ ๋ญ๋น ์์ด ํจ์จ์ ์ผ๋ก ์ฌ์ฉํ๋ฉด์ ๋ณด๋ค ์ ์ ์๊ฐ ๋ด์ ์ํ๋ ๊ฒฐ๊ณผ๋ฅผ ์ป๊ธฐ ์ํด ๋ ์ฌ๋ฆฐ ๊ฒ์ด Set์ด์๋ค. Red-Black Tree๋ก ๊ตฌํ๋ Set์ 1๊ฐ์ ์์๋ฅผ ์ฝ์
ํ ๋ ๊ฑธ๋ฆฌ๋ ์๊ฐ์ด ์ด๋ฉฐ ํ์์ด ํฌํจ๋์ด ์๊ธฐ ๋๋ฌธ์, ์ฝ์
์ฐ์ฐ๋ง์ผ๋ก ์ค๋ณต ๊ฒ์ฌ๋ฅผ ์ํํ ์ ์๋ค. ์ฆ, ๊ฐ์ ์์๋ฅผ ์ฝ์
ํ ๋๋ ์ด ์๊ตฌ๋๋ฉฐ ์ด ๊ณผ์ ์์ ์ค๋ณต ์ธ์๊ฐ ๋ค์ด์๋์ง ํ๋ณ์ด ๊ฐ๋ฅํด์ง๋ค.
Red-Black Tree?
Red-Black Tree๋ ์ด์ง ํ์ ํธ๋ฆฌ์ ํ ์ข
๋ฅ์ด๋ค. ์ด์ง ํ์ ํธ๋ฆฌ์ ํน์ฑ ์ Balance๋ฅผ ์ ์ ์งํ์ง ๋ชปํ๋ฉด ์ ๊ทผ์ ํ ์ฑ๋ฅ์ด ๋์ค๊ฒ ๋๋๋ฐ, Red-Black Tree๋ ์ฝ์
์ฐ์ฐ ํ Balance๊ฐ ์ ์ง๋ ์ ์๋๋ก ์์ฒด์ ์ผ๋ก ๊ท ํ์ ์กฐ์ ํ์ฌ ์ฝ์
, ์ญ์ , ํ์์ Worst Case์ ๋ํด์๋ ํญ์ ์ ์ฑ๋ฅ์ ๋ณด์ฅํ๋ค. ๊ท ํ์ ์กฐ์ ํ ๋๋ ์ํฉ์ ๋ฐ๋ผ Left Rotation ํน์ Right Rotation์ ์ํํ์ฌ ๋ด๋ถ์ ์ ์ง ์ค์ธ Node๋ค์ ํ์ ์ํจ๋ค. ์๋์ ์ผ๋ก AVL Tree ๋ณด๋ค๋ ๊ท ํ์ ๋ํ ๊ธฐ์ค์ด ์๊ฒฉํ ํธ์ ์๋์ด์ Worst Case์ AVL Tree๋ณด๋ค ์ ์ Rotation์ ์ํํ๋ฏ๋ก ๊ณ ์ ๋ ์ ์ฑ๋ฅ์ ๋ณด์ฅํ ์ ์๋ ๊ฒ์ด๋ค.
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)
๊ธฐ๋ณธ์ ์ผ๋ก ํ๊ฐ ๊ธฐ์ค์์ ์ ํํ๋ ๋ช
๋ น์ด์ ์ ํ์ ๋ง์ถ๊ธฐ ์ํด์ ์ ๋ฐฉ๋ฒ์ผ๋ก๋ ๋ง์ถ ์ ์๊ธฐ ๋๋ฌธ์ ์ ๋ฐฉ๋ฒ์ ์ฐพ์๋ณด์์ผ ํ๋ค. ์ ๊ฐ์ ์ธ์๋ค์ ๋ํ ๊ฒฐ๊ณผ์ด๋ฏ๋ก ๊ฐ๋จํ๊ฒ ์๊ฐํด์ 1๊ฐ์ ์ธ์๋ ์ ๋๋ก ์ฒ๋ฆฌ ๋์ด์ผ ํจ์ ์ ์ ์๋ค.
๋ฐ๋ผ์ ๊ฐ์ฅ ๋จผ์ ๋ ์ฌ๋ฆฐ ๋ฐฉ์์ 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์ ๋ฌธ์ ๊ฐ ์์๋ ๊ฒ์ด๋ค. , ์ง์ ์ ๋ฐ๋ก Pivotting์ ํ๋ ๊ฒ๋ณด๋ค, ์ ๋ ฌํ๋ ค๋ ๊ตฌ๊ฐ์ ์ ๋ ฌ๋ ๊ฐ์ ๋ํด์ , ์ง์ ์ Pivotting์ ํ๋ฉด ๋ถํ์ํ push์ swap๋ค์ ์ ๋ง ๋ง์ด ์์จ ์ ์์๋ค. Pivotting์ ์ค์์ฑ์ ๋ค์ ํ ๋ฒ ๊นจ๋ฌ์ ์ ์์๋ค. ์ด๋ฐ์๋ ์ ์ ๋ ฌ๋ ์ํ์ ์ง์ ๊ฐ์ ์ด์ฉํ ์๊ฐ์ ์ํ๋์ง ๋ชจ๋ฅด๊ฒ ๋ค ใ
ใ
...
4. Predicate
๋ฆฌํ๋ ์ฌ๋ฅผ ํ ๊ฒธ ์ฌ๋ฌ ์๊ณ ๋ฆฌ์ฆ๋ค์ ์ฐพ์๋ณด๋ค๊ฐ ๊ฒฐ๊ตญ์ Quick Sort์ ํน์ฑ์ ๋ค์ ํ ๋ฒ ์๊ฐํด๋ณด๊ฒ ๋์๋ค.
Quick Sort๋ ๋ค๋ฅธ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ๊ณผ ๋ฌ๋ฆฌ ๊ณ ์ ์ ์ผ๋ก ์ด๋ผ๋ ์ฑ๋ฅ์ ๋ณด์ฅํ์ง ์๊ณ , ํ๊ท ์ ์ผ๋ก ์ ์ฑ๋ฅ์ ๋ธ๋ค. ์ฆ, Worst Case์๋ ์ด ๋๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ผ๋ ๊ฒ์ด๋ค. ๊ทธ๋ผ์๋ 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์ ์ ๋ ฌ๋์ด ์๋ ๊ฐ๋ค์ด ๊ฐ๋ผ๊ณ ํ์ ๋ pa์ pb๋ฅผ ํธ์ถํ๋ ํ์๋ ๊ฐ ๋๊ณ , ๊ฐ์ ํ์ ์ ์ผ๋ก ์ฎ๊ธธ ๋ ์ธ์๋ push๋ ์ฌ์ฉ๋์ง ์๋๋ค. ๋ํ ์ ์ ์ธ์๋ฅผ ์ ๋ ฌํ๋ ๊ฒ์ด ์๋๋ผ๋ฉด ์ด์ ๊ฐ์ ์ผ๋ฐ์ ์ธ ์ธ์๋ค์ ์ ๋ ฌํ ๋๋ ๋ณ๋์ swap์ด ์ฌ์ฉ๋์ง ์๋๋ค. ๋ฐ๋ผ์ ์์ํ๊ฒ rotation๋ง์ผ๋ก ์ ๋ ฌ์ ์ํํ๊ฒ ๋๊ณ , ์ด๋ rotation ์ํ ์ ์ ๋ช
๋ น์ด๋ฅผ ํ์
ํ ๋ cw ํน์ ccw ์ค ๋ ์์ ๊ฐ์ผ๋ก ๋ช
๋ น์ด๋ฅผ ์ํํ ์ ์๊ฒ ๋๋ค. ๋ฐ๋ผ์ rotation์ ๋ํด์๋ ๋ณ๋์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํ ๋น๋ฐ๊ณ ํ์ฒ๋ฆฌ๋ฅผ ํ๋ ์์ผ๋ก ์ต์ ํ๋ฅผ ํ์ง ์์๋ ๋๋ค.
ํ์ ๋ฐฉ์์ 1ํ์ฐจ์๋ ๋ฒ, 2ํ์ฐจ์๋ ๋ฒ, ... , ํ์ฐจ์๋ 1๋ฒ์ด ๋์ด Big-O Notation์ผ๋ก๋ ์ด ๋์ง๋ง, ์ค์ ๋ก๋ ์์ํ ๋ณด๋ค๋ ์ ์ ์ฐ์ฐ์ด ๋์๊ฐ๋ฉด์ A Stack ๋ด์ ์ธ์๋ค์ด ๋ง์ด ์ ๋ ฌ์ด ๋์ด ์์์๋ก ๋ ์ ์ ์๊ฐ์ด ์์๋๋ค. ๋ช
๋ น์ด ์ํ ์ธก์ ์๋ ํ์ ๊ณผ์ ์ด ํฌํจ๋์ง ์๊ธฐ ๋๋ฌธ์ ๋ช
๋ น์ด ์ํ ํ์๋ฅผ ๋ฐ๋ก ์๊ฐํ์ฌ ์ฒ๋ผ ๋์ํ๋์ง ์๊ฐํด๋ด์ผ ํ๋๋ฐ ์ด ์ญ์๋ ์ ๋ฏธ์น์ง ์๋๋ค๋ ๊ฒ์ ๋ ์ฌ๋ฆด ์ ์๋ค. ์์ฌ ์ฝ๋๋ ์๋์ ๊ฐ๋ค.
// 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์ ๋๋ ์์ผ๋ก ํ์ฉํด๋ ์ข์ผ๋ฏ๋ก ํ์ํ๋ค๋ฉด ๊ฐ์ ธ๋ค ์ฌ์ฉํด๋ ์ข๋ค.