inflearn logo
강의

강의
N
챌린지

챌린지
멘토링

멘토링
N
클립

클립
로드맵

로드맵
지식공유

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

suover
1

image

image

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

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

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

3주차 발자국 입니다.

학습 내용 요약

자료구조·알고리즘

컴퓨터 구조

미션

🎯 자료구조·알고리즘 미션3: 허프만 코딩 구현

class Node {
  constructor(char = null, freq = 0, left = null, right = null) {
    this.char  = char;
    this.freq  = freq;
    this.left  = left;
    this.right = right;
  }
}

class HuffmanCoding {
  compress(str) {
    if (!str) return [];

    // 빈도 계산
    const freqMap = new Map();
    for (const ch of str) {
      freqMap.set(ch, (freqMap.get(ch) || 0) + 1);
    }

    // 초기 노드 리스트 생성
    const nodes = [];
    for (const [ch, f] of freqMap.entries()) {
      nodes.push(new Node(ch, f));
    }

    // 허프만 트리 구성
    while (nodes.length > 1) {
      nodes.sort((a, b) => a.freq - b.freq);
      const a = nodes.shift();
      const b = nodes.shift();
      nodes.push(new Node(null, a.freq + b.freq, a, b));
    }
    const root = nodes[0];

    // 코드 생성
    const codes = {};
    const build = (node, prefix) => {
      if (node.char !== null) {
        codes[node.char] = prefix || "0";
      } else {
        build(node.left,  prefix + "0");
        build(node.right, prefix + "1");
      }
    };
    build(root, "");

    // [문자, 코드] 쌍 배열 반환
    return Object.entries(codes);
  }
}

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.";
const result = huffmanCoding.compress(str);
console.log(result);
// 결과
[
  [ 'i', '000' ],      [ 'q', '001000' ],
  [ 'v', '001001' ],   [ 'o', '00101' ],
  [ 'l', '0011' ],     [ 'd', '01000' ],
  [ 'E', '0100100' ],  [ 'g', '0100101' ],
  [ 'x', '0100110' ],  [ 'P', '0100111' ],
  [ 'a', '0101' ],     [ 'e', '011' ],
  [ 'm', '10000' ],    [ 'r', '10001' ],
  [ 'u', '1001' ],     [ 't', '1010' ],
  [ 'p', '10110' ],    [ 'L', '10111000' ],
  [ 'C', '10111001' ], [ 'f', '10111010' ],
  [ 'b', '10111011' ], [ '.', '101111' ],
  [ ' ', '110' ],      [ 's', '1110' ],
  [ 'c', '11110' ],    [ 'n', '11111' ]
]

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

🎯 컴퓨터 구조 미션3: STOREB 명령어와 A·B 비교 어셈블리어 구현

LOADA 14   // A = RAM[14]
SUB 15     // A -= RAM[15]
JMPC 5     // CF = 1 → A ≥ B일 때 5번 주소로 점프
LOADI 2    // A < B → 결과 2
JMP 9      // 결과 출력으로 점프
JMPZ 8     // ZF = 1 → A = B일 때 8번 주소로 점프
LOADI 1    // A > B → 결과 1
JMP 9      // 결과 출력으로 점프
LOADI 0    // A = B → 결과 0
OUT        // 결과 출력
HLT        // 프로그램 종료
0
0
0
7          // A값
3          // B값

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

회고

잘한 점

아쉬웠던 점 & 보완

마치며

이번 주차에는 Trie, 그래프, 다익스트라 학습을 진행하고, 제어 장치 명령어 확장과 허프만 코딩 구현 미션을 병행하며 이론과 실습을 모두 경험했습니다. 단계별 실습을 통해 개념이 실제 코드나 회로로 연결되는 과정을 체감했고, 디버깅과 테스트 습관을 강화할 수 있었습니다. 다음주에는 추가 알고리즘 학습을 통해 더욱 탄탄한 이해를 쌓아가겠습니다. 감사합니다!

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

답변 0