Archive: 2020/4

0

64bit ๋ฉ€ํ‹ฐ์ฝ”์–ด OS ์›๋ฆฌ์™€ ๊ตฌ์กฐ - Day 2

์ด ๊ธ€์€ โ€˜64๋น„ํŠธ ๋ฉ€ํ‹ฐ์ฝ”์–ด OS ์›๋ฆฌ์™€ ๊ตฌ์กฐ - ํ•œ์Šนํ›ˆ ์ €์žโ€™์„ ๊ณต๋ถ€ํ•˜๋ฉฐ ์ •๋ฆฌํ•œ ๋‚ด์šฉ์„ ์ž‘์„ฑํ–ˆ์Šต๋‹ˆ๋‹ค. ์ด๋ฏธ์ง€ ๋กœ๋”ฉ ๊ตฌํ˜„์ฑ…์—์„œ ๊ตฌํ˜„ํ•˜๊ฒŒ ๋  OS๋Š” ๋ถ€ํŠธ ๋กœ๋”, ๋ณดํ˜ธ ๋ชจ๋“œ ์ปค๋„, IA-32e ๋ชจ๋“œ ์ปค๋„๋กœ ๊ตฌ์„ฑ๋˜๊ณ  ์„นํ„ฐ ๋‹จ์œ„๋กœ ์ •๋ ฌ๋˜ ํ•˜๋‚˜์˜ ๋ถ€ํŒ… ์ด๋ฏธ์ง€๋กœ ๋งŒ๋“ค์–ด์ง€๋ฉฐ ๋‘ ๋ฒˆ์งธ ์„นํ„ฐ๋ถ€ํ„ฐ ์ฝ์–ด ๋ฉ”๋ชจ๋ฆฌ์— ๋ณต์‚ฌํ•˜๋ฉด ์ด๋ฏธ์ง€ ๋กœ๋”ฉ์ด ๋๋‚˜๊ฒŒ ๋œ๋‹ค. ์ฑ…์—์„œ ๊ตฌํ˜„ํ•˜๋Š” OS๋Š”

0

64bit ๋ฉ€ํ‹ฐ์ฝ”์–ด OS ์›๋ฆฌ์™€ ๊ตฌ์กฐ - Day 1

์ด ๊ธ€์€ โ€˜64๋น„ํŠธ ๋ฉ€ํ‹ฐ์ฝ”์–ด OS ์›๋ฆฌ์™€ ๊ตฌ์กฐ - ํ•œ์Šนํ›ˆ ์ €์žโ€™์„ ๊ณต๋ถ€ํ•˜๋ฉฐ ์ •๋ฆฌํ•œ ๋‚ด์šฉ์„ ์ž‘์„ฑํ–ˆ์Šต๋‹ˆ๋‹ค. ์„ธ์ƒ์—์„œ ๊ฐ€์žฅ ๊ฐ„๋‹จํ•œ BootLoader๋ถ€ํŠธ ๋กœ๋”๋ฅผ ์ •์ƒ์ ์œผ๋กœ ๋ถˆ๋Ÿฌ์˜ค๊ธฐ ์œ„ํ•ด์„œ๋Š” ํ•œ๊ฐ€์ง€ ๊ทœ์น™์ด ์žˆ๋‹ค. ๋จผ์ € ๋ถ€ํŠธ ์„นํ„ฐ 512Byte์˜ ๋งˆ์ง€๋ง‰ 2Byte๋Š” ๋ฐ˜๋“œ์‹œ 0x55, 0xAA๋ฅผ ๊ฐ€์ ธ์•ผ ํ•œ๋‹ค. ์•„๋ž˜๋Š” ์„ธ์ƒ์—์„œ ๊ฐ€์žฅ ๊ฐ„๋‹จํ•œ ๋ถ€ํŠธ๋กœ๋”๋ฅผ ์ž‘์„ฑํ•œ ์†Œ์Šค ์ฝ”

0

Merge sort algorithm

ํ•ฉ๋ณ‘ ์ •๋ ฌ(merge sort)ํ•ฉ๋ณ‘ ์ •๋ ฌ์€ ๋ถ„ํ• ์ •๋ณต ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ฉฐ ๊ธธ์ด๊ฐ€ N์ธ ๋ฆฌ์ŠคํŠธ๋ฅผ ๊ธธ์ด๊ฐ€ 1์ธ ๋ฆฌ์ŠคํŠธ๋กœ ์ชผ๊ฐœ๊ณ  ๋‹ค์‹œ ์ชผ๊ฐœ์ง„ ๊ฐ๊ฐ์˜ ๋ฆฌ์ŠคํŠธ๋ฅผ ์ •๋ ฌํ•˜๋ฉฐ ํ•ฉ๋ณ‘ํ•ด ์ตœ์ข…์ ์œผ๋กœ ์ •๋ ฌ๋œ ๋ฆฌ์ŠคํŠธ๋ฅผ ๊ฐ€์ง€๊ฒŒ ๋œ๋‹ค. ํ•จ์ˆ˜์˜ ๊ตฌ์กฐ๋ฅผ ๋ณด๋ฉด ์•Œ๊ฒ ์ง€๋งŒ, ์ค‘์•™ ์œ„์น˜๋ฅผ ์ฐพ๊ณ  ์ค‘์•™ ์œ„์น˜๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์ขŒ์ธก, ์šฐ์ธก์„ ๋‚˜๋ˆ  ์žฌ๊ท€ ํ˜ธ์ถœ๋œ๋‹ค. ์žฌ๊ท€ ์ข…๋ฃŒ ์กฐ๊ฑด์€ start < end์˜ ์กฐ๊ฑด์—

0

Quick sort algorithm

ํ€ต ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜ํ€ต ์ •๋ ฌ์€ ํ”ผ๋ฒ—์„ ๊ธฐ์ค€์œผ๋กœ ์ขŒ/์šฐ์— ์ž์‹ ๋ณด๋‹ค ํฐ/์ž‘์€ ๊ฐ’์„ ๋ชฐ๊ณ , ๋ฌธ์ œ๋ฅผ ์กฐ๊ธˆ์”ฉ ๋‚˜๋ˆ ๊ฐ€๋ฉฐ ์ •๋ ฌ์„ ํ•˜๊ฒŒ ๋œ๋‹ค. ์ตœ์•…์˜ ๊ฒฝ์šฐ(ํ•ญ์ƒ ํ”ผ๋ฒ—์ด ๋ชจ๋“  ๊ฐ’ ์ค‘ ๊ฐ€์žฅ ์ž‘์€ ๊ฒฝ์šฐ) O(n^2)๋ฅผ ๊ฐ€์ง€๋Š” ์ƒํ™ฉ์ด ๋‚˜์˜ฌ ์ˆ˜ ์žˆ์ง€๋งŒ, ํ™•๋ฅ ์ ์œผ๋กœ ๊ทธ๋Ÿด ์ผ์€ ์ ๊ธฐ์— ํ‰๊ท ์ ์œผ๋กœ O(NlogN)์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง„๋‹ค. ๊ตฌํ˜„123456789101112131415161718

0

Dijkstra Algorithm

๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜Dijkstra algorithm(์ดํ•˜ ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜)์€ ์Œ์˜ ๊ฐ€์ค‘์น˜๊ฐ€ ์—†๋Š” ๊ทธ๋ž˜ํ”„์—์„œ ํ•œ ๋…ธ๋“œ์—์„œ ๋‹ค๋ฅธ ๋ชจ๋“  ๋…ธ๋“œ๊นŒ์ง€์˜ ๊ฐ€์žฅ ์งง์€ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ค‘ ํ•˜๋‚˜์ด๋‹ค. ์„ ํ˜•๊ตฌ์กฐ๋กœ ๊ตฌํ˜„๋œ ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ O(N^2)์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง€์ง€๋งŒ ํž™์„ ์ด์šฉํ•ด ๊ตฌํ˜„ํ•˜๊ฒŒ ๋˜๋ฉด O(NlogN)์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง€๊ฒŒ ๋œ๋‹ค. ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•˜๋Š”