[워밍업클럽4기-CS] 발자국 2

자료구조와 알고리즘Red-Black treeAVL 트리와 같은 자가 균형 이진 트리, AVL 트리 보다는 덜 엄격한 균형노드는 빨강(Red) 또는 검정(Black)루트 노드와 모든 터미널 노드(NIL)는 검정빨간 노드는 연속할 수 없음 어떤 노드에서 NIL까지 도달할 때의 black-height는 동일함컴퓨터 구조하드웨어 시뮬레이터를 활용한 ALU 구현8비트 2,4,8,16 입력 MUX각각 앞단계의 MUX를 활용해 만들 수 있음디코더, 컨트롤버퍼 구현반가산기, 전가산기 구현 회고연휴를 활용해서 진도에 집중할 계획이었는데, 여러 일정으로 생각보다 시간을 할애하지 못했던 점이 아쉽다.연휴가 끝난만큼 차주부터는 원래의 흐름을 회복할 필요가 있을 것 같다.

[워밍업클럽4기-CS] 미션1 - 자료구조와 알고리즘

문제Python, JavaScript, C# 같은 언어는 가비지 컬렉터를 이용해 메모리를 자동으로 정리하는 매니지드 언어(Managed Language)에 속합니다. 매니지드 언어의 가비지 컬렉터는 개발자가 메모리를 요청하면 운영체제의 힙 영역에 할당하고, 더 이상 필요하지 않을 때 자동으로 해제하며 메모리를 관리합니다. 여러분이 속한 회사에서 새로운 매니지드 언어를 개발 중이며, 여러분은 가비지 컬렉터 개발을 담당하게 되었습니다. 특히 메모리 검색 부분을 맡게 되었는데, 사용자가 특정 크기(Byte)의 메모리를 요청하면 사용 가능한 메모리 중 가장 적절한 크기를 찾아 반환하는 GarbageCollector 클래스를 구현해보세요.(같은 크기의 메모리는 없다고 가정)풀이추상 자료형 정의빈 메모리 삽입 : insertFreeMemory적당한 크기의 메모리 검색 : searchFreeMemory'적당한' 크기? : 요청된 사이즈보다 같거나 크면서 요청 사이즈와의 차이가 가장 적은 값사용될 빈 메모리 제거 : releaseFreeMemoryinsertFreeMemorygc에 새로운 노드 삽입 후 변환된 root 정보 반환searchFreeMemory변수 선언currentNode : 현재 노드 정보freeMemory : 반환될 메모리 사이즈에 해당하는 노드 검색(while)요청 사이즈와 동일한 사이즈의 메모리 존재 : freeMemory를 해당 노드로 업데이트 후 break요청 사이즈보다 현재 노드의 메모리 사이즈가 더 큰 경우 freeMemory != null이고, freeMemory가 현재 노드보다 더 작다면 대치 하지 않고 왼쪽 서브 트리 검색freeMemory가 null이거나 현재 노드보다 더 크다면 freeMemory를 현재 노드로 대치 후 왼쪽 서브 트리 검색요청 사이즈보다 현재 노드의 메모리 사이즈가 더 작은 경우 : freeMemory를 대치하지 않고 오른쪽 서브 트리 검색최종 freeMemory 값 반환releaseFreeMemory사용할 사이즈에 해당하는 노드를 제거구현 코드 import { AVLTree } from "./avlTree.mjs" // 추상 자료형 // 빈 메모리 삽입 : insertFreeMemory // 적당한 크기의 메모리 검색 : searchFreeMemory // 사용될 빈 메모리 제거 : releaseFreeMemory class GabageCollector{ constructor(){ this.avlTree = new AVLTree(); } // 빈 메모리 삽입 insertFreeMemory(size){ this.avlTree.root = this.avlTree.insert(this.avlTree.root, size); } // 적당한 크기의 메모리 검색 searchFreeMemory(size){ let currentNode = this.avlTree.root; let freeMemory = null; while(currentNode != null){ if(currentNode.getData() == size){ // 딱 맞는 사이즈인 경우 freeMemory = currentNode; break; } else if(currentNode.getData() > size){ // 요청 사이즈보다 더 큰 경우 if(freeMemory && freeMemory.getData 실행 결과========== 빈 메모리 영역 초기화 ========== 6 13 34 40 48 61 64 87 102 freeMemory 64 BinaryTree { data: 64, leftSubTree: BinaryTree { data: 34, leftSubTree: BinaryTree { data: 13, leftSubTree: [BinaryTree], rightSubTree: null, height: 2 }, rightSubTree: BinaryTree { data: 48, leftSubTree: [BinaryTree], rightSubTree: [BinaryTree], height: 2 }, height: 3 }, rightSubTree: BinaryTree { data: 87, leftSubTree: null, rightSubTree: BinaryTree { data: 102, leftSubTree: null, rightSubTree: null, height: 1 }, height: 2 }, height: 4 } freeMemory 48 BinaryTree { data: 48, leftSubTree: BinaryTree { data: 40, leftSubTree: null, rightSubTree: null, height: 1 }, rightSubTree: null, height: 2 }

[워밍업클럽4기-CS] 미션 1 - 컴퓨터구조

4입력 AND, OR, NAND, NOR, XOR 연산의 진리표를 작성해보세요. # 4 input AND # 네 입력 모두 1이어야 1 A B C D Q 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 0 0 1 1 1 1 1# 4 input NAND # Not AND A B C D Q 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0# 4 input OR # 네 입력 중 하나라도 1이면 1 A B C D Q 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1# 4 input NOR # Not OR A B C D Q 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 0 0 1 1 1 1 0# 4 input XOR # 입력 중 1의 수가 홀수이면 1, 짝수이면 0 A B C D Q 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0다음 불 방정식들을 여러 방법을 이용해 간략화 해보세요. a. A( (BB)’+ 0A) + (CC)' = (AB’) +C # 좌변 A((BB)'+ 0) + (CC)' // 0 and A = 0 A((BB)') + (CC)' // 덧셈의 항등원 0 A(B)' + (C)' // A and A = A AB' + C' # 우변 AB' + C # 결론 C' != C 이므로 좌변과 우변이 같지 않음b. (B’B’) + (AD’ + (CA)’)D = B’ + (DC’) + (DA’) # 좌변 B' + (AD'+(CA)')D // A and A = A B' + AD'D + (CA)'D // 분배 법칙 B' + (CA)'D // A and notA = 0 B' + (C'+A')D // 드 모르간의 법칙 B' + C'D + A'D // 분배 법칙 # 우변 B' + DC' + DA' B' + C'D + A'D // 교환 법칙 # 결론 좌변 = 우변 = B' + C'D + A'Dc. (A’B) + B(B1 + BC) = B # 좌변 (A'B) + B(B + BC) // 곱셈의 항등원 1 A'B + BB + BBC // 분배 법칙 A'B + B + BC // A and A = A A'B + 1B + CB // 곱셈의 항등원 1, 교환 법칙 (A' + 1 + C)B // 결합 법칙 B // A or 1 = 1 # 우변 B # 결론 좌변 = 우변 = Bd. B’(1C + BD) + DB = (B’C) + (DB) # 좌변 B'C + B'BD + DB // 분배 법칙, 곱셈의 항등원 1 B'C + DB // A and notA = 0 # 우변 (B'C) + (DB) # 결론 좌변 = 우변 = B'C + DB 3. 다음 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 => 32 + 8 + 2 = 424. 다음 10진수를 2진수로 변환해보세요.1. 10 = 8 + 2 => 1000 + 10 = 1010 2. 27 = 16 + 8 + 2 + 1 => 10000 + 1000 + 10 + 1 = 11011 3. 86 = 64 + 16 + 4 + 2 => 1000000 + 10000 + 100 + 10 = 1010110 4. 516 = 512 + 4 => 1000000000 + 100 = 10000001005. 다음 불 방정식을 logisim을 이용해 회로를 만들어보세요.(회로 이미지와 .circ파일 첨부)1. (B’C) + (DB) 2. (AB’) +C 3. B’ + (DC’) + (DA’)a. (B’C) + (DB)b. (AB’) +Cc. B’ + (DC’) + (DA’)파일 첨부회로 파일(mission1-5.circ)

[워밍업클럽4기-CS] 발자국 1

자료구조와 알고리즘 P-NP 개념P: 결정론적 튜링기계로 다항시간 내 풀수 있는 문제 NP: 비결정론적 튜링기계로 다항시간 내 풀수 있는 문제NP-complete : 다른 NP문제를 환원한 결과인 NP 문제NP-hard : 비결정론적 튜링기계로도 다항시간 내 풀 수 있음이 증명되지 않은 문제P=NP가 증명된다면 존재하는 모든 문제는 결정론적 튜링기계로 해결 가능하다.이진 트리자식 노드를 최대 두 개만 가지는 트리 자료구조모든 자식노드가 2개라면 포화 이진 트리, 왼쪽부터 채워진다면 완전 이진 트리이진탐색트리이진 트리 중 각 서브트리의 루트가 왼쪽 자식노드 보다는 크고 오른쪽 자식노드 보다는 작은 트리균형을 보장하지 않으므로 최악의 경우 탐색에 O(n) 소요AVL트리삽입,제거로 인해 균형이 깨질 경우 회전을 통해 스스로 균형을 맞추는 트리컴퓨터 구조개요 - 블랙박스, 컴퓨터의 역사, 프로그램 동작 원리블랙박스 : 인풋에 따른 아웃풋은 예상 가능하나, 내부 동작 원리는 이해할 수 없음 -> 모듈화에 활용CPU / 메모리 / 주변장치 / bit접근속도 : 하드디스크 저장용량 : 하드디스크 > RAM/ROM > 캐시메모리 > 레지스터불 대수 / 진리표1(true)/0(false)를 활용한 대수 연산진리표 : 불 대수 연산의 결과표하드웨어 시뮬레이터를 활용한 게이트 구현 회고인강 수강에 출퇴근 시간 활용이 생각보다 더 효율적임을 알게되었다. 인강 수강과 별개로 금주는 개인 일정 등으로 저녁에 복습을 위해 가진 시간이 많지 않았던 점이 아쉽다.출퇴근 시간에 수강할 수 있는 인강의 양이 예상보다 더 많음을 확인했으니 차주는 출퇴근 시간 활용으로 벌어둔 저녁 시간을 더 활용하면 좋을 것 같다.