๋ฒ๋ธ ์ ๋ ฌ์ ๋ ์ธ์ ํ ๋ฐ์ดํฐ์ ํฌ๊ธฐ๋ฅผ ๋น๊ตํด ์ ๋ ฌํ๋ ๋ฐฉ์์ด๋ค. ์๊ฐ๋ณต์ก๋: O(n^2)์ผ๋ก ๋๋ฆฐ ํธ ๋ฃจํ๋ฅผ ๋๋ฉด์ ์ธ์ ํ ๋ฐ์ดํฐ ๊ฐ์ swap ์ฐ์ฐ์ผ๋ก ์ ๋ ฌํ๋ค. ๋ฒ๋ธ ์ ๋ ฌ ๊ณผ์ 1. ๋น๊ต ์ฐ์ฐ์ด ํ์ํ ๋ฃจํ ๋ฒ์๋ฅผ ์ค์ ํ๋ค. 2. ์ธ์ ํ ๋ฐ์ดํฐ ๊ฐ์ ๋น๊ตํ๋ค. 3. swap ์กฐ๊ฑด์ ๋ถํฉํ๋ฉด swap ์ฐ์ฐ์ ์ํํ๋ค. 4. ๋ฃจํ ๋ฒ์๊ฐ ๋๋ ๋๊น์ง 2~3์ ๋ฐ๋ณตํ๋ค. 5. ์ ๋ ฌ ์์ญ์ ์ค์ ํ๋ค. ๋ค์ ๋ฃจํ๋ฅผ ์คํํ ๋๋ ์ด ์์ญ์ ์ ์ธํ๋ค. 6. ๋น๊ต ๋์์ด ์์ ๋๊น์ง 1~5๋ฅผ ๋ฐ๋ณตํ๋ค. ๋ง์ฝ ํน์ ๋ฃจํ ์ ์ฒด ์์ญ์์ swap์ด ํ๋ฒ๋ ๋ฐ์ํ์ง ์์๋ค๋ฉด ๊ทธ ์์ญ ๋ค์ ์๋ ๋ฐ์ดํฐ๋ ์ ๋ ฌ์ด ์๋ฃ๋ ๊ฒ์ด๋ฏ๋ก ํ๋ก์ธ์ค ์ข
๋ฃ
๐ฏ์๊ณ ๋ฆฌ์ฆ/BOJ
์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ ๋ฒ๋ธ ์ ๋ ฌ: ๋ฐ์ดํฐ์ ์ธ์ ์์๋ผ๋ฆฌ ๋น๊ตํ๊ณ , swap ์ฐ์ฐ์ ์ํํ๋ฉฐ ์ ๋ ฌํ๋ ๋ฐฉ์ ์ ํ ์ ๋ ฌ: ๋์์์ ๊ฐ์ฅ ํฌ๊ฑฐ๋ ์์ ๋ฐ์ดํฐ๋ฅผ ์ฐพ์๊ฐ ์ ํ์ ๋ฐ๋ณตํ๋ฉด์ ์ ๋ ฌํ๋ ๋ฐฉ์ ์ฝ์
์ ๋ ฌ: ๋์์ ์ ํํด ์ ๋ ฌ๋ ์์ญ์์ ์ ํ ๋ฐ์ดํฐ์ ์ ์ ํ ์์น๋ฅผ ์ฐพ์ ์ฝ์
ํ๋ฉด์ ์ ๋ ฌํ๋ ๋ฐฉ์ ํต ์ ๋ ฌ: pivot ๊ฐ์ ์ ์ ํด ํด๋น ๊ฐ์ ๊ธฐ์ค์ผ๋ก ์ ๋ ฌํ๋ ๋ฐฉ์ ๋ณํฉ ์ ๋ ฌ: ์ด๋ฏธ ์ ๋ ฌ๋ ๋ถ๋ถ ์งํฉ๋ค์ ํจ์จ์ ์ผ๋ก ๋ณํฉํด ์ ์ฒด๋ฅผ ์ ๋ ฌํ๋ ๋ฐฉ์ ๊ธฐ์ ์ ๋ ฌ: ๋ฐ์ดํฐ์ ์๋ฆฟ์๋ฅผ ๋ฐํ์ผ๋ก ๋น๊ตํด ๋ฐ์ดํฐ๋ฅผ ์ ๋ ฌํ๋ ๋ฐฉ์
1. ์ฝ๋ฉ ํ
์คํธ๋?๋ฌธ์ ํ์ด์ํ, ๋ฌธ์ ํด๊ฒฐ ์ญ๋ ํ๊ฐ์จ๋ผ์ธ ์ฝ๋ฉ ํ
์คํธ-์ธํฐ๋ท ํ์ฉ, ์ธํฐ๋ท ๊ฒ์ ํ์ฉ์คํ๋ผ์ธ ์ฝ๋ฉ ํ
์คํธ-์ํ์ฅ, ์ธํฐ๋ท ๊ฒ์ ๋ถํ, ํ์ฌ ์ปดํจํฐ ํ๊ฒฝ์จ๋ผ์ธ์ ์ง-๋ฐฑ์ค, ์ฝ๋์
, ํ๋ก๊ทธ๋๋จธ์คํ๋ก๊ทธ๋๋ฐ ์ธ์ด- C++(44%), ํ์ด์ฌ(36%)์ถ์ ๊ฒฝํฅ- ๊ทธ๋ฆฌ๋ , ๊ตฌํ, BFS/DFS2019๋
์ ํ์ผ์ฑ์ ์: 3์๊ฐ 2๋ฌธ์ -์์ ํ์,์๋ฎฌ๋ ์ด์
,๊ตฌํ,DFS/BFS์นด์นด์ค: 5์๊ฐ 7๋ฌธ์ -๊ตฌํ,์ด์งํ์,์๋ฃ๊ตฌ์กฐ๋ผ์ธ: 3์๊ฐ 5๋ฌธ์ - ํ์,๊ตฌํ,๋ฌธ์์ด, ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ2. ์๊ณ ๋ฆฌ์ฆ ์ฑ๋ฅ ํ๊ฐ๋ณต์ก๋- ์๊ณ ๋ฆฌ์ฆ ์ฑ๋ฅ ๋ํ๋ด๋ ์ฒ๋, ๋ณต์ก๋๊ฐ ๋ฎ์ ์๋ก ์ข์ ์๊ณ ๋ฆฌ์ฆ์๊ฐ๋ณต์ก๋: ํน์ ํฌ๊ธฐ์ ์
๋ ฅ์ ๋ํ ์๊ณ ๋ฆฌ์ฆ์ ์ํ ์๊ฐ ๋ถ์๊ณต๊ฐ๋ณต์ก๋: ํน์ ํฌ๊ธฐ์ ์
๋ ฅ์ ๋ํ ์๊ณ ๋ฆฌ์ฆ์ ๋ฉ๋ชจ๋ฆฌ ์ฌ์ฉ๋ ๋ถ์๋น
์ค ํ..
https://www.acmicpc.net/problem/11720 11720๋ฒ: ์ซ์์ ํฉ ์ฒซ์งธ ์ค์ ์ซ์์ ๊ฐ์ N (1 ≤ N ≤ 100)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค์ ์ซ์ N๊ฐ๊ฐ ๊ณต๋ฐฑ์์ด ์ฃผ์ด์ง๋ค. www.acmicpc.net ๋ฌธ์ N๊ฐ์ ์ซ์๊ฐ ๊ณต๋ฐฑ ์์ด ์ฐ์ฌ์๋ค. ์ด ์ซ์๋ฅผ ๋ชจ๋ ํฉํด์ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์
๋ ฅ ์ฒซ์งธ ์ค์ ์ซ์์ ๊ฐ์ N (1 ≤ N ≤ 100)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค์ ์ซ์ N๊ฐ๊ฐ ๊ณต๋ฐฑ์์ด ์ฃผ์ด์ง๋ค. ์ถ๋ ฅ ์
๋ ฅ์ผ๋ก ์ฃผ์ด์ง ์ซ์ N๊ฐ์ ํฉ์ ์ถ๋ ฅํ๋ค. ์์ ์
๋ ฅ 1 1 1 ์์ ์ถ๋ ฅ 1 1 ์์ ์
๋ ฅ 2 5 54321 ์์ ์ถ๋ ฅ 2 15 ์์ ์
๋ ฅ 3 25 7000000000000000000000000 ์์ ์ถ๋ ฅ 3 7 ์์ ์
๋ ฅ 4 11 10987654321 ์์ ์ถ๋ ฅ ..