ํ๋ก์ธ์ค ๋ฉ๋ชจ๋ฆฌ์ ํ ๋น๋์ด ์คํ์ค์ ์๋ ํ๋ก๊ทธ๋จ (program in execution)์ ๋งํ๋ค. ํ๋ก๊ทธ๋จ์ ์ผ๋ฐ์ ์ผ๋ก ์ ์ฅ์ฅ์น์ ์ ์ฅ๋์ด ์๋ฌด์ผ๋ ํ์ง ์๋ ์ํ์ด๋ค. ํ๋ก์ธ์ค๋ฅผ job, task ๋ฑ์ผ๋ก ๋งํ๊ธฐ๋ ํ๋ค. ํ๋ก์ธ์ค ์ํ New : ์ ์ฅ์ฅ์น๋ก ๋ถํฐ ํ๋ก๊ทธ๋จ์ ๋ฉ๋ชจ๋ฆฌ์ ํ ๋นํ ๊ฒฝ์ฐ์ด๋ค. Ready : New ์ํ์์ ์ด๊ธฐํ ๊ณผ์ ํ ์คํํ ์ค๋น๊ฐ ์๋ฃ๋๊ฑฐ๋, Running ์ํ์์ ์ธํฐ๋ฝํธ๊ฐ ๋ฐ์ํ ๊ฒฝ์ฐ์ด๋ค. Running : ์ค์ผ์ค๋ฌ๋ฅผ ํตํด ๋ค์์ ์คํ๋ ํ๋ก์ธ์ค๋ก ์ ํ๋ ๊ฒฝ์ฐ Running ์ํ๋ก ๋ฐ๋์ด ์์ ์ ์ํํ๋ค. Wating : I/O์ ์ด๋ฒคํธ๋ฅผ ์ฒ๋ฆฌํ๋ ๊ฒ์ ์ง์ฐ์๊ฐ์ด ํฌ๋ฏ๋ก ์ด์ ๊ฐ์ ๊ฒฝ์ฐ Waiting ์ํ ํ ๋ค์ Ready๋ก ๊ฐ๋ค. Terminated : ํ๋ก์ธ์ค๋ฅผ ..
์ด์์ฒด์ ๋ฅผ ์ด์ฉํ๋ ๋ชจ๋ ์ฌ์ฉ์๊ฐ ๋ณ๋์ ๊ถํ์ ํ์ธํ์ง ์๊ณ , ํ์ผ์ ์ ์ฅํ ์ ์๋ค๋ฉด ์ด๋ป๊ฒ ๋ ๊น? ์ ์์ ์ธ ํ๋ก๊ทธ๋จ์ ์คํํ ๊ฒฝ์ฐ ํ์ธ์ ์ ์ฅ๊ณต๊ฐ์ ์นจ๋ฒํ์ฌ ๋ฐ์ดํฐ๋ฅผ ์์ค์ํฌ ์ ์๋ ์ํฉ์ด ๋ฐ์ํ ์ ๋ ์๋ค. ๋ํ, ์ด์์ฒด์ ๋ฅผ ์ข ๋ฃํ๋ ๋ช ๋ น์ด์ ๊ฐ์ ์คํ์ ์น๋ช ์ ์ธ ๋ช ๋ น์ด๋ฅผ ์ฌ์ฉํ ๊ฒฝ์ฐ๋ ๋น์ทํ ์ํฉ์ด ๋ฐ์ํ๋ค. Dual Mode ์ด์์ฒด์ ๋ ํน๊ถ ๋ช ๋ น(Privileged Instructions)์ ์ง์ ํ๊ณ ์ผ๋ฐ ์ฌ์ฉ์๋ ์ฌ์ฉํ์ง ๋ชปํ๊ฒ ๋ง์๋ค. Applications์์ ํน๊ถ ๋ช ๋ น ์ฌ์ฉ์ด ํ์ํ ๊ฒฝ์ฐ ์ธํฐ๋ฝํธ๋ฅผ ๋ฐ์์์ผ kernel mode์ ์ง์ ํ, ์ด์์ฒด์ ๋ฅผ ํตํด ์ฒ๋ฆฌํ๊ณ ์ ํ๋ ์์ ์ ์ฒ๋ฆฌํ๋ค. (ํน๊ถ ๋ช ๋ น์ด ์ฌ์ฉ ๊ฐ๋ฅํ kernel mode์ ๋ฐ๋์ธ user mode๋ CPU ๋ ์ง์คํฐ์..
์ด์์ฒด์ ๋? ์ด์์ฒด์ ๋ ์ปดํจํฐ์ ์์๋ค์ ์ฌ์ฉํ ์ ์๋ ํ๊ฒฝ์ ์ ๊ณตํ๋ค. ๋ค์ํ ํ๋์จ์ด๋ฅผ ์ฌ์ฉํ ์ ์๋๋ก ํธ์์ฑ์ ์ ๊ณตํ๋ค. ๋ค์์ ์ฌ์ฉ์๊ฐ ์ฌ์ฉํ๊ฑฐ๋, ์ฌ๋ฌ ๊ฐ์ ํ๋ก๊ทธ๋จ์ด ์คํ๋ ๊ฒฝ์ฐ ์ ์ ํ ์คํ๋๋๋ก ๊ด๋ฆฌํ๋ค. ์ฆ, ์ปดํจํฐ์ ํ๋์จ์ด์ ๊ด๋ฆฌ์ ์ฌ์ฉ์๊ฐ ์ ์์ ์ฌ์ ์ฌ์ฉํ ์ ์๋ ํ๊ฒฝ์ ์ ๊ณตํ๋ค. ๋ถํ (Booting) ์ปดํจํฐ ๋ถํ ๊ณผ์ ์ ํฌ๊ฒ 2๊ฐ์ง๋ก ๋๋๊ฒ ๋๋ค. ์ฒซ๋ฒ์งธ๋ POST(Power-On-Self-Test)๋ฅผ ํตํด ์ปดํจํฐ์ ๊ฐ ์ฅ์น์ ๋ํ ์ ๊ฒ์ ์งํํ๋ ๊ณผ์ ์ด๋ค. ๋๋ฒ์งธ๋ ๋ถํธ๋ก๋(Boot loader)๋ฅผ ํตํด ์ ์ฅ์ฅ์น ๋ด์ ์ด์์ฒด์ ์ ๊ด๋ จ๋ ๋ฐ์ดํฐ๋ฅผ ๋ฉ๋ชจ๋ฆฌ์ ์ ์ฌํ๋ ๊ณผ์ ์ด๋ค. ์์ ๊ณผ์ ์ ๋ง์น๊ฒ ๋๋ฉด ์ ์์ ์ผ๋ก ์ด์์ฒด์ ๋ฅผ ์ฌ์ฉํ ์ ์๋ค. ์ด์์ฒด์ ์ ๊ณ์ธต์ ์์น ์ด์์ฒด์ ์ ๊ณ์ธต์ ..
์ ๋ ฌ ๋ฐฉ์ ์์ฃผ ์ฌ์ฉํ๋ ์ ๋ ฌ ๋ฐฉ์์ ํฌ๊ฒ 2๊ฐ์ง๋ก ๋๋ ์ ์๋ค. ์ฒซ ๋ฒ์งธ๋ก 2์ค ๋ฐ๋ณต๋ฌธ์ ์ฌ์ฉํ๋ Bubble, Select, Insert ์ ๋ ฌ์ด๋ค. ๋ ๋ฒ์งธ๋ ๋ถํ -์ ๋ณต ๋ฐฉ๋ฒ์ ์ฌ์ฉํ๋ ๋ณํฉ, ํต ์ ๋ ฌ์ด๋ค. 2์ค ๋ฐ๋ณต๋ฌธ์ ์ฌ์ฉํ๋ ์ ๋ ฌ ๋ฐฉ์ ํด๋น ๋ฐฉ์์ ์ต์ ์ ๊ฒฝ์ฐ ์๊ฐ๋ณต์ก๋๋ O(N^2)์ด ๋๋ค. ์ด์ ๊ฐ์ ์ด์ ๋ 2๊ฐ์ ๋ฐ๋ณต๋ฌธ์ ํตํด ๊ฐ์ ๋น๊ตํ๊ธฐ ๋๋ฌธ์ด๋ค. Bubble Sort ์๋ก ์ธ์ ํ ๋ ์์๋ฅผ ๊ฒ์ฌํ์ฌ ์ ๋ ฌํ๋ ๋ฐฉ์์ ์ฌ์ฉํ๋ค. swap์ด ๋ ์ด์ ๋ฐ์ํ์ง ์์ผ๋ฉด, ์ค๋จํ์ฌ ๋ถํ์ํ ๋ฐ๋ณต๋ฌธ์ ์คํํ์ง ์์ ์ ์๋ค. def bubble_sort(nums): for i in range(len(nums)): swap = False for j in range(1, len(nums)): if ..
๊ทธ๋ํ ํ์ ๋ฐฉ๋ฒ ๊ทธ๋ํ๋ฅผ ํ์ํ๋ ๋ฐฉ๋ฒ์ค DFS(Depth First Search์ BFS(Breadth First Search)๋ฅผ ๊ฐ๋จํ ์์๋ฅผ ํตํด ์ดํดํ๊ณ ์ ํ๋ค. ๋ ๋ฐฉ์์ ๊ฐ๊ฐ Stack๊ณผ Queue๋ฅผ ํตํด ๊ตฌํํ ์ ์์ผ๋ฉฐ, ๊ทธ๋ํ ๋ฐฉ๋ฌธ ์ฌ๋ถ๋ฅผ ์ฒดํฌํ์ฌ ์ค๋ณต์ผ๋ก ํ์ํ๋ ๊ฒ์ ๋ฐฉ์งํ์ฌ์ผ ํ๋ค. ๊ทธ๋ํ๋ฅผ ์ฝ๋๋ก ๋ํ๋ด๊ธฐ ๊ทธ๋ฆผ 1์ ๊ทธ๋ํ์ ๋ํ ๋ ธ๋ ์ ๋ณด๋ฅผ ์ฝ๋๋ก ๋ํ๋ด๋ฉด ๋ค์๊ณผ ๊ฐ๋ค. graph = { 'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'E', 'F'], 'D': ['B', 'G'], 'E': ['C', 'H'], 'F': ['C'], 'G': ['D'], 'H': ['E'], } DFS ๊ทธ๋ฆผ 2๋ ๋ฃจํธ ๋ ธ๋๋ฅผ ์์์ผ๋ก ๋ชจ๋ ๊ทธ๋ํ ๊ฒฝ๋ก๋ฅผ ํ์ํ..
Recursion? ์ฌ๊ท๋ ํน์ ํจ์ ๋ด์์ ํจ์ ์์ ์ ๋ค์ ํธ์ถํ๋ ๊ฒ์ ์๋ฏธํ๋ค. ์ฌ๊ท๋ Stack์ ํน์ฑ์ ๊ทธ๋๋ก ๋ฐ์ํ์ฌ, ๊ฐ์ฅ ์ต๊ทผ์ ํธ์ถ๋ ํจ์ ๋ถํฐ ์ฒ๋ฆฌ๋๋ ๋ฐฉ์์ผ๋ก ์งํ๋๋ค. ์ฌ๊ท๋ฅผ ์ ๋ค๋ฃฐ ์ ์๋ค๋ฉด DFS์ ๋ฐฑํธ๋ํน, ํธ๋ฆฌ ํ์๊ณผ ๊ฐ์ ๋ฌธ์ ๋ฅผ ํด๊ฒฐ ํ ๋ ํจ์จ์ ์ผ๋ก ์ ๊ทผํ ์ ์๊ฒ ๋๋ค. ์ด์ง ํธ๋ฆฌ ์ํ ๊ทธ๋ฆผ 1๊ณผ ๊ฐ์ ์ด์ง ํธ๋ฆฌ๊ฐ ์์ ๊ฒฝ์ฐ, 3๊ฐ์ง ๋ฐฉ์์ผ๋ก ํธ๋ฆฌ๋ฅผ ์ํํ ์ ์๋ค. ์ฒซ ๋ฒ์งธ๋ ์ ์ ์ํ๋ก 1-2-4-5-3-6-7 ์์๋ก ํธ๋ฆฌ๋ฅผ ์ํํ๋ค. ๋ ๋ฒ์งธ๋ ์ค์ ์ํ๋ก 4-2-5-1-6-3-7 ์์๋ก ํธ๋ฆฌ๋ฅผ ์ํ ํ๋ค. ๋ง์ง๋ง์ผ๋ก ํ์์ํ๋ 4-5-2-6-7-3-1๋ก ์ํํ๋ค. ํธ๋ฆฌ๋ฅผ ์ํํ๋ ๊ฒ์ ์ฌ๊ท ํธ์ถ์ ํตํด์ ๊ตฌํ ํ ์ ์๋ค. Simple Tree Travel de..
Linked List? ๋จ์ํ ์ ํ ๋ฐฐ์ด(๋ฆฌ์คํธ)์ ์ ์ธํ๋ฉด ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์ฐ์์ ์ผ๋ก ํ ๋นํ๋ค. ๋ง์ฝ, ๋ฐฐ์ด ๋ด์ ๊ฐ ์ญ์ ๊ฐ ํ์ํ๊ฑฐ๋ ์ถ๊ฐ๊ฐ ํ์ํ ๊ฒฝ์ฐ ๊ฐ๋ค์ ์๋ฆฌ ๊ต์ฒด๊ฐ ํ์ํ๋ค. ์ด์ ๋ฌ๋ฆฌ ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ ์ฐ์์ ์ธ ๊ณต๊ฐ์ ์ฌ์ฉํ์ง ์๊ณ , ๊ฐ๊ฐ์ ๋ ธ๋๋ค์ ์ฐ๊ฒฐํ ๊ตฌ์กฐ๋ก ์ฐ๊ฒฐ๋์ด ์ค๊ฐ์ ๊ฐ ์ญ์ ๊ฐ ๋น๋ฒํ๊ฒ ์ผ์ด๋๋ ์๋ฃ๋ฅผ ๊ด๋ฆฌํ๊ธฐ์ ๋ณด๋ค ํจ์จ์ ์ด๋ค. Single Linked List class Node: def __init__(self, data): self.data = data self.next = None class SingleLinkedList: def __init__(self, data): self.head = Node(data) def add(self, data): node = self.head w..
Queue? ๊ฐ์ฅ ์ฒ์์ ์ฝ์ ๋ ๋ฐ์ดํฐ๋ฅผ ๋จผ์ ๋บ ์ ์๋ ๋ฐฉ์(First in First Out) ํ์์ ์๋ฃ๊ตฌ์กฐ Queue์ ์ฐ์ฐ enqueue(data) : data๋ฅผ Queue์ ๊ฐ์ฅ ๋ง์ง๋ง์ ์ถ๊ฐํ๋ค. dequeue() : Queue์ ๊ฐ์ฅ ์ต๊ทผ์ ์ถ๊ฐ๋ data๋ฅผ ์ ๊ฑฐํ๊ณ ๋ฐํํ๋ค. peek() : pop()๊ณผ ๋ฌ๋ฆฌ ๊ฐ์ฅ ์ต๊ทผ์ ์ถ๊ฐ๋ data๋ฅผ ๋ฐํํ๊ณ , ์ ๊ฑฐํ์ง ์๋๋ค. is_empty() : pop()์ ์ํํ๊ธฐ ์ํด์๋ ์ถ๊ฐ๋ data๊ฐ ์กด์ฌํ์ฌ์ผ ํ๋๋ฐ ์ด๋ฅผ ํ๋ณํ๊ธฐ ์ํจ์ด๋ค. Queue๋ฅผ ํ์ฉํ๋ ๊ฒฝ์ฐ ์ ์ ์ ์ถ์ด ํ์ํ ๊ฒฝ์ฐ ํ๋ก์ธ์ค ๊ด๋ฆฌ, ์ฐ์ ์์ ๋๊ธฐ์ด, ํ๋ฆฐํฐ ์ถ๋ ฅ ์ฒ๋ฆฌ ๋ฑ BFS ๊ตฌํ Queue์ ์ ์ ์ ์ถ ๋ฐฉ์์ ํตํด BFS๋ฅผ ๊ตฌํํ ์ ์๋ค. DFS์ ๊ฒฝ์ฐ Stack์ ์ฌ์ฉ..