์ธ๊ธฐ๋:B(A,B,C), ์ฑ๊ณต๋ฅ :๋ณดํต(๋ฎ์,๋ณดํต,๋์), ๋ ๋ฒจ:2(1~4)
About ShellSort ¶
์ฌํ ์(King Yertle)์ ๊ทธ์ ๊ฑฐ๋ถ์ด ์๊ด์ ์ฌ๋ฐฐ์นํด์ ๊ฐ์ฅ ๊ณ๊ธ์ด ๋์ ๊ท์กฑ๊ณผ ๊ฐ์ฅ ๊ฐ๊น์ด ์ธก๊ทผ๋ค์ ๋ ์์ชฝ์ผ๋ก ์ฌ๋ฆฌ๊ณ ์ถ์ดํ๋ค. ์์ฌ์๋ ๊ฑฐ๋ถ์ด๋ค์ ์์๋ฅผ ๋ฐ๊พธ๋ ๋ฐฉ๋ฒ์ ๊ฑฐ๋ถ์ด ํ ๋ง๋ฆฌ๊ฐ ์๋ ์๊ธฐ ์์น์์ ๋น ์ ธ ๋์์ ๋งจ ์๋ก ์ฌ๋ผ๊ฐ์ ์๋ฆฌ๋ฅผ ์ก๋ ๋ฐฉ๋ฒ ๋ฐ์ ์๋ค.
๊ฑฐ๋ถ์ด ์คํ์ ์๋ ์์์ ์๋ก ๋ง๋ค์ด์ ธ์ผ ํ ์คํ์ ์์๊ฐ ์ฃผ์ด์ก์ ๋ ์ต์ํ์ ์ด๋ ํ์๋ง์ผ๋ก ์๋ ์คํ์ ์๋ก์ด ์คํ์ผ๋ก ์ฌ๋ฐฐ์นํ ์ ์๋ ์์๋ฅผ ์ฐพ์์ผ ํ๋ค.
Input ¶
์
๋ ฅ์ ์ฒซ๋ฒ์งธ ์ค์๋ ํ
์คํธ ์ผ์ด์ค์ ๊ฐ์๋ฅผ ๋ํ๋ด๋ K๋ผ๋ ์ ์ ํ๋๋ง ๋ค์ด์๋ค. ๊ฐ ํ
์คํธ ์ผ์ด์ค๋ ์คํ์ ๋ค์ด์๋ ๊ฑฐ๋ถ์ด์ ๊ฐ์๋ฅผ ๋ํ๋ด๋ n์ด๋ผ๋ ์ ์๋ก ์์๋๋ฉฐ ๊ทธ ๋ฐ์ผ๋ก n๊ฐ์ ์ค์ ๊ฑธ์ณ์ ๊ฑฐ๋ถ์ด ์คํ์ ์๋ ๋ฐฐ์น๊ฐ ๊ธฐ์ ๋๋ค. ๊ฐ ์ค์๋ ๊ฑฐ๋ถ์ด์ ์ด๋ฆ์ด ๋ค์ด์์ผ๋ฉฐ ๋งจ ์ ์ค์๋ ์คํ ๋งจ ์์ ์๋ ๊ฑฐ๋ถ์ด์ ์ด๋ฆ์ด ์๊ณ ์์์ ์๋๋ก ์์๋๋ก ๊ฑฐ๋ถ์ด์ ์ด๋ฆ์ด ๋์ด๋๋ค. ๊ฐ ๊ฑฐ๋ถ์ดํํ
๋ ๊ทธ ๊ฑฐ๋ถ์ด๋ง์ ์ด๋ฆ์ด ์ฃผ์ด์ง๋ฉฐ ๊ฐ ์ด๋ฆ์ 80๊ธ์๋ฅผ ๋์ง ์๋ ๋ฌธ์์ด์ด๊ณ , ์ํ๋ฒณ, ์ซ์, ์คํ์ด์ค ๋ฌธ์, ์ ('.')๋ง ์ฐ์ธ๋ค. ๊ทธ ๋ฐ์ผ๋ก๋ n๊ฐ์ ์ค์ ๊ฑธ์ณ์ ์๋ก์ด ์คํ์ด ๊ธฐ์ ๋๋ฉฐ ์ฌ๊ธฐ์์๋ ์์ ์๋ ๊ฑฐ๋ถ์ด๋ถํฐ ์๋์๋ ๊ฑฐ๋ถ์ด ์์ผ๋ก ์ด๋ฆ์ด ์ด๊ฑฐ๋๋ค. ๊ฐ ํ
์คํธ ์ผ์ด์ค๋ ์ ํํ๊ฒ 2n+1๊ฐ์ ์ค๋ก ๊ตฌ์ฑ๋๋ค. ๊ฑฐ๋ถ์ด์ ์(n)๋ 200 ์ดํ๋ก ์ ํ๋๋ค.
output ¶
๊ฐ ํ
์คํธ ์ผ์ด์ค์ ๋ํด ํ ์ค์ ํ๋์ฉ์ ๊ฑฐ๋ถ์ด ์ด๋ฆ์ด ์ถ๋ ฅ๋๋ฉฐ ์ด ๊ฑฐ๋ถ์ด ์ด๋ฆ์ ์คํ์ ๋น ์ ธ ๋์์ ๋งจ ์๋ก ์ฌ๋ผ๊ฐ๋ ๊ฑฐ๋ถ์ด์ ์ด๋ฆ์ ์๋ฏธํ๋ค. ์ด ์ถ๋ ฅ์ ๋์์๋ ์์๋๋ก ์๊ธฐ ์๋ฆฌ๋ฅผ ๋น ์ ธ ๋์์ ๋งจ ์๋ก ์ฌ๋ผ๊ฐ๋ ๊ณผ์ ์ ๋ฐ๋ณตํ๋ฉด ์๋์ ์คํ์ด ์๋ก์ด ์คํ์ผ๋ก ๋ฐ๋์ด์ผ ํ๋ฉฐ ์ต์ํ์ ์ด๋ ํ์๋ก ์์
์ ๋๋ผ ์ ์์ด์ผ ํ๋ค. ์ด ์กฐ๊ฑด์ ๋ง์กฑํ๋ ์ด๋ ๋ฐฉ๋ฒ์ด ์ฌ๋ฌ ๊ฐ์ง ์์ผ๋ฉด ๊ทธ ์ค ์๋ฌด ๊ฒ์ด๋ ์ถ๋ ฅํด๋ ๋๋ค.
์๋ก ๋ค๋ฅธ ํ
์คํธ ์ผ์ด์ค ์ฌ์ด์๋ ๋น ์ค์ ํ๋์ฉ ์ถ๋ ฅํ๋ค.
Sample Input ¶
~cpp 2 3 Yertle Duke of Earl Sir Lancelot Duke of Earl Yertle Sir Lancelot 9 Yertle Duke of Earl Sir Lancelot Elizabeth Windsor Michael Eisner Richard M. Nixon Mr. Rogers Ford Perfect Mack Yertle Richard M. Nixon Sir Lancelot Duke of Earl Elizabeth Windsor Michael Eisner Mr. Rogers Ford Perfect Mack
Sample Output ¶
~cpp Duke of Earl Sir Lancelot Richard M. Nixon Yertle
ํ์ด ¶
| ์์ฑ์ | ์ฌ์ฉ์ธ์ด | ๊ฐ๋ฐ์๊ฐ | ์ฝ๋ |
| ๋ฌธ๋ณด์ฐฝ | C++ | 2์๊ฐ | ShellSort/๋ฌธ๋ณด์ฐฝ |
