๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

์ฝ”๋”ฉํ…Œ์ŠคํŠธ121

[ํˆฌ ํฌ์ธํ„ฐ] 5. ์—ฐ์†๋œ ์ž์—ฐ์ˆ˜์˜ ํ•ฉ 5. ์—ฐ์†๋œ ์ž์—ฐ์ˆ˜์˜ ํ•ฉ ์„ค๋ช… N์ž…๋ ฅ์œผ๋กœ ์–‘์˜ ์ •์ˆ˜ N์ด ์ž…๋ ฅ๋˜๋ฉด 2๊ฐœ ์ด์ƒ์˜ ์—ฐ์†๋œ ์ž์—ฐ์ˆ˜์˜ ํ•ฉ์œผ๋กœ ์ •์ˆ˜ N์„ ํ‘œํ˜„ํ•˜๋Š” ๋ฐฉ๋ฒ•์˜ ๊ฐ€์ง“์ˆ˜๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์„ธ์š”. ๋งŒ์•ฝ N=15์ด๋ฉด 7+8=15 4+5+6=15 1+2+3+4+5=15 ์™€ ๊ฐ™์ด ์ด 3๊ฐ€์ง€์˜ ๊ฒฝ์šฐ๊ฐ€ ์กด์žฌํ•œ๋‹ค. ์ž…๋ ฅ ์ฒซ ๋ฒˆ์งธ ์ค„์— ์–‘์˜ ์ •์ˆ˜ N(7 n) sum -= lt++; } } return answer; } public static void main(String[] args) { Main T = new Main(); Scanner in = new Scanner(System.in); int n = in.nextInt(); System.out.print(T.solution(n)); } } -๊ฐ•์‚ฌ๋‹˜ ํ’€์ด- ๊ฐ•์‚ฌ๋‹˜ ํ’€์ด๋Š” ๋‘ ๊ฐ€์ง€๊ฐ€ ์žˆ์—ˆ๋Š”.. ์ฝ”๋”ฉํ…Œ์ŠคํŠธ 2023. 12. 26.
[๋ณตํ•ฉ๋ฌธ์ œ] 4. ์—ฐ์† ๋ถ€๋ถ„์ˆ˜์—ด 4. ์—ฐ์† ๋ถ€๋ถ„์ˆ˜์—ด ์„ค๋ช… N๊ฐœ์˜ ์ˆ˜๋กœ ์ด๋ฃจ์–ด์ง„ ์ˆ˜์—ด์ด ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. ์ด ์ˆ˜์—ด์—์„œ ์—ฐ์†๋ถ€๋ถ„์ˆ˜์—ด์˜ ํ•ฉ์ด ํŠน์ •์ˆซ์ž M์ด ๋˜๋Š” ๊ฒฝ์šฐ๊ฐ€ ๋ช‡ ๋ฒˆ ์žˆ๋Š”์ง€ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์„ธ์š”. ๋งŒ์•ฝ N=8, M=6์ด๊ณ  ์ˆ˜์—ด์ด ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค๋ฉด 1 2 1 3 1 1 1 2 ํ•ฉ์ด 6์ด ๋˜๋Š” ์—ฐ์†๋ถ€๋ถ„์ˆ˜์—ด์€ {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}๋กœ ์ด 3๊ฐ€์ง€์ž…๋‹ˆ๋‹ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— N(1โ‰คNโ‰ค100,000), M(1โ‰คMโ‰ค100,000,000)์ด ์ฃผ์–ด์ง„๋‹ค. ์ˆ˜์—ด์˜ ์›์†Œ๊ฐ’์€ 1,000์„ ๋„˜์ง€ ์•Š๋Š” ์ž์—ฐ์ˆ˜์ด๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ์˜ˆ์‹œ ์ž…๋ ฅ 1 8 6 1 2 1 3 1 1 1 2 ์˜ˆ์‹œ ์ถœ๋ ฅ 1 3 -๋‚˜์˜ ํ’€์ด- ๋‘ ๊ฐ€์ง€ ๋ฐฉ์‹์œผ๋กœ ํ’€์—ˆ๋˜ ์šฐ์„  ์ฒซ ๋ฒˆ์งธ, ์‹œ๊ฐ„ ๋ณต์žก๋„: O(N^2) ์ผ๋‹จ ๋‚˜์˜ ํ’€์ด์ด.. ์ฝ”๋”ฉํ…Œ์ŠคํŠธ 2023. 12. 24.
[์Šฌ๋ผ์ด๋”ฉ ์œˆ๋„์šฐ] 3. ์ตœ๋Œ€ ๋งค์ถœ 3. ์ตœ๋Œ€ ๋งค์ถœ ์„ค๋ช… ํ˜„์ˆ˜์˜ ์•„๋น ๋Š” ์ œ๊ณผ์ ์„ ์šด์˜ํ•ฉ๋‹ˆ๋‹ค. ํ˜„์ˆ˜ ์•„๋น ๋Š” ํ˜„์ˆ˜์—๊ฒŒ N์ผ ๋™์•ˆ์˜ ๋งค์ถœ๊ธฐ๋ก์„ ์ฃผ๊ณ  ์—ฐ์†๋œ K์ผ ๋™์•ˆ์˜ ์ตœ๋Œ€ ๋งค์ถœ์•ก์ด ์–ผ๋งˆ์ธ์ง€ ๊ตฌํ•˜๋ผ๊ณ  ํ–ˆ์Šต๋‹ˆ๋‹ค. ๋งŒ์•ฝ N=10์ด๊ณ  10์ผ ๊ฐ„์˜ ๋งค์ถœ๊ธฐ๋ก์ด ์•„๋ž˜์™€ ๊ฐ™์Šต๋‹ˆ๋‹ค. ์ด๋•Œ K=3์ด๋ฉด 12 1511 20 2510 20 19 13 15 ์—ฐ์†๋œ 3์ผ๊ฐ„์˜ ์ตœ๋Œ€ ๋งค์ถœ์•ก์€ 11+20+25=56๋งŒ์›์ž…๋‹ˆ๋‹ค. ์—ฌ๋Ÿฌ๋ถ„์ด ํ˜„์ˆ˜๋ฅผ ๋„์™€์ฃผ์„ธ์š”. ์ž…๋ ฅ ์ฒซ ์ค„์— N(5 ์ฝ”๋”ฉํ…Œ์ŠคํŠธ 2023. 12. 24.
[ํˆฌ ํฌ์ธํ„ฐ] 2. ๊ณตํ†ต์›์†Œ ๊ตฌํ•˜๊ธฐ 2. ๊ณตํ†ต์›์†Œ ๊ตฌํ•˜๊ธฐ ์„ค๋ช… A, B ๋‘ ๊ฐœ์˜ ์ง‘ํ•ฉ์ด ์ฃผ์–ด์ง€๋ฉด ๋‘ ์ง‘ํ•ฉ์˜ ๊ณตํ†ต ์›์†Œ๋ฅผ ์ถ”์ถœํ•˜์—ฌ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์„ธ์š”. ์ž…๋ ฅ ์ฒซ ๋ฒˆ์งธ ์ค„์— ์ง‘ํ•ฉ A์˜ ํฌ๊ธฐ N(1 ์ฝ”๋”ฉํ…Œ์ŠคํŠธ 2023. 12. 23.
[ํˆฌ ํฌ์ธํ„ฐ] 1. ๋‘ ๋ฐฐ์—ด ํ•ฉ์น˜๊ธฐ ํˆฌ ํฌ์ธํ„ฐ(Two Pointers) ๋ฆฌ์ŠคํŠธ์— ์ˆœ์ฐจ์ ์œผ๋กœ ์ ‘๊ทผํ•ด์•ผ ํ•  ๋•Œ ๋‘ ๊ฐœ์˜ ์ ์˜ ์œ„์น˜๋ฅผ ๊ธฐ๋กํ•˜๋ฉด์„œ ์ฒ˜๋ฆฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ •๋ ฌ ๋˜์–ด ์žˆ๋Š” ๋‘ ๋ฆฌ์ŠคํŠธ์˜ ํ•ฉ์ง‘ํ•ฉ์—๋„ ์‚ฌ์šฉ๋œ๋‹ค. ๋ณ‘ํ•ฉ์ •๋ ฌ(merge sort)์˜ counquer ์˜์—ญ์˜ ๊ธฐ์ดˆ๊ฐ€ ๋˜๊ธฐ๋„ ํ•œ๋‹ค. ์‹œ๊ฐ„๋ณต์žก๋„ ํšจ์œจ์„ฑ : O(n^2)-->O(n) 1. ๋‘ ๋ฐฐ์—ด ํ•ฉ์น˜๊ธฐ ์„ค๋ช… ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌ์ด ๋œ ๋‘ ๋ฐฐ์—ด์ด ์ฃผ์–ด์ง€๋ฉด ๋‘ ๋ฐฐ์—ด์„ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ํ•ฉ์ณ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์„ธ์š”. ์ž…๋ ฅ ์ฒซ ๋ฒˆ์งธ ์ค„์— ์ฒซ ๋ฒˆ์งธ ๋ฐฐ์—ด์˜ ํฌ๊ธฐ N(1 ์ฝ”๋”ฉํ…Œ์ŠคํŠธ 2023. 12. 23.