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

문제STOREB(1001) 명령어를 만들어보세요.(OPcode는 1001이고 operand가 가리키는 RAM주소에 현재 레지스터B의 데이터 저장하는 기능)1. operand 를 MAR에 저장하기 위해 IO와 MI 활성화 레지스터 B의 데이터를 램에 저장하기 위해 BO과 RI을 활성화STOREB(1001) 명령어 작업 A와 B를 비교해서 A와 B가 같으면 0, A가 더 크면 1, B가 더 크면 2를 출력 레지스터에 출력하는 어셈블리어를 작성해보세요.JMPC는 A JMPZ는 A == B일 때 점프해주는 명령어이기 때문에 각 분기로 나눠 실행할 명령어 코드로 점프를 시켜줬고 하위에는 값 A, B와 결과를 담을 상수(0, 1, 2)를 저장해주었다.LOADA 15 // A 값 SUB 14 // A - B JMPC 7 // A B, 값 1 출력 OUT HLT LOADA 13 // 값 2 출력 OUT LOADA 11 // 값 0 출력 OUT 0 // A == B 출력값 1 // A > B 출력값 2 // A 하지만 상위 코드에는 치명적인 문제점이 있다.A > B일 경우에는 OUT 레지스터에 값을 출력하고 프로그램을 종료시키는데, 그 외의 경우는 OUT만 시켜주고 프로그램을 종료시키지 않다보니 무한 루프가 돌게 되며 처음에는 올바른 결과가 출력되다가 루프를 통해 결과값이 바뀌게 된다.그래서 아마 문제에선 A,B 값이 주어지지 않았으니LOADA 15 // A 값 SUB 14 // A - B JMPC 7 // A B, 값 1 출력 OUT HLT LOADA 13 // 값 2 출력 OUT HLT LOADA 11 // 값 0 출력 OUT HLT 0 // A == B 출력값 1 // A > B 출력값 2 // A 이렇게 각 조건마다 프로그램을 종료시키는 명령어를 넣고, A와 B의 값은 수동으로 혹은 다른 기능에 의해 삽입해야하지 않을까 싶다. 후기미션을 제대로 수행했는지 감도 안잡힐 정도로 개념이 어려웠던 것 같다. 사실 미션은 다 틀린 것 같은데 최대한 아는 내용에서 머리를 굴려서 문제를 풀었던 것 같다 😅 그럼에도 개념을 계속 복습하면서 문제를 풀어서 제출하는 것에 의의를 두었고 처음 어셈블리어까지 혹은 컴퓨터 회로 구조까지 내려가면서 딥하게 볼 수 있어서 더 인상 깊었던 로드맵이었고 현재는 나에게 크게 와닿지는 않겠지만 나중에 업무를 하며 분명히 나에게 도움이 될 때가 올 것이라고 확신할 수 있을 것 같다 :)

[인프런 워밍업 클럽 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' ] ] 풀이허프만 알고리즘이란 압축 알고리즘으로 문자의 출현 빈도를 통해 0과 1로 코드로 변환하여 데이터를 압축하는 알고리즘이다.문자의 출현 빈도와 그에 따른 데이터 저장 자료구조가 필요하기 때문에 최소 힙을 통해 자료를 저장하고 우선순위 큐를 통해 출현 빈도에 따른 코드를 생성해낼 수 있다.import { Heap } from "./heap.mjs"; class CharacterNode { constructor(char, frequency, left = null, right = null) { this.char = char; this.frequency = frequency; this.priority = frequency; this.left = left; this.right = right; } } class HuffmanCoding { constructor() { this.root = null; this.frequency = new Map(); } mergingNodes() { const heap = new Heap(); for (let char of this.frequency.keys()) { const node = new CharacterNode(char, this.frequency.get(char)); heap.insert(node); } while (heap.getSize() > 1) { const left = heap.remove().getData(); const right = heap.remove().getData(); const merged = new CharacterNode(null, left.frequency + right.frequency, left, right); heap.insert(merged); } this.root = heap.remove().getData(); return this.root; } generateCodes(node = this.root, code = "", result = new Map()) { if (node === null) return result; if (node.left === null && node.right === null) { result.set(node.char, code || "0"); return result; } this.generateCodes(node.left, code + "0", result); this.generateCodes(node.right, code + "1", result); return result; } formatResult(result) { const formattedResult = []; for (let [char, code] of result.entries()) { formattedResult.push([char, code]); } return formattedResult; } compress(str) { for (let char of str) { this.frequency.set(char, (this.frequency.get(char) || 0) + 1); } this.mergingNodes(); const result = this.generateCodes(); return this.formatResult(result); } } 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); HuffmanCoding의 가장 중심인 compress 메서드를 통해 매개변수로 받은 문자열을 압축하도록 코드를 작성하였다.compress는 4가지 단계를 통해 문자열을 압축한다.frequency 저장우선순위 큐를 활용하기 위해선 어떤 기준으로 우선순위를 할 것인지 정해야하며 허프만 알고리즘은 문자 빈도에 따라 압축 코드가 생성된다.매개변수로 받은 문자열 값을 반복문을 통해 각 문자를 순회하며 Map 의 key로 문자, value로 빈도 수를 저장해준다.힙 노드 병합mergingNodes 메서드가 힙 노드를 병합해주는 기능을 수행한다.문자 빈도가 저장된 frequency Map을 순회하며 우선순위에 따라 Heap에 저장해준다.허프만 알고리즘은 가장 빈도가 적은 두 문자를 병합한 노드를 생성하고 해당 노드의 자식으로 병합된 노드들을 이어준다.A {frequency: 1}, B {frequency: 2} 일 경우에는 Null { frequency: 3, left: A, right: B } 이런 노드를 만들어서 Heap에 삽입해준다.해당 작업은 while문을 통해 구현되기에 Heap 클래스에서 전체 힙의 사이즈를 알 수 있는 Heap.getSize() 메서드를 만들어주었다.return 1 + this.getSize(node.getLeftSubTree()) + this.getSize(node.getRightSubTree());모든 노드를 병합하여 허프만 알고리즘을 위한 트리 구조를 만들고 해당 트리의 root를 반환시켜준다.코드 생성반환된 트리 구조의 root부터 다시 순회를 해가면서 코드를 생성해주는 기능이다.해당 트리 구조의 노드는 '문자 노드'와 '병합 노드'로 분류되며 병합 노드는 우선순위가 문자 노드보다 높기 때문에 모든 문자 노드는 리프노드가 된다.코드와 문자를 저장할 result Map을 선언하고, 허프만 알고리즘에 따라 왼쪽 간선으로 이동하면 0을 오른쪽 간선으로 이동하면 1을 코드에 추가하며 재귀적으로 각 노드를 순회한다.마지막 리프노드(문자노드)에 다다르게 되면 해당 코드를 result에 저장하게 된다.출력 포매팅그렇게 출력된 result는 현재 Map 자료구조에 저장되어 있기 때문에 원하는 출력값으로 포매팅을 진행해주었다.출력값을 빈 배열로 선언해주고 Map을 순회하면서 key와 value를 하나의 배열에 저장하여 출력 배열에 다시 push해주었다. 후기기존에 배웠던 자료구조를 통해 직접 새로운 알고리즘을 공부하고 실제 구현까지 해볼 수 있는 뜻깊은 경험이었다. 분명 알고리즘을 구현하는 과정까지는 쉽지 않았지만 기존에 배웠던 자료구조를 한 번 더 복습할 수 있었고 세부적인 동작과정까지 한 번 천천히 돌아볼 수 있었던 계기가 되었다.역시 이론을 배우고 연습하는 것보다 뭔가 만들기 위해서 활용하고 그 과정에서 여러 시행착오들을 겪는 경험들이 해당 이론과 개념을 더 깊이 있게 이해하고 나아가 활용할 수 있는 기회를 다시 만들어낸다는 것을 다시 한 번 깨달을 수 있었다.

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

📕 자료구조와 알고리즘(심화)✅ 트라이와 자동완성📌 개념자동완성 기능을 구현할 수 있는 최적의 자료구조retrieval에서 유래되었다.이진트리는 아니라 자식 노드의 개수 제한이 없음저장하려는 단어를 한 글자씩 저장해서 key엔 글자, value에는 자식 노드를 저장한다.📌 성능해시테이블 검색 시간 복잡도 = O(1)트라이 시간 복잡도 = O(k) - 트라이에 저장된 노드 수에 따라 다름✅ 그래프📌 개념트리는 그래프의 종류 중 하나이다. 트리는 그래프이지만 그래프는 트리가 아니다.트리노드는 부모와 자식으로 계층적 구조를 가지며그래프에서 사이클이 없어야 한다.연결되지 않는 노드가 있으면 안된다.용어정점: 노드간선: 노드를 연결하는 선인접(adjacent): 간선으로 연결된 정점이웃(neighbor): 인접한 정점a와 b는 인접해있으며 a는 b의 이웃이며 b는 a의 이웃이다.방향 그래프: 양방향으로 간선의 방향이 정해져있음무방향 그래프: 간선의 방향이 없음 📌 깊이 우선 탐색 알고리즘(DFS)방문한 정점을 해시 테이블에 저장한다.사이클이 있는 경우 무한 루프에 걸릴 수 있음1. 현재 정점을 해시테이블에 방문한 정점으로 저장2. 현재 정점의 인접 정점들을 순회 (방문한 정점이라면 순회하지 않는다)3. 방문하지 않은 정점이면 재귀적으로 깊이 우선 탐색 수행📌 너비 우선 탐색 알고리즘(BFS)1. 방문한 정점을 저장하고 큐에 삽입2. 큐에 dequeue3. dequeue한 인접 정점을 순회한다1. 이미 방문한 정점이라면 건너뛰고2. 방문하지 않은 경우 첫 번째 경우 반복📌 DFS vs BFSDFS는 깊이를 우선 탐색BFS는 너비를 우선 탐색상황에 맞게 적절하게 사용하는 것친구 추천을 제공: 너비 우선 탐색 사용특정 지인을 찾는 경우: 깊이 우선 탐색 사용성능그래프의 성능은 정점 뿐만 아니라 간선에 따라서도 달라질 수 있다.O(V + E)V: 정점E: 간선 ✅ 가중 그래프📌 개념간선의 크기를 저장한다.- 크기는 사용자가 정하기 나름(정점 간의 거리나 비용이 될 수 있음)간선은 방향도 있으며 방향에 따라 가중치가 달리질 수도 있음 📌 다익스트라 알고리즘최적의 경로를 찾을 때 최적의 알고리즘1. shorted_path_table에 목표 정점과 거리를 초기화2. visited와 unvisited 배열로 구분3. unvisited에서 차례로 visited로 이동하면서 표 업데이트1. 인접도시의 거리들을 shorted_path_table에 저장하고2. 가까운 거리의 정점을 선택하여 visited로 이동3. 표의 값 + 인접 도시 거리 > 표의 값이면 표 수정 X ✅ 알고리즘📌 탐욕 알고리즘최적해를 구하는데 사용되는 근사적인 방법최적해를 구하는 보장은 없지만 단순하게 구할 수 있음매 선택지에서 가장 좋은 선택을 고름조건1. 탐욕스러운 선택 속성1. 앞의 선택이 이후의 선택에 영향을 주지 않음2. 최적 부분 구조 조건1. 문제에 대한 최적해는 부분에 대해서도 최적해이다=> '매트로이드' 📌 최소 신장 트리신장 트리그래프에 순환 구조없이 모든 정점이 연결되어 있음최소 신장 트리: 간선의 길이가 가장 짧은 신장 트리1. 크루스칼 알고리즘2. 프림 알고리즘1. 다익스트라 알고리즘과 비슷2. 최소 비용으로 연결3. 무방향 그래프에서 동작 📌 최대 유량 문제(Network Flow)용량이 다른 여러 상수관을 통해 Source에서 Sink까지 최대한 많은 양의 물을 보내는 문제1. 용량(Capacity): 한 상수관에 최대한 흐를 수 있는 물의 양2. 유량(Flow): 현재 상수관에 흐르고 있는 물의 양3. 잔여 용량 = 용량 - 유량탐색 알고리즘1. 포드 폴커슨 알고리즘: DFS1. Source에서 Sink로 가는 경로 하나를 DFS로 찾는다. (증가경로 찾긴)2. 증가 경로에 흐를 수 있는 최대 유량을 찾는다3. 찾은 증가 경로에서 보낼 수 있는 최대 유량을 흘린다.2. 에드몬드 카프 알고리즘: BFS📕 컴퓨터 구조✅ 제어장치📌 명령어제어장치: RAM에 저장된 데이터를 가져와 정해진 동작을 수행하는 장치이다.명령어, 데이터 모두 제어장치에 저장되어 있음.상위 4비트 명령어, 하위 4비트 데이터(주소, 값)📌 프로그램 카운터RAM에서 메모리 주소를 이동시키거나 원하는 주소로 바로 접근할 수 있게 해주는 장치다음 실행한 명령어의 주소를 가리킨다.JK Flip-Flop을 통해 메모리 주소 1씩 카운팅혹은 JUMP를 통해 원하는 주소로 바로 이동 📌 스탭 카운터명령어 인출, 해석 및 실행 단계를 카운팅해주는 장치후기이번 주차에서는 그래프와 다양한 알고리즘에 대해서 배웠다. 매일 알고리즘 문제를 풀면서 개념은 알지 못하였지만 dfs나 bfs 혹은 그래프 문제를 해결하면서 접한 풀이과정에 대해 익혀가면서 단순히 재귀적인 문제의 심화 과정이라고 생각을 하였지만 이번 과정에서 해당 개념에 대해 깊이 있게 배울 수 있었고 간단한 풀이 예시와 함께 공부하다보니 더 쉽게 체감해볼 수 있었다. 컴퓨터 구조에서는 지금까지 배웠던 개념들을 토대로 본격적인 CPU 를 간단하게 제작해볼 수 있는 실습이 진행되었다. 개념적인 내용은 실습을 진행하면서 깊이 있게 다루지는 못하였지만 실제 동작되는 과정을 보면서 CPU의 명령과 연산 하나하나가 어떻게 동작하는 지 확인해볼 수 있었다. 점점 다양한 입력 핀들과 동작들을 혼합하여 제작하니 점점 구조가 복잡해지고 이해하는 것이 어려워지긴 하였지만 복습과 미션을 통해서 더 깊이 있게 이해해보려고 한다.

[인프런 워밍업 클럽 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()); // 웹브라우저 프로세스 출력 풀이풀이 1Process 클래스와 생성자에 필요한 property들을 설정해주었다.PriorityQueue에 Heap 메서드인 isBigPriority를 오버라이드하여 필요한 함수로 작성해주었다.조건문을 통해 executionCount가 적은 프로세스 먼저 실행시키고(오름차순) 만약 executionCount가 동일하다면 cpuReturnCount가 높은 값부터 호출한다(내림차순)//mission.mjs import { PriorityQueue as CpuScheduler } from "./priorityQueue.mjs"; class Process { constructor(name, cpuReturnCount, executionCount) { this.name = name; this.cpuReturnCount = cpuReturnCount; this.executionCount = executionCount; } }//priorityQueue.mjs import { Heap } from "./heap.mjs"; export class PriorityQueue { constructor() { this.heap = new Heap(); // 첫 번째 우선순위, 두 번째 우선순위 비교 this.heap.isBigPriority = (first, second) => { if (first.executionCount === second.executionCount) { return first.cpuReturnCount > second.cpuReturnCount; } return first.executionCount 하지만 상위 문제 풀이에는 두 가지 문제점이 있다.첫 번째는 우선 순위의 추가가 불편하다는 점이다. 문제에서는 두 개의 우선순위만 주어졌기에 함수에 isBigPriority 함수에 조건문을 통해 작성하였지만 10개, 100개로 늘어갈 수록 함수의 조건문은 점점 길어져갈 것이다.두 번째는 우선순위의 변경이 불편하다는 점이다. 만약 문제와 반대로 executionCount와 cpuReturnCount의 우선순위가 바뀐다면 함수에서 조건문 전체를 변경해줘야 한다. 두 개의 우선순위를 변경하는 것도 귀찮은 일인데 만약 이 또한 100개가 되는 우선순위 순서를 변경해야한다면 오랜 시간이 걸릴 것이다. 풀이 2Process에서 첫 번째 우선순위 priority를 executionCount로 설정하고, 두 번째 우선순위 secondPriority를 cpuReturnCount를 선언하였다.PriorityQueue에서 Heap 클래스의 isBigPriority를 오버라이드하여 새로운 우선순위 함수로 정의해주었다.첫 번째 우선순위는 오름차순으로 설정하고 조건문을 통해 첫 우선순위가 동일할 경우, 두 번째 우선순위로 비교하여 내림차순으로 설정하였다.//mission.mjs import { PriorityQueue as CpuScheduler } from "./priorityQueue.mjs"; class Process { constructor(name, cpuReturnCount, executionCount) { this.name = name; this.cpuReturnCount = cpuReturnCount; this.executionCount = executionCount; // 첫 번째 우선순위 this.priority = executionCount; // 두 번째 우선순위 this.secondPriority = cpuReturnCount; } }//priorityQueue.mjs import { Heap } from "./heap.mjs"; export class PriorityQueue { constructor() { this.heap = new Heap(); // 1. 첫 번째 우선순위 오름차순 // 2. 두 번째 우선순위 내림차순 this.heap.isBigPriority = (first, second) => { if (first.priority === second.priority) { return first.secondPriority > second.secondPriority; } return first.priority 상위 풀이는 풀이 1의 두 번째 문제를 해결하였다. 각 우선순위의 대상이 되는 변수를 함수에 직접 구현한 것이 아닌 priority, secondPriority와 같이 우선 순위를 담는 변수를 따로 선언하여 함수에 구현하였기 때문에, 우선순위를 변경하려면 간단히 Process 클래스에서 property만 변경해주면 된다는 이점이 있다. 하지만 풀이 1의 첫 번째 문제는 아직 해결되지 못하였다. 여전히 priority가 10개, 100개로 늘어난다면 Process에 선언해야 할 property가 그만큼 늘어나게 될 것이다. 풀이 3우선순위 큐를 선언하기 전, Priority를 결정하는 rules 배열을 선언해주었다. rules에는 우선순위로 활용할 process 인스턴스의 property와 오름차순, 내림차순을 결정할 type으로 형성된 객체를 배열로 받는다.이 후, 우선순위 큐를 생성하면서 rules를 매개변수로 생성자에 넘겨주고 isBigPriority에서는 전달받은 각각의 rule들을 비교해가며 해당 property을 비교하여 type에 따라 정렬하게 된다.isBigPriority에서는 for 반복문을 돌다가 정렬할 수 있는 상태(값이 동일하지 않은 상태)에는 return을 통해 첫 번째 우선순위만 비교하여 정렬을 하고, 만약 첫 번째 우선순위에서 정렬을 할 수 없다면 다음 rule로 넘어가 비교를 하게된다.// mission.mjs import { PriorityQueue as CpuScheduler } from "./priorityQueue.mjs"; const rules = [ { property: "executionCount", type: "ASC" }, { property: "cpuReturnCount", type: "DESC" }, ]; class Process { constructor(name, cpuReturnCount, executionCount) { this.name = name; this.cpuReturnCount = cpuReturnCount; this.executionCount = executionCount; } } let cpuScheduler = new CpuScheduler(rules);//priorityQueue.mjs import { Heap } from "./heap.mjs"; export class PriorityQueue { constructor(rules) { this.heap = new Heap(); this.rules = rules; this.heap.isBigPriority = (first, second) => { for (const rule of this.rules) { const { property, type } = rule; if (type === "ASC") { if (first[property] second[property]) return false; } else { if (first[property] > second[property]) return true; if (first[property] 미리 rules라는 배열을 선언하여 해당 변수 안에서 우선순위를 선택할 property와 type을 관리해주면 Process 나 PriorityQueue에서는 우선 순위의 변경이 발생하여도 수정을 할 필요가 없어진다. 현재는 rules를 직접 하드코딩하여 관리해주고 있는데 에러처리나 동적으로 삽입해줄 수 있는 메서드를 활용해봐도 좋을 것 같다. 회고수강하면서 heap과 우선 순위큐를 직접 구현하고 이론을 설명들을 때는 이해가 되지 않는 부분이 많았는데, 이번 미션을 통해서 직접 어떤 상황에서 사용될 수 있는지 이해할 수 있었고 간접적으로 CPU의 우선순위를 구현해보면서 해당 자료구조의 이점을 몸소 체험할 수 있었다. 또한 문제를 풀면서 각각 내가 구현한 방식과 그에 대한 단점들을 발견하면서 이를 개선시키는 과정이 인상깊었던 것 같다.

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

문제다음 파일의 모든 연결을 터널로 대체해보세요.(회로 이미지와 .circ파일 첨부)8비트 32입력 MUX를 제작해보세요.(회로 이미지와 .circ파일 첨부)3. 10비트 입력 두 개(A, B)를 계산하는 ALU 만들어보세요.(회로 이미지와 .circ파일 첨부),32바이트 RAM을 만들어보세요. 디코더와 MUX는 logisim 기본 내장된 걸 사용해도 좋습니다.(회로 이미지와 .circ파일 첨부)후기어째서인지 맥북에서는 .circ 파일을 열 수가 없다. 연결할 응용프로그램을 logisim으로 연결할 수도 없고 logisim에서 파일을 찾아올 수가 없다.. 그래서 결국 새로운 logisim 파일을 열어서 기존 작업된 circ를 텍스트 파일로 열어서 해당 데이터를 새로운 circ 파일에 덮어써서 파일을 열어가며 작업했던 것 같다.. 그리고 가끔가다 작업했던 circuit 파일들도 사라져서 동일한 미션을 다시 만들기도 하였다 😃 그럼에도 여러번 만들면서 익숙해지다보니 확실히 강의에서만 듣고 이해하는 것보다 더 체감이 되는 것 같고 학습했던 내용에 대해 머리 속에 더 깊숙히 남아있는 것 같다. 특히 레지스터와 RAM과 같은 경우에는 어떤 역할을 하고 있는 지에 대해서만 알고 있었던 과거와는 달리, 직접 구현해보며 내부적으로 어떻게 동작하는 지 혹은 각각의 부품들이 어떤 관계를 갖고 있는 지 자세히 알 수 있어서 인상깊은 과제였다.

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

📕 자료구조와 알고리즘(심화)✅ Red-Black 트리AVL 트리는 균형을 엄격히 지키기 때문에 삽입, 제거는 느리지만 검색이 빠름Red-Black 트리는 균형에 대해 관대하여 삽입, 제거는 빠르지만 검색이 느림삽입 규칙1. 모든 노드는 빨간색이나 검은색 두 가지 색 중 하나이다2. 루트 노드는 항상 검은색이다3. 모든 터미널 노드(NIL)는 검정색이다4. 연속해서 빨간색 노드가 올 수 없다.1. 현재 노드가 빨간색이라면 부모, 자식은 빨간색일 수 없음5. 검은색은 연속으로 올 수 있다6. 루트 노드에서 터미널 노드인 NIL노드까지 모든 경로에는 같은 수의 검은색 노드가 있어야 한다. 높이1. 트리의 높이2. Black Height: 루트부터 NIL 노드까지 Black 노드의 수 삽입을 할 때 회전도 하지만 노드의 색도 다시 칠해준다. (recoloring)새로운 노드를 삷입할 때 무조건 빨간 색 노드를 칠한다.이 후 균형을 잡아주는 함수를 호출(rebalanceAfterInsertion 함수) 1. 새로운 노드가 루트노드인 경우1. 검정색으로 변경2. 부모노드와 삼촌노드가 빨간색인 경우1. 삼촌노드: 부모의 형제 노드2. 할아버지를 빨간색으로, 부모/삼촌 노드를 검정색으로 변경3. 규칙을 위반하지 않을 때까지 재귀적으로 상위로 올라감3. 부모는 빨간색, 삼촌은 검정색, 새로운 노드는 안쪽 손자인 경우1. 안쪽 손자: 할아버지, 부모, 자신이 삼각형을 이루는 노드 (RL)2. 부모 노드를 회전, 할아버지 노드는 반대 회전3. 새로 삽입된 노드는 검은색, 할아버지 노드는 빨간색으로 변경4. 부모 빨간색, 삼촌 검정색, 새로운 노드가 바깥쪽 손자인 경우1. 바깥쪽 손자: 할아버지, 부모, 자신이 일자를 이루는 노드(LL)2. 할아버지노드는 삽입 방향 반대로 회전3. 부모 노드는 검정, 할아버지 노드는 빨강으로 변경 제거 규칙1. 터미널 노드를 제거1. 제거할 노드의 두 자식 노드가 모두 NIL인 경우1. 해당 노드 제거 후 부모 노드를 NIL에 연결2. 제거할 노드의 자식 노드 중 하나가 NIL1. 해당 노드 제거 후 부모 노드에 나머지 노드 연결3. 제거할 노드의 자식노드에 NIL이 없음1. 왼쪽 자식 노드의 큰 값 혹은 오른쪽 자식 노드의 작은 값으로 대체2. 대체한 후 나머지 자식노드를 대체 노드의 자식으로 연결3. 제거한 노드가 빨간색인 경우에는 색 규칙이 올바름4. 검은색이라면 균형을 잡아야 함 균형을 잡는 방법1. 형제 노드가 빨간색인 경우1. 형제 노드의 색을 검정, 부모노드를 빨간색으로 변경2. 부모노드 왼쪽 회전, 부모노드를 검정색으로, 형제 노드를 빨간색으로 변경2. 형제노드와 형제노드의 자식노드들이 검은색이고 부모노드는 빨간색1. 형제 노드 빨간색, 부모 노드 검은색3. 형제노드와 형제노드의 자식노드, 부모 노드 모두 검정색1. 형제노드의 색을 빨간색으로 변경2. 부모노드에 대해 2번 규칙 적용4. 형제노드가 검은색, 형제 두 자식 노드 중 하나라도 빨간색 노드가 있고 바깥쪽 조카 노드가 검은 색인 경우1. 안쪽 조카는 검정, 형제 노드는 빨간색2. 형제 노드를 제거한 노드의 반대방향으로 회전3. 조카노드와 부모, 형제 노드 색 변경4. 부모 노드 제거 노드 반대방향으로 회전5. 형제 노드가 검은색이고 형제의 두 자식노드 중 하나라도 빨간색 노드가 있고 바깥쪽 조카가 빨간색인 경우1. 형제 노드를 부모 노드 색으로 변경2. 부모노드와 바깥쪽 조카 노드 색 변경3. 부모 노드를 제거된 노드의 방향으로 변경✅ 우선순위 큐와 힙개념큐: FIFO > 먼저 들어간 데이터가 먼저 나온다.우선순위 큐: 먼저 들어간 순서와 상관없이 우선순위에 따라 나온다.Enqueue: 삽입Dequeue: 삭제힙(heap): 완전 이진트리 - 최소 힙: 루트 노드가 가장 작은 값을 가지는 완전 이진 트리 - 최대 힙: 루트 노드가 가장 큰 값을 가지는 완전 이진 트리힙1. 삽입1. 마지막 노드로부터 부모 노드와 비교해가며 적절한 위치에 삽입2. 처음 삽입할 위치를 찾는 것은 어렵기 때문에 미리 마지막 삽입 노드 위치를 저장해둠2. 제거1. 마지막 삽입 노드를 루트 노드를 가져온 후, 자식 노드와 비교하면서 위치를 바꿈2. 마지막 삽입 노드의 위치를 마지막 이전에 삽입된 노드로 변경3. 성능: 삽입, 제거: O(log n) 새로 삽입될 위치 (`getInsertingParent`)1. 루트 노드인 경우1. 루트 노드의 왼쪽 자식으로 삽입2. 부모노드의 왼쪽 자식인 경우1. 오른쪽 형제, 부모 노드 오른쪽 자식으로 삽입3. 부모노드의 오른쪽 자식인 경우1. 부모노드의 오른쪽 형제 노드가 자식 노드를 가지는 경우1. 해당 형제 노드의 왼쪽 자식 노드로 내려감2. 오른쪽 형제 노드가 없는 경우1. 루트 노드부터 가장 왼쪽 노드로 내려감 힙 정렬최소 힙에서 dequeue를 하면 오름 차순 정렬최대 힙에서 dequeue를 하면 내림 차순 정렬성능: O(nlogn)📕 컴퓨터 구조✅ 하드웨어 만들기멀티플렉서: 여러 입력 중 하나를 선택하여 출력으로 내보내는 장치디멀티 플렉서: 하나의 입력을 여러 출력 중 하나로 내보내는 장치selection을 통해 선택입력 수에 따라 비트 수가 달라짐Selection이 가리키는 수에 따라서만 출력이 변경됨0 -> 0번1 -> 1번10 -> 2번선이 많이지기 때문에 터널을 통해 연결할 수 있다.디코더: n 비트의 입력을 2^n개의 출력 중 하나만 활성화하는 장치컨트롤 버퍼: 출력을 제어하는 장치 - 선을 끊어주는 역할을 한다.전압은 물리적으로 방해를 받을 수도 있기 때문에 출력을 제어할 수 있게 된다.✅ CPU 만들기반가산기1비트 두 개를 더할 때는 올림을 표현하는 carry와 합을 의미하는 sum 이 필요carry: AND 게이트sum: XOR> 1비트의 두 값만 더할 수 있기 때문에, 다비트 연산에서는 LSB 자리에만 쓰고, 나머지 자리에서는 전가산기를 써야 한다📌 전가산기전압은 물리적으로 방해를 받을 수도 있기 때문에 출력을 제어할 수 있게 된다.✅ 메모리조합 논리회로: 입력에 대해서만 출력하기 때문에 상태를 기억할 수 없음기본 게이트, 멀티플렉서, 디코더, 반가산기, 전가산기, ALU,,순차 논리회로(메모리 역할)출력을 다시 조합 논리회로의 입력으로 들어가야지 현재 상태를 만들어서 다음 상태를 결정시킬 수 있음SR LatchD latchJK latch클럭과 플리플롭여러 회로의 딜레이 차이로 인해 순차적으로 결과값이 출력되고 있다. -> 원하지 않는 출력을 받게된다.레지스터: 1비트 메모리 Latch를 연결해 여러 비트를 저장할 수 있는 메모리레지스터의 enable을 0으로 바꿔서 값이 다 처리될 때까지 기다렸다가 끝나면 enable을 1로 바꿔준다.클럭이 정해진 주기에 따라 enable을 직접 변경시켜준다.클럭이 1인 상태에서 출력 값이 계속 바뀔 수 있다는 문제가 있다.-> 트리거: 래치의 출력을 활성화하는 조건1. 레벨 트리거1. High Level: 입력이 1인 동안에만 반영2. Low Level: 입력이 0인 동안에만 반영2. 엣지 트리거1. Rising Edge: 0에서 1이 되었을 때 반영2. Falling Edge: 1에서 0이 되었을 때 반영-> 플리플롭: 래치 트리거를 엣지 트리거로 변경하는 것 레지스터데이터를 출력하고 LOAD를 통해 레지스터에 저장해두었다가 Enable을 통해 출력을 통제한다.8비트 레지스터 = 0~255까지 데이터 저장 가능CPU내부에 있어서 적은 메모리만 저장 RAM1비트 저장 - 래치 || 플립플롭8비트 저장 - 레지스터MSB를 포함한 4비트 = 명령어LSB를 포함한 4비트 = 메모리 주소메모리 주소는 0 ~ 15번까지 사용 가능RAM은 16개의 메모리 주소를 갖으며 하나의 메모리 주소는 8비트(1바이트)의 레지스터로 구성 => 16바이트 메모리-> 현대 컴퓨터는 최소 4GB의 램이다.address에서 주소를 받아서 디코더를 통해 출력된 값을 해당 메모리 주소에 연결해주면 각각의 레지스터에 값을 저장해둘 수 있다.레지스터의 출력을 멀티플레서에 연결하고 Enable을 통해 제어하면 값을 출력할 수 있다.후기Red-Black Tree나 우선순위 큐와 같은 이론이 한번에 이해가 되지 않았고 구현하는 과정이 익숙하지 않아서 이론과 함께 반복적으로 확인해보면서 구현을 거쳤던 것 같다. 반복적으로 개념을 익혀나가면서 구현하다보니 점점 어느정도 감이 잡히는 것 같다는 느낌이 들었고 미션을 통해 직접 과제를 구현하다보면 더 자료구조에 대해 가까워질 수 있을 것 같다.컴퓨터 구조를 만들어볼 수 있는 logisim 프로그램이 맥북에서는 설치가 안되거나 파일을 바로 열 수가 없어서 애 좀 먹었던 것 같다. 단축키를 몰라서 하나씩 조합을 하다보니 시간이 좀 걸렸지만 점점 강의를 따라하면서 이 또한 손에 점점 익어갔다.CPU에 들어가있는 레지스터라는 존재에 대해서만 알고 있었지만 레지스터가 어떻게 동작하는 지, 내부 회로가 어떤 식으로 연결되어있는 지 직접 구현해보면서 확인해보니 흥미로웠었고 RAM 또한 레지스터와 어떤 관계를 갖고 있는지 알 수 있어서 좋았던 것 같다.

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

문제1. 4입력 AND, OR, NAND, NOR, XOR 연산의 진리표를 작성해보세요.(3입력 AND게이트의 예)| A | B | C | D | AND | OR | NAND | NOR | XOR | | --- | --- | --- | --- | --- | --- | ---- | --- | --- | | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |AND: 모든 값이 1일 경우에만 1OR: 하나의 값이라도 1이면 1NAND: AND 반대NOR: OR 반대XOR: (((A ⊕ B) ⊕ C) ⊕ D) > 두 입력이 같으면 0, 다르면 1 2.다음 불 방정식들을 여러 방법을 이용해 간략화 해보세요.1. A( (BB)’+ 0A) + (CC)' = (AB’) +C ㄴ A( (B)’+ 0A) + (C)' : 동일 법칙 ㄴ A(B’) + (C)' : 항등원 ㄴ AB’ + C’ 2. (B’B’) + (AD’ + (CA)’)D = B’ + (DC’) + (DA’) ㄴ (B’) + (AD’ + (CA)’)D : 동일 법칙 ㄴ (B’) + (AD’ + C’+ A’)D : 드모르간 법칙 ㄴ B’ + DC’+ DA’: 항등원 3. (A’B) + B(B1 + BC) = B ㄴ (A’B) + B(B + BC): 항등원 ㄴ (A’B) + B(B) : 흡수법칙 ㄴ (A’B) + B: 동일법칙 ㄴ B(A’ + 1): 결합법칙 ㄴ B(1): 항등원 ㄴ B 4. B’(1C + BD) + DB = (B’C) + (DB) ㄴ B’(C + BD) + DB = 항등원 ㄴ B’C + B’BD + DB = 분배법칙 ㄴ B’C + DB = 보완법칙다음 2진수를 10진수로 변환해보세요.1. 110111 = 1 + 2 + 4 + 16 + 32 = 55 2. 10000001 = 1 + 128 = 129 3. 11111100000 = 32 + 64 + 128 +256 + 512 + 1024 = 2016 4. 101010 = 2 + 8 + 32 = 42다음 10진수를 2진수로 변환해보세요.1. 10 = 1010(2) - 10/2 = 5 ...0 - 5/2 = 2...1 - 2/2 = 1...0 - 1/2 = 0...1 2. 27 = 11011(2) - 27/2 = 13...1 - 13/2 = 6...1 - 6/2 = 3...0 - 3/2 = 1...1 - 1/2 = 0...1 3. 86 = 1010110(2) - 86/2 = 43...0 - 43/2 = 21...1 - 21/2 = 10...1 - 10/2 = 5...0 - 5/2 = 2...1 - 2/2 = 1...0 - 1/2= 0...1 4. 516 = 100000100(2) - 516/2 =258...0 - 258/2 = 129...0 - 129/2 = 64...1 - 64/2 = 32...0 - 32/2 = 16...0 - 16/2 = 8...0 - 8/2 = 4...0 - 4/2 = 2...0 - 2/2 = 1...0 - 1/2 = 0...1다음 불 방정식을 logisim을 이용해 회로를 만들어보세요.(회로 이미지와 .circ파일 첨부)1. (B’C) + (DB) 2. (AB’) +C 3. B’ + (DC’) + (DA’) 1. (B’C) + (DB)2. (AB’) +C3. B’ + (DC’) + (DA’)후기불 대수나 불 연산에 대해서 개념을 공부할 때는 크게 와닿지 못하였고 외우기 바빴지만 직접 미션을 통해서 작업해보고 불 대수에서 나온 여러 법칙들이 왜 사용되게 되는지 흐름을 이해할 수 있었다. 또한 직접 프로그램을 통해 회로를 연결해보는 경험이 불 연산을 더 깊이 체감해볼 수 있는 경험이 되었다.

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

문제Python, JavaScript, C# 같은 언어는 가비지 컬렉터를 이용해 메모리를 자동으로 정리하는 매니지드 언어(Managed Language)에 속합니다.매니지드 언어의 가비지 컬렉터는 개발자가 메모리를 요청하면 운영체제의 힙 영역에 할당하고, 더 이상 필요하지 않을 때 자동으로 해제하며 메모리를 관리합니다.여러분이 속한 회사에서 새로운 매니지드 언어를 개발 중이며, 여러분은 가비지 컬렉터 개발을 담당하게 되었습니다.특히 메모리 검색 부분을 맡게 되었는데, 사용자가 특정 크기(Byte)의 메모리를 요청하면 사용 가능한 메모리 중 가장 적절한 크기를 찾아 반환하는 GarbageCollector 클래스를 구현해보세요.(같은 크기의 메모리는 없다고 가정)import { AVLTree } from "./avlTree.mjs" class GabageCollector{ } const gc = new GabageCollector(); console.log("========== 빈 메모리 영역 초기화 =========="); gc.insertFreeMemory(64); // 빈 64바이트 삽입 gc.insertFreeMemory(48); // 빈 48바이트 삽입 gc.insertFreeMemory(87); // 빈 87바이트 삽입 gc.insertFreeMemory(13); // 빈 13바이트 삽입 gc.insertFreeMemory(102); // 빈 102바이트 삽입 gc.insertFreeMemory(34); // 빈 34바이트 삽입 gc.insertFreeMemory(61); // 빈 61바이트 삽입 gc.insertFreeMemory(40); // 빈 40바이트 삽입 gc.insertFreeMemory(6); // 빈 6바이트 삽입 let freeMemory1 = gc.searchFreeMemory(64); // 64바이트 메모리 console.log(freeMemory1); if(freeMemory1){ gc.releaseFreeMemory(freeMemory1.data); } let freeMemory2 = gc.searchFreeMemory(42); // 48바이트 메모리 획득 console.log(freeMemory2); if(freeMemory2){ gc.releaseFreeMemory(freeMemory2.data); } 풀이import { AVLTree } from "./avlTree.mjs"; class GabageCollector { constructor() { this.tree = new AVLTree(); } // 노드 추가 insertFreeMemory(data) { this.tree.root = this.tree.insert(this.tree.root, data); } // 가장 인근의 노드 찾기 searchFreeMemory(data) { if (this.tree.root === null) { return null; } let currentNode = this.tree.root; let parentNode = null; while (currentNode !== null) { // 현재 노드가 찾고자 하는 데이터보다 작을 경우 오른쪽 서브트리로 이동 if (currentNode.getData() 문제에서는 총 세 가지 메서드를 구현하여야 했다.insertFreeMemory: 빈 메모리를 삽입할 수 있는 기능searchFreeMemory: 데이터를 할당할 수 있는 최소의 메모리 공간을 검색하는 기능3. releaseFreeMemory: 해당 메모리를 삭제할 수 있는 기능우선적으로 GarbaceCollector에서 메모리 영역은 하나의 AVL 트리로 다뤄진다고 생각을 하여서 this.tree 속성으로 AVL 트리를 생성해주었다. insertFreeMemory의 경우, AVL Tree에서 제공해주는 insert 메서드를 통해 트리의 root를 설정해주고 그 하위에 적절한 위치를 찾아서 각 노드를 삽입해주었다. releaseFreeMemory의 경우, 동일하게 AVL Tree에서 제공하는 remove 메서드를 통해 데이터를 찾아가며 해당 노드를 삭제하고 각 노드의 height나 unbalance한 노드의 균형을 잡아주었다. searchFreeMemory는 새롭게 기능을 추가하여야 하였다. 처음에는 단순하게 매개변수의 데이터 값과 일치하는 노드만 반환하면 될 줄 알았지만 문제에서 '사용 가능한 메모리 중 가장 적절한 크기' 를 반환해야 한다고 적혀있듯 매개변수로 받는 데이터 이상의 노드들 중 최소값을 가진 노드를 반환해야 했다.메서드를 작성하기 전에 먼저 예외처리를 하였다.AVL Tree의 루트 노드가 없을 경우매개변수로 받는 데이터가 모든 노드의 값보다 클 경우두 가지 경우에는 null을 반환하고 "매모리를 추가할 수 없습니다."라고 로그를 찍어주었다.그 외의 경우에는 이제 while문을 통해 가장 인접한 값의 노드로 이동을 시켜주었다.만약 현재 위치한 노드의 값이 찾으려는 데이터보다 작다면 우측 서브트리로 이동해주고,데이터보다 큰 노드를 발견하게 된다면 부모 노드를 미리 저장해주고 좌측 서브트리로 이동해주었다.부모노드를 저장해주는 이유는 좌측 서브트리의 노드를 데이터보다 작을 수도 있기에 반환해줄 수 있는 노드 변수를 만들어주었다.그렇게 while 문을 반복하다보면 현재 위치의 노드가 null이 나오게 되고 기저 조건을 벗어나서 결국 부모 노드에 저장된 노드값이 사용 가능한 메모리 중 가장 적절한 크기가 되며 부모 노드가 null이라면 아까처리한 예외 조건에 의해 로그가 찍히게 된다. 저번 기수보다 더 어려운 문제를 미션으로 출제하신다는 코치님의 말씀에 겁을 먹었었지만 막상 이렇게 실용적인 예제와 직접 구현을 해보면서 미션을 진행하다보니 기존에 배웠던 AVL Tree에 대해 더 자세히 익히게 되고 동작 방식이나 해당 자료구조에 대한 특징을 몸소 체험해볼 수 있었던 것 같다.

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

📕 자료구조와 알고리즘(심화)✅ P-NP문제가 어려운 지, 쉬운 지 혹은 해결이 가능한 지 불가한 지 판단하는 것.결정 문제: 참 혹은 거짓을 대답할 수 있는 문제최적화 문제: 최적의 해를 찾을 수 있는 문제 (대부분의 최적화 문제는 결정 문제가 된다)결정론적 튜링 머신: 다음 상태가 유일한(오직 하나의) 상태로 결정되는 것비결정론적 튜링 머신: 현재 상태와 기호에 대해 여러 개의 가능한 다음 상태가 존재할 수 있는 것 (현실에는 존재 X 가정으로 상상)다항 시간: 어떤 문제의 해결 시간을 다항식으로 표현이 가능한 것다항 시간 내 1. 상수 시간: O(1) 2. 로그 시간: O(log n) 3. 선형 시간: O(n) 4. 로그-선형 시간: O(nlog n) 5. 다항 시간: O(n^k) 다항 시간 외 1. 지수 시간: O(k^n) 2. 팩토리얼 시간: O(n!) P 문제: 결정문제에 대해 결정론적 튜링 머신을 통해 다항 시간 내에 답을 구할 수 있는 문제NP 문제: 결정문제에 대해 비결정론적 튜링 머신을 사용하여 다항 시간 내에 답을 구할 수 있는 문제NP Hard: 모든 NP문제들을 다항 시간 내에 어떤 문제 A로 환원이 가능한 것NP Complete: NP-Hard이면서 NP에 포함되는 문제결정론적 / 비결정론적 문제ex) 완전 이진 트리 형태로 되어 있고 깊이가 k인 갈림길에 하나의 리프에만 보물이 있다고 가정결정론적: 한 번씩 모든 길을 거쳐서 보물을 확인 > 최악의 경우 2^k의 시간이 걸린다.비결정론적: 갈림길을 마주할 때마다 분신술을 사용하여 동시에 모든 리프 확인 > k의 시간이 걸린다.어떠한 힌트가 주어지게 된다면 비결정론적 문제들은 결정론적 문제로 검증이 가능모든 결정론적 문제들은 비결정론적 문제들에 속함 (P⊆NP) ✅ 트리와 이진 트리트리: 하나의 노드에서 점차 내려가는 자료구조Edge: 각 노드를 연결하는 선루트 노드: 트리에서 최상위 노드터미널 노드: 자식 노드가 없는 노드인터널 노드: 터미널 노드를 제외한 노드서브 트리: 트리 구조 내에 작은 트리 (터미널 노드 또한 루트 노드만 있는 트리라고 판단)레벨: 각트리의 높이이진 트리: 각 노드는 최대 2개의 자식 노드를 갖는 트리포화 이진 트리: 트리의 최대 레벨에 있는 모든 터미널 노드가 꽉 찬 트리완전 이진 트리: 최대 레벨을 제외한 나머지 레벨에는 모두 노드가 존재하고 최대 레벨의 노드는 왼쪽부터 채워진 트리순회: 트리의 노드들을 순회전위: 루트 노드 먼저 순회중위: 루트 노드를 중간에 순회후위: 루트 노드를 마지막에 순회 ✅ 이진 탐색 트리이진 탐색 알고리즘: 정렬되어 있는 배열에서 반씩 나눠 탐색을 해가며 범위를 줄여나가는 알고리즘이진 탐색 트리이진 탐색은 정렬된 상태에서만 가능하며 배열의 경우 데이터 삽입, 삭제가 비효율적이다.해시 테이블은 데이터 조회, 삽입, 제거가 빠르지만 해시 함수에 따라 성능이 달라지고 데이터를 저장할 메모리가 필요하다.이진 탐색 테이블은 데이터 조회, 삽입, 제거가 빠르고 해시 테이블에 비해 메모리 사용량이 적다규칙자식 노드는 모두 이진 트리여야 한다.중복된 노드의 데이터는 없어야 한다.A 노드의 왼쪽 자식 노드값은 A 노드값보다 작아야 한다.A 노드의 오른쪽 자식 노드값은 A 노드값보다 커야 한다.자식 트리도 상위 규칙을 따라야 한다.평가:트리가 만들어졌을 때 : O(logn)트리가 잘 만들어지지 않을 때 : O(n)이진 트리는 균형을 유지하는 것이 성능에 중요삽입, 삭제 시 트리의 균형이 깨질 가능성이 크다.✅ AVL 트리이진 트리에서는 균형을 유지하는 것이 중요하다.규칙:왼쪽과 오른쪽 자식트리의 높이가 최대 1까지만 차이가 날 수 있다.균형이 맞지 않는 트리는 회전을 통해 균형을 다시 맞출 수 있다.(못 맞추는 경우도 존재)회전LL회전: 오른쪽으로 뻗은 트리에 대해 적용 가능RR회전: 왼쪽으로 뻗은 트리에 대해 적용 가능LR회전: 왼쪽으로 꺾였다가 안쪽으로 꺾인 트리 적용 가능RL회전: 오른쪽으로 꺾였다가 안쪽으로 꺾인 트리 적용 가능📕 컴퓨터 구조✅ 컴퓨터 구조블랙박스: 내부 작동 원리는 모르더라도 입력에 따라 출력이 예측 가능한 것들모듈화: 큰 문제를 작은 문제로 분할하여 복잡함을 단순화 시키는 방법역사:수동식 계산기- 주판기계식 계산기- 계산봉, 파스칼린, 라이프니츠 휠자동 계산기- 차분 기관(톱니바퀴로 계산 결과 활용), 해석 기관(프로그래밍 가능)디지털 계산기- ENIAC- 폰노이만 구조(중앙 처리 장치, 메모리, 입출력 장치)- 트랜지스터 (진공관 대체)- 집척 회로- ,,, 동작방식컴퓨터는 0,1로 이루어진 명령어만 해석이 가능하다.기계어: 0,1로 이루어진 명령어컴파일러: 정적 코드를 기계어로 변환하는 과정에서 에러 발견 가능하고 실행속도가 매우 빠름 (c, C++) / 변환 과정이 오래 걸림인터프리터: 한 줄씩 기계어로 변환하기에 프로그램 실행 도중 문법 오류 발생 가능, 실행 속도가 느림✅ 컴퓨터 구성 요소CPU:프로그램 카운터: 다음 실행할 명령어 저장제어 유닛: 명령어 해석 및 실행산술 논리 연산장치: 산술, 논리 연산을 수행레지스터: 용량은 적지만 속도가 빠른 CPU 내장 메모리버스: 데이터 전송 통로Memory:RAM(Random Access Memory): 어떤 메모리에 접근하여도 접근 시간이 동일하며 휘발성ROM(Read Only Memory): 쓰기가 불가하며 비휘발성이기 때문에 컴퓨터 동작을 위한 BIOS가 저장 1. CPU가 프로그램 실행 시, 코드와 데이터를 RAM에서 가져온다. 2. 연산에 필요한 데이터 레지스터 저장 3. 연산 이후 결과를 RAM에 저장 4. 자주 사용되는 데이터 CPU 내부에 캐시 메모리 저장 ( RAM) 주변 장치:입출력 장치1. 키보드 / 마우스2. 모니터 / 스피커 / 프린터보조기억 장치1. HDD / SSD32, 64bit 컴퓨터:1bit (0,1 표현) = 21byte = 8bit = 2564byte = 32bit = 약 42억8byte = 64bit = 약 18경플리플롭: 1비트를 저장할 수 있는 회로컴퓨터 비트에 맞춰서 레지스터와 버스의 비트 수가 맞춰짐- 64비트 -> 64비트 레지스터 / 64개의 버스비트 수에 따라 저장할 수 있는, 계산할 수 있는 한계가 정해짐RAM이 여러개를 갖고 있더라도 CPU에서 처리할 수 있는 한계가 있음컴퓨터의 성능은 클럭, 명령어 최적화, 메모리, 레지스터 속도가 중요✅ 불 대수디지털 장치들은 불 대수 기반으로 작동한다.true: 1false: 0 불 연산:NOT: 입력값의 반대AND: A와 B가 같을 때만 1 (논리곱)OR: A와 B중 하나만 1이면 1 (논리합)NAND: AND 연산의 반대NOR: 하나라도 1이면 1XOR: 하나만 1일 경우에만 1 (두 입력이 다를 때)불 대수의 성질과 법칙항등원:원산 결과가 자기 자신이 되는 수AND (⋅) / A ⋅ 1 = AOR (+) / A + 0 = A교환법칙: 피연산자의 순서를 바꿔도 결과는 동일하다A ⋅ B = B ⋅ A결합법칙: 괄호의 위치를 바꿔도 결과 동일(A ⋅ B) ⋅ C = A ⋅ (B ⋅ C)분배법칙A ⋅ (B + C) = A⋅B + A⋅C동일법칙: 동일한 값을 두 번 연산해도 원래 값A ⋅ A = A이중 부정법칙: 두 번 부정하면 원래 값으로 돌아감흡수법칙A(A + B)= AA + AB ← 분배법칙= A + AB ← AA = A (동일법칙)= A(1 + B). ← A로 묶음 (결합법칙의 역)= A(1) ← 1 + B = 1 (항등원)= A 드모르간 법칙AND = NOT A OR NOT BA NOR B = NOT A AND NOT B불 함수함수: 입력 값에 따라 출력 값이 변하는 것불함수: 입력 값과 출력 값 모두 boolean 진리표 변환결과가 0인 행은 제외(Don't care 행)모든 행을 AND 연산으로 만들고결과값에 맞춰서 수정✅ 비트10진법과 2진법1개의 비트로 표현할 수 있는 수의 개수 = 2^1개2개의 비트로 표현할 수 있는 수의 개수 = 2^2개3개의 비트로 표현할 수 있는 수의 개수 = 2^3개,,, 10진법 > 2진법 변환10진수를 2로 나눌 수 있을 때까지 나누는 것ex) 9 > 9/2 = 4...1 > 4/2 > 2...0 > 2/2 > 1...09(10) = 1001(2) 16진법0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F16진법을 사용하는 이유는 2진수를 10진법으로 표현하는 것보다 더 간단하기 때문16은 2^4이기 때문에 간단히 변환 가능11111111(2) = FF(16)Ox1001 => 16진수 표기법 빅 엔디안과 리틀 엔디안MSB: 가장 왼쪽 비트LSB: 가장 오른쪽 비트 빅 엔디안: MSB를 가장 낮은 주소부터 채우는 방식리틀 엔디안: LSB를 가장 낮은 주소부터 채우는 방식하나의 방식으로 통일해서 사용해야 함. 오버플로우와 인터럽트오버플로우: 값이 데이터 타입(또는 레지스터)이 표현할 수 있는 범위를 초과했을 때 발생하는 현상인터럽트: CPU가 실행 중인 작업을 중단하고 인터럽트 서비스를 실행 음수- 부호없는 정수 (양수만 표현 가능)0000 ~ 1111 = 0 ~ 15까지 16개 값 표현- 부호있는 정수 (양수, 음수 표현 가능)0000 ~ 1111 = -8 ~ 7까지 16개 값 표현MSB가 부호를 표현(0이면 양수, 1이면 음수) > 나머지 3비트로만 값 표현 가능예: +5 → 00000101 (8비트 기준)음수 표현 만들기 (예: -5)① 비트를 반전 (1의 보수): 11111010② +1 더함: 11111010 + 1 = 11111011 00000101 ( +5 ) + 11111011 ( -5 ) ----------- 00000000 → 결과: 0 후기직접 프로그램을 통해 불 연산을 시각화해볼 수 있다는 것이 가장 인상깊었다. 기존에는 논리 연산을 통해서 조건문을 작성할 때를 제외하고는 생각해본 적이 없었는데, 더 하위 레벨에서 불대수, 불함수, 그리고 불 연산에서 자주 사용되는 수학적인 법칙까지 직접 공부해보고 이를 통해 간단한 프로그램을 만들어 보는 경험이 어렵지 않으면서 가장 크게 체감을 할 수 있었던 것 같다. 자료구조와 알고리즘 또한 트리가 나오게된 배경부터 AVL 트리가 탄생하게 된 계기까지 그 흐름을 잘 따라갈 수 있었고 AVL 트리만의 특징과 균형을 잡기 위한 여러 회전 원리에 대해서도 탄탄히 공부해볼 수 있었다.

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

지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.버블정렬인접한 두 수를 비교하여 차례대로 자리를 바꿔나가며 정렬하는 방식시간복잡도: O(n^2)선택정렬선택된 정렬 영역에 정렬되지 않은 영역의 최솟값을 삽입시간복잡도: O(n^2)삽입정렬정렬되지 않은 영역의 첫 원소를 정렬된 원소들과 비교하여 올바른 위치에 삽입시간복잡도: O(n^2)병합정렬배열을 더 이상 나눌 수 없을 때까지 쪼개고(분할)다시 정렬된 상태로 병합(정복)재귀를 통해서 구현이 가능시간 복잡도 O(nlogn)퀵정렬배열 중 하나를 pivot으로 설정하고배열의 시작과 끝에서부터 pivot과 비교해가며 좌, 우로 정렬하고두 인덱스가 교차되면 pivot을 교차점이랑 교체재귀를 통해서 반복시간 복잡도 O(nlogn) - 최악의 경우 O(n^2)하지만 최악의 경우가 나올 확률이 거의 없고, 병합정렬보다 메모리 사용이 적기 때문에 더 좋은 알고리즘이라고 판단메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.메모리제이션이란 알고리즘 계산 과정에서 동일한 계산이 반복되어 실행되는 경우, 함수를 실행해가며 계산 값을 저장해두고 동일한 계산 실행 시 저장된 결과 값을 불러오며 계산하는 방식을 의미한다. 이 방법은 하향식 계산을 하며 중복되는 계산을 제거할 수 있기에 연산 속도는 빠르고 하향식 접근 문제에 대해 빠르게 풀이할 수 있다는 장점이 있지만 계산에 필요한 결과를 저장해두어야 함으로 메모리의 사용량이 크다는 단점이 있다.타뷸레이션은 상향식 계산 방식으로 모든 값을 자료구조에 저장해두고 계산에 필요한 결과 값을 불러오며 계산하는 방식을 의미한다. 반복적인 함수 호출이 없기 때문에 메모리에 큰 부담이 없으며 상향식 접근이 필요한 문제에 사용될 수 있다는 장점이 있지만 미리 모든 연산을 진행하여 저장해야 하기 때문에 불필요한 연산이 발생할 수 있다는 단점이 있다.'메모리가 부족한' 시스템에서 '재귀로 쉽게' 구현이 가능한 상황에서 문제를 해결하기 위해서는 타뷸레이션을 사용할 것 같다. 메모이제이션은 재귀로 쉽게 구현이 가능한 문제에 대해 이점을 발휘하지만 메모리의 사용이 크다는 단점으로 인해, 결국 메모리가 부족한 시스템에서 구현이 완료되어도 실행이 안된다면 의미가 없다고 판단하였다. 반면 타뷸레이션은 재귀로 문제를 푸는 것에 이점은 없지만 쉽지 않더라도 재귀가 아닌 상향식으로 문제를 접근하여 풀이할 수 있을 것이라고 생각한다. 📒 회고 미션을 통해서 강의를 통해서 공부했던 내용들을 전체적으로 복습해볼 수 있었으며 이번에도 실무적인 환경에서 실제로 고민해볼만한 주제를 받고 이에 대해 생각해볼 수 있는 시간을 가져서 좋았다. 아직 기초 수준의 자료구조와 알고리즘에 대해서 공부를 하였지만 꾸준히 문제를 풀어가면서 심화 알고리즘에 접근하며 실력을 키워나가고 싶다.