ํฌํฌ์ธํฐ2 [ํ๋ก๊ทธ๋๋จธ์ค Lv2] : ๊ตฌ๋ช ๋ณดํธ ๋ฌธ์ ๋งํฌ https://programmers.co.kr/learn/courses/30/lessons/42885 ์ฝ๋ฉํ ์คํธ ์ฐ์ต - ๊ตฌ๋ช ๋ณดํธ ๋ฌด์ธ๋์ ๊ฐํ ์ฌ๋๋ค์ ๊ตฌ๋ช ๋ณดํธ๋ฅผ ์ด์ฉํ์ฌ ๊ตฌ์ถํ๋ ค๊ณ ํฉ๋๋ค. ๊ตฌ๋ช ๋ณดํธ๋ ์์์ ํ ๋ฒ์ ์ต๋ 2๋ช ์ฉ ๋ฐ์ ํ ์ ์๊ณ , ๋ฌด๊ฒ ์ ํ๋ ์์ต๋๋ค. ์๋ฅผ ๋ค์ด, ์ฌ๋๋ค์ ๋ชธ๋ฌด๊ฒ๊ฐ [70kg, 50kg, 80kg, 5 programmers.co.kr ๋ฌด์ธ๋์ ๊ฐํ ์ฌ๋๋ค์ ๋ชจ๋ ๊ตฌํ๊ธฐ ์ํด ํ์ํ ์ต์ ๊ตฌ๋ช ๋ณดํธ ์๋ฅผ ๋ฆฌํดํ๋ ๋ฌธ์ . ํ์ด ๋ณดํธ์๋ ์ต๋ 2๋ช ์ ์ฌ๋์ด ํ ์ ์์ผ๋ฉฐ, ๋ฌด๊ฒ ์ ํ์ด ์๋ค. ํ์ด ์๊ณ ๋ฆฌ์ฆ ๋ฌด๊ฒ๊ฐ ๊ฐ๋ฒผ์ด ์ฌ๋์ ์ต๋ํ ๋ฌด๊ฒ๊ฐ ๋ฌด๊ฑฐ์ด ์ฌ๋์ด๋ ๊ฐ์ด ํ์ผ ์ต๋ํ ๋ง์ ์ฌ๋๋ค์ด ์ง์ ์ด๋ค์ ๋ณดํธ์ ํ ์ ์๋ค. ์ผ๋จ ํ์ถํด์ผํ ์ฌ๋๋ค์ ๋ฌด๊ฒ์์ผ๋ก ์ ๋ ฌ.. 2022. 6. 23. [BOJ] 2470 : ๋ ์ฉ์ก ๋ฌธ์ ๋งํฌ 2470๋ฒ: ๋ ์ฉ์ก (acmicpc.net) 2470๋ฒ: ๋ ์ฉ์ก ์ฒซ์งธ ์ค์๋ ์ ์ฒด ์ฉ์ก์ ์ N์ด ์ ๋ ฅ๋๋ค. N์ 2 ์ด์ 100,000 ์ดํ์ด๋ค. ๋์งธ ์ค์๋ ์ฉ์ก์ ํน์ฑ๊ฐ์ ๋ํ๋ด๋ N๊ฐ์ ์ ์๊ฐ ๋น์นธ์ ์ฌ์ด์ ๋๊ณ ์ฃผ์ด์ง๋ค. ์ด ์๋ค์ ๋ชจ๋ -1,000,000,000 ์ด์ 1,000,00 www.acmicpc.net ํ์ด ๋ ์ฉ์ก์ ํน์ฑ๊ฐ์ ํฉ์ด 0์ ๊ฐ์ฅ ๊ฐ๊น์ด ์ฉ์ก์ ๋ง๋๋ ๋ฌธ์ . ๋ธ๋ฃจํธํฌ์ค๋ก ํด๊ฒฐํ๋ ค ํ๋ค๋ฉด O(N^2) ์ด๊ธฐ๋๋ฌธ์ ๋น์ฐํ ์๊ฐ์ด๊ณผ๊ฐ ๋๋ค. ํฌํฌ์ธํธ ๊ธฐ๋ฒ์ ์ฌ์ฉํด์ผํ๋๋ฐ ๋ง ๊ทธ๋๋ก ๊ทธ๋ฅ ๋ ๊ฐ์ ์ ์ ์ฐ๋ ๋ฐฉ์์ด๋ค. ๋จผ์ ์ฉ์ก์ ํน์ฑ๊ฐ๋ค์ด ๋ด๊ธด ๋ฒกํฐ๋ฅผ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํ๋ค. Left๋ฅผ 0 Right๋ฅผ N-1๋ก ์ก๊ณ (Left์ Right๊ฐ ๋ ์ ์ด ๋๋ค) ๋ฒกํฐ์ Le.. 2022. 2. 2. ์ด์ 1 ๋ค์