인프런 워밍업 클럽 스터디 4기 - CS 전공지식 2주차 발자국

suover 2개월 전

그림으로 쉽게 배우는 자료구조와 알고리즘 (심화편)

만들면서 쉽게 배우는 컴퓨터 구조

강의와 함께한 인프런 워밍업 클럽 스터디 4기 - CS 전공지식 (자료구조, 알고리즘, 컴퓨터구조)

2주차 발자국 입니다.

학습 내용 요약

그림으로 쉽게 배우는 자료구조와 알고리즘 (심화편)

이번 주에는 균형 이진 탐색 트리의 대표 주자인 Red-Black 트리의 삽입·삭제 개념과 실제 구현을 다뤘습니다.

개념(삽입/제거) 단계에서 색상 규칙과 회전을 통해 균형을 유지하는 원리를 학습했고
보조 함수(색 변경, 회전 함수), 삽입 로직, 삭제 로직을 차례로 완성하며, 각 단계마다 균형 인자가 올바르게 갱신되는지 확인했습니다.

이어 우선순위 큐와 힙을 학습했습니다.

힙(Heap) 의 개념과 완전 이진 트리 구조를 이해하고, 힙 삽입, 힙 제거 과정을 직접 구현해 보았습니다.
이를 기반으로 미션에서 CpuScheduler 를 만들어, 실행 횟수 우선 & I/O 바운드 우선 정책을 Heap 비교 함수를 수정해 적용했으며
마지막으로 힙 정렬(Heapsort) 알고리즘까지 학습했습니다.

만들면서 쉽게 배우는 컴퓨터 구조

지난주 불 대수·진리표·Logisim 기초를 다진 뒤, 이번 주에는

MUX: 1비트 2입력부터 8비트 16입력까지 다양한 MUX 설계
디코더: 3비트·4비트 디코더 설계
컨트롤 버퍼(Buffer) 이해
ALU: 반 가산기·전 가산기·ALU 제작
메모리: SR/D/JK 래치, 플립플롭, 레지스터, RAM 구현
까지 확장하며, 각 모듈을 직접 구현하고 테스트하며 신호 흐름을 검증했습니다.

미션

🎯 미션1. 자료구조와 알고리즘 미션: CPU 스케줄링

목표

프로세스의 executionCount(실행 횟수)와 cpuReturnCount(I/O 바운드 횟수)로 우선순위를 매기는 스케줄러 구현

실행 횟수(executionCount)가 가장 작은 프로세스가 우선순위가 높다.
실행 횟수가 같을 경우, I/O Bound 프로세스(cpuReturnCount가 큰 프로세스) 가 우선순위가 높다.

구현 개요

자료구조: 완전 이진 트리 기반의 Heap 활용

비교 함수 재정의

// CpuScheduler 생성자 내부
this.heap.isBigPriority = (first, second) => {
  if (first.executionCount !== second.executionCount) {
    // 실행 횟수가 적은 프로세스가 우선
    return first.executionCount < second.executionCount;
  }
  // 실행 횟수가 같다면 I/O Bound 정도(cpuReturnCount)가 큰 쪽이 우선
  return first.cpuReturnCount > second.cpuReturnCount;
};

CpuScheduler 클래스

import { Heap } from "../../heap/heap.mjs";

class Process {
  constructor(name, cpuReturnCount, executionCount) {
    this.name = name;
    this.cpuReturnCount = cpuReturnCount;
    this.executionCount = executionCount;
  }
}

class CpuScheduler {
  constructor() {
    this.heap = new Heap();
    this.heap.isBigPriority = (first, second) => {
      if (first.executionCount !== second.executionCount) {
        return first.executionCount < second.executionCount;
      }
      return first.cpuReturnCount > second.cpuReturnCount;
    };
  }

  enqueue(process) {
    this.heap.insert(process);
  }

  dequeue() {
    const node = this.heap.remove();
    return node ? node.getData() : null;
  }
}

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()); // 웹브라우저 프로세스 출력

테스트 결과

Process { name: '수치계산프로그램', cpuReturnCount: 4,  executionCount: 0  }
Process { name: '터미널2',        cpuReturnCount: 93, executionCount: 2  }
Process { name: '터미널1',        cpuReturnCount: 34, executionCount: 2  }
Process { name: '뮤직플레이어',    cpuReturnCount: 11, executionCount: 10 }
Process { name: '웹브라우저',      cpuReturnCount: 27, executionCount: 25 }

O(log N) 삽입·삭제 성능으로 대규모 프로세스 관리 가능
비교 함수만 바꿔 다양한 스케줄링 정책 가능

🔗 자료구조·알고리즘 미션2 블로그 링크

🎯 미션2. 컴퓨터 구조 미션: 터널 연결부터 32바이트 RAM까지

미션 구성

모든 회로 연결을 터널(Tunnel)로 대체
8비트 32입력 MUX 제작
10비트 입력 두 개(A, B)를 계산하는 ALU 설계
32바이트 RAM 구현

1) 모든 회로 연결을 터널(Tunnel)로 대체

목표: Logisim의 Tunnel 컴포넌트를 사용해 복잡한 선 숨기기
결과: 캔버스가 한눈에 들어오고, 라벨만으로 신호 흐름 파악 가능

2) 8비트 32입력 MUX 제작

목표: IN_0…IN_31 중 하나 선택하여 출력
구현: Logisim 내장 32-to-1 MUX + 8비트 버스
검증: SELECTION 값 변화 시 기대 출력 확인

3) 10비트 입력 두 개(A, B)를 계산하는 ALU 설계

목표: 덧셈(SU=0)/뺄셈(SU=1), Carry-in/Carry-out, Zero Flag
구현:
- 10개 Full Adder 체인
- B 입력 XOR + SU → 뺄셈 지원
- 마지막 Adder의 Carry-out → CF, 출력 전 비트 OR·NOT → ZF
검증: 다양한 A, B 조합 테스트, CF/ZF 정상 동작

4) 32바이트 RAM 구현

목표: 5비트 주소 + 8비트 데이터 입·출력, ENABLE_WRITE, ENABLE_OUT
구현:
- 5→32 디코더 + AND → 각 레지스터 Load
- 읽기 MUX로 선택 출력
검증: WRITE=1 시 해당 워드에 저장, OUT=1 시 올바른 데이터 읽기

🔗 컴퓨터 구조 미션2 블로그 링크

회고

잘한 점

단계적 학습
- Red-Black 트리 개념 → 보조 함수 → 삽입 → 삭제까지 차근차근 구현하며 균형 유지 원리를 확실히 체득했습니다.
- 힙 기반 스케줄러와 힙 정렬, 다양한 크기의 MUX·디코더 구현으로 자료구조·회로 설계 감각을 크게 확장했어요.
모듈화 & 재사용성
- Heap 비교 함수만 바꿔 다양한 스케줄링 정책을 손쉽게 실험했고, Logisim 터널·버퍼 적용으로 회로 블록을 깔끔하게 재사용할 수 있었습니다.
플래그·메모리 회로 반복 학습
- 반·전 가산기, Zero/Carry Flag, 래치·플립플롭, 레지스터 파일, RAM까지 차례로 구현하며 신호 흐름과 제어 신호 이해가 깊어졌습니다.

아쉬웠던 점 & 보완

테스트 케이스 부족
- Red-Black 트리 삭제의 예외 케이스를 더 다양하게 검증하지 못했습니다.
- 힙 스케줄러에도 executionCount·cpuReturnCount 동률 시나리오를 추가할 필요가 있습니다.
시간 관리
- 다양한 모듈 구현에 몰두하느라 후반부 학습이 빠듯했습니다.

마치며

이번 주차에도 "작게 쪼개고 하나씩 검증하는" 학습 방식을 통해, 알고리즘과 회로 설계 모두에서 자신감을 많이 얻었습니다.
다음 주에는 부족했던 것들을 보완해, 더 탄탄한 결과물을 만들어 보겠습니다. 감사합니다!