์์ ๋์งํ
-
์์ ๋์งํAlgorithm 2021. 5. 26. 11:08
์๋ ๋ฌธ์ ๋ ํ๋ก๊ทธ๋๋จธ์ค์์ ์ ๊ณตํ๋ 2017 ํ์ค๋ค์ด > ์์ ๋์งํ์ ๋ฌธ์ ์ ๋๋ค๐ง๐ป๐ป ๋ฌธ์ ์ ์ โณโณ ๊ฒ์๋ํ๊ฐ ๊ฐ์ต๋์์ต๋๋ค. ์ด ๋ํ๋ N๋ช ์ด ์ฐธ๊ฐํ๊ณ , ํ ๋๋จผํธ ํ์์ผ๋ก ์งํ๋ฉ๋๋ค. N๋ช ์ ์ฐธ๊ฐ์๋ ๊ฐ๊ฐ 1๋ถํฐ N๋ฒ์ ์ฐจ๋ก๋๋ก ๋ฐฐ์ ๋ฐ์ต๋๋ค. ๊ทธ๋ฆฌ๊ณ , 1๋ฒ↔2๋ฒ, 3๋ฒ↔4๋ฒ, ... , N-1๋ฒ↔N๋ฒ์ ์ฐธ๊ฐ์๋ผ๋ฆฌ ๊ฒ์์ ์งํํฉ๋๋ค. ๊ฐ ๊ฒ์์์ ์ด๊ธด ์ฌ๋์ ๋ค์ ๋ผ์ด๋์ ์ง์ถํ ์ ์์ต๋๋ค. ์ด๋, ๋ค์ ๋ผ์ด๋์ ์ง์ถํ ์ฐธ๊ฐ์์ ๋ฒํธ๋ ๋ค์ 1๋ฒ๋ถํฐ N/2๋ฒ์ ์ฐจ๋ก๋๋ก ๋ฐฐ์ ๋ฐ์ต๋๋ค. ๋ง์ฝ 1๋ฒ↔2๋ฒ ๋ผ๋ฆฌ ๊ฒจ๋ฃจ๋ ๊ฒ์์์ 2๋ฒ์ด ์น๋ฆฌํ๋ค๋ฉด ๋ค์ ๋ผ์ด๋์์ 1๋ฒ์ ๋ถ์ฌ๋ฐ๊ณ , 3๋ฒ↔4๋ฒ์์ ๊ฒจ๋ฃจ๋ ๊ฒ์์์ 3๋ฒ์ด ์น๋ฆฌํ๋ค๋ฉด ๋ค์ ๋ผ์ด๋์์ 2๋ฒ์ ๋ถ์ฌ๋ฐ๊ฒ ๋ฉ๋๋ค. ๊ฒ์์ ์ต์ข ํ ๋ช ์ด ๋จ์ ๋๊น์ง ์ง..