인프런 워밍업 클럽 스터디 4기 - CS 전공지식 1주차 발자국
강의와 함께한 인프런 워밍업 클럽 스터디 4기 - CS 전공지식 (자료구조, 알고리즘, 컴퓨터구조)
1주차 발자국 입니다.
학습 내용 요약
이번 주에는 두 가지 강의를 통해 자료구조·알고리즘과 컴퓨터 구조의 큰 틀을 살펴보며, 이론과 실습을 병행했습니다.
그림으로 쉽게 배우는 자료구조와 알고리즘 (심화편)
크게 트리 구조와 이진 탐색 트리(BST), 그리고 그 위에 균형을 더한 AVL 트리를 다뤘습니다.
초반에는 "트리와 이진 트리 개념"으로 부모·자식 노드 간 관계를 복습했고, 이어서 BST의 삽입·검색·삭제 과정을 훑어보았습니다.
마지막으로 AVL 트리 개념과 구현(보조 함수, 삽입, 삭제)을 익히며, "왜 균형 인자가 중요한지"와 "삽입/삭제 후 어떻게 회전으로 높이를 조정하는지"를 이해했습니다.
만들면서 쉽게 배우는 컴퓨터 구조
컴퓨터 구조 전반(블랙박스 관점, CPU·메모리·주변 장치)과 함께, 불 대수 및 논리 게이트 설계로 넘어가 간단한 하드웨어 시뮬레이션을 해보았습니다.
먼저 "컴퓨터 구조를 배우는 이유"와 명령어가 메모리→CPU→다시 메모리로 흐르는 과정을 개념적으로 파악했고, CPU 내부와 메모리 계층도 간단히 살펴봤습니다.
이어서 불 대수 기본 연산과 성질을 학습한 뒤, 직접 Logisim을 설치해 NAND/NOT/AND/OR/XOR 게이트를 조합해 보는 실습을 경험했습니다.
또 10진수↔2진수 변환, 16진법, 빅·리틀 엔디안, 2의 보수 음수 표현 같은 비트 단위 개념을 짚으며, 디지털 회로의 밑바탕이 되는 이진 표현 방식을 정리했습니다.
미션
🎯 자료구조·알고리즘 미션1: GarbageCollector 클래스 구현
목표: AVL 트리로 빈 메모리 블록을 관리해, 요청 크기와 정확히 일치하는 블록이나 그보다 큰 값 중 최소값을 찾아 반환·삭제하도록 한다.
코드
import { AVLTree } from "../../avlTree/avlTree.mjs"; class GabageCollector { constructor() { this.avlTree = new AVLTree(); } // 빈 메모리 블록 삽입 insertFreeMemory(size) { this.avlTree.root = this.avlTree.insert(this.avlTree.root, size); } // 요청 크기 이상인 블록 검색 searchFreeMemory(requestSize) { let current = this.avlTree.root; let candidate = null; while (current) { const nodeSize = current.getData(); if (nodeSize === requestSize) { // 정확히 같은 크기를 찾으면 즉시 반환 candidate = current; break; } if (nodeSize > requestSize) { // 후보로 저장한 뒤, 더 작은 후보를 찾기 위해 왼쪽 서브트리 탐색 candidate = current; current = current.getLeftSubTree(); } else { current = current.getRightSubTree(); } } return candidate; } // 반환된 블록(크기) 삭제 releaseFreeMemory(size) { this.avlTree.root = this.avlTree.remove(this.avlTree.root, size); } } // 실행 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); }실행 요약
const gc = new GarbageCollector();빈 블록
[64, 48, 87, 13, 102, 34, 61, 40, 6]을insertFreeMemory(...)로 순차 삽입searchFreeMemory(64)→ 정확히 64 노드를 찾아 반환 →releaseFreeMemory(64)삭제searchFreeMemory(42)→ 42와 동일한 값이 없어 “42보다 큰 값 중 최소(48)” 반환 →releaseFreeMemory(48)삭제
회고
AVL 트리의 삽입·삭제 시 "LL·RR·LR·RL 회전"이 실제로 동작하는 것을 확인하며, 균형 인자의 중요성을 체감했습니다.
삽입, 삭제, 검색이 모두 로그 시간에 동작하기 때문에, 빈 메모리 블록이 많아질 때도 성능을 보장할 수 있다는 점을 체감했습니다.
"정확히 같은 크기가 없을 때, 그보다 큰 값 중 최소값을 찾는 후보(candidate)" 로직을 루트부터 내려가며 올바르게 업데이트해야 합니다.
🎯 컴퓨터 구조 미션1 (총 5개)
미션 1. 4입력 논리 연산 진리표 작성
내용: 4개의 입력(A, B, C, D)에 대한 AND, OR, NAND, NOR, XOR 진리표를 총 16조합으로 작성
실행
A B C D를
0000 → 0001 → … → 1111순서로 나열각 연산(AND, OR, NAND, NOR, XOR)의 출력(Q)을 직접 채워 넣음
느낀 점
2진수 순서대로 입력 조합을 정리하니 빠짐없이 작성할 수 있었고, XOR처럼 "1 개수 홀짝 판정" 연산은 중간에 헷갈려도 정리 순서를 엄수하면 실수를 줄일 수 있었다.
미션 2. 불 방정식 간략화
내용: 아래 네 개의 불 방정식을 단계별로 법칙(아이디엠포턴트, 드모르간, 흡수 등)을 적용해 간략화했다.
A( (BB)’ + 0A) + (CC)’ = (AB’) + C’(B’B’) + (AD’ + (CA)’)D = B’ + (DC’) + (DA’)(A’B) + B(B1 + BC) = BB’(1C + BD) + DB = (B’C) + (DB)
느낀 점
드모르간·흡수법칙을 차례로 적용하며 "복잡해 보이던 식이 단번에 간결해지는 과정"이 인상적이었다.
단계별로 어떤 법칙을 먼저 적용해야 가장 효율적으로 축약되는지 아직 직관이 부족해, 다음주엔 다양한 예제를 풀어 보며 연습할 예정이다.
미션 3. 2진수를 10진수로 변환
내용: 다음 네 개의 2진수를 10진수로 바꿔 보았다.
110111₂ = 55₁₀ 10000001₂ = 129₁₀ 11111100000₂ = 2016₁₀ 101010₂ = 42₁₀실행
각 2진수를 우측 끝 비트부터 자리값(2⁰, 2¹, 2², …)을 곱해 합산
예:
11111100000₂ = 1·2¹⁰ + 1·2⁹ + … + 1·2⁵ + 0·… = 1024 + 512 + 256 + 128 + 64 + 32 = 2016
느낀 점
자릿값을 일일이 계산하는 것은 번거롭지만, "가장 큰 2의 거듭제곱부터 차례로 빼 나가는 방식"으로 익히니 긴 이진수도 비교적 빠르게 변환할 수 있었다.
미션 4. 10진수를 2진수로 변환
내용: 다음 네 개의 10진수를 2진수로 바꿔 보았다.
10₁₀ = 1010₂ 27₁₀ = 11011₂ 86₁₀ = 1010110₂ 516₁₀ = 1000000100₂실행
나눗셈→나머지 반복: 예를 들어
86 ÷ 2 = 43, 나머지 0→43 ÷ 2 = 21, 나머지 1→ … → 최종 이진수 역순또는 "가장 큰 2의 거듭제곱(2⁶=64)부터 빼 나가기" 방식으로 빠르게 도출
느낀 점
처음엔 헷갈렸지만, "2ⁿ 이하 최대값을 찾아서 빼고, 나머지로 또 반복"하는 방식이 머릿속에 각인되자 더 긴 수도 금방 변환할 수 있었다.
미션 5. 불 방정식을 Logisim으로 회로 구현
내용: 불 방정식을 logisim을 이용해 회로 만들기
실행
(B′·C) + (D·B)B → NOT → B′
AND1: (B′, C)
AND2: (D, B)
OR: (AND1, AND2) → 출력
(A·B′) + CB → NOT → B′
AND: (A, B′)
OR: (AND, C) → 출력
B′ + (D·C′) + (D·A′)B → NOT → B′ (첫 OR 입력)
C → NOT → C′, A → NOT → A′
AND1: (D, C′)
AND2: (D, A′)
OR( B′, AND1, AND2 ) → 출력
대표 입력별 검증
(B′·C)+(D·B)→ B=0,C=1,D=0 → OUT=1, B=1,C=0,D=1 → OUT=1, B=1,C=1,D=0 → OUT=0(A·B′)+C→ A=0,B=0,C=1 → OUT=1, A=1,B=1,C=0 → OUT=0B′+(D·C′)+(D·A′)→ A=0,B=0,C=0,D=0 → OUT=1, A=1,B=1,C=0,D=1 → OUT=1
느낀 점
Logisim을 통해 "진리표상의 연산이 실제 게이트 단위 회로에서 어떻게 동작하는지"를 직접 눈으로 확인할 수 있었다.
회로가 복잡해질수록 배선이 겹치는 문제가 있었으나, 다음에는 모듈 단위(예:
(B′·C)회로 →(D·B)회로 → OR)로 나눠서 단계별로 검증하려 한다.
회고
이번 주에는 AVL 트리와 논리 회로 설계를 함께 학습했습니다.
AVL 트리 구현: 삽입·삭제 시 LL·RR·LR·RL 회전을 거쳐 균형을 유지하는 과정을 직접 코드로 확인했습니다. "정확히 같은 값이 없으면 그보다 큰 값 중 최소값을 찾는 로직"을 구현하면서, 균형 인자를 어떻게 업데이트해야 하는지 확실히 알게 되었습니다.
논리 회로 설계: 4입력 진리표 작성부터 불 방정식 간략화, Logisim 회로 구성까지 순서대로 진행했습니다. 직접 회로를 만들어 입력을 바꿔 볼 때마다 결과가 즉시 바뀌는 모습을 보면서, 이론이 실제 게이트 동작으로 이어진다는 점이 와닿았습니다.
스스로 칭찬하는 점
이론과 실습 병행
AVL 트리 코드와 Logisim 회로를 동시에 구현하며, 배운 내용을 손으로 직접 확인한 점이 좋았습니다.
진리표 정리법 습득
2진수 순서대로 진리표를 빠짐없이 작성하면서, 체계적인 정리 방법을 제대로 익혔습니다.
아쉬웠던 점 & 보완
회로 배선 정리 부족
Logisim에서 선이 겹치다 보니 가끔 헷갈렸습니다.
→ 다음에는 작은 모듈로 나눠 단계별로 검증하고, 마지막에 합치는 방식을 사용하겠습니다.개념 정리 자료 부족
AVL 트리나 불 대수 법칙을 공부할 때, 머릿속으로만 이해하고 따로 요약해 두지 않아 복습할 때 헷갈리는 부분이 있었습니다.
→ 학습 중에는 핵심 개념을 노트에 간단히 정리하여, 부족한 부분을 바로 찾아볼 수 있도록 하겠습니다.
마치며
이번 주차는 이론을 코드와 회로로 연결해 보는 경험을 했습니다. 다음 주에도 부족했던 부분을 보완하며 차근차근 학습을 이어가겠습니다! 감사합니다!
답변 0