MCP๋กœ ์—ฐ๊ฒฐ โ†’

๊ณ„์‚ฐ ์ž…๋ ฅ

๊ณต์‹

๊ด‘๊ณ 

๊ฒฐ๊ณผ

Sum of the first 10 cubes
3,025
ฮฃ kยณ for k = 1 to 10
ํ•ญ์˜ ๊ฐœ์ˆ˜ (n) 10
์‚ผ๊ฐ์ˆ˜ n(n+1)/2 55
ํ•ญ๋“ฑ์‹ (n(n+1)/2)ยฒ

์ด ๊ณ„์‚ฐ๊ธฐ๋Š” ๋ฌด์—‡์„ ํ•˜๋‚˜์š”

์ด ๋„๊ตฌ๋Š” ์ฒ˜์Œ n๊ฐœ์˜ ์™„์ „์„ธ์ œ๊ณฑ์ˆ˜์˜ ํ•ฉ, ์ฆ‰ \(1^3 + 2^3 + 3^3 + \ldots + n^3\)์„ ๊ณ„์‚ฐํ•ฉ๋‹ˆ๋‹ค. ๋ชจ๋“  ํ•ญ์„ ํ•˜๋‚˜์”ฉ ๋”ํ•˜๋Š” ๋Œ€์‹ , ์œ ๋ช…ํ•œ ๋‹ซํžŒ ๊ณต์‹(closed-form)์„ ์‚ฌ์šฉํ•ด n์ด ์•„๋ฌด๋ฆฌ ์ปค๋„ ์ •ํ™•ํ•œ ๋‹ต์„ ์ฆ‰์‹œ ๊ตฌํ•ด์ค๋‹ˆ๋‹ค.

์‚ฌ์šฉ ๋ฐฉ๋ฒ•

ํ•ญ์˜ ๊ฐœ์ˆ˜ n์— ์–‘์˜ ์ •์ˆ˜๋ฅผ ์ž…๋ ฅํ•˜๋ฉด ๊ฒฐ๊ณผ๊ฐ€ ๋ฐ”๋กœ ํ‘œ์‹œ๋ฉ๋‹ˆ๋‹ค. ๋˜ํ•œ ๋‹ต์ด ์–ด๋–ป๊ฒŒ ๋งŒ๋“ค์–ด์ง€๋Š”์ง€ ์•Œ ์ˆ˜ ์žˆ๋„๋ก ๊ทธ ๋ฐ”ํƒ•์ด ๋˜๋Š” ์‚ผ๊ฐ์ˆ˜ \(n(n+1)/2\)๋„ ํ•จ๊ป˜ ๋ณด์—ฌ์ค๋‹ˆ๋‹ค.

๊ณต์‹ ์„ค๋ช…

ํ•ต์‹ฌ์ด ๋˜๋Š” ๊ฒฐ๊ณผ๋Š” ๋‹ˆ์ฝ”๋งˆ์ฝ”์Šค ํ•ญ๋“ฑ์‹(Nicomachus identity)์ž…๋‹ˆ๋‹ค.

$$\sum_{k=1}^{n} k^{3} = \left( \frac{n\left(n+1\right)}{2} \right)^{2}$$

๋†€๋ž๊ฒŒ๋„ ์ฒ˜์Œ n๊ฐœ ์„ธ์ œ๊ณฑ์˜ ํ•ฉ์€ ์ฒ˜์Œ n๊ฐœ ์ •์ˆ˜์˜ ํ•ฉ์„ ์ œ๊ณฑํ•œ ๊ฐ’๊ณผ ์ •ํ™•ํžˆ ๊ฐ™์Šต๋‹ˆ๋‹ค. ์•ˆ์ชฝ์˜ \(n(n+1)/2\)๋Š” n๋ฒˆ์งธ ์‚ผ๊ฐ์ˆ˜ \(T(n)\)์ด๋ฏ€๋กœ, ์„ธ์ œ๊ณฑ์˜ ํ•ฉ์€ ๊ณง \(T(n)\)์„ ์ œ๊ณฑํ•œ ๊ฐ’์ž…๋‹ˆ๋‹ค. ๋•๋ถ„์— ๋ฐ˜๋ณต ๊ณ„์‚ฐ ์—†์ด \(O(1)\)๋กœ ์ฒ˜๋ฆฌํ•  ์ˆ˜ ์žˆ์œผ๋ฉฐ, ์ •์ˆ˜ ์ž…๋ ฅ์— ๋Œ€ํ•ด ํ•ญ์ƒ ์ •ํ™•ํ•œ ๊ฐ’์„ ์ค๋‹ˆ๋‹ค.

์‚ผ๊ฐ์ˆ˜์˜ ์ œ๊ณฑ๊ณผ ๊ฐ™์€, ์ ์  ์ปค์ง€๋Š” ์ •์œก๋ฉด์ฒด ๋”๋ฏธ
์ฒ˜์Œ n๊ฐœ ์„ธ์ œ๊ณฑ์ˆ˜์˜ ํ•ฉ์€ n๋ฒˆ์งธ ์‚ผ๊ฐ์ˆ˜์˜ ์ œ๊ณฑ \(\left(n(n+1)/2\right)^2\)๊ณผ ๊ฐ™๋‹ค.

์˜ˆ์ œ ํ’€์ด

n = 4์ธ ๊ฒฝ์šฐ: ์‚ผ๊ฐ์ˆ˜๋Š” \(4\times 5/2 = 10\)์ž…๋‹ˆ๋‹ค. ์ด๋ฅผ ์ œ๊ณฑํ•˜๋ฉด \(10^2 = 100\)์ด ๋ฉ๋‹ˆ๋‹ค. ์ง์ ‘ ๋”ํ•ด์„œ ํ™•์ธํ•ด ๋ณด๋ฉด \(1 + 8 + 27 + 64 = 100\)์œผ๋กœ ์ผ์น˜ํ•˜๋ฏ€๋กœ, ํ•ญ๋“ฑ์‹์ด ์„ฑ๋ฆฝํ•จ์„ ์•Œ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์ž์ฃผ ๋ฌป๋Š” ์งˆ๋ฌธ

์ •์ˆ˜์— ๋Œ€ํ•ด์„œ๋งŒ ์ž‘๋™ํ•˜๋‚˜์š”? ๋„ค โ€” ์ด ํ•ญ๋“ฑ์‹์€ k = 1๋ถ€ํ„ฐ n๊นŒ์ง€ ์ •์ˆ˜ ํ•ญ์— ๋Œ€ํ•œ ํ•ฉ์— ์ ์šฉ๋˜๋ฏ€๋กœ, n์€ ์–‘์˜ ์ •์ˆ˜์—ฌ์•ผ ํ•ฉ๋‹ˆ๋‹ค.

์™œ ๋‹ต์€ ํ•ญ์ƒ ์™„์ „์ œ๊ณฑ์ˆ˜์ธ๊ฐ€์š”? ํ•ฉ์ด \(T(n)^2\)๊ณผ ๊ฐ™๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค. ์—ฌ๊ธฐ์„œ \(T(n)\)์€ n๋ฒˆ์งธ ์‚ผ๊ฐ์ˆ˜์ด๋ฉฐ, ์ •์ˆ˜๋ฅผ ์ œ๊ณฑํ•˜๋ฉด ํ•ญ์ƒ ์™„์ „์ œ๊ณฑ์ˆ˜๊ฐ€ ๋ฉ๋‹ˆ๋‹ค.

n์ด ์•„์ฃผ ์ปค๋„ ๋˜๋‚˜์š”? ๋„ค. ๋‹ซํžŒ ๊ณต์‹์ด๋ฏ€๋กœ n์ด ์ปค๋„ ์ฆ‰์‹œ ๊ณ„์‚ฐ๋ฉ๋‹ˆ๋‹ค. ๋‹ค๋งŒ ๊ฐ’์ด ์ง€๋‚˜์น˜๊ฒŒ ํฌ๋ฉด ์ผ๋ฐ˜์ ์ธ ๋ถ€๋™์†Œ์ˆ˜์  ์ •๋ฐ€๋„๋ฅผ ๋„˜์–ด์„ค ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์ตœ์ข… ์—…๋ฐ์ดํŠธ: