๊ด€๋ฆฌ ๋ฉ”๋‰ด

๋ชฉ๋ก๐Ÿ“š Language & CS knowledge/Algorithm (๊ธฐ์ดˆ๋ฌธ์ œํ’€์ด) (74)

Daehyunii's Dev-blog

์œ ํšจํ•œ ํŒฐ๋ฆฐ๋“œ๋กฌ(๋ฌธ์ž์—ด ํƒ์ƒ‰)

๋ฌธ์ œ(์ถœ์ฒ˜ : ์ธํ”„๋Ÿฐ ์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œํ’€์ด ๊ฐ•์˜, ์ •๋ณด์˜ฌ๋ฆผํ”ผ์•„๋“œ) ์•ž์—์„œ ์ฝ์„ ๋•Œ๋‚˜ ๋’ค์—์„œ ์ฝ์„ ๋•Œ๋‚˜ ๊ฐ™์€ ๋ฌธ์ž์—ด์„ ํŒฐ๋ฆฐ๋“œ๋กฌ์ด๋ผ๊ณ  ํ•ฉ๋‹ˆ๋‹ค.๋ฌธ์ž์—ด์ด ์ž…๋ ฅ๋˜๋ฉด ํ•ด๋‹น ๋ฌธ์ž์—ด์ด ํŒฐ๋ฆฐ๋“œ๋กฌ์ด๋ฉด "YES", ์•„๋‹ˆ๋ฉด “NO"๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์„ธ์š”.๋‹จ ํšŒ๋ฌธ์„ ๊ฒ€์‚ฌํ•  ๋•Œ ์•ŒํŒŒ๋ฒณ๋งŒ ๊ฐ€์ง€๊ณ  ํšŒ๋ฌธ์„ ๊ฒ€์‚ฌํ•˜๋ฉฐ, ๋Œ€์†Œ๋ฌธ์ž๋ฅผ ๊ตฌ๋ถ„ํ•˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค. ์•ŒํŒŒ๋ฒณ ์ด์™ธ์˜ ๋ฌธ์ž๋“ค์˜ ๋ฌด์‹œํ•ฉ๋‹ˆ๋‹ค. โ–ฃ ์ž…๋ ฅ์„ค๋ช… ์ฒซ ์ค„์— ์ •์ˆ˜ ๊ธธ์ด 100์„ ๋„˜์ง€ ์•Š๋Š” ๊ณต๋ฐฑ์ด ์—†๋Š” ๋ฌธ์ž์—ด์ด ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. โ–ฃ ์ถœ๋ ฅ์„ค๋ช… ์ฒซ ๋ฒˆ์งธ ์ค„์— ํŒฐ๋ฆฐ๋“œ๋กฌ์ธ์ง€์˜ ๊ฒฐ๊ณผ๋ฅผ YES ๋˜๋Š” NO๋กœ ์ถœ๋ ฅํ•ฉ๋‹ˆ๋‹ค. โ–ฃ ์ž…๋ ฅ์˜ˆ์ œ 1 found7, time: study; Yduts; emit, 7Dnuof โ–ฃ ์ถœ๋ ฅ์˜ˆ์ œ 1 YES Tip ๋ฌธ์ œํ’€์ด // ๋ฉ”์„œ๋“œ๋ฅผ ํ™œ์šฉํ•ด์„œ ์ž‘์„ฑํ•˜๊ธฐ (์ •๋‹ต๋ณด๊ณ  ..

ํšŒ๋ฌธ ๋ฌธ์ž์—ด(๋ฌธ์ž์—ด ํƒ์ƒ‰)

๋ฌธ์ œ(์ถœ์ฒ˜ : ์ธํ”„๋Ÿฐ ์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œํ’€์ด ๊ฐ•์˜, ์ •๋ณด์˜ฌ๋ฆผํ”ผ์•„๋“œ) ์•ž์—์„œ ์ฝ์„ ๋•Œ๋‚˜ ๋’ค์—์„œ ์ฝ์„ ๋•Œ๋‚˜ ๊ฐ™์€ ๋ฌธ์ž์—ด์„ ํšŒ๋ฌธ ๋ฌธ์ž์—ด์ด๋ผ๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๋ฌธ์ž์—ด์ด ์ž…๋ ฅ๋˜๋ฉด ํ•ด๋‹น ๋ฌธ์ž์—ด์ด ํšŒ๋ฌธ ๋ฌธ์ž์—ด์ด๋ฉด "YES", ํšŒ๋ฌธ ๋ฌธ์ž์—ด์ด ์•„๋‹ˆ๋ฉด “NO"๋ฅผ ์ถœ๋ ฅ ํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์„ธ์š”. ๋‹จ ํšŒ๋ฌธ์„ ๊ฒ€์‚ฌํ•  ๋•Œ ๋Œ€์†Œ๋ฌธ์ž๋ฅผ ๊ตฌ๋ถ„ํ•˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค. โ–ฃ ์ž…๋ ฅ์„ค๋ช… ์ฒซ ์ค„์— ์ •์ˆ˜ ๊ธธ์ด 100์„ ๋„˜์ง€ ์•Š๋Š” ๊ณต๋ฐฑ์ด ์—†๋Š” ๋ฌธ์ž์—ด์ด ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. โ–ฃ ์ถœ๋ ฅ์„ค๋ช… ์ฒซ ๋ฒˆ์งธ ์ค„์— ํšŒ๋ฌธ ๋ฌธ์ž์—ด์ธ์ง€์˜ ๊ฒฐ๊ณผ๋ฅผ YES ๋˜๋Š” NO๋กœ ์ถœ๋ ฅํ•ฉ๋‹ˆ๋‹ค. โ–ฃ ์ž…๋ ฅ์˜ˆ์ œ 1 gooG โ–ฃ ์ถœ๋ ฅ์˜ˆ์ œ 1 YES Tip 1) ๋ณ€์ˆ˜๋ฅผ ๋งŒ๋“ค์–ด์„œ 'NO'๋ฅผ ํ• ๋‹นํ•œ๋‹ค.(let result = 'NO';) 2) ์ธ์ˆ˜๋กœ ๋ฐ›์€ ๋ฌธ์ž์—ด์„ ๋Œ€๋ฌธ์ž ๋˜๋Š” ์†Œ๋ฌธ์ž๋กœ ํ†ต์ผ ์‹œ์ผœ ๋ณ€์ˆ˜์— ๋‹ด์•„ ๋†“๋Š”๋‹ค..

๋ด‰์šฐ๋ฆฌ(1,2์ฐจ์› ํƒ์ƒ‰)

๋ฌธ์ œ(์ถœ์ฒ˜ : ์ธํ”„๋Ÿฐ ์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œํ’€์ด ๊ฐ•์˜, ์ •๋ณด์˜ฌ๋ฆผํ”ผ์•„๋“œ) ์ง€๋„ ์ •๋ณด๊ฐ€ N*N ๊ฒฉ์žํŒ์— ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. ๊ฐ ๊ฒฉ์ž์—๋Š” ๊ทธ ์ง€์—ญ์˜ ๋†’์ด๊ฐ€ ์“ฐ์—ฌ์žˆ์Šต๋‹ˆ๋‹ค. ๊ฐ ๊ฒฉ์ž ํŒ์˜ ์ˆซ์ž ์ค‘ ์ž์‹ ์˜ ์ƒํ•˜์ขŒ์šฐ ์ˆซ์ž๋ณด๋‹ค ํฐ ์ˆซ์ž๋Š” ๋ด‰์šฐ๋ฆฌ ์ง€์—ญ์ž…๋‹ˆ๋‹ค. ๋ด‰์šฐ๋ฆฌ ์ง€์—ญ์ด ๋ช‡ ๊ฐœ ์žˆ๋Š” ์ง€ ์•Œ์•„๋‚ด๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์„ธ์š”. ๊ฒฉ์ž์˜ ๊ฐ€์žฅ์ž๋ฆฌ๋Š” 0์œผ๋กœ ์ดˆ๊ธฐํ™” ๋˜์—ˆ๋‹ค๊ณ  ๊ฐ€์ •ํ•œ๋‹ค. ๋งŒ์•ฝ N=5 ์ด๊ณ , ๊ฒฉ์žํŒ์˜ ์ˆซ์ž๊ฐ€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค๋ฉด ๋ด‰์šฐ๋ฆฌ์˜ ๊ฐœ์ˆ˜๋Š” 10๊ฐœ์ž…๋‹ˆ๋‹ค. 0 0 0 0 0 0 0 0 5 3 7 2 3 0 0 3 7 1 6 1 0 0 7 2 5 3 4 0 0 4 3 6 4 1 0 0 8 7 3 5 2 0 0 0 0 0 0 0 0 โ–ฃ ์ž…๋ ฅ์„ค๋ช… ์ฒซ ์ค„์— ์ž์—ฐ์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค.(1 ๋‚จ > ์„œ ๋ฐฉํ–ฅ์œผ๋กœ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋‹ค. 2) ์ด๋™์‹œ, ์ฃผ..

์ ์ˆ˜ ๊ณ„์‚ฐ(1,2์ฐจ์› ํƒ์ƒ‰)

๋ฌธ์ œ(์ถœ์ฒ˜ : ์ธํ”„๋Ÿฐ ์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œํ’€์ด ๊ฐ•์˜, ์ •๋ณด์˜ฌ๋ฆผํ”ผ์•„๋“œ) OX ๋ฌธ์ œ๋Š” ๋งž๊ฑฐ๋‚˜ ํ‹€๋ฆฐ ๋‘ ๊ฒฝ์šฐ์˜ ๋‹ต์„ ๊ฐ€์ง€๋Š” ๋ฌธ์ œ๋ฅผ ๋งํ•œ๋‹ค. ์—ฌ๋Ÿฌ ๊ฐœ์˜ OX ๋ฌธ์ œ๋กœ ๋งŒ๋“ค์–ด์ง„ ์‹œํ—˜์—์„œ ์—ฐ์†์ ์œผ๋กœ ๋‹ต์„ ๋งžํžˆ๋Š” ๊ฒฝ์šฐ์—๋Š” ๊ฐ€์‚ฐ์ ์„ ์ฃผ๊ธฐ ์œ„ํ•ด์„œ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ ์ˆ˜ ๊ณ„์‚ฐ์„ ํ•˜๊ธฐ ๋กœ ํ•˜์˜€๋‹ค. 1๋ฒˆ ๋ฌธ์ œ๊ฐ€ ๋งž๋Š” ๊ฒฝ์šฐ์—๋Š” 1์ ์œผ๋กœ ๊ณ„์‚ฐํ•œ๋‹ค. ์•ž์˜ ๋ฌธ์ œ์— ๋Œ€ํ•ด์„œ๋Š” ๋‹ต์„ ํ‹€๋ฆฌ๋‹ค๊ฐ€ ๋‹ต์ด ๋งž๋Š” ์ฒ˜์Œ ๋ฌธ์ œ๋Š” 1์ ์œผ๋กœ ๊ณ„์‚ฐํ•œ๋‹ค. ๋˜ํ•œ, ์—ฐ์†์œผ๋กœ ๋ฌธ์ œ์˜ ๋‹ต์ด ๋งž๋Š” ๊ฒฝ์šฐ์—์„œ ๋‘ ๋ฒˆ์งธ ๋ฌธ์ œ๋Š” 2์ , ์„ธ ๋ฒˆ์งธ ๋ฌธ์ œ๋Š” 3์ , ..., K๋ฒˆ์งธ ๋ฌธ์ œ๋Š” K์ ์œผ๋กœ ๊ณ„์‚ฐํ•œ๋‹ค. ํ‹€๋ฆฐ ๋ฌธ์ œ๋Š” 0์ ์œผ๋กœ ๊ณ„ ์‚ฐํ•œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ์•„๋ž˜์™€ ๊ฐ™์ด 10 ๊ฐœ์˜ OX ๋ฌธ์ œ์—์„œ ๋‹ต์ด ๋งž์€ ๋ฌธ์ œ์˜ ๊ฒฝ์šฐ์—๋Š” 1๋กœ ํ‘œ์‹œํ•˜๊ณ , ํ‹€๋ฆฐ ๊ฒฝ ์šฐ์—๋Š” 0์œผ๋กœ ํ‘œ์‹œํ•˜์˜€์„ ๋•Œ, ์ ์ˆ˜ ๊ณ„์‚ฐ์€..

๊ฐ€์œ„ ๋ฐ”์œ„ ๋ณด(1,2์ฐจ์› ํƒ์ƒ‰)

๋ฌธ์ œ(์ถœ์ฒ˜ : ์ธํ”„๋Ÿฐ ์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œํ’€์ด ๊ฐ•์˜, ์ •๋ณด์˜ฌ๋ฆผํ”ผ์•„๋“œ) A, B ๋‘ ์‚ฌ๋žŒ์ด ๊ฐ€์œ„๋ฐ”์œ„๋ณด ๊ฒŒ์ž„์„ ํ•ฉ๋‹ˆ๋‹ค. ์ด N๋ฒˆ์˜ ๊ฒŒ์ž„์„ ํ•˜์—ฌ A๊ฐ€ ์ด๊ธฐ๋ฉด A๋ฅผ ์ถœ๋ ฅํ•˜๊ณ , B๊ฐ€ ์ด๊ธฐ๋ฉด B๋ฅผ ์ถœ๋ ฅํ•ฉ๋‹ˆ๋‹ค. ๋น„๊ธธ ๊ฒฝ์šฐ์—๋Š” D๋ฅผ ์ถœ๋ ฅํ•ฉ๋‹ˆ๋‹ค. ๊ฐ€์œ„, ๋ฐ”์œ„, ๋ณด์˜ ์ •๋ณด๋Š” 1:๊ฐ€์œ„, 2:๋ฐ”์œ„, 3:๋ณด๋กœ ์ •ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด N=5์ด๋ฉด ํšŸ์ˆ˜ 1 2 3 4 5 A์˜ ์ •๋ณด 2 3 3 1 3 B์˜ ์ •๋ณด 1 1 2 2 3 ์Šน์ž A B A B D ๋‘ ์‚ฌ๋žŒ์˜ ๊ฐ ํšŒ์˜ ๊ฐ€์œ„, ๋ฐ”์œ„, ๋ณด ์ •๋ณด๊ฐ€ ์ฃผ์–ด์ง€๋ฉด ๊ฐ ํšŒ๋ฅผ ๋ˆ„๊ฐ€ ์ด๊ฒผ๋Š”์ง€ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ ์„ ์ž‘์„ฑํ•˜์„ธ์š”. โ–ฃ ์ž…๋ ฅ์„ค๋ช… ์ฒซ ๋ฒˆ์งธ ์ค„์— ๊ฒŒ์ž„ ํšŸ์ˆ˜์ธ ์ž์—ฐ์ˆ˜ N(1