๊ธฐํ์ ์ด์ฉ๊ณ 1์ธ ๊ฐ๋ฐ ์ด์ฉ๊ณ ์๋ฌด ์ฐ์๋ฐ๊ธฐ ์๋ ๊ฑธ ๋ฌผ์ด๋ฏ๊ณ ์๋
์ฌ๊ธฐ์ ์๊ณ ๋ฆฌ์ฆ ๊ฐ์ ๊ฑฐ ๊ฐ๊ณ ๋ญ๊ฐ ํจ์จ์ ์ด๋ค ๋ญ๊ฐ ๋ซ๋ค๋ก ๋ ผ์ ์ผ์ด๋๋ ๊ฑธ ๋ณธ ์ ์ด ์๋ ๊ฑฐ ๊ฐ๋ค
์ ์ด์ 1์ธ๊ฐ๋ฐ์ด ์ด๋ ํํ์์ ๋ฌด์จ๋ฌด์จ ๊ธฐ์ค์ ๋ง์กฑํด์ผ 1์ธ๊ฐ๋ฐ์ด๋ค ์ ํด๋์ ๊ฒ๋ ์๋๋ฐ ๋จ์ด ์์ ์ ์ฐ๊ฑด ์ธ์ฃผ๋ฅผ ์ฐ๊ฑด ๋ญ ์๊ด์ธ๊ฐ
๋ณธ์ธ ๊ฒ์์ด๋ ๋ง๋ค๋ฉด ๋์ง
์ฌ๊ธฐ์ ์๊ณ ๋ฆฌ์ฆ ๊ฐ์ ๊ฑฐ ๊ฐ๊ณ ๋ญ๊ฐ ํจ์จ์ ์ด๋ค ๋ญ๊ฐ ๋ซ๋ค๋ก ๋ ผ์ ์ผ์ด๋๋ ๊ฑธ ๋ณธ ์ ์ด ์๋ ๊ฑฐ ๊ฐ๋ค
์ ์ด์ 1์ธ๊ฐ๋ฐ์ด ์ด๋ ํํ์์ ๋ฌด์จ๋ฌด์จ ๊ธฐ์ค์ ๋ง์กฑํด์ผ 1์ธ๊ฐ๋ฐ์ด๋ค ์ ํด๋์ ๊ฒ๋ ์๋๋ฐ ๋จ์ด ์์ ์ ์ฐ๊ฑด ์ธ์ฃผ๋ฅผ ์ฐ๊ฑด ๋ญ ์๊ด์ธ๊ฐ
๋ณธ์ธ ๊ฒ์์ด๋ ๋ง๋ค๋ฉด ๋์ง
O(n^2) ์๊ณ ๋ฆฌ์ฆ์ ๋ํด์ ์ด๋ป๊ฒ ์๊ฐํ์ญ๋๊น
๋ ๊ฐ์๋ฆฌ๊ณ ๊ทธ๋ฅ ์ฌ๊ธฐ ๋ณ๋จน๊ธ์ด ์ ์๋จ
์๋ฅ๊ฐค๋ฌ๋ฆฌ ๊ฐ์ ๊ณณ์์ ๊ฐ์๋ฆฌ ํ๋๊ฑฐ๋ ๊ฐ๋ค๊ณ ๋ด ใ ใ ใ ใ ๋ญ๊ฐ ํด์ผํ๋๋ฐ ํ ์์์ด ์์ด์ ๊ดํ ์๊ธฐ๋ ๊ฐ์ ์ฒ์ง์ ์ฌ๋๋ค ๊น๋ด๋ฆฌ๋ฉด์ ์์กด๊ฐ ์ฑ์ฐ๋
๋๋จธ์ง๋ ๊ฒ๋ง๋๋๋ผ ๋ฐ๋น ์
๋์์์ ๋ญ ๊ธฐ๋ํ๋ ๊ฒ๋๊น ๋๊ฒ