Notice
Recent Posts
Recent Comments
Link
๊ด€๋ฆฌ ๋ฉ”๋‰ด

๋ชฉ๋ก์ „์ฒด ๊ธ€ (1097)

KoreanFoodie's Study

[์ข…๋งŒ๋ถ ๋ฌธ์ œ] ๋‘๋‹ˆ๋ฐœ ๋ฐ•์‚ฌ์˜ ํƒˆ์˜ฅ (๋ฌธ์ œ ID : NUMB3RS, ๋‚œ์ด๋„ : ์ค‘)

ํ”„๋กœ๊ทธ๋ž˜๋ฐ ๋Œ€ํšŒ์—์„œ ๋ฐฐ์šฐ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œํ•ด๊ฒฐ ์ „๋žต(์ดํ•˜ ์ข…๋งŒ๋ถ)์—์„œ ์†Œ๊ฐœ๋œ ๋ฌธ์ œ๋ฅผ ํ’€์ดํ•ฉ๋‹ˆ๋‹ค. ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ์ง„์‹ฌ์ด์‹œ๋ผ๋ฉด, ์ง์ ‘ ๊ตฌ๋งคํ•˜์…”์„œ ์ฝ์–ด๋ณด์‹œ๋Š” ๊ฒƒ์„ ์ถ”์ฒœํ•ฉ๋‹ˆ๋‹ค! ํ•ต์‹ฌ : 1. ํ .. ์ด ์ •๋ˆ๊ฐ€? [์ข…๋งŒ๋ถ ๋ฌธ์ œ] ๋‘๋‹ˆ๋ฐœ ๋ฐ•์‚ฌ์˜ ํƒˆ์˜ฅ (๋ฌธ์ œ ID : NUMB3RS, ๋‚œ์ด๋„ : ์ค‘) ์—ฌ๊ธฐ๊นŒ์ง€ ์™”์œผ๋ฉด, ์ด์ œ DP ๋ฌธ์ œ๋Š” ํŒจํ„ด์ด ํ•™์Šต๋˜์—ˆ์„ ๊ฒƒ์ด๋‹ค. ๊ทธ๋ƒฅ... ์•„๋ž˜์ฒ˜๋Ÿผ ํ’€๋ฉด ๋œ๋‹ฌ๊นŒ์š”(์›ƒ์Œ). #include #include "stdlib.h" #include #include #include #include #include using namespace std; /*************************************************************************************..

[์ข…๋งŒ๋ถ ๋ฌธ์ œ] ํด๋ฆฌ์˜ค๋ฏธ๋…ธ (๋ฌธ์ œ ID : POLY, ๋‚œ์ด๋„ : ์ค‘)

ํ”„๋กœ๊ทธ๋ž˜๋ฐ ๋Œ€ํšŒ์—์„œ ๋ฐฐ์šฐ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œํ•ด๊ฒฐ ์ „๋žต(์ดํ•˜ ์ข…๋งŒ๋ถ)์—์„œ ์†Œ๊ฐœ๋œ ๋ฌธ์ œ๋ฅผ ํ’€์ดํ•ฉ๋‹ˆ๋‹ค. ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ์ง„์‹ฌ์ด์‹œ๋ผ๋ฉด, ์ง์ ‘ ๊ตฌ๋งคํ•˜์…”์„œ ์ฝ์–ด๋ณด์‹œ๋Š” ๊ฒƒ์„ ์ถ”์ฒœํ•ฉ๋‹ˆ๋‹ค! ํ•ต์‹ฌ : 1. ์–ธ๋œป ๋ถˆ๊ฐ€๋Šฅํ•ด ๋ณด์ด๋Š” ๋ฌธ์ œ๋„, ๋ฌธ์ œ์˜ ์กฐ๊ฑด์„ ์ž˜ ๋ณด๋ฉด ๋ถ€๋ถ„ ๋ฌธ์ œ์˜ ์กฐํ•ฉ์œผ๋กœ ๋ถ„ํ•ดํ•ด ๋ณผ ์ˆ˜ ์žˆ๋‹ค! [์ข…๋งŒ๋ถ ๋ฌธ์ œ] ํด๋ฆฌ์˜ค๋ฏธ๋…ธ (๋ฌธ์ œ ID : POLY, ๋‚œ์ด๋„ : ์ค‘) ํœด.. ๋งจ ์ฒ˜์Œ์—๋Š” ๋ฌด์Šจ ๋ฌธ์ œ์ธ๊ฐ€ ์‹ถ์—ˆ์ง€๋งŒ, ๊ฒฐ๊ตญ ํ’€์–ด๋‚ด์„œ ์„ฑ์ทจ๊ฐ์ด ์žˆ๋Š” ๋ฌธ์ œ์˜€๋‹ค. ์ฑ…์— ์žˆ๋Š” ์ ‘๊ทผ๋ฒ•์„ ์กฐ๊ธˆ ๊ฐ€์ ธ์™€ ๋ณด์ž๋ฉด... ์œ„์˜ ์„ฑ์งˆ์„ ์ด์šฉํ•ด์„œ ์ ํ™”์‹์„ ์„ธ์šฐ๋ฉด ๋œ๋‹ค. ์™œ ์ด๋ ‡๊ฒŒ ๋˜๋ƒ๋ฉด, ํ•œ ์ค„์— ์žˆ๋Š” ๋ธ”๋Ÿญ๋“ค์€ ์„œ๋กœ ๋–จ์–ด์ ธ ์žˆ์œผ๋ฉด ์•ˆ๋˜๊ณ  ๋ถ™์–ด ์žˆ์–ด์•ผ ํ•˜๋Š” ์„ฑ์งˆ ๋•Œ๋ฌธ์ด๋‹ค! ๐Ÿ˜‰ ์ ํ™”์‹์€ ๋Œ€๋žต ์•„๋ž˜์ฒ˜๋Ÿผ ์ƒ๊ฒผ๋‹ค. ๋‚˜ ๊ฐ™์€ ๊ฒฝ์šฐ, ์ฒ˜์Œ์—๋Š” ์•„๋ž˜์ฒ˜๋Ÿผ for-loop ์œผ๋กœ..

[์ข…๋งŒ๋ถ ๋ฌธ์ œ] ๋น„๋Œ€์นญ ํƒ€์ผ๋ง (๋ฌธ์ œ ID : ASYMTILING, ๋‚œ์ด๋„ : ํ•˜)

ํ”„๋กœ๊ทธ๋ž˜๋ฐ ๋Œ€ํšŒ์—์„œ ๋ฐฐ์šฐ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œํ•ด๊ฒฐ ์ „๋žต(์ดํ•˜ ์ข…๋งŒ๋ถ)์—์„œ ์†Œ๊ฐœ๋œ ๋ฌธ์ œ๋ฅผ ํ’€์ดํ•ฉ๋‹ˆ๋‹ค. ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ์ง„์‹ฌ์ด์‹œ๋ผ๋ฉด, ์ง์ ‘ ๊ตฌ๋งคํ•˜์…”์„œ ์ฝ์–ด๋ณด์‹œ๋Š” ๊ฒƒ์„ ์ถ”์ฒœํ•ฉ๋‹ˆ๋‹ค! ํ•ต์‹ฌ : 1. ์‹ ๋น„๋กœ์šด ๋™์  ๊ณ„ํš๋ฒ•์˜ ์„ธ๊ณ„... ์„ธ๋Š” ๋ฐฉ๋ฒ•์€ ์—ฌ๋Ÿฌ ๊ฐ€์ง€์ผ ์ˆ˜ ์žˆ๋‹ค. [์ข…๋งŒ๋ถ ๋ฌธ์ œ] ๋น„๋Œ€์นญ ํƒ€์ผ๋ง (๋ฌธ์ œ ID : ASYMTILING, ๋‚œ์ด๋„ : ํ•˜) ์‚ฌ์‹ค ์ด ๋ฌธ์ œ๋Š” ์ด์ „์˜ ํƒ€์ผ๋ง ๋ฌธ์ œ์™€ ๋งค์šฐ ๋น„์Šทํ•˜๋‹ค. ์ค‘์š”ํ•œ ๊ฑด '๋Œ€์นญ์ธ ๊ฒฝ์šฐ๋ฅผ ์–ด๋–ป๊ฒŒ ๋บผ ๊ฒƒ์ธ๊ฐ€?' ์ธ๋ฐ, ์ž˜ ์ƒ๊ฐํ•ด ๋ณด๋ฉด ๊ธธ์ด๊ฐ€ ํ™€์ˆ˜์ผ ๋•Œ์™€ ์ง์ˆ˜์ผ ๋•Œ๋ฅผ ๋‚˜๋ˆ ์„œ ๊ฐ„๋‹จํ•œ ์—ฐ์‚ฐ์„ ํ•ด ์ฃผ๋ฉด ๋œ๋‹ค๋Š” ๊ฒƒ์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค. ์‚ฌ์‹ค ๊ทธ๋‹ค์ง€ ๊น”๋”ํ•˜์ง€๋Š” ์•Š์ง€๋งŒ, ๋‚˜๋Š” ์•„๋ž˜ ์ฝ”๋“œ์ฒ˜๋Ÿผ ํ’€์—ˆ๋‹ค. #include #include "stdlib.h" #include #include #include #i..

[์ข…๋งŒ๋ถ ๋ฌธ์ œ] ๋‹ฌํŒฝ์ด (๋ฌธ์ œ ID : SNAIL, ๋‚œ์ด๋„ : ํ•˜)

ํ”„๋กœ๊ทธ๋ž˜๋ฐ ๋Œ€ํšŒ์—์„œ ๋ฐฐ์šฐ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œํ•ด๊ฒฐ ์ „๋žต(์ดํ•˜ ์ข…๋งŒ๋ถ)์—์„œ ์†Œ๊ฐœ๋œ ๋ฌธ์ œ๋ฅผ ํ’€์ดํ•ฉ๋‹ˆ๋‹ค. ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ์ง„์‹ฌ์ด์‹œ๋ผ๋ฉด, ์ง์ ‘ ๊ตฌ๋งคํ•˜์…”์„œ ์ฝ์–ด๋ณด์‹œ๋Š” ๊ฒƒ์„ ์ถ”์ฒœํ•ฉ๋‹ˆ๋‹ค! ํ•ต์‹ฌ : 1. ์‹œ์‹œํ•ด์„œ ์ฃฝ๊ณ  ์‹ถ์–ด์กŒ๋‹ค. [์ข…๋งŒ๋ถ ๋ฌธ์ œ] ๋‹ฌํŒฝ์ด (๋ฌธ์ œ ID : SNAIL, ๋‚œ์ด๋„ : ํ•˜) ์‰ฌ์šด DP ๋ฌธ์ œ๋‹ค. ์ ํ™”์‹๋งŒ ์ž˜ ์„ธ์šฐ๋ฉด ๋˜๋Š”๋ฐ... ์ฑ…์—์„œ๋Š” ์•„๋ž˜์ฒ˜๋Ÿผ ๋งŒ๋“ค๋”๋ผ. ๋‚˜ ๊ฐ™์€ ๊ฒฝ์šฐ, ์•„๋ž˜์™€ ๊ฐ™์ด ํ’€์—ˆ๋‹ค. ์ ํ™”์‹์˜ ์›๋ฆฌ๋Š” ๊ฑฐ์˜ ๋™์ผํ•˜๋‹ค! #include #include "stdlib.h" #include #include #include #include #include using namespace std; /******************************************************************..

[์ข…๋งŒ๋ถ ๋ฌธ์ œ] ์‚ผ๊ฐํ˜• ์œ„์˜ ์ตœ๋Œ€ ๊ฒฝ๋กœ ์ˆ˜ ์„ธ๊ธฐ (๋ฌธ์ œ ID : TRIPATHCNT, ๋‚œ์ด๋„ : ์ค‘)

ํ”„๋กœ๊ทธ๋ž˜๋ฐ ๋Œ€ํšŒ์—์„œ ๋ฐฐ์šฐ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œํ•ด๊ฒฐ ์ „๋žต(์ดํ•˜ ์ข…๋งŒ๋ถ)์—์„œ ์†Œ๊ฐœ๋œ ๋ฌธ์ œ๋ฅผ ํ’€์ดํ•ฉ๋‹ˆ๋‹ค. ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ์ง„์‹ฌ์ด์‹œ๋ผ๋ฉด, ์ง์ ‘ ๊ตฌ๋งคํ•˜์…”์„œ ์ฝ์–ด๋ณด์‹œ๋Š” ๊ฒƒ์„ ์ถ”์ฒœํ•ฉ๋‹ˆ๋‹ค! ํ•ต์‹ฌ : 1. ๊ฐ„๋‹จํ•œ DP ๋ฌธ์ œ์ง€๋งŒ.. ์žฌ๊ท€๋กœ๋„ ํ’€์–ด๋ณด์ž. [์ข…๋งŒ๋ถ ๋ฌธ์ œ] ์‚ผ๊ฐํ˜• ์œ„์˜ ์ตœ๋Œ€ ๊ฒฝ๋กœ ์ˆ˜ ์„ธ๊ธฐ (๋ฌธ์ œ ID : TRIPATHCNT, ๋‚œ์ด๋„ : ์ค‘) ์ด๋ฒˆ ๋ฌธ์ œ๋„, ๊ฐ„๋‹จํ•˜๊ฒŒ DP ๋กœ ํ’€ ์ˆ˜ ์žˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค. #include #include "stdlib.h" #include #include #include #include using namespace std; /*****************************************************************************************..

[์ข…๋งŒ๋ถ ๋ฌธ์ œ] Quantization (๋ฌธ์ œ ID : QUANTIZE, ๋‚œ์ด๋„ : ์ค‘)

ํ”„๋กœ๊ทธ๋ž˜๋ฐ ๋Œ€ํšŒ์—์„œ ๋ฐฐ์šฐ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œํ•ด๊ฒฐ ์ „๋žต(์ดํ•˜ ์ข…๋งŒ๋ถ)์—์„œ ์†Œ๊ฐœ๋œ ๋ฌธ์ œ๋ฅผ ํ’€์ดํ•ฉ๋‹ˆ๋‹ค. ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ์ง„์‹ฌ์ด์‹œ๋ผ๋ฉด, ์ง์ ‘ ๊ตฌ๋งคํ•˜์…”์„œ ์ฝ์–ด๋ณด์‹œ๋Š” ๊ฒƒ์„ ์ถ”์ฒœํ•ฉ๋‹ˆ๋‹ค! ํ•ต์‹ฌ : 1. ์ตœ์  ๋ถ€๋ถ„ ๋ฌธ์ œ๋ฅผ ์ฐพ๋Š” ๊ฒƒ์€ ๊ฐ„ํ˜น, ๋งค์šฐ ์‰ฝ์ง€ ์•Š์€ ์ผ์ด๋‹ค... ๋ฌด์‹ํ•˜๊ฒŒ ํ‘ธ๋Š” ์ „๋ฒ•๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜๋ฉด ํฐ์ฝ”๊ฐ€ ๋‹ค์น  ์ˆ˜ ์žˆ๋‹ค. ๊ทผ๋ฐ ๋‚˜ ์ฝ” ๋‚ฎ์€๋ฐ.. ์–ด์จŒ๋“  ๋‹ค์ณค๋‹ค. [์ข…๋งŒ๋ถ ๋ฌธ์ œ] Quantization (๋ฌธ์ œ ID : QUANTIZE, ๋‚œ์ด๋„ : ์ค‘) ์ด ๋ฌธ์ œ๋Š” ์•„์ด๋””์–ด๊ฐ€ ํ•„์š”ํ•˜๋‹ค. ๋‹จ์ˆœํžˆ ์ˆ˜์—ด์„ ์ •๋ ฌํ•œ ๋‹ค์Œ์—, ์ˆซ์ž๋ฅผ ์ตœ์†Ÿ๊ฐ’์—์„œ ์ตœ๋Œ“๊ฐ’๊นŒ์ง€ ๋„ฃ๋Š” ๋ฐฉ์‹์œผ๋กœ๋Š” ํ’€ ์ˆ˜ ์—†๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค. ๊ทธ๋Ÿฐ๋ฐ ์ด๋ ‡๊ฒŒ ๋ฌถ์–ด๋ณด๋ฉด ์–ด๋–จ๊นŒ? ์ด๋ ‡๊ฒŒ ๋ฌถ์–ด ๋†“๊ณ  ๋ณด๋ฉด, ์ธ์ ‘ํ•œ ์ˆซ์ž๋ผ๋ฆฌ ์ ์ ˆํžˆ ๋ฌถ๊ณ , ์ตœ์†Œ ์˜ค์ฐจ๋ฅผ ๋‚ด๋Š” ์ˆ˜๋ฅผ ์ฐพ๋Š” ๋ฌธ์ œ๋กœ ๋ณ€ํ˜•ํ•  ์ˆ˜ ์žˆ๋‹ค! ๊ทธ๋Ÿผ ์•„๋ž˜์™€ ..

[์ข…๋งŒ๋ถ ๋ฌธ์ œ] ์›์ฃผ์œจ ์™ธ์šฐ๊ธฐ (๋ฌธ์ œ ID : PI, ๋‚œ์ด๋„ : ํ•˜)

ํ”„๋กœ๊ทธ๋ž˜๋ฐ ๋Œ€ํšŒ์—์„œ ๋ฐฐ์šฐ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œํ•ด๊ฒฐ ์ „๋žต(์ดํ•˜ ์ข…๋งŒ๋ถ)์—์„œ ์†Œ๊ฐœ๋œ ๋ฌธ์ œ๋ฅผ ํ’€์ดํ•ฉ๋‹ˆ๋‹ค. ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ์ง„์‹ฌ์ด์‹œ๋ผ๋ฉด, ์ง์ ‘ ๊ตฌ๋งคํ•˜์…”์„œ ์ฝ์–ด๋ณด์‹œ๋Š” ๊ฒƒ์„ ์ถ”์ฒœํ•ฉ๋‹ˆ๋‹ค! ํ•ต์‹ฌ : 1. ์›์ฃผ์œจ ๊ฐ™์€๊ฑฐ ์ข€ ์™ธ์šฐ๊ณ  ๋‹ค๋‹ˆ์ง€ ๋ง์ž; [์ข…๋งŒ๋ถ ๋ฌธ์ œ] ์›์ฃผ์œจ ์™ธ์šฐ๊ธฐ (๋ฌธ์ œ ID : PI, ๋‚œ์ด๋„ : ํ•˜) ๋ฌธ์ œ ์ž์ฒด๋Š” ์–ด๋ ต์ง€ ์•Š๋‹ค! ๊ทธ๋ƒฅ ์ ํ™”์‹๋งŒ ์ž˜ ์„ธ์šฐ๋ฉด ๋˜๋Š”๋ฐ... ์ผ๋‹จ ์ฝ”๋“œ๋ฅผ ๋ณด์ž. #include #include "stdlib.h" #include #include #include using namespace std; int N; vector arr; vector cache; int diff(int i, int j) { if (i > j) return 0; if (j >= N) return 10; if ((j - i ..

[์ข…๋งŒ๋ถ ๋ฌธ์ œ] ํ•ฉ์นœ LIS (๋ฌธ์ œ ID : JLIS, ๋‚œ์ด๋„ : ํ•˜)

ํ”„๋กœ๊ทธ๋ž˜๋ฐ ๋Œ€ํšŒ์—์„œ ๋ฐฐ์šฐ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œํ•ด๊ฒฐ ์ „๋žต(์ดํ•˜ ์ข…๋งŒ๋ถ)์—์„œ ์†Œ๊ฐœ๋œ ๋ฌธ์ œ๋ฅผ ํ’€์ดํ•ฉ๋‹ˆ๋‹ค. ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ์ง„์‹ฌ์ด์‹œ๋ผ๋ฉด, ์ง์ ‘ ๊ตฌ๋งคํ•˜์…”์„œ ์ฝ์–ด๋ณด์‹œ๋Š” ๊ฒƒ์„ ์ถ”์ฒœํ•ฉ๋‹ˆ๋‹ค! ํ•ต์‹ฌ : 1. ์ ํ™”์‹์„ ์ž˜ ์„ธ์›Œ๋ณด์ž. [์ข…๋งŒ๋ถ ๋ฌธ์ œ] ํ•ฉ์นœ LIS (๋ฌธ์ œ ID : JLIS, ๋‚œ์ด๋„ : ํ•˜) ์ด๊ฒƒ๋„ LIS ์™€ ๋น„์Šทํ•œ ๋กœ์ง์„ ์ ์šฉํ•˜๋ฉด ๋œ๋‹ค. ์ผ๋‹จ, jlis ํ•จ์ˆ˜๋ฅผ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ •์˜ํ•  ๊ฒƒ์ด๋‹ค. jlis(indexA, indexB) = A[indexA] ์™€ B[indexB] ์—์„œ ์‹œ์ž‘ํ•˜๋Š” ํ•ฉ์นœ ์ฆ๊ฐ€ ๋ถ€๋ถ„์ˆ˜์—ด์˜ ์ตœ๋Œ€ ๊ธธ์ด ์ˆœ์„œ๋ฅผ ๋”ฑํžˆ ์ง€์ •ํ•˜์ง€๋Š” ์•Š์•˜์œผ๋‹ˆ A[indexA] ์™€B[indexB] ์ค‘ ์ž‘์€ ์ชฝ์ด ์•ž์— ์˜จ๋‹ค๊ณ  ๊ฐ€์ •ํ•˜์ž. ๊ทธ๋Ÿผ ์ ํ™”์‹์„ ์•„๋ž˜์™€ ๊ฐ™์ด ์„ธ์šธ ์ˆ˜ ์žˆ๋‹ค. ๊ทธ๋Ÿผ ์œ„์˜ ์ ํ™”์‹์„ ์‹ค์ œ๋กœ ๊ตฌํ˜„ํ•ด ๋ณด์ž! ๐Ÿ˜Š #include ..