인프런 워밍업 클럽 4기 CS - 3주차 컴퓨터 구조 미션

미션 1STOREB(1001) 명령어를 만들어보세요.(OPcode는 1001이고 operand가 가리키는 RAM주소에 현재 레지스터B의 데이터 저장하는 기능)답 미션 2A와 B를 비교해서 A와 B가 같으면 0, A가 더 크면 1, B가 더 크면 2를 출력 레지스터에 출력하는 어셈블리어를 작성해보세요. 답LOADA 15 SUB 14 JMPZ 5 JMPC 6 LOADI 2 JMP 9 LOADI 0 JMP 9 LOADI 1 OUT HLT 0 0 0 1 1

인프런 워밍업 클럽 4기 CS - 3주차 자료구조와 알고리즘 미션

미션여러분은 문서 압축 프로그램을 개발해야 합니다. '허프만 코딩'이라는 압축 알고리즘을 사용하여, 아래와 같은 결과가 나오도록 구현해보세요. (필요하다면 사용된 자료구조를 수정해도 좋습니다.) const huffmanCoding = new HuffmanCoding(); const str = "Lorem ipsum dolor sit amet consectetur adipiscing elit. Consectetur adipiscing elit quisque faucibus ex sapien vitae. Ex sapien vitae pellentesque sem placerat in id. Placerat in id cursus mi pretium tellus duis. Pretium tellus duis convallis tempus leo eu aenean." let result = huffmanCoding.compress(str) console.log(result); // 결과 [ [ 'i', '000' ], [ 'v', '001000' ], [ 'q', '001001' ], [ 'd', '00101' ], [ 'l', '0011' ], [ 'o', '01000' ], [ 'b', '0100100' ], [ 'P', '0100101' ], [ 'L', '01001100' ], [ 'E', '01001101' ], [ 'C', '01001110' ], [ 'f', '01001111' ], [ 'a', '0101' ], [ 'e', '011' ], [ 'm', '10000' ], [ 'r', '10001' ], [ 't', '1001' ], [ 'u', '1010' ], [ 'x', '1011000' ], [ 'g', '1011001' ], [ '.', '101101' ], [ 'p', '10111' ], [ ' ', '110' ], [ 's', '1110' ], [ 'c', '11110' ], [ 'n', '11111' ] ] 풀이class HuffmanNode { constructor(char = null, freq = 0) { this.char = char; this.freq = freq; this.left = null; this.right = null; } } class HuffmanCoding { constructor() { this.codes = {}; } buildTree(frequency) { let heap = []; for (let char in frequency) { heap.push(new HuffmanNode(char, frequency[char])); } heap.sort((a, b) => a.freq - b.freq); while (heap.length > 1) { let node1 = heap.shift(); let node2 = heap.shift(); let merged = new HuffmanNode(null, node1.freq + node2.freq); merged.left = node1; merged.right = node2; heap.push(merged); heap.sort((a, b) => a.freq - b.freq); } return heap.length > 0 ? heap[0] : null; } buildCodes(root, currentCode = '') { if (root === null) { return; } if (root.char !== null) { this.codes[root.char] = currentCode; return; } this.buildCodes(root.left, currentCode + '0'); this.buildCodes(root.right, currentCode + '1'); } compress(text) { let frequency = {}; for (let char of text) { frequency[char] = (frequency[char] || 0) + 1; } let root = this.buildTree(frequency); this.codes = {}; this.buildCodes(root, ''); let result = []; for (let char in this.codes) { result.push([char, this.codes[char]]); } return result.sort((a, b) => a[0].localeCompare(b[0])); } }

인프런 워밍업 클럽 4기 CS - 3주차 발자국

학습 내용 요약 자료구조 & 알고리즘트라이자동완성에 주로 사용되는 트리 자료구조그래프깊이 우선 탐색(DFS)너비 우선 탐색(BFS)가중 그래프다익스트라탐욕 알고리즘(그리디)최소 신장 트리프림 알고리즘포드 풀커슨 알고리즘비트 마스킹 컴퓨터 구조프로그램 카운터다음에 실행할 명령어의 주소 관리스텝 카운터실행 중인 명령어의 단계(스탭) 관리명령어 구현NOPLOADAADDSUBSTOREALOADIJMPJMPCJMPZOUTHLT 회고자료구조의 경우 트라이를 제외하면 이전에 학습한 적이 있어 수월했습니다알고리즘의 경우 프림 알고리즘, 포드 풀커슨 알고리즘은 개인적으로 난이도가 높게 느껴져서 많은 시간이 필요했습니다컴퓨터 구조의 경우 단순히 따라하는 것만으로는 부족했는데 미션을 진행하면서 어느 정도 체득할 수 있었습니다

인프런 워밍업 클럽 4기 CS - 2주차 발자국

학습 내용 요약 자료구조 & 알고리즘레드블랙 트리 우선순위 힙 우선순위 큐 컴퓨터 구조MUX디코더컨트롤 버퍼 반 가산기전 가산기ALU(산술논리연산장치)조합 논리회로 / 순차 논리회로SR 래치, D 래치, JK 래치 플립플롭레지스터RAM 회고 트리 자료구조가 끝나고 우선순위 큐까지 학습했으나 트리에 대한 이해도가 아직 부족하다고 느꼈습니다 여러 번 강의를 복습하고 직접 구현도 여러 번 해야 할 것 같습니다컴퓨터 구조의 경우 1주차에 비해 2주차에 학습할 내용이 많이 등장했으나 난이도 자체는 크게 어렵지 않아 무난하게 학습이 가능했습니다

인프런 워밍업 클럽 4기 CS - 2주차 자료구조와 알고리즘 미션

미션여러분은 간단한 운영체제를 개발하고 있습니다. 운영체제의 CPU 스케줄링을 구현해야 하는 차례입니다. 여러 프로세스들이 골고루 실행되도록 하기 위해, 프로세스 실행 횟수(executionCount)가 작은 프로세스의 우선순위를 높게 설정하는 CPU 스케줄링 정책을 만들려고 합니다. 또한, 모든 프로세스가 비슷하게 실행될 때는 사용자의 반응성을 높이기 위해 I/O Bound 프로세스들의 처리를 우선적으로 하려고 합니다. I/O Bound 프로세스는 CPU를 사용하다가 자발적으로 CPU를 반납(cpuReturnCount)하는 것으로 판단할 수 있습니다.따라서 다음 두 가지 조건으로 CPU 스케줄러를 구현해 보세요: 프로세스 실행 횟수가 가장 적은 프로세스가 우선순위가 높습니다.실행 횟수가 같을 경우, I/O Bound 프로세스가 우선순위가 높습니다.class Process{ constructor(name, cpuReturnCount, executionCount){ } } let cpuScheduler = new CpuScheduler(); cpuScheduler.enqueue(new Process("수치계산프로그램", 4, 0)); // cpu반납 4회, 실행횟수 0회 cpuScheduler.enqueue(new Process("뮤직플레이어", 11, 10)); // cpu반납 11회, 실행횟수 10회 cpuScheduler.enqueue(new Process("웹브라우저", 27, 25)); // cpu반납 27회, 실행횟수 25 cpuScheduler.enqueue(new Process("터미널1", 34, 2)); // cpu반납 34회, 실행횟수 2회 cpuScheduler.enqueue(new Process("터미널2", 93, 2)); // cpu반납 93회, 실행횟수 2회 console.log(cpuScheduler.dequeue()); // 수치계산프로그램 프로세스 출력 console.log(cpuScheduler.dequeue()); // 터미널2 프로세스 출력 console.log(cpuScheduler.dequeue()); // 터미널1 프로세스 출력 console.log(cpuScheduler.dequeue()); // 뮤직플레이어 프로세스 출력 console.log(cpuScheduler.dequeue()); // 웹브라우저 프로세스 출력답class Process { constructor(name, cpuReturnCount, executionCount) { this.name = name; this.cpuReturnCount = cpuReturnCount; this.executionCount = executionCount; } } import { Heap } from "./heap.mjs"; class CpuScheduler { constructor() { this.heap = new Heap(); this.heap.isBigPriority = function(first, second) { if (first.executionCount !== second.executionCount) { return first.executionCount second.cpuReturnCount; }; } enqueue(process) { this.heap.insert(process); } dequeue() { let removedNode = this.heap.remove(); return removedNode ? removedNode.getData() : null; } } let cpuScheduler = new CpuScheduler(); cpuScheduler.enqueue(new Process("수치계산프로그램", 4, 0)); cpuScheduler.enqueue(new Process("뮤직플레이어", 11, 10)); cpuScheduler.enqueue(new Process("웹브라우저", 27, 25)); cpuScheduler.enqueue(new Process("터미널1", 34, 2)); cpuScheduler.enqueue(new Process("터미널2", 93, 2)); console.log(cpuScheduler.dequeue()); // 수치계산프로그램 console.log(cpuScheduler.dequeue()); // 터미널2 console.log(cpuScheduler.dequeue()); // 터미널1 console.log(cpuScheduler.dequeue()); // 뮤직플레이어 console.log(cpuScheduler.dequeue()); // 웹브라우저

인프런 워밍업 클럽 4기 CS - 2주차 컴퓨터 구조 미션

미션 1다음 파일의 모든 연결을 터널로 대체해보세요.(회로 이미지와 .circ파일 첨부) 미션 28비트 32입력 MUX를 제작해보세요.(회로 이미지와 .circ파일 첨부)미션 310비트 입력 두 개(A, B)를 계산하는 ALU 만들어보세요.(회로 이미지와 .circ파일 첨부) 미션 432비트 RAM을 만들어보세요. 디코더와 MUX는 logisim 기본 내장된 걸 사용해도 좋습니다.(회로 이미지와 .circ파일 첨부)파일 공유 링크

인프런 워밍업 클럽 4기 CS - 1주차 컴퓨터 구조 미션

미션 1문제4입력 AND, OR, NAND, NOR, XOR 연산의 진리표를 작성해보세요.답 미션 2문제다음 불 방정식들을 여러 방법을 이용해 간략화 해보세요.,1. A( (BB)’+ 0A) + (CC)' = (AB’) +C 2. (B’B’) + (AD’ + (CA)’)D = B’ + (DC’) + (DA’) 3. (A’B) + B(B1 + BC) = B 4. B’(1C + BD) + DB = (B’C) + (DB) 답AB' + C' = AB' + C B' + AD' + CD' = B' + AD' + CD' B = B B'C + DB = B'C + DB 미션 3문제다음 2진수를 10진수로 변환해보세요.1. 110111 = 2. 10000001 = 3. 11111100000 = 4. 101010 = 답1. 55 2. 129 3. 2106 4. 42 미션 4문제다음 10진수를 2진수로 변환해보세요.1. 10 = 2. 27 = 3. 86 = 4. 516 = 답1. 1010 2. 11011 3. 1010110 4. 1000000100 미션 5문제다음 불 방정식을 logisim을 이용해 회로를 만들어보세요.(회로 이미지와 .circ파일 첨부) (B’C) + (DB)(AB’) + CB’ + (DC’) + (DA’)파일 공유 링크

인프런 워밍업 클럽 4기 CS - 1주차 자료구조와 알고리즘 미션

미션Python, JavaScript, C# 같은 언어는 가비지 컬렉터를 이용해 메모리를 자동으로 정리하는 매니지드 언어(Managed Language)에 속합니다. 매니지드 언어의 가비지 컬렉터는 개발자가 메모리를 요청하면 운영체제의 힙 영역에 할당하고, 더 이상 필요하지 않을 때 자동으로 해제하며 메모리를 관리합니다.여러분이 속한 회사에서 새로운 매니지드 언어를 개발 중이며, 여러분은 가비지 컬렉터 개발을 담당하게 되었습니다. 특히 메모리 검색 부분을 맡게 되었는데, 사용자가 특정 크기(Byte)의 메모리를 요청하면 사용 가능한 메모리 중 가장 적절한 크기를 찾아 반환하는 GarbageCollector 클래스를 구현해보세요.(같은 크기의 메모리는 없다고 가정) 답import { AVLTree } from "./avlTree.mjs" class GarbageCollector { constructor() { this.memoryTree = new AVLTree(); } insertFreeMemory(size) { this.memoryTree.insert(this.memoryTree.root, size); } searchFreeMemory(requestedSize) { return this.findBestFit(this.memoryTree.root, requestedSize); } findBestFit(node, requestedSize, target = null) { if (node == null) { return target; } if (node.getData() === requestedSize) { return node; } if (node.getData() >= requestedSize) { if (target == null || node.getData()

인프런 워밍업 클럽 4기 CS - 1주차 발자국

학습 내용 요약 자료구조 & 알고리즘P-NP 문제트리계층구조를 표현하기에 적합이진 트리각각의 노드가 최대 2개의 자식 노드를 가질 수 있는 트리성능조회 - O(n) / O(logn)종류완전이진트리포화이진트리AVL 트리스스로 균형을 잡는 이진 트리회전RR 회전LL 회전RL 회전LR 회전 컴퓨터 구조컴퓨터 구성 요소CPU메모리주변 장치비트불 대수연산성질과 법칙교환법칙결합법칙분배법칙흡수법칙드모르간의 법칙불 함수카르노 맵비트10진법, 2진법, 16진법빅 라디안, 리틀 라디안 LSB, MSB오버플로우, 인터럽트음수2의 보수 + 1로 치환 뺄셈을 덧셈으로 편리하게 연산 가능 logisim-evolution 사용법 후기컴퓨터 구조의 경우 초반이라 그런지 강의 내용도 간단했고 실습도 간단해서 편하게 볼 수 있었습니다컴퓨터 구조의 미션도 크게 어렵지 않았습니다 자료구조 & 알고리즘의 경우 심화편이라서 그런지 초반 내용부터 꽤 시간이 필요했습니다 미션 제출 이후에도 추가적인 복습이 필요하다는 것을 느꼈습니다

인프런 워밍업 클럽 3기 CS - 3주차 발자국

해당 글은 감자님의 강의인 그림으로 쉽게 배우는 운영체제, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)을 수강하고 적은 글입니다. 학습 내용운영체제입출력 장치주변 장치메인보드 내 버스로 연결입출력 제어기를 통해 여러 주변 장치 처리마우스 / 키보드사용자 이벤트 발생 -> 디바이스 컨트롤러에서 이벤트 감지 -> 디바이스 컨트롤러가 CPU에 인터럽트 신호 전달 -> 드라이버가 운영체제에게 이벤트 전달 -> 운영체제가 포그라운드 애플리케이션에게 이벤트 전달파일 / 디스크하나의 파일은 여러 블록으로 이루어짐연속 할당불연속 할당 자료구조와 알고리즘동적 프로그래밍메모이제이션하향식, 재귀타뷸레이션상향식, 반복문 회고 부족한 지식을 그림과 상황극을 통해 이해할 수 있어 좋았습니다.학습한 내용을 바탕으로 꾸준히 복습하면서 연관된 더 깊은 내용을 학습해야 할 것이라는걸 알게 되었습니다.