๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
  • ์žฅ์›์ต ๊ธฐ์ˆ ๋ธ”๋กœ๊ทธ

๐Ÿ’ป Computer Science191

[์•Œ๊ณ ๋ฆฌ์ฆ˜] ์œ ํด๋ฆฌ๋“œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ํ†ตํ•œ ์ตœ์†Œ ๊ณต๋ฐฐ์ˆ˜์™€ ์ตœ๋Œ€ ๊ณต์•ฝ์ˆ˜ ๊ตฌํ•˜๊ธฐ ์œ ํด๋ฆฌ๋“œ ํ˜ธ์ œ๋ฒ• (์•Œ๊ณ ๋ฆฌ์ฆ˜)์€ ์„ธ๊ณ„ ์ตœ์ดˆ์˜ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ์ด ์„ธ๊ณ„ ์ตœ์ดˆ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์–ด๋–ค ๋™์ž‘์„ ํ•˜๊ณ  ์–ด๋–ค ๊ฒฐ๊ณผ๋ฅผ ๋‚ด๋Š”์ง€ ์•Œ์•„๋ณด์ž. ์šฐ๋ฆฌ๊ฐ€ ๋ฐฐ์šธ ๊ฒƒ ์œ ํด๋ฆฌ๋“œ ํ˜ธ์ œ๋ฒ• ์ตœ๋Œ€ ๊ณต์•ฝ์ˆ˜ ์ตœ์†Œ ๊ณต๋ฐฐ์ˆ˜ Java๋กœ ๊ตฌํ˜„ํ•˜๊ธฐ ์ตœ๋Œ€ ๊ณต์•ฝ์ˆ˜ ๋ฐ˜๋ณต๋ฌธ์„ ํ†ตํ•œ ๊ตฌํ˜„ ์žฌ๊ท€ํ˜ธ์ถœ์„ ํ†ตํ•œ ๊ตฌํ˜„ ์ตœ์†Œ ๊ณต๋ฐฐ์ˆ˜ ์‹œ๊ฐ„๋ณต์žก๋„ ์œ ํด๋ฆฌ๋“œ ํ˜ธ์ œ๋ฒ• ์œ ํด๋ฆฌ๋“œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ 2๊ฐœ์˜ ์ž์—ฐ์ˆ˜์˜ ์ตœ๋Œ€ ๊ณต์•ฝ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค. ์ตœ๋Œ€ ๊ณต์•ฝ์ˆ˜๋ž€ ๋ฌด์—‡์ธ์ง€ ๊ธฐ์–ต์ด ๋‚˜๋ฉด ์ข‹๊ฒ ์ง€๋งŒ ์ตœ๋Œ€๊ณต์•ฝ์ˆ˜๋Š” ์ค‘ํ•™๊ต 1ํ•™๋…„ ๊ต์œก ๊ณผ์ •์— ๋‚˜์˜ค๋Š” ๋‚ด์šฉ์ด๋ผ ๊นŒ๋จน์—ˆ์„ ์ˆ˜ ์žˆ๋Š” ์—ฌ๋Ÿฌ๋ถ„์—๊ฒŒ ๋‹ค์‹œ ํ•œ๋ฒˆ ์ƒ๊ธฐ์‹œ์ผœ์ฃผ์ž๋ฉด ์ตœ๋Œ€ ๊ณต์•ฝ์ˆ˜์™€ ์ตœ์†Œ ๊ณต๋ฐฐ์ˆ˜ ์ตœ๋Œ€ ๊ณต์•ฝ์ˆ˜์™€ ์ตœ์†Œ ๊ณต๋ฐฐ์ˆ˜๋ฅผ ๊ฐ€์žฅ ๋นจ๋ฆฌ ์ƒ๊ธฐ์‹œํ‚ค๋Š” ๋ฐฉ๋ฒ•์€ ์šฐ๋ฆฌ๊ฐ€ ์ฃฝ์–ด๋ผ ํ–ˆ๋˜ ๊ณต์‹์„ ํ•œ ๋ฒˆ ๋ณด์—ฌ์ฃผ๋Š” ๊ฒƒ์ด๋ผ ์ƒ๊ฐํ–ˆ๋‹ค. ์ตœ๋Œ€๊ณต์•ฝ์ˆ˜(GCD) ๋Š” ์–ด๋–ค ๋‘ ์ˆ˜ A, B๊ฐ€.. 2021. 2. 4.
[์•Œ๊ณ ๋ฆฌ์ฆ˜ PS] ๋ฐฑ์ค€ 1158๋ฒˆ ์š”์„ธํ‘ธ์Šค ๋ฌธ์ œ ์ž๋ฐ” ๋ฌธ์ œํ’€์ด (ํ, ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ ํ’€์ด) ๋ฌธ์ œ ํ•ด๋‹น ํฌ์ŠคํŒ…์€ ๋ฐฑ์ค€์˜ 1158๋ฒˆ ์š”์„ธํ‘ธ์Šค ๋ฌธ์ œ ์˜ ์ ‘๊ทผ๊ณผ ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•์„ ์„ค๋ช…ํ•œ ๊ธ€ ์ž…๋‹ˆ๋‹ค. ์ •๋‹ต ์†Œ์Šค ์ฝ”๋“œ๋ฅผ ํ™•์ธํ•˜์‹œ๋ ค๋ฉด solve url ์—์„œ ํ™•์ธ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค. ์ด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด ์–ด๋–ค ๋ฐฉ์‹์œผ๋กœ ์ ‘๊ทผํ•ด์•ผ ํ•˜๋Š”์ง€๋ฅผ ๋จผ์ € ์ƒ๊ฐํ•ด๋ณด์ž. ํ•ด๊ฒฐ๋ฒ• ์ด ๋ฌธ์ œ๋Š” ํ ์ž๋ฃŒ๊ตฌ์กฐ๋กœ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋Š” ๋Œ€ํ‘œ์ ์ธ ๋ฌธ์ œ๊ฒฉ์ด๋‹ค. ๋ฌธ์ œ๋Š” ์ด๋ ‡๋‹ค. 1 ~ N ๊นŒ์ง€ ์ˆ˜๋ฅผ 1์ž๋กœ ๋Š˜์—ฌ๋†“๋Š”๋‹ค. N = 7 1, 2, 3, 4, 5, 6, 7 ๊ทธ๋ฆฌ๊ณ  ํฌ์ธํ„ฐ๋ฅผ K๋งŒํผ ์›€์ง์ธ ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•˜๊ณ  ํ•ด๋‹น ๋ฆฌ์ŠคํŠธ์—์„œ ์ œ์™ธ์‹œํ‚จ๋‹ค. ์ด ๊ณผ์ •์„ ๋ฆฌ์ŠคํŠธ์— ์›์†Œ๊ฐ€ ์—†์„ ๋•Œ ๊นŒ์ง€ ๋ฐ˜๋ณตํ•˜๋Š”๋ฐ, ๋‹ค์Œ๊ณผ ๊ฐ™์€ ํ˜•ํƒœ์ด๋‹ค. N = 7, K = 3 Rount 1 => 1, 2, 3, 4, 5, 6, 7 => - => return => 3, Rount 2 => 1, 2, .. 2021. 2. 3.
[์•Œ๊ณ ๋ฆฌ์ฆ˜ PS] ๋ฐฑ์ค€ 11656๋ฒˆ ์ ‘๋ฏธ์‚ฌ ๋ฐฐ์—ด ์ž๋ฐ” ๋ฌธ์ œํ’€์ด ๋ฌธ์ œ ํ•ด๋‹น ํฌ์ŠคํŒ…์€ ๋ฐฑ์ค€์˜ 11656๋ฒˆ ์ ‘๋ฏธ์‚ฌ ๋ฐฐ์—ด ์˜ ์ ‘๊ทผ๊ณผ ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•์„ ์„ค๋ช…ํ•œ ๊ธ€ ์ž…๋‹ˆ๋‹ค. ์ •๋‹ต ์†Œ์Šค ์ฝ”๋“œ๋ฅผ ํ™•์ธํ•˜์‹œ๋ ค๋ฉด solve url ์—์„œ ํ™•์ธ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค. ์ด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด ์–ด๋–ค ๋ฐฉ์‹์œผ๋กœ ์ ‘๊ทผํ•ด์•ผ ํ•˜๋Š”์ง€๋ฅผ ๋จผ์ € ์ƒ๊ฐํ•ด๋ณด์ž. ํ•ด๊ฒฐ๋ฒ• ๋ฌธ์ œ ๋ถ„์„์„ ํ•ด๋ณด์ž. ์šฐ์„  ๋ฌธ์ž์—ด ๊ธธ์ด๊ฐ€ n์ธ ๋ฌธ์ž๊ฐ€ ๋“ค์–ด์˜จ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ์šฐ๋ฆฌ๋Š” ๊ทธ ๋ฌธ์ž์—ด์˜ ๊ธธ์ด๊ฐ€ n-1, n-2 ... 1์ด ๋  ๋•Œ ๊นŒ์ง€ ๋ฐ˜๋ณตํ•ด์„œ ๋ฌธ์ž์—ด์„ ๋‚˜๋ˆ„๊ณ  ํ•ด๋‹น ๋ฌธ์ž ๋ฐฐ์—ด์„ ์ •๋ ฌํ•˜๋ฉด ๋œ๋‹ค. ์‹œ๊ฐ„ ๋ณต์žก๋„ ํ˜น์‹œ ๋ชจ๋ฅด๋‹ˆ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ๊ณ„์‚ฐ ํ•ด๋ณด์ž. ์ผ๋‹จ ๋ฌธ์ž์—ด์˜ ๊ธธ์ด๊ฐ€ ์ด๋ฒˆ ๋ฐ˜๋ณต์˜ ์ฃผ์ฒด์ธ n์ด ๋  ๊ฒƒ์ด๋ฏ€๋กœ n์€ ์ตœ๋Œ€ 1,000์ด๋‹ค. ๋˜ํ•œ ์šฐ๋ฆฌ๋Š” java์— ํฌํ•จ๋œ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•  ๊ฒƒ์ธ๋ฐ, java ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ Object์ธ ๊ฒฝ์šฐ TimSort๋ฅผ ์ˆ˜.. 2021. 2. 3.
[์•Œ๊ณ ๋ฆฌ์ฆ˜ PS] ๋ฐฑ์ค€ 10824๋ฒˆ ๋„ค ์ˆ˜ ์ž๋ฐ” ๋ฌธ์ œํ’€์ด ๋ฌธ์ œ ํ•ด๋‹น ํฌ์ŠคํŒ…์€ ๋ฐฑ์ค€์˜ 10824๋ฒˆ ๋„ค ์ˆ˜ ์˜ ์ ‘๊ทผ๊ณผ ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•์„ ์„ค๋ช…ํ•œ ๊ธ€ ์ž…๋‹ˆ๋‹ค. ์ •๋‹ต ์†Œ์Šค ์ฝ”๋“œ๋ฅผ ํ™•์ธํ•˜์‹œ๋ ค๋ฉด solve url ์—์„œ ํ™•์ธ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค. ์ด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด ์–ด๋–ค ๋ฐฉ์‹์œผ๋กœ ์ ‘๊ทผํ•ด์•ผ ํ•˜๋Š”์ง€๋ฅผ ๋จผ์ € ์ƒ๊ฐํ•ด๋ณด์ž. ํ•ด๊ฒฐ๋ฒ• ์ด๋ฒˆ ๋ฌธ์ œ๋Š” ๊ฐ„๋‹จํ•œ ๋…ผ๋ฆฌ๋กœ ํ’€ ์ˆ˜ ์žˆ์ง€๋งŒ ์ •๋‹ต ๋น„์œจ์ด 39%๋กœ ๋†’์€ ๋น„์œจ์€ ์•„๋‹ˆ๋‹ค. ์™œ ์‚ฌ๋žŒ๋“ค์ด ๋งŽ์ด ํ‹€๋ฆด์ง€ ์ƒ๊ฐํ•ด๋ณด๋ฉฐ ๋ฌธ์ œ๋ฅผ ํ’€์–ด๋ณด์ž. ์ ‘๊ทผ๋ฒ• ์šฐ์„  ์šฐ๋ฆฌ๋Š” 4๊ฐœ์˜ ์ž์—ฐ์ˆ˜๋ฅผ ๋ฐ›๊ฒŒ ๋œ๋‹ค. AB๋ฅผ ๋ถ™ํžˆ๊ณ  CD๋ฅผ ๋ถ™ํžŒ ์ˆ˜์— ์‚ฐ์ˆ  ํ•ฉ์„ ๊ตฌํ•˜๋ฉด ๋ฌธ์ œ๋Š” ๋๋‚œ๋‹ค. ๊ทธ๋Ÿผ AB๋ผ๋Š” ์ˆ˜๋ฅผ ํ•ฉ์น˜๋ ค๋ฉด ์–ด๋–ป๊ฒŒ ํ•ด์•ผํ• ๊นŒ? ์ •๋‹ต์ด๋‹ค. ๋ฌธ์ž์—ด๋กœ ๋งŒ๋“ค๊ณ  ์ด๋ฅผ ์„œ๋กœ ํ•ฉ์น˜๋ฉด ๋œ๋‹ค. ์˜ค๋‹ต ํ›„๋ณด ์—ฌ๊ธฐ์„œ ์ฃผ์˜ํ•ด์•ผํ•  ์ ์ด ํ•˜๋‚˜ ์žˆ๋‹ค. ์ž…๋ ฅ a, b, c, d๋Š” ์ตœ๋Œ€ ๋ฐฑ๋งŒ์˜ ์ˆ˜๊ฐ€ ๋“ค์–ด์˜จ๋‹ค. ๊ทธ๋Ÿผ a ์™€ b๋ฅผ.. 2021. 2. 3.
[์•Œ๊ณ ๋ฆฌ์ฆ˜ PS] ๋ฐฑ์ค€ 11655๋ฒˆ ROT13 ์ž๋ฐ” ๋ฌธ์ œ ํ’€์ด ๋ฌธ์ œ ํ•ด๋‹น ํฌ์ŠคํŒ…์€ ๋ฐฑ์ค€์˜ 11656๋ฒˆ ROT13 ์˜ ์ ‘๊ทผ๊ณผ ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•์„ ์„ค๋ช…ํ•œ ๊ธ€ ์ž…๋‹ˆ๋‹ค. ์ •๋‹ต ์†Œ์Šค ์ฝ”๋“œ๋ฅผ ํ™•์ธํ•˜์‹œ๋ ค๋ฉด solve url ์—์„œ ํ™•์ธ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค. ์ด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด ์–ด๋–ค ๋ฐฉ์‹์œผ๋กœ ์ ‘๊ทผํ•ด์•ผ ํ•˜๋Š”์ง€๋ฅผ ๋จผ์ € ์ƒ๊ฐํ•ด๋ณด์ž. ํ•ด๊ฒฐ๋ฒ• ์ด๋ฒˆ ๋ฌธ์ œ๋Š” ๋ฌธ์ž์—ด ์ฒ˜๋ฆฌ ๋ฌธ์ œ์ค‘ ์žฌ๋ฐŒ๊ฒŒ ํ’€ ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ์ด๋‹ค. ์šฐ์„  ๋ฌธ์ œ ๋ถ„์„๋ถ€ํ„ฐ ํ•ด๋ณด์ž. ROT13์€ ์นด์ด์‚ฌ๋ฅด ์•”ํ˜ธ์˜ ์ผ์ข…์ด๋ผ๊ณ  ํ•˜๋Š”๋ฐ, ํ•ต์‹ฌ์€ 13๊ธ€์ž ์•ž์œผ๋กœ shiftํ•˜๋ฉด ๋œ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๋ฌธ์ œ์—์„œ๋Š” 4๊ฐ€์ง€ ๋ฌธ์ž๊ฐ€ ๋“ค์–ด์˜ฌ ์ˆ˜ ์žˆ๋Š”๋ฐ, ๋Œ€๋ฌธ์ž ์•ŒํŒŒ๋ฒณ ์†Œ๋ฌธ์ž ์•ŒํŒŒ๋ฒณ ์ˆซ์ž ๊ณต๋ฐฑ ์•ŒํŒŒ๋ฒณ๋งŒ shiftํ•ด์•ผ ํ•œ๋‹ค. ์ ‘๊ทผ๋ฒ• ์กฐ๊ธˆ ๋” ์ƒ๊ฐํ•ด๋ณด๋ฉด ์‹ค์ œ๋กœ shift ์—ฐ์‚ฐ์„ ์ˆ˜ํ–‰ํ•˜์ง€ ์•Š๊ณ ๋„ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์„ ๊ฒƒ ๊ฐ™๋‹ค. ์•ŒํŒŒ๋ฒณ ์ธ๋ฑ์Šค์— + 13์„ ๋‘ ๋ฒˆ ํ•˜๋ฉด ๋‹ค์‹œ ์›๋ž˜์˜ ๋ฌธ์ž๋กœ.. 2021. 2. 3.
[์•Œ๊ณ ๋ฆฌ์ฆ˜ PS] ๋ฐฑ์ค€ 10820๋ฒˆ ๋ฌธ์ž์—ด ๋ถ„์„ ์ž๋ฐ” ๋ฌธ์ œํ’€์ด ๋ฌธ์ œ ํ•ด๋‹น ํฌ์ŠคํŒ…์€ ๋ฐฑ์ค€์˜ 10820๋ฒˆ ๋ฌธ์ž์—ด ๋ถ„์„ ์˜ ์ ‘๊ทผ๊ณผ ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•์„ ์„ค๋ช…ํ•œ ๊ธ€ ์ž…๋‹ˆ๋‹ค. ์ •๋‹ต ์†Œ์Šค ์ฝ”๋“œ๋ฅผ ํ™•์ธํ•˜์‹œ๋ ค๋ฉด solve url ์—์„œ ํ™•์ธ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค. ์ด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด ์–ด๋–ค ๋ฐฉ์‹์œผ๋กœ ์ ‘๊ทผํ•ด์•ผ ํ•˜๋Š”์ง€๋ฅผ ๋จผ์ € ์ƒ๊ฐํ•ด๋ณด์ž. ํ•ด๊ฒฐ๋ฒ• ์ด๋ฒˆ ๋ฌธ์ œ๋Š” ๋ฌธ์ž์—ด์ด ์ฃผ์–ด์ง€๋ฉด ๋‹ค์Œ 4๊ฐœ์˜ ๋ฌธ์ž ํ˜•ํƒœ์ค‘ ์–ด๋–ค ํ˜•ํƒœ๋ฅผ ๋„๊ณ ์žˆ๋Š”์ง€๋ฅผ ๋ฌผ์–ด๋ณด๋Š” ๋ฌธ์ œ์ด๋‹ค. ์˜์–ด ์†Œ๋ฌธ์ž. ์˜์–ด ๋Œ€๋ฌธ์ž. ์ˆซ์ž. ๊ณต๋ฐฑ ์ด๋Ÿฐ ์ข…๋ฅ˜์˜ ๋ฌธ์ œ๋Š” ๋Œ€๊ฐœ ์•„์Šคํ‚ค ์ฝ”๋“œ๋ฅผ ์ด์šฉํ•˜๋ฉด ๋น ๋ฅด๊ฒŒ ํ’€ ์ˆ˜ ์žˆ๋‹ค. ์•„์Šคํ‚ค ์ฝ”๋“œํ‘œ์— ๊ด€ํ•œ ๊ฒƒ์€ ํ•ด๋‹น ๋งํฌ๋ฅผ ํด๋ฆญํ•ด์„œ ํ™•์ธํ•  ์ˆ˜ ์žˆ๋‹ค. ์ ‘๊ทผ๋ฒ• ๋‹ค์‹œ ๋ฌธ์ œ๋กœ ๋Œ์•„์™€ ์šฐ๋ฆฌ๊ฐ€ ์ฐพ์œผ๋ ค๋Š” ๋ฌธ์ž ํ˜•ํƒœ์˜ ์•„์Šคํ‚ค ์ฝ”๋“œ๋ฅผ ํ™•์ธํ•ด๋ณด์ž. ๊ทธ๋Ÿผ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋ฒ”์œ„๊ฐ€ ์ƒ์„ฑ๋œ๋‹ค. ์˜์–ด ์†Œ๋ฌธ์ž : 97 ~ 122 ์˜์–ด ๋Œ€๋ฌธ์ž : 65 ~ 90 ์ˆซ์ž .. 2021. 2. 3.