๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
๊ฐœ์ธ๊ณต๋ถ€/Algorithm

[Level 1] ์‹œ์ € ์•”ํ˜ธ

by ๐Ÿ‡๋ฐ•๋ด‰๋ด‰๐Ÿ‡ 2021. 4. 19.

 

 

 

Algorithm

-  ์‹œ์ € ์•”ํ˜ธ -

 


 

๋ฌธ์ œ

์–ด๋–ค ๋ฌธ์žฅ์˜ ๊ฐ ์•ŒํŒŒ๋ฒณ์„ ์ผ์ •ํ•œ ๊ฑฐ๋ฆฌ๋งŒํผ ๋ฐ€์–ด์„œ ๋‹ค๋ฅธ ์•ŒํŒŒ๋ฒณ์œผ๋กœ ๋ฐ”๊พธ๋Š” ์•”ํ˜ธํ™” ๋ฐฉ์‹์„ ์‹œ์ €์•”ํ˜ธ๋ผ๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด "AB"๋Š” 1๋งŒํผ ๋ฐ€๋ฉด "BC"๊ฐ€ ๋˜๊ณ , 3๋งŒํผ ๋ฐ€๋ฉด "DE"๊ฐ€ ๋ฉ๋‹ˆ๋‹ค.

"Z"๋Š” 1๋งŒํผ ๋ฐ€๋ฉด "A"๊ฐ€ ๋ฉ๋‹ˆ๋‹ค. ๋ฌธ์ž์—ด s์™€ ๊ฑฐ๋ฆฌ n์„ ์ž…๋ ฅ๋ฐ›์•„ s๋ฅผ n๋งŒํผ ๋ฏผ ์•”ํ˜ธ๋ฌธ์„ ๋งŒ๋“œ๋Š” ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด๋ณด์„ธ์š”.

 

- ๊ณต๋ฐฑ์€ ์•„๋ฌด๋ฆฌ ๋ฐ€์–ด๋„ ๊ณต๋ฐฑ์ž…๋‹ˆ๋‹ค.

- s๋Š” ์•ŒํŒŒ๋ฒณ ์†Œ๋ฌธ์ž, ๋Œ€๋ฌธ์ž, ๊ณต๋ฐฑ์œผ๋กœ๋งŒ ์ด๋ฃจ์–ด์ ธ ์žˆ์Šต๋‹ˆ๋‹ค.

- s์˜ ๊ธธ์ด๋Š” 8000์ดํ•˜์ž…๋‹ˆ๋‹ค.

- n์€ 1 ์ด์ƒ, 25 ์ดํ•˜์ธ ์ž์—ฐ์ˆ˜์ž…๋‹ˆ๋‹ค.

 

์ž…์ถœ๋ ฅ ์˜ˆ์‹œ

s n result
"AB" 1 "BC"
"a B z" 4 "e F d"

 

๋ฌธ์ œ ํ’€๊ธฐ

 

์ด๋ฒˆ ๋ฌธ์ œ๋Š” ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ๋ฐ›์•„์˜ค๋Š” ๋ฌธ์ž์™€ ์ˆซ์ž๋ฅผ ๊ธฐ๋ฐ˜์œผ๋กœ ๊ฐ ๋ฌธ์ž๋ฅผ  n๋งŒํผ ๋ฐ€์–ด์„œ ๊ฐ’์„ ๋ฆฌํ„ดํ•˜๋Š” ํ˜•์‹์œผ๋กœ ์ผ๋‹จ์€ ๊ฐ ์•ŒํŒŒ๋ฒณ์˜ ์ธ๋ฑ์Šค๋ฅผ ํŒŒ์•…ํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” ๋น„๊ตํ•  ๋Œ€์ƒ์ด ํ•„์š”ํ•˜๊ธฐ ๋•Œ๋ฌธ์— alpha๋ผ๋Š” ๋ณ€์ˆ˜์•ˆ์— ์•ŒํŒŒ๋ฒณ๋“ค์„ ๋„ฃ์–ด์„œ ์ธ๋ฑ์Šค๋ฅผ ํ™•์ธํ•  ์ˆ˜ ์žˆ๋„๋ก ํ•˜์˜€๋‹ค.

 

๊ทธ๋ฆฌ๊ณ  s์˜ ๊ธธ์ด๋งŒํผ ๋ฐ˜๋ณต๋ฌธ์„ ๋Œ๋ ค์„œ ๊ฐ ์ธ๋ฑ์Šค์—์„œ +n๋งŒํผํ•œ ์ƒˆ๋กœ์šด ์•ŒํŒŒ๋ฒณ์„ result์•ˆ์— ๋„ฃ์„ ์ˆ˜ ์žˆ๋„๋ก ํ•˜์˜€๋‹ค.

 

์ด๋•Œ ๊ธฐ์กด์œ„์น˜์˜ ์ธ๋ฑ์Šค์™€ n์˜ ๊ฐ’์„ ๋”ํ–ˆ์„๋•Œ alpha์˜ ๊ธธ์ด๋ฅผ ๋„˜๊ฒผ์„ ๊ฒฝ์šฐ alpha์˜ ๊ธธ์ด๋งŒํผ ๋‚˜๋ˆˆ๋’ค ๋‚˜๋จธ์ง€๋ฅผ ์ธ๋ฑ์Šค ๊ฐ’์„ ๊ฐ€์งˆ ์ˆ˜ ์žˆ๋„๋ก ๋ฏธ๋ฆฌ ์„ค์ •ํ•ด์ฃผ์—ˆ๋‹ค.

 

๊ทธ๋Ÿฐ๋‹ค์Œ์— ๊ฐ’์„ ๋ฆฌํ„ดํ•˜๋ฉด ๋ฌธ์ œ๊ฐ€ ์ œ๋Œ€๋กœ ํ•ด๊ฒฐ๋œ ๊ฒƒ์„ ํ™•์ธํ•  ์ˆ˜ ์žˆ์—ˆ๋‹ค.

 

 

๋ฐ˜์‘ํ˜•

๋Œ“๊ธ€