๐Ÿ“Šํ‘œ๋ณธ ๋ถ„์‚ฐ vs ๋ชจ๋ถ„์‚ฐ ๊ตฌ๋ถ„ ๊ณ„์‚ฐ๊ธฐ

๋™์ผ ๋ฐ์ดํ„ฐ์— ๋Œ€ํ•ด ๋ชจ๋ถ„์‚ฐ(รทn)๊ณผ ํ‘œ๋ณธ ๋ถ„์‚ฐ(รทnโˆ’1)์„ ๊ตฌ๋ถ„ํ•ด ๊ณ„์‚ฐ

ํ‘œ๋ณธ ๋ถ„์‚ฐ vs ๋ชจ๋ถ„์‚ฐ ๊ตฌ๋ถ„ ๊ณ„์‚ฐ๊ธฐ ์‚ฌ์šฉ๋ฒ•

๊ฐ™์€ ๋ฐ์ดํ„ฐ๋ผ๋„ ๊ทธ๊ฒƒ์ด ๋ชจ์ง‘๋‹จ ์ „์ฒด์ธ์ง€ ์ผ๋ถ€ ํ‘œ๋ณธ์ธ์ง€์— ๋”ฐ๋ผ ๋ถ„์‚ฐ ๊ณ„์‚ฐ ๋ฐฉ์‹์ด ๋‹ฌ๋ผ์ง‘๋‹ˆ๋‹ค. ์ด ๊ณ„์‚ฐ๊ธฐ๋Š” ์‰ผํ‘œ๋‚˜ ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„ํ•œ ์ˆซ์ž๋ฅผ ์ž…๋ ฅํ•˜๋ฉด ๋ชจ๋ถ„์‚ฐ๊ณผ ํ‘œ๋ณธ ๋ถ„์‚ฐ์„ ๋™์‹œ์— ๊ณ„์‚ฐํ•ด ๋‘ ๊ฐ’์„ ๋‚˜๋ž€ํžˆ ๋น„๊ตํ•  ์ˆ˜ ์žˆ๊ฒŒ ํ•ด์ค๋‹ˆ๋‹ค.

๋ชจ๋ถ„์‚ฐ์€ ํ‰๊ท ๊ณผ์˜ ํŽธ์ฐจ ์ œ๊ณฑ์„ ๋ชจ๋‘ ๋”ํ•œ ๋’ค ๋ฐ์ดํ„ฐ ๊ฐœ์ˆ˜ n์œผ๋กœ ๋‚˜๋ˆ•๋‹ˆ๋‹ค. ๋ฐ˜๋ฉด ํ‘œ๋ณธ ๋ถ„์‚ฐ์€ ํ‘œ๋ณธ์œผ๋กœ ๋ชจ์ง‘๋‹จ์„ ์ถ”์ •ํ•˜๋Š” ๊ฒƒ์ด๋ฏ€๋กœ n ๋Œ€์‹  nโˆ’1๋กœ ๋‚˜๋ˆ„๋Š”๋ฐ, ์ด๋ฅผ ๋ฒ ์…€ ๋ณด์ •์ด๋ผ๊ณ  ๋ถ€๋ฆ…๋‹ˆ๋‹ค. n์ด ์ž‘์„์ˆ˜๋ก ๋‘ ๊ฐ’์˜ ์ฐจ์ด๊ฐ€ ํฌ๊ฒŒ ๋ฒŒ์–ด์ง€๊ณ , n์ด ์ปค์งˆ์ˆ˜๋ก ์ฐจ์ด๋Š” ์ ์  ์ค„์–ด๋“ญ๋‹ˆ๋‹ค.

ํ‘œ์ค€ํŽธ์ฐจ๋Š” ๋ถ„์‚ฐ์— ์ œ๊ณฑ๊ทผ์„ ์ทจํ•œ ๊ฐ’์œผ๋กœ, ๋ฐ์ดํ„ฐ์˜ ํฉ์–ด์ง„ ์ •๋„๋ฅผ ์›๋ž˜ ๋‹จ์œ„๋กœ ํ•ด์„ํ•  ์ˆ˜ ์žˆ๊ฒŒ ํ•ด์ค๋‹ˆ๋‹ค. ์‹คํ—˜ ๋ฐ์ดํ„ฐ, ์„ค๋ฌธ ์‘๋‹ต, ์„ฑ์ ์ฒ˜๋Ÿผ ์ „์ฒด ์ค‘ ์ผ๋ถ€๋งŒ ์กฐ์‚ฌํ•œ ๊ฒฝ์šฐ๋ผ๋ฉด ํ‘œ๋ณธ ๋ถ„์‚ฐ์„, ๋ฐ˜ ํ•™์ƒ ์ „์ฒด ์ ์ˆ˜์ฒ˜๋Ÿผ ๋ฐ์ดํ„ฐ๋ฅผ ๋ชจ๋‘ ๊ฐ€์ง„ ๊ฒฝ์šฐ๋ผ๋ฉด ๋ชจ๋ถ„์‚ฐ์„ ์‚ฌ์šฉํ•˜๋Š” ๊ฒƒ์ด ํ†ต๊ณ„์ ์œผ๋กœ ์˜ฌ๋ฐ”๋ฅธ ์ ‘๊ทผ์ž…๋‹ˆ๋‹ค.

์‹ค์ œ ํ†ต๊ณ„ ์†Œํ”„ํŠธ์›จ์–ด๋‚˜ ์Šคํ”„๋ ˆ๋“œ์‹œํŠธ์—์„œ๋„ ํ•จ์ˆ˜ ์ด๋ฆ„์— ๋”ฐ๋ผ ๋ชจ๋ถ„์‚ฐ๊ณผ ํ‘œ๋ณธ ๋ถ„์‚ฐ ๊ฒฐ๊ณผ๊ฐ€ ๋‹ค๋ฅด๊ฒŒ ๋‚˜์˜ค๋Š” ๊ฒฝ์šฐ๊ฐ€ ๋งŽ์œผ๋ฏ€๋กœ, ๋‘ ๊ฐ’์˜ ์ฐจ์ด๋ฅผ ๋ฏธ๋ฆฌ ์ดํ•ดํ•ด๋‘๋ฉด ๋ฐ์ดํ„ฐ ๋ถ„์„ ๊ณผ์ •์—์„œ ํ˜ผ๋™์„ ์ค„์ผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋ฐ์ดํ„ฐ๋ฅผ ๋ฐ”๊ฟ”๊ฐ€๋ฉฐ n์ด ์ปค์งˆ์ˆ˜๋ก ๋‘ ๊ฐ’์ด ์–ด๋–ป๊ฒŒ ๊ฐ€๊นŒ์›Œ์ง€๋Š”์ง€๋„ ํ•จ๊ป˜ ํ™•์ธํ•ด ๋ณด์„ธ์š”.

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

๋ชจ๋ถ„์‚ฐ๊ณผ ํ‘œ๋ณธ ๋ถ„์‚ฐ์€ ์™œ ๋‹ค๋ฅด๊ฒŒ ๊ณ„์‚ฐํ•˜๋‚˜์š”?

๋ชจ๋ถ„์‚ฐ์€ ์ „์ฒด ๋ฐ์ดํ„ฐ(๋ชจ์ง‘๋‹จ)๋ฅผ ๋‹ค ์•Œ๊ณ  ์žˆ์„ ๋•Œ n์œผ๋กœ ๋‚˜๋ˆ„์ง€๋งŒ, ํ‘œ๋ณธ ๋ถ„์‚ฐ์€ ์ „์ฒด ์ค‘ ์ผ๋ถ€(ํ‘œ๋ณธ)๋งŒ์œผ๋กœ ๋ชจ์ง‘๋‹จ์„ ์ถ”์ •ํ•˜๋Š” ๊ฒƒ์ด๋ผ n-1๋กœ ๋‚˜๋ˆ  ํŽธํ–ฅ์„ ๋ณด์ •ํ•ฉ๋‹ˆ๋‹ค. ์ด๋ฅผ ๋ฒ ์…€ ๋ณด์ •์ด๋ผ๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

๋ฐ์ดํ„ฐ๊ฐ€ 2๊ฐœ ๋ฏธ๋งŒ์ด๋ฉด ์™œ ๊ณ„์‚ฐ์ด ์•ˆ ๋˜๋‚˜์š”?

ํ‘œ๋ณธ ๋ถ„์‚ฐ์€ n-1๋กœ ๋‚˜๋ˆ„๊ธฐ ๋•Œ๋ฌธ์— ๋ฐ์ดํ„ฐ๊ฐ€ 1๊ฐœ๋ฉด ๋ถ„๋ชจ๊ฐ€ 0์ด ๋˜์–ด ๊ณ„์‚ฐํ•  ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค. ์ตœ์†Œ 2๊ฐœ ์ด์ƒ์˜ ๊ฐ’์„ ์ž…๋ ฅํ•ด์•ผ ํ‘œ๋ณธ ๋ถ„์‚ฐ๊นŒ์ง€ ํ•จ๊ป˜ ๊ณ„์‚ฐ๋ฉ๋‹ˆ๋‹ค.