Loading [MathJax]/jax/output/CommonHTML/jax.js

๐Ÿ–ฅ Computer Science

BCD to Excess-3 Code Converter BCD๋ฅผ ์ž…๋ ฅ๋ฐ›์•„์„œ ์ด์— 3์„ ๋”ํ•œ ๊ฐ’์„ ์ถœ๋ ฅํ•˜๋Š” ๋ณ€ํ™˜๊ธฐ๋ฅผ ์„ค๊ณ„ํ•ด๋ณด๋„๋ก ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. ์ˆœ์„œํšŒ๋กœ์˜ ์˜ˆ์ œ์ธ๋งŒํผ, ์ž…๋ ฅ์€ ์ง๋ ฌ๋กœ ๋“ค์–ด์˜ค๊ณ , ์ถœ๋ ฅ๋„ ๊ทธ์— ๋งž๊ฒŒ ๋ฐ”๋กœ ๋ฐ”๋กœ ์ง๋ ฌ๋กœ ์ถœ๋ ฅ๋œ๋‹ค๊ณ  ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. 1. ์ƒํƒœ๊ทธ๋ž˜ํ”„ ์ž‘์„ฑํ•˜๊ธฐ ์šฐ์„  ์ƒํƒœ๊ทธ๋ž˜ํ”„๋ฅผ ์ž‘์„ฑํ•˜๋ ค ํ•˜๋Š”๋ฐ, BCD์— 3์„ ๋”ํ•˜๋Š” ๊ฒƒ์— ๋Œ€ํ•œ ์ƒํƒœ๊ทธ๋ž˜ํ”„๋ฅผ ๊ทธ๋ฆฌ๊ธฐ๊ฐ€ ์กฐ๊ธˆ ์–ด๋ ต์Šต๋‹ˆ๋‹ค. ์ด๋Ÿฐ ๊ฒฝ์šฐ ๋จผ์ € ์ž…๋ ฅ์— ๋Œ€ํ•œ ์ถœ๋ ฅํ‘œ๋ฅผ ์ž‘์„ฑํ•ฉ๋‹ˆ๋‹ค. ์ด๋ฅผ ๊ฐ€์ง€๊ณ  ์ƒํƒœ ๊ทธ๋ž˜ํ”„๋ฅผ ์ž‘์„ฑํ•ด ๋ณด๋„๋ก ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. 2. ์ตœ์†Œ์ƒํƒœ์ˆ˜๋กœ ๊ฐ„๋žตํ™” ๋‘ ์ƒํƒœ๊ฐ€ ์•ž์œผ๋กœ์˜ ๋ชจ๋“  ์ž…๋ ฅ์— ๋Œ€ํ•ด ๊ฐ™์€ ์ถœ๋ ฅ์„ ๋ฐœ์ƒ์‹œํ‚จ๋‹ค๋ฉด ์ด๋Š” ๊ตฌ๋ถ„๋ถˆ๊ฐ€๋Šฅํ•œ ์ƒํƒœ์ด๋ฉฐ, ๋”ฐ๋ผ์„œ ์ค„์ผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๊ฐ„๋žตํ™”ํ•˜๋Š” ๋ฐฉ๋ฒ•์€ ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค. (ํ™•์‹คํ•˜์ง€๋Š” ์•Š์€ ๋ฐฉ๋ฒ•์ด๋‹ˆ, ์ฐธ๊ณ ์šฉ์œผ๋กœ๋งŒ ํ™•์ธํ•ด์ฃผ์„ธ..
๊ฐ€์„ค ๊ฒ€์ • (Hypotheses testing) ์–ด๋– ํ•œ ์ถ”์ธก์ด๋‚˜ ๊ฐ€์„ค์— ๋Œ€ํ•˜์—ฌ, ํ•ด๋‹น ๊ฐ€์„ค์˜ ํƒ€๋‹น์„ฑ์„ ์กฐ์‚ฌํ•˜๋Š” ๊ฒƒ์„ ๊ฐ€์„ค ๊ฒ€์ •์ด๋ผ๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๋ชจ์ˆ˜(parameter) ฮธ ๊ฐ€ ์•Œ๋ ค์ง€์ง€ ์•Š์€ ์–ด๋– ํ•œ ๋ถ„ํฌ๋ฅผ ๊ฐ€์ •ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ฮฉ ๋ฅผ ฮธ ์— ๋Œ€ํ•œ ๋ชจ์ˆ˜ ๊ณต๊ฐ„ (paramter space)์ด๋ผ ์ •์˜ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. ฮฉ ๋ฅผ ๋ถ„ํ• (partition)ํ•˜๋Š” ฮฉ0 ๊ณผ ฮฉ1๋ฅผ ์ •์˜ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. ์ฆ‰ ฮฉ0โˆฉฮฉ1=โˆ… , ฮฉ0โˆชฮฉ1=ฮฉ ์ž…๋‹ˆ๋‹ค. ์œ„์™€ ๊ฐ™์€ ์ƒํ™ฉ์—์„œ, ํ†ต๊ณ„ํ•™์ž๋Š” ์‹ค์ œ ๋ชจ์ˆ˜ ฮธ๊ฐ€ ์œ„ ๋‘ ๊ณต๊ฐ„ ์ค‘ ์–ด๋Š ๊ณต๊ฐ„์— ํฌํ•จ๋˜๋Š”์ง€ ๊ด€์‹ฌ์ด ..
Multiway Search Tree (๋‹ค์› ํƒ์ƒ‰ ํŠธ๋ฆฌ) / m-way Search Tree (m ๋ถ„๊ธฐ ํƒ์ƒ‰ ํŠธ๋ฆฌ) ํ•œ ๋…ธ๋“œ๊ฐ€ ๊ฐ€์งˆ ์ˆ˜ ์žˆ๋Š” key์˜ ๊ฐ’์ด ์ตœ๋Œ€ m-1๊ฐœ์ด๊ณ  ๊ฐ€์งˆ ์ˆ˜ ์žˆ๋Š” Child์˜ ์ˆ˜๊ฐ€ m๊ฐœ์ธ ํŠธ๋ฆฌ๋ฅผ Mulituway Search Tree๋ผ ํ•ฉ๋‹ˆ๋‹ค. ์ด์ง„ ํŠธ๋ฆฌ : 2-way search tree AVL ํŠธ๋ฆฌ : 2-way search tree 2-3 ํŠธ๋ฆฌ : 3-way search tree ์ •์˜๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค. m-way Search Tree๋Š” ๋‹ค์Œ์„ ๋งŒ์กฑํ•˜๋Š” ๊ฒ€์ƒ‰ ํŠธ๋ฆฌ์ž…๋‹ˆ๋‹ค. 1. Leaf Node๋ฅผ ์ œ์™ธํ•œ ๋ชจ๋“  ๋…ธ๋“œ๋Š” m๊ฐœ ์ดํ•˜์˜ ์„œ๋ธŒ ํŠธ๋ฆฌ๋ฅผ ๊ฐ€์ง‘๋‹ˆ๋‹ค. 2. k๊ฐœ์˜ ์ž์‹ ๋…ธ๋“œ๋ฅผ ๊ฐ–๋Š” ๋…ธ๋“œ๋Š”, k-1๊ฐœ์˜ ์š”์†Œ(key)๋ฅผ ๊ฐ€์ง‘๋‹ˆ๋‹ค. 3. ๊ฐ ๋…ธ๋“œ์˜ key๋Š” ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌ๋˜์–ด ์žˆ..
2-3 Tree 2-3ํŠธ๋ฆฌ๋Š” ๊ฒ€์ƒ‰ ํŠธ๋ฆฌ์ด์ง€๋งŒ BST๋Š” ์•„๋‹™๋‹ˆ๋‹ค. ์ฐจ์ˆ˜๊ฐ€ 3์ธ ๋…ธ๋“œ๊ฐ€ ์กด์žฌํ•  ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ, Binary๊ฐ€ ์•„๋‹ˆ๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค. 2-3 Tree๋Š” ํŠธ๋ฆฌ์˜ ๋†’์ด๊ฐ€ ๊ท ํ˜•์„ ์ด๋ฃจ๋ฉฐ ๋‚ด๋ถ€๋…ธ๋“œ์˜ ์ฐจ์ˆ˜๊ฐ€ 2 ๋˜๋Š” 3์ธ ๊ท ํ˜• ํƒ์ƒ‰ํŠธ๋ฆฌ์ž…๋‹ˆ๋‹ค. 2-3 Tree ์กฐ๊ฑด 2-3 Tree์—๋Š” Internal Node์™€ External Node์˜ ๊ฐœ๋…์ด ์กด์žฌํ•ฉ๋‹ˆ๋‹ค. Internal Node(๋‚ด๋ถ€๋…ธ๋“œ)๋Š” Key๊ฐ€ ๋“ค์–ด์žˆ๋Š” ๋‚ด๋ถ€ ๋…ธ๋“œ์ด๋ฉฐ, External Node(์™ธ๋ถ€๋…ธ๋“œ)๋Š” ๋ฐ์ดํ„ฐ๊ฐ€ ๋“ค์–ด์žˆ์ง€ ์•Š์€ ๋…ธ๋“œ๋กœ์จ Internal Node์˜ Leaf Node์˜ ์ž์‹์œผ๋กœ ์กด์žฌํ•˜๋Š” ๊ฐ€์ƒ์˜ ๋…ธ๋“œ์ž…๋‹ˆ๋‹ค. 2-3 Tree์—์„œ ๊ฐ๊ฐ์˜ ๋‚ด๋ถ€ ๋…ธ๋“œ๋Š” 2-Node ์ด๊ฑฐ๋‚˜ 3-Node ์ž…๋‹ˆ๋‹ค. ์ค‘๋ณต๋œ Key๋Š” ํ—ˆ์šฉํ•˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค. 2-Node๋Š” 1..
BST์˜ ๋ฌธ์ œ์  ์ผ๋ฐ˜์ ์ธ BST(์ด์ง„ ๊ฒ€์ƒ‰ ํŠธ๋ฆฌ)๋Š” ๋ฐ์ดํ„ฐ๊ฐ€ ์‚ฝ์ž…๋˜๋Š” ์ˆœ์„œ์— ๋”ฐ๋ผ ํ•œ์ชฝ์œผ๋กœ ํŽธํ–ฅ๋˜๋Š” ํ˜•ํƒœ๋กœ ํŠธ๋ฆฌ๊ฐ€ ํ˜•์„ฑ๋  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด ์ž…๋ ฅ์—ด์ด 50 -> 30 -> 100 -> 20 -> 150 ์ธ ๊ฒฝ์šฐ ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค. ๊ทธ๋Ÿฌ๋‚˜ ์ž…๋ ฅ์—ด์ด 20 -> 30 -> 50 -> 100 -> 150 ์ธ ๊ฒฝ์šฐ ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค. ์ด๋ ‡๊ฒŒ BST๋Š” ํŠธ๋ฆฌ์˜ ๋†’์ด๋ฅผ log(n) ์œผ๋กœ ๋ณด์žฅ๋ฐ›์ง€ ๋ชปํ•  ๊ฐ€๋Šฅ์„ฑ์ด ์žˆ์Šต๋‹ˆ๋‹ค. ํŠธ๋ฆฌ์—์„œ์˜ ์„ฑ๋Šฅ์€ ํŠธ๋ฆฌ์˜ ๋†’์ด์™€ ์—ฐ๊ด€๋˜์–ด ์žˆ์Šต๋‹ˆ๋‹ค. ์ฆ‰ ํŠธ๋ฆฌ์˜ ๋†’์ด๊ฐ€ log(n)์„ ๋ณด์žฅ๋ฐ›์ง€ ๋ชปํ•œ๋‹ค๋ฉด, BST์˜ ์‚ฝ์ž…๊ณผ ์‚ญ์ œ, ๊ฒ€์ƒ‰์˜ ์—ฐ์‚ฐ ์—ญ์‹œ ์‹œ๊ฐ„๋ณต์žก๋„ O(log(n))์„ ๋ณด์žฅ๋ฐ›์ง€ ๋ชปํ•ฉ๋‹ˆ๋‹ค. AVL ํŠธ๋ฆฌ AVL ํŠธ๋ฆฌ๋Š” ์ด์ง„ ๊ฒ€์ƒ‰ ํŠธ๋ฆฌ(BST)์˜ ํ•œ๊ฐ€์ง€ ์ข…๋ฅ˜๋กœ์จ ์Šค์Šค๋กœ ๋†’์ด์˜ ๊ท ํ˜•์„ ์žก๋Š”..
๋“ค์–ด๊ฐ€๊ธฐ์— ์•ž์„œ ํ•ด์‹œ๊ฐ€ ์–ด๋””์— ์“ฐ์ด๋Š”์ง€ ์•Œ์•„๋ณด๋„๋ก ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. ์œ ํŠœ๋ธŒ๋ฅผ ์˜ˆ์‹œ๋กœ ์ƒ๊ฐํ•ด ๋ณด๋„๋ก ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. ์ œ๊ฐ€ ์–ด๋–ค ์‚ฌ๋žŒ์˜ ๋™์˜์ƒ์„ ๊ทธ๋Œ€๋กœ ์ œ ์ฑ„๋„์— ์˜ฌ๋ฆฌ๋ ค๊ณ  ํ•œ๋‹ค๋ฉด, ๊ทธ ์ˆœ๊ฐ„ ๋ฐ”๋กœ ์œ ํŠœ๋ธŒ์—์„œ ์ค‘๋ณต๋˜๋Š” ๋™์˜์ƒ์ด๋ผ๋Š” ์—๋Ÿฌ ๋ฉ”์„ธ์ง€๋ฅผ ๋ณด๋‚ด์ค๋‹ˆ๋‹ค. ๋™์˜์ƒ์€ ํฌ๊ธฐ๋„ ๋งค์šฐ ํฌ๊ณ , ๊ทธ ์ˆ˜๋„ ๋งค์šฐ ๋งŽ์Šต๋‹ˆ๋‹ค. ๊ทธ๋ ‡๊ฒŒ ๋งŽ์€ ๋™์˜์ƒ ์ค‘์—์„œ ์–ด๋–ป๊ฒŒ ์ค‘๋ณต๋˜๋Š” ๋™์˜์ƒ์ธ์ง€๋ฅผ ๋น ๋ฅด๊ฒŒ ํŒ๋‹จํ•  ์ˆ˜ ์žˆ์„๊นŒ์š”? ์•ž์œผ๋กœ ์‚ดํŽด๋ณผ ์ž๋ฃŒ๊ตฌ์กฐ์ธ ํ•ด์‹œํ…Œ์ด๋ธ”์ด ๋ฐ”๋กœ ์ด๊ฒƒ์„ ๊ฐ€๋Šฅํ•˜๊ฒŒ ๋งŒ๋“ค์–ด์ค๋‹ˆ๋‹ค. Hash Function (ํ•ด์‹œ ํ•จ์ˆ˜) ํ•ด์‹œ ํ•จ์ˆ˜ (Hash Function) ๋˜๋Š” ํ•ด์‹œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์ž„์˜์˜ ๋ฐ์ดํ„ฐ๋ฅผ ๋ฐฐ์—ด์˜ ์ธ๋ฑ์Šค๋กœ ๋งคํ•‘(๋ณ€ํ™˜)ํ•˜๋Š” ํ•จ์ˆ˜์ž…๋‹ˆ๋‹ค. ํ•ด์‹œ ํ…Œ์ด๋ธ”์€ ๋ฐฐ์—ด์ž…๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ ์ธ๋ฑ์Šค๋ฅผ ํ†ตํ•ด ์ ‘๊ทผํ•  ๋•Œ์—๋Š” O(1)์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋กœ ๋งค์šฐ ๋น ๋ฅด๊ฒŒ ..
๊ฐ€์„ค ๊ฒ€์ • ์–ด๋– ํ•œ ์ถ”์ธก์ด๋‚˜ ๊ฐ€์„ค์— ๋Œ€ํ•˜์—ฌ, ํ•ด๋‹น ๊ฐ€์„ค์˜ ํƒ€๋‹น์„ฑ์„ ์กฐ์‚ฌํ•˜๋Š” ๊ฒƒ์„ ๊ฐ€์„ค ๊ฒ€์ •์ด๋ผ๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ํ†ต๊ณ„์  ๊ฐ€์„ค ํ†ต๊ณ„๋ฅผ ํ†ตํ•ด ์•Œ ์ˆ˜ ์žˆ๋Š” ๊ฒƒ์€ ํ‰๊ท ๊ณผ ํ‘œ์ค€ํŽธ์ฐจ์™€ ๊ฐ™์€ ๋ชจ์ˆ˜(parameter)์ž…๋‹ˆ๋‹ค. ์ฆ‰ ๋ชจ์ˆ˜(parameter)์— ๋Œ€ํ•œ ์˜ˆ์ƒ, ์ถ”์ธก ๋“ฑ์„ ํ†ตํ‹€์–ด ํ†ต๊ณ„์  ๊ฐ€์„ค์ด๋ผ ๋ถ€๋ฆ…๋‹ˆ๋‹ค. '์–ด๋–ค ์ง‘๋‹จ์˜ ํ‰๊ท ์€ A์ผ๊ฑฐ์•ผ!' ๋“ฑ์„ ์˜ˆ์‹œ๋กœ ๋ณผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ํ†ต๊ณ„์  ๊ฐ€์„ค ๊ฒ€์ • ํ†ต๊ณ„์  ๊ฐ€์„ค ๊ฒ€์ •์€ ํ†ต๊ณ„์  ๊ฐ€์„ค์— ๋Œ€ํ•˜์—ฌ ํ•ด๋‹น ๊ฐ€์„ค์˜ ํƒ€๋‹น์„ฑ์„ ์กฐ์‚ฌํ•˜๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค. ํ†ต๊ณ„์  ๊ฐ€์„ค ๊ฒ€์ •์„ ์œ„ํ•ด์„œ๋Š” ๋‘๊ฐœ์˜ ๋Œ€๋ฆฝ๋œ ๊ฐ€์„ค์ด ํ•„์š”ํ•ฉ๋‹ˆ๋‹ค. ์ด์ œ๋ถ€ํ„ฐ ์ดํ•ด๋ฅผ ๋•๊ธฐ ์œ„ํ•ด ์นœ๊ตฌ ํ•œ๋ช…์„ ํ†ตํ•ด ๋‹ค์Œ ์˜ˆ์‹œ๋ฅผ ํ•˜๋‚˜ ์ƒ๊ฐํ•ด ๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค. ์นœ๊ตฌ์˜ ์ด๋ฆ„์€ ๊น€์œ ๊ฒธ์ด๋ผ๊ณ  ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. ์–ด๋– ํ•œ ๋ชจ์ง‘๋‹จ์— ๋Œ€ํ•˜์—ฌ ์œ ๊ฒธ์ด๊ฐ€ ํ•ด๋‹น ๋ชจ์ง‘๋‹จ์˜ ํ‰๊ท ์€ A๋ผ๊ณ  ์ฃผ์žฅํ•˜๊ณ  ์žˆ์Šต..
Deap์ด๋ž€? ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ(Complete Binary Tree)์ด๋ฉฐ, ๋น„์–ด์žˆ๊ฑฐ๋‚˜ ๋‹ค์Œ์„ ๋งŒ์กฑ์‹œํ‚ค๋Š” ์ž๋ฃŒ๊ตฌ์กฐ์ž…๋‹ˆ๋‹ค. 1. Root ๋…ธ๋“œ๋Š” ์•„๋ฌด๋Ÿฐ ์š”์†Œ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ์ง€ ์•Š์Šต๋‹ˆ๋‹ค. 2. ์™ผ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ๋Š” min-heap ์ž…๋‹ˆ๋‹ค. 3. ์˜ค๋ฅธ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ๋Š” max-heap ์ž…๋‹ˆ๋‹ค. ๋งŒ์•ฝ ์˜ค๋ฅธ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ๊ฐ€ ๋น„์–ด์žˆ์ง€ ์•Š์€ ๊ฒฝ์šฐ ileft ๋ฅผ ์™ผ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ์˜ ์ž„์˜์˜ ์š”์†Œ๋ผ ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. jright ๋ฅผ ileft ์— ๋Œ€์‘๋˜๋Š” ์šฐ์ธก ์„œ๋ธŒํŠธ๋ฆฌ์˜ ์š”์†Œ๋ผ๊ณ  ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. ๋งŒ์•ฝ jright ๊ฐ€ ์กด์žฌํ•˜์ง€ ์•Š๋Š” ๊ฒฝ์šฐ, jright ์˜ ์œ„์น˜๋Š” ileft ์˜ ๋ถ€๋ชจ(parent)๋…ธ๋“œ์— ๋Œ€์‘๋˜๋Š”max-heap์˜ ์›์†Œ๊ฐ€ ๋ฉ๋‹ˆ๋‹ค. ํ•ญ์ƒ ileft ๋Š” jright ๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜..