블로그

최신순
인기순
좋아요순

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

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

인프런 워밍업 클럽 스터디 4기 - CS 전공지식 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 동률 시나리오를 추가할 필요가 있습니다.시간 관리다양한 모듈 구현에 몰두하느라 후반부 학습이 빠듯했습니다. 마치며이번 주차에도 "작게 쪼개고 하나씩 검증하는" 학습 방식을 통해, 알고리즘과 회로 설계 모두에서 자신감을 많이 얻었습니다.다음 주에는 부족했던 것들을 보완해, 더 탄탄한 결과물을 만들어 보겠습니다. 감사합니다!

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

인프런 워밍업 클럽 스터디 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 블로그 링크🎯 컴퓨터 구조 미션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) = B B’(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)로 나눠서 단계별로 검증하려 한다. 🔗컴퓨터 구조 미션1 블로그 링크회고이번 주에는 AVL 트리와 논리 회로 설계를 함께 학습했습니다.AVL 트리 구현: 삽입·삭제 시 LL·RR·LR·RL 회전을 거쳐 균형을 유지하는 과정을 직접 코드로 확인했습니다. "정확히 같은 값이 없으면 그보다 큰 값 중 최소값을 찾는 로직"을 구현하면서, 균형 인자를 어떻게 업데이트해야 하는지 확실히 알게 되었습니다.논리 회로 설계: 4입력 진리표 작성부터 불 방정식 간략화, Logisim 회로 구성까지 순서대로 진행했습니다. 직접 회로를 만들어 입력을 바꿔 볼 때마다 결과가 즉시 바뀌는 모습을 보면서, 이론이 실제 게이트 동작으로 이어진다는 점이 와닿았습니다.스스로 칭찬하는 점이론과 실습 병행AVL 트리 코드와 Logisim 회로를 동시에 구현하며, 배운 내용을 손으로 직접 확인한 점이 좋았습니다.진리표 정리법 습득2진수 순서대로 진리표를 빠짐없이 작성하면서, 체계적인 정리 방법을 제대로 익혔습니다.아쉬웠던 점 & 보완회로 배선 정리 부족Logisim에서 선이 겹치다 보니 가끔 헷갈렸습니다.→ 다음에는 작은 모듈로 나눠 단계별로 검증하고, 마지막에 합치는 방식을 사용하겠습니다. 개념 정리 자료 부족AVL 트리나 불 대수 법칙을 공부할 때, 머릿속으로만 이해하고 따로 요약해 두지 않아 복습할 때 헷갈리는 부분이 있었습니다.→ 학습 중에는 핵심 개념을 노트에 간단히 정리하여, 부족한 부분을 바로 찾아볼 수 있도록 하겠습니다.마치며이번 주차는 이론을 코드와 회로로 연결해 보는 경험을 했습니다. 다음 주에도 부족했던 부분을 보완하며 차근차근 학습을 이어가겠습니다! 감사합니다!

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

[워밍업클럽3기] CS전공지식 2주차

기본편 - Section 03 알고리즘재귀 (recursion)사전적 정의: 어떠한 것을 정의할 때 자기 자신을 참조하는 것.탈출조건(=기저조건)이 필수적으로 있어야함.콜스택함수가 호출되면서 올라가는 메모리 영역FILO의 조건을 가짐스택자료구조를 잘 활용한 대표적 사례재귀함수는, 호출할 때마다 콜스택영역을 차지함탈출조건이 없으면 콜스택에 계속 쌓이기만함-> 메모리부족->자동stopfor문 대신 사용하기보다는, 팩토리얼과 같이 더 쉽게 함수구현을 위한것임.재귀함수내에서 자기자신을 호출할때, 이미 함수가 구현되어있다고 가정함.재귀함수: 나 자신을 호출, 구현할때는 이미 구현된 것을 부르는 것처럼 구현하면 쉬움 재귀적으로 생각하기pattern 01:단순 반복실행반복문으로 구현했을때보다 성능이 떨어짐pattern 02:하위 문제 결과를 기반으로 현재문제 계산팩토리얼을 예를 들으면, return number*factorial(number -1);여기에서 하위문제(=factorial(number-1);)를 기반으로, 현재문제(number*factorial(number-1);)를 해결함for문이용은 상향식 계산, 재귀함수를 이용하는 것은 하향식 계산모든 재귀가 하향식은 아님상향식: for문, 재귀함수 구현가능(상향식에서 재귀함수는 매리트없음)하향식: only 재귀함수만 가능 재귀 - 하노이탑재귀함수의 대표적인 예하향식 계산법의 대표적인 예임!순서대로 예상 스택을 쌓아보면 알수 있음1st stack원반 3 -> 기둥 C원반 2, 1 -> 기둥 B원반 1 -> 기둥 C위에서 1번째를 스택 제일 아래에 놓으면,원반 1 -> 기둥 C 부터 실행하게됨2nd stack원반 2 -> 기둥 C원반 1 -> 기둥 A버블정렬(Bubble sort)배열에 무작위로 섞인 숫자 정렬 방법 중 1개그 중 가장 쉽게 생각 할 수 있는 알고리즘구현 쉬움, but 성능 안좋음[4,2,3,1] -> [2,4,3,1] ->[2,3,4,1]->[2,3,1,4]->[2,3,1,4]->[2,1,3,4]->[2,1,3,4]->[1,2,3,4]버블정렬의 성능알고리즘의 빅오 표기법으로 할때, 숫자로 바꾸어보면 쉬움버블 정렬은 (n-1)+(n-2) ... +2+1 = n(n-1)/2 =(n^2-n)/2b 결과적으로 O(n^2)for문 두개가 중첩되어있으니 O(n^2)이라고 예측이 가능하기도함.버블 정렬의 장단점장점: 이해와 구현이 간단함단점: 성능이 O(n^2)으로 좋지만은 않음. 선택정렬(Selection Sort)버블정렬처럼 간단한 정렬에 속함정렬되지 않은 영역의 첫번째 원소를 시작으로 마지막 원소까지 비교후 가장 작은값을 첫번째 원소로 가져옴정렬이 되지 않은 영역에서 가장 작은수와 가장 큰수 위치 바꿔치기!선택정렬의 성능바깥 for문이 실행될수록 안쪽 for문이 줄어듦 -> 선택 정렬의 성능도 버블정렬과 동일한 O(n^2)선택정렬의 장단점은 버블정렬의 장단점과 동일함.그림으로 배우는 운영체제 Section 04프로세스간 통신프로세스: 독립적이기도 데이터를 주고받기도함한 컴퓨터내의 다른 프로세스 or 네트워크로 연결된 다른 프로세스와 데이터를 주고받기도함종류한컴퓨터 내에서 데이터 주고받음파일을 이용: 여러개의 프로세스가 하나의 파일을 읽고씀파이프 이용: 운영체제가 생성한 파이프를 이용함쓰레드를 이용함: 한프로세스내에서 쓰레드가 주고받음네트워크를 이용함소켓통신RPC(원격 프로시져호출)공유자원: 프로세스가 통신할때 공동으로 이용하는 파일이나 변수각프로세스의 접근 순서에 따라 결과가 달라질 수 있음.컨텍스트 스위칭으로 시분할 처리: 어떤 프로세스가 먼저 실행되는지 예측어려움연산결과 예측 어려움 -> 동기화 문컨텍스트 스위칭(Context Switching): 운영체제(OS)가 여러 개의 프로세스를 실행해야 할 때, 현재 실행 중인 작업을 멈추고 다른 작업으로 전환하는 과정임계구역(Critical Section): 여러 프로세스가 동시에 사용하면 안되는 구역!임계구역 문제 해결을 위한 조건상호배제 메커니즘: 임계영역엔 동시에 하나의 프로세스만 접근, 여러 요청에 도 하나의 프로세스 접근만 허용, 임계구역에 들어간 프로세스는 빠르게 나와야함.세마포어: 상호배제 메커니즘 중 한가지경쟁조건(Race Condition): 공유자원을 차지하기 위한 프로세스의 경쟁?동기화에서 가장 중요한 개념프로세스가 공유자원에 접근하기 위해서 운영체제가 세마포어를 우선순위가 높은 프로세스에게 먼저주고, 프로세스가 일을 다하면 운영체제에게 세마포어를 주고, 다시 운영체제는 세마포어를 대기큐에있던 다른 프로세스에게 전달해주는 식임.쉽게 생각해서 은행줄 같은느낌?손님 = 프로세스, 은행원 = 공유자원, 번호표 기계 = 운영체제, 세마포어 = 번호표세마포어를 이용하면, 공유자원에 여러 프로세스가 동시에 접근하지 않기 때문에 동기화문제가 일어나지 않음.세마포어: 정수형 변수임단점: 함수 순서가 중요함 (모니터를 통해 커버가능) 모니터: 세마포어의 단점을 해결하기 위한 상호배제메카니점프로그래밍 언어 차원에서 지원하는 방법synchronized: 자바에서 이것이 붙으면 동시에 여러 프로세스에서 실행할 수 없음!상호배제가 완벽하게 이루어짐이런 것을 제지해주는 것이 모니터의 역할임실제 모니터아니고 지켜본다의 모니터인듯?Section 05 데드락(교착상태)여러 프로세스가 서로 다른 프로세스의 작업이 끝나기를 기다리다가 아무 작업이 이루어지지않는 상태약간 고집센 상태?교착상태 발생이유: 공유자원을 서로 차지하려다 발생함.교착상태의 필요조건상호배제: 먼저 차지하면 다른 프로세스가 사용할 수 없는 리소스임.비선점: 프로세스가 이미 사용하고 있는 것을 다른 프로세스가 뺒을 수 없음.점유와 대기: 프로세스가 다른 리소스를 기다리는 상태원형대기: 점유와 대기를 하는 프로세스의 관계가 원형을 이룸예로 프로세스 A는 프로세스 B의 리소스를, 프로세스 B는 프로세스 C의 리소스를, 프로세스 C는 프로세스 A 의 리소스를 원하는 상태.교착상태 해결교착상태 회피(Deadlock avoidance)프로세스에 자원을 할당할 때 교착상태가 발생하지 않는 수준의 자원을 할당하는 것.전체 자원과 할당된 자원을 기반으로 안정상태를 유지하려 하는것.불안정 상태 =/= 교착상태. 그저 가능성이 높을 뿐.은행원 알고리즘: 전체자원의 수를 알고 있지 않은 채로 자원을 잘못나눠주면 교착상태가됨최대요구자원: 프로세스가 원하는 자원의 수교착상태 검출 방법가벼운 교착상태 검출: 타이머이용일정시간동안 프로세스가 일을 안함 = 교착상태해결법: 중간저장해서 교착상태되면 중간저장한데로 가는것무거운 교착상태 검출: 자원할당 그래프 이용운영체제가 어떠한 자원을 프로세스가 사용하는지 관찰순환구조가 생기는 그래프 = 교착상태교착상태 발생 -> 강제종료강제 종료된 프로세스를 체크포인트에서 롤업오버헤드가 발생하기도함. Section 06컴파일과 프로세스프로그래밍언어컴파일 언어: 개발자가 코드작성 -> 컴파일을 이용하여 기계어로 변환컴파일 과정: 문법 오류 검증 및 기계어로 변환함.C, C++, C#등이 이에 속함인터프리터언어: 개발자가 작성한 코드를 한줄씩 해석해 기계어로 변환미리 검사하지 않아 실행 시 오류가 발생할 수 있음.컴파일 대비 느림JS, Python, Ruby가 이에 속함프로세스: code, data, stack, heap영역code: 말그대로 코드가 들어감data: 전역변수 or 배열stack: 지역변수나 함수 매개변수, 함수의 리턴 주소저장.heap: 동적 메모리 할당.<컴파일 과정>test.c: 개발자가 C언어로 코딩함.전처리기: 개발자 코딩보고, 전처리부분(C언어에서 #부분)을 코드에 치환시킨 후 주석제거test.i: 전처리 된것 저장컴파일러: C언어 파일을 어셈블리어로 저장함.test.s: 어셈블리어 파일어셈블러: 어셈블리어를 오브젝트 파일로 변환test.o: 0과 1로 된 기계어로 구성된 오브젝트 파일 (코드영역과 데이터 영역이 나누어있음)링커: 오브젝트 파일을 실행파일로 변환.모든 오브젝트 파일을 하나의 데이터영역과 코드영역으로 바꿈실제 실행될 주소 매핑test.exe: 운영체제가 프로세스를 만들어줌. 완벽한 상태의 코드영역과 데이터 영역으로 나누어짐.이후...운영체제 ->exe파일의 코드영역과 데이터영역을 프로세스의 코드영역과 데이터영역에 넣어줌-> 빈상태의 스택과 힙을 할당 ->PCB를 만들어 관리가 가능하게 만들어줌 -> 프로그램 카운터(다음 실행할 명령어의 주소를 생성한 프로세스의 코드를 첫번째 주소로 설정) -> CPU 스케줄링에 맞추어 프로세스 실행후 작업을 마침Section 07메모리의 종류 (1번이 가장 속도가 빠르고 용량이 작으며 비쌈)레지스터: 가장빠른 기억장소, CPU내에 존재휘발성 메모리레지스터의 크기= 32bit, 64 bit메인메모리의 값을 레지스터로 가져와 계산 후 메인 메모리로 옮김캐시: 메인메모리에서 레지스터로 옮길때 미리 가져오는 데이터를 캐시에 옮겨둔다.캐시는 여러개를 둠. 가장 빠른 캐시 = L1.RAM(매인 메모리): 실제 운영체제와 여러 프로세스를 사용실행중인 프로그램만 돌림보조저장장치(HDD, SSD)비휘발성 메모리 메인메모리폰노이만 구조는 모든 프로그램을 메모리에서 실행시킴멀티프로그래밍 환경에서 여러개가 한번에 진행하여야 하기 때문에 복잡하고 어려워짐운영체제 : 1바이트 크기의 주소를 만들어 관리32bit= 레지스터, ALU, 데이터 이동버스 , 사용가능 메모리도 2^34=4Gb64bit = 레지스터, ALU, 데이터 이동버스, 사용가능 메모리는 2^64로 거의 무한대즉, 32bit보다 64bit ram이 더빠름 메모리에는 운영체제 영역이 따로있음.악의적이 프로그램이 운영체제를 침범하면 위험하기 때문에 경계레지스터( CPU내에 존재)를 통하여 보호함.절대주소: 실제 프로그램이 올라가는 주소, 물리 주소공간이라고도함.상대주소: 사용자가 바라보는 주소, 논리 주소라고 하기도함.메모리 할당방식메모리보다 더큰 프로그램은!!!프로그램을 메모리만큼 자른뒤 필요한거 일부 실행, 나머지 일부는 하드디스크내 스왑영역에 두었다가 사용함. = memory overlay멀티 프로그램 환경에서는,가변분할 방식 사용프로세스 크기에 따라 메모리는 나눔한프로세스가 메모리의 연속된 공간에 할당: 연속 메모리 할당단점: 외부단편화 발생장점: 빈공간 없음.고정 분할 방식프로세스 크기 상관없이 메모리 나눔 비연속 메모리할당: 메모리가 잘라서 나누어 들어가기도 하기때문장점: 구현이 간단하고 오버헤드가 적음단점: 내부단편화 발생외부단편화세그멘테이션 = 가변분할방식일부 프로세스가 종료되어 그만큼의 메모리(50+10MB)를 다른 프로세스(60MB필요)가 사용할때, 메모리가 연속으로 붙어있지 않으면 다른 프로세스에 할당이 어려운 것을 외부단편화라 함.해결방법: 조각모음,단점: 사용중 메모리 전부 중단, 메모리 이동해야함 -> 오버헤드 발생내부단편화페이징 = 고정분할 방식일정하게 분할된 메모리(20MB)이지만, 프로세스가 더 많은 메모리(50MB)가 필요하면 불할된 메모리를 프로세스가 필요한 메모리보다 많은 메모리(60MB)를 제공함버디시스템2의 승스로 메모리 분할해 할당함내부단편화가 발생하지만, 크기가작음동일하게 나누었기 때문에 조립하기 쉬움 (조각모음보다 간단함) 2주차 후 소감...확실히, 한글로 배우니까 너무 좋음.자세히 그림으로 설명해주시는것도 너무 좋음...이해 쏙쏙되어서 너무 좋다.학기 시작할때 알고 시작했으면 더 좋았을걸 하는 아쉬움남은 2주 화이팅 :)

cs･전공지식