YYYEJI

Interrupt(인터룹트) Hardware나 software의 관심을 필요로 하여 보내는 asynchronous signal입니다. interrput를 받으면 interrupt vector로 들어갑니다. Interrupt vector Interrupt vector는 Interrupt handler의 시작 주소를 모아둔 표입니다. Interrupt handler (ISR, interrupt service routine) Interrupt를 해결하기 위한 code, routine 입니다. ① PC: Program Counter ② IRQ: Interrupt ReQuest ③ ISR: Interrupt Service Routine Interrupt를 처리하는 코드를 한 번 살펴보겠습니다. InterruptR..

버스(bus)란? 데이터가 움직이는 길의 종류 중 하나입니다. 버스를 사용하게 되면 무엇보다 빠르게 데이터를 전송할 수 있습니다. 또한 다른 devices가 일할 때 CPU가 일을 할 수 있습니다(병렬구조). 사진으로 살펴보겠습니다. device들을 연결하는 선들이 버스입니다. 여기서 buffer가 등장하는데 ! buffer는 controller 안에 존재하는 작은 메모리입니다. keyboard에서 key를 하나 누르면 CPU로 바로 가는 게 아니라 controller 안에 있는 buffer 안으로 들어갑니다. I/O(input/output)은 해당 device에서부터 해당 controoler의 local buffer까지의 data transfer입니다. 이제 buffer까지 온 데이터를 memory로 ..

펌웨어(Firmware)란? User가 컴퓨터 전원을 키면 main-board에 있는 조그만한 프로그램이 돌아가면서 system을 진단하게 됩니다. 이때 조그만한 프로그램이 펌웨어(firmware)입니다. System을 진단할 때 devices 들이 잘 설치되어 있는지 진단하고, 운영체제를 로드(load)해서 실행시킵니다. Q. 펌웨어가 각각 다른 os를 어떻게 로드(load)하나요? A. os가 설치될 때 os 스스로가 disk의 0번 block에 설치합니다. 즉, firmware는 os가 어떻게 생긴지 알 필요 없습니다. OS가 booting이 되면 software 실행에 필요한 환경을 다 갖혀놓게 됩니다. Q. OS booting이 끝나면 OS는 무엇을 하나요? A. OS는 어떠한 행동도 하지 않고..

0-1 knapsac 문제는 제한된 가방 용량(W) 안에서 물건들의 가치(bi)와 무게(wi)가 주어졌을 때, 물건들을 조합해 최대의 가치를 가지도록 하는 문제입니다. 단, 각 물건은 딱 한 번만 사용할 수 있습니다. 배낭문제,수도코드(pseudo code)를 살펴보겠습니다. for w = 0 to W B[0, w] = 0 for i = 1 to n B[i, 0] = 0 for w = 1 to W if wi B[i-1, w] B[i,w] = bi + B[i-1, w-wi] else B[i,w] = B[i-1, w] else B[i, w] = B[i-1, w] 해당 코드는 냅색(Napsack) 문제를 동적 계획법(Dynamic Programming)으로 푸는 방법 중 하나인 0/1 냅색 문제를 푸는 코드입..

Knapsack이란? 냅색(Napsack) 문제는 배낭에 담을 수 있는 무게 한계가 정해져 있고, 각각의 물건들은 무게와 가치가 정해져 있을 때, 배낭에 담을 수 있는 최대 가치의 합을 구하는 문제입니다. 배낭문제는 대표적으로 두 가지 종류로 나뉩니다. 1. 0-1 knapsack problem: 각각의 물건은 단 하나씩만 존재하며, 배낭에 담거나 담지 않거나 둘 중 하나의 선택만 가능하다. 2. Fractional knapsack problem: 각각의 물건은 무게에 비례하여 일부분만 담을 수 있으며, 물건을 자를 수 있다. Branch and Bound Branch and Bound는 최적화 문제를 풀기 위한 알고리즘으로 가능한 모든 해를 차는 대신, 최적의 해를 빠르게 찾기 위해 탐색 범위를 줄이는..

Greedy 란? 각 단계에서 가장 최적의 선택을 하는 것으로, 그 순간에는 최선의 선택이지만 전체적으로는 최적해를 보장하지는 않는 알고리즘입니다. Huffman code란? 데이터를 인코딩(encoding)/디코딩(decoding)하기 위해 필요한 알고리즘입니다. 인코딩하는 과정 ① 입력 문자열에서 문자의 빈도수를 구한다. ② 빈도수를 기준으로 이진 트리를 생성한다. ③ 왼쪽 자식 노드는 0, 오른쪽 자식 노드는 1를 부여해서 huffman 코드를 생성한다. ④ 입력 문자열에서 찾은 huffman 코드를 순차적으로 연결하여 하나의 비트 스트림으로 생성한다. 디코딩하는 과정 ① 저장된 비트 스트림을 읽어 각 문자의 huffman code를 생성해서 원래 문자로 변형한다. 디코딩하는 과정에서 중요하게 살펴..

다이나믹 프로그래밍(Dynamic Programming)란? 큰 문제를 작은 문제로 쪼개서 그 답을 리스트에 저장해서 사용하는 알고리즘입니다. DP를 사용하게 되면 같은 문제를 여러 번 반복되지 않아도 되는 장점이 있기 때문입니다. Recursion을 사용하면 아래 코드와 같이 자기 자신을 계속 호출하게 됩니다. Fib(n) { if(n

마스터 정리 (Master Theorem)란? T(n)=aT(n/b)+f(n) 형식의 재귀적인 알고리즘을 계산하기 위한 방법입니다. ① If f(n) = O(nˡºᵍ𝚋ª⁻ᵋ) Ɛ>0, then T(n) = θ(nˡºᵍ𝚋ª). ② If f(n) = θ(nˡºᵍ𝚋ª), then T(n) = θ(nˡºᵍ𝚋ªlg n). ③ If f(n) = Ω(nˡºᵍ𝚋ª⁺ᵋ) Ɛ>0 and a f(n/b) ≤ c f(n), T(n) = θ(f(n)) 문제를 풀면서 이해를 해보도록 하겠습니다. Excercise 1: T(n) = 4T(n/2) + n T(n)=aT(n/b)+f(n)을 보면 a = 4, b = 2, f(n) = n임을 알 수 있습니다. Case 1에 만족함을 확인했습니다. Excercise 2: T(n) = 4T..