์ผ๊ฐ์๋ ๋ฌด์์ธ๊ฐ์?
์ผ๊ฐ์๋ ์ ์ผ๊ฐํ ๋ชจ์์ผ๋ก ๋ฐฐ์ดํ ์ ์๋ ์ (๋๋ ๋ฌผ๊ฑด)์ ๊ฐ์๋ฅผ ๋ปํฉ๋๋ค. n๋ฒ์งธ ์ผ๊ฐ์๋ T(n)์ผ๋ก ํ๊ธฐํ๋ฉฐ, 1๋ถํฐ n๊น์ง์ ๋ชจ๋ ์์ ์ ์๋ฅผ ๋ํ ๊ฐ์ ๋๋ค. ์์ด์ 1, 3, 6, 10, 15, 21, 28 โฆ๋ก ์ด์ด์ง๋๋ฐ, ํญ์ด ํ๋์ฉ ๋์ด๋ ๋๋ง๋ค ๋ค์ ์์ฐ์๊ฐ ๋ํด์ง๋ ๊ตฌ์กฐ์ ๋๋ค. ์ด ๊ณ์ฐ๊ธฐ๋ 0 ์ด์์ ์ ์๋ฅผ ์ ๋ ฅํ๋ฉด ๊ทธ์ ํด๋นํ๋ \(T(n)\)์ ๋ฐ๋ก ์๋ ค ์ค๋๋ค.
๊ณ์ฐ๊ธฐ ์ฌ์ฉ ๋ฐฉ๋ฒ
์ ๋ ฅ๋์ ํญ ๋ฒํธ \(n\)(์: 10)์ ์ ๊ณ ์คํํ๋ฉด ๋ฉ๋๋ค. ๊ทธ๋ฌ๋ฉด ์ผ๊ฐ์๊ฐ ์ฆ์ ๋์ค๋๋ฐ, ์ด๋ 1๋ถํฐ n๊น์ง ๋ชจ๋ ์ ์๋ฅผ ๋ํ ํฉ๊ณ์ ๊ฐ์ต๋๋ค. 0์ ์ ๋ ฅํ๋ฉด ๋ํ ๊ฐ์ด ์์ผ๋ฏ๋ก ๊ฒฐ๊ณผ๋ 0์ด ๋ฉ๋๋ค.
๊ณต์ ์์ธํ ์์๋ณด๊ธฐ
์ผ๊ฐ์์ ์ผ๋ฐํญ(๋ซํ ํ์) ๊ณต์์ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
$$T_n = \frac{\text{Term (n)}\left(\text{Term (n)}+1\right)}{2}$$
1๋ถํฐ ์ฐจ๋ก๋ก ๋ํ๋ ๋์ , n์ ๋ฐ๋ก ๋ค์ ์ ์์ธ (n+1)์ ๊ณฑํ ๋ค 2๋ก ๋๋๋ฉด ๋ฉ๋๋ค. ์ด๋ ๊ฒ ๊ณ์ฐํ ์ ์๋ ์ด์ ๋, ๋งจ ์๊ณผ ๋งจ ๋ค ํญ, ๋ ๋ฒ์งธ์ ๋์์ ๋ ๋ฒ์งธ ํญ์ ์ง์ง์ผ๋ฉด ๊ทธ ํฉ์ด ํญ์ (n+1)๋ก ์ผ์ ํ๊ณ , ์ด๋ฐ ์ง์ด ๋ชจ๋ n/2๊ฐ ์๊ธฐ๊ธฐ ๋๋ฌธ์ ๋๋ค. ์ด๋ฆฐ ์นด๋ฅผ ํ๋ฆฌ๋๋ฆฌํ ๊ฐ์ฐ์ค๊ฐ 1๋ถํฐ 100๊น์ง๋ฅผ ๋ํด ์์๊ฐ์ 5050์ ๊ตฌํด ๋๋ค๋ ์ผํ๊ฐ ์ ๋ช ํ๋ฐ, ์ด ๊ณต์์ผ๋ก ์ง์ ํ์ธํ ์ ์์ต๋๋ค. \(100 \times 101 / 2 = 5050\)์ด์ฃ .
ํ์ด ์์
n = 10์ด๋ผ๊ณ ํด ๋ด ์๋ค. ๊ทธ๋ฌ๋ฉด
$$T(10) = \frac{10 \times (10 + 1)}{2} = \frac{10 \times 11}{2} = \frac{110}{2} = 55$$
์ ๋๋ค. ๋ฐ๋ผ์ \(1 + 2 + 3 + \dots + 10 = 55\)๊ฐ ๋๊ณ , ์ 55๊ฐ๋ฅผ ๋งจ ์๋ ์ค์ 10๊ฐ๊ฐ ๋์ด๋๋ก ์ฐจ๊ณก์ฐจ๊ณก ์์ผ๋ฉด ๊น๋ํ ์ผ๊ฐํ ๋ชจ์์ด ๋ง๋ค์ด์ง๋๋ค.
์์ฃผ ๋ฌป๋ ์ง๋ฌธ
100๋ฒ์งธ ์ผ๊ฐ์๋ ์ผ๋ง์ธ๊ฐ์? \(T(100) = 100 \times 101 / 2 = 5050\)์ ๋๋ค.
n์ ์์๋ฅผ ๋ฃ์ด๋ ๋๋์? ์ผ๊ฐ์๋ 0 ์ด์์ ์ ์์ ๋ํด ์ ์๋๋ฏ๋ก, ๊ณ์ฐ๊ธฐ๋ ์ ๋ ฅ๊ฐ์ ์ ์ ๋ถ๋ถ๋ง ์ฌ์ฉํฉ๋๋ค.
T(n)์ ํญ์ ์ ์์ธ๊ฐ์? ๋ค. n๊ณผ n+1 ์ค ํ๋๋ ๋ฐ๋์ ์ง์์ด๋ฏ๋ก \(n(n+1)\)์ ์ธ์ ๋ 2๋ก ๋๋์ด๋จ์ด์ง๋๋ค.