user-img
๋ฐฐ์—ด ์ž๋ฅด๊ธฐ 1
thumbnail
[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] n*2 ๋ฐฐ์—ด ์ž๋ฅด๊ธฐ ๋ฌธ์ œ ํ’€์ด java
1. ๋ฌธ์ œ ์„ค๋ช…๋ฌธ์ œ๋งํฌ2์ฐจ์› ๋ฐฐ์—ด์˜ ๊ฐ’์„ ์ง‘์–ด๋„ฃ๊ณ , ๊ทธ๊ฒƒ์„ 1์ฐจ์› ๋ฐฐ์—ด๋กœ ๋Š˜์–ด๋œจ๋ ค์„œ, ๋ฌธ์ œ์—์„œ ์›ํ•˜๋Š” ๊ตฌ๊ฐ„ ๋‚ด์˜ ์ˆซ์ž๋“ค์„ ๋ฌถ์–ด์„œ ๋ฐ˜ํ™˜ํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค.2. ์ ‘๊ทผ ๋ฐฉ์‹KEY WORD: Brute Force, 1์ฐจ์› ๋ฐฐ์—ด๊ณผ 2์ฐจ์› ๋ฐฐ์—ด์˜ ์œ„์น˜ ๊ด€๊ณ„ํ•ด๋‹น ๋ฌธ์ œ๋Š” n์˜ maximum์ด 10^7์ด๋ฏ€๋กœ, O(n)์„ ์ดˆ๊ณผํ•˜๋Š” ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ์‚ฌ์šฉํ•˜์ง€ ๋ชปํ•œ๋‹ค. ๋”ฐ๋ผ์„œ 2์ฐจ์› ๋ฐฐ์—ด์— ๊ฐ’์„ ๋‹ค ์ง‘์–ด๋„ฃ๊ณ , ๊ทธ๊ฒƒ์„ 1์ฐจ์›์œผ๋กœ ๋งŒ๋“œ๋Š”, ๋งˆ์น˜ ๋ฌธ์ œ์—์„œ ์ง€์‹œํ•œ๋Œ€๋กœ๋Š” ํ’€์ด๋ฅผ ํ•˜์ง€ ๋ชปํ•œ๋‹ค. ๋˜ํ•œ 1์ฐจ์› ๋ฐฐ์—ด์„ ๋ฐ”๋กœ ๋งŒ๋“ค๋”๋ผ๋„, n*n์€ ๋ฐฐ์—ด์˜ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์ดˆ๊ณผํ•˜๋Š” ๊ฐ’์„ ์ดˆ๋ž˜ํ•  ์ˆ˜ ์žˆ๊ธฐ ๋•Œ๋ฌธ์— 1์ฐจ์› ๋ฐฐ์—ด ์ „์ฒด๋ฅผ ๋งŒ๋“œ๋Š” ๊ฒƒ๋„ ๋ฌด๋ฆฌ๋‹ค.๋”ฐ๋ผ์„œ ์šฐ๋ฆฌ๋Š” ์ •ํ™•ํžˆ left ~ right ๊นŒ์ง€์˜ ๋ฐฐ์—ด์„ ๋งŒ๋“ค์–ด ๊ฐ’์„ ๊ตฌํ•ด ๋ฐ˜ํ™˜ํ•ด์•ผ ํ•œ๋‹ค.(1) 1์ฐจ์› ๋ฐฐ์—ด 2..
2024.09.05
์•Œ๊ณ ๋ฆฌ์ฆ˜/๋ฌธ์ œ ํ’€์ด