인프런 워밍업 클럽 스터디 4기 - CS 전공지식 3주차 발자국
그림으로 쉽게 배우는 자료구조와 알고리즘 (심화편)만들면서 쉽게 배우는 컴퓨터 구조강의와 함께한 인프런 워밍업 클럽 스터디 4기 - CS 전공지식 (자료구조, 알고리즘, 컴퓨터구조)3주차 발자국 입니다.학습 내용 요약자료구조·알고리즘트라이(Trie)와 자동완성개념: 문자열 집합을 효율적으로 저장·탐색하기 위해, 각 노드가 문자 하나를 나타내며 공통 접두사를 공유하는 트리 구조입니다.학습: 삽입 및 탐색 로직의 흐름을 개념적으로 이해하였습니다.인사이트: 삽입·탐색이 문자열 길이에 비례하기 때문에, 대규모 단어 집합에서 접두사 검색이 빠르지만 메모리 사용이 커질 수 있음을 감안해야 함을 체감했습니다.그래프개념: 그래프는 정점과 간선으로 관계를 표현하는 자료구조로, 방향 여부나 가중치 유무에 따라 다르게 다루며 인접 리스트와 인접 행렬 방식으로 표현할 수 있습니다.학습: 간단한 예제 그래프를 구성해 보고, DFS는 재귀나 스택으로 깊이 우선 탐색하며 방문 체크로 순환을 막고, BFS는 큐로 레벨별 탐색해 비가중치 최단 경로에 유리함을 코드로 확인했습니다.인사이트: DFS는 깊이 탐색이 필요할 때, BFS는 단계별 탐색이 필요할 때 유용하며, 그래프 표현 방식도 데이터 크기와 목적에 맞춰 결정해야 한다는 점을 깨달았습니다.가중 그래프와 다익스트라 알고리즘개념: 가중치가 있는 그래프에서 시작 정점으로부터 다른 정점까지 최단 경로를 찾는 문제입니다.다익스트라 알고리즘원리: 현재까지 알려진 최단 거리 후보 정점을 선택해 인접 간선을 완화(relaxation)하며 거리 배열을 갱신합니다.인사이트: 그래프가 커질수록 일반 방식은 느려지고, 우선순위 큐(힙)를 쓰면 더 빠르게 최단 경로를 구할 수 있음을 느꼈습니다.컴퓨터 구조제어 장치 없는 컴퓨터 & 조립CPU 주요 구성 요소(CPU 레지스터, ALU, 프로그램 카운터, 스텝 카운터)를 복습하고, 실습을 통해 신호 흐름을 이해했습니다.CPU 만들기: 제어 장치(Control Unit)명령어 처리 흐름: 명령어 인출(fetch), 디코딩, 실행(execute) 단계의 제어 신호 타이밍을 확인했습니다.주요 명령어: NOP, LOADA, ADD, SUB, STOREA, LOADI, JMP/JMPC/JMPZ, OUT, HLT 등의 제어 신호와 ALU·레지스터·메모리 동작 방식을 이해했습니다. 제어 장치 조립: Logisim에서 각 단계별 신호를 조합해 제어 유닛을 완성하고, 시뮬레이션으로 신호 흐름과 분기 동작을 확인했습니다.미션🎯 자료구조·알고리즘 미션3: 허프만 코딩 구현목표주어진 문자열에 대해 HuffmanCoding.compress(str)를 호출했을 때, [ [문자, 코드], … ]형태의 배열을 출력하도록 허프만 코딩을 구현합니다.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);흐름 및 구현 요약빈도 계산문자열을 순회해 Map 또는 객체에 문자별 등장 빈도를 집계했습니다.코드 생성재귀 탐색으로 왼쪽 자식은 '0', 오른쪽 자식은 '1'을 prefix에 추가하며 리프에서 코드 할당. 단일 문자 입력 시 빈 prefix에 "0" 처리 로직도 반영했습니다.검증실행 결과에서 빈도가 높은 문자는 짧은 코드, 낮은 문자는 긴 코드가 할당되는지 확인했습니다.빈도와 코드 길이 관계가 적절한지, 모든 문자가 포함되었는지, 코드끼리 충돌이 없는지 점검했습니다. // 결과 [ [ '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 비교 어셈블리어 구현목표STOREB 명령어(OPcode 1001)를 추가해 레지스터 B의 값을 메모리 주소에 저장하도록 구현합니다.A와 B 값을 비교해 같으면 0, A>B면 1, A<B면 2를 출력 레지스터에 내보내는 어셈블리어를 작성하고 검증합니다.구현STOREB(1001) 명령어 추가기존 STOREA 처리 경로를 참고하여 opcode 1001 분기 로직을 제어 장치에 추가했습니다.스텝 카운터가 각 단계에 진입할 때, STOREB 신호와 연관된 핀들이 의도한 타이밍에 활성화되는지 확인했습니다.A·B 비교 어셈블리어메모리에 저장된 A와 B 값을 불러와 비교하는 순서LOADA addrA → SUB addrB (A = A - B, 플래그 설정)JMPC 분기로 A≥B 처리, 아닐 경우 LOADI 2로 A<B 결과 세팅 후 출력분기한 경우 ZF 검사: ZF=1일 때 A=B(LOADI 0), ZF=0일 때 A>B(LOADI 1)이후 OUT, HLT로 마무리주소 라벨 매핑과 분기 주소 계산을 꼼꼼히 검토했습니다.Logisim에서 다양한 A·B 조합 테스트를 통해 출력 레지스터가 기대값(0/1/2)을 잘 내보내는지 확인했습니다.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 블로그 링크회고잘한 점단계적 접근: 컴퓨터 구조와 알고리즘 미션을 작은 단위로 나눠 핵심 로직과 흐름을 차근차근 구현하고 검증했습니다.디버깅 습관 강화: Logisim 시뮬레이션과 코드 실행 결과를 반복 확인하며, 문제 발생 시 신호 흐름이나 분기 주소 동작을 빠르게 점검했습니다.이론·실습 병행: 트라이, 그래프, 다익스트라 개념 학습 뒤 직접 구현 연습, 제어 유닛 명령어 설계 뒤 Logisim 실습, 허프만 코딩 이론 뒤 코드 작성으로 이론과 실습을 잘 연결했습니다. 아쉬웠던 점 & 보완테스트 부족 : 테스트가 부족해 다양한 상황을 확인하지 못했습니다. 다음에는 다양한 입력과 경계값을 더 많이 시도해 보겠습니다.성능 최적화 부족: 성능 최적화 연습이 부족했습니다. 시간이 된다면 구현했던 자료구조와 알고리즘을 재작성해보고, 다양한 시도를 통해 실행 시간을 비교해 보겠습니다. 마치며이번 주차에는 Trie, 그래프, 다익스트라 학습을 진행하고, 제어 장치 명령어 확장과 허프만 코딩 구현 미션을 병행하며 이론과 실습을 모두 경험했습니다. 단계별 실습을 통해 개념이 실제 코드나 회로로 연결되는 과정을 체감했고, 디버깅과 테스트 습관을 강화할 수 있었습니다. 다음주에는 추가 알고리즘 학습을 통해 더욱 탄탄한 이해를 쌓아가겠습니다. 감사합니다!
