inflearn logo
강의

강의
N
챌린지

챌린지
멘토링

멘토링
N
클립

클립
로드맵

로드맵
지식공유

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

suover
1

image

image

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

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

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

2주차 발자국 입니다.

학습 내용 요약

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

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

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

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

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

미션

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

목표

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

  1. 실행 횟수(executionCount)가 가장 작은 프로세스가 우선순위가 높다.

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

구현 개요

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

  2. 비교 함수 재정의

    // 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;
};

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

  4. 테스트 결과

    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까지

미션 구성

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

  2. 8비트 32입력 MUX 제작

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

  4. 32바이트 RAM 구현

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

image

2) 8비트 32입력 MUX 제작

image

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

image

4) 32바이트 RAM 구현

image

 

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

회고

잘한 점

아쉬웠던 점 & 보완

마치며

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

알고리즘 · 자료구조 인프런 워밍업클럽 스터디 CS 전공지식 자료구조 컴퓨터구조 발자국 회고 4기

답변 0