[인프런 워밍업 클럽 3기 CS] 자료구조와 알고리즘 / 운영체제 회고3

1. 메모리 종류• 레지스터(가장 빠름), 캐시(CPU-RAM 중간), RAM(실행 메모리), 가상 메모리(HDD/SSD 활용), 보조 저장 장치(영구 저장).2. 운영체제 보호 레지스터• 베이스 레지스터: 시작 주소 저장.• 한계 레지스터: 접근 가능한 최대 주소 설정.3. 메모리 할당 방식 비교• 가변 분할: 메모리 효율적 사용 but 외부 단편화 발생.• 고정 분할: 관리가 쉬움 but 내부 단편화 발생.4. 스레싱(Thrashing)• 멀티프로그래밍 증가 → 스왑 증가 → CPU 사용률 0%.5. HDD/SSD 없이 컴퓨터 실행 가능?• 가능하지만 운영체제를 저장할 공간이 필요함.6. 삭제된 파일 복구 가능 이유• 파일 삭제 시 데이터는 그대로 남고, 인덱스만 삭제됨. 1. 정렬 알고리즘 비교• 버블/선택/삽입 정렬: O(n²)로 느림.• 퀵/병합 정렬: O(n log n)로 효율적.2. 메모이제이션 vs. 타뷸레이션• 메모리가 부족한 경우 → 타뷸레이션(반복문 방식) 사용.• 이유: 재귀 호출(메모이제이션)은 스택 오버플로우 발생 위험이 있음.

[인프런 워밍업 클럽 3기 CS] 자료구조 및 알고리즘 3주 차 미션

자료구조와 알고리즘1. 5가지 정렬 알고리즘 비교정렬 알고리즘 시간 복잡도 (최선/평균/최악)장점단점버블 정렬O(n) / O(n²) / O(n²)구현이 쉬움성능이 매우 낮음선택 정렬O(n²) / O(n²) / O(n²)교환 횟수가 적음속도가 느림삽입 정렬O(n) / O(n²) / O(n²)거의 정렬된 데이터에서 빠름역순 데이터에서 느림퀵 정렬O(n log n) / O(n log n) / O(n²)평균적으로 빠름최악의 경우 성능 저하 (피벗 선택에 따라)병합 정렬O(n log n) / O(n log n) / O(n log n)안정적인 정렬추가 메모리 사용 필요 2. 메모이제이션 vs. 타뷸레이션 선택• 메모리가 부족한 경우 → 타뷸레이션(반복문 방식) 선택• 이유:• 메모이제이션(Top-Down, 재귀 방식)은 호출 스택이 깊어지면 스택 오버플로우(Stack Overflow)가 발생할 수 있음.• 타뷸레이션(Bottom-Up, 반복문 방식)은 스택을 사용하지 않고, 테이블을 채우는 방식이므로 메모리 사용이 더 효율적임.

[인프런 워밍업 클럽 3기 CS] 운영체제 3주 차 미션

운영체제1. 메모리의 종류와 특징1. 레지스터(Register) – CPU 내부에 위치, 가장 빠름, 용량 작음.2. 캐시(Cache) – CPU와 RAM 사이에 위치, 자주 사용하는 데이터를 저장하여 속도 향상.3. 메인 메모리(RAM) – 휘발성(전원 차단 시 데이터 삭제), 실행 중인 프로그램이 사용.4. 가상 메모리(Virtual Memory) – RAM이 부족할 때 HDD/SSD 일부를 메모리처럼 사용.5. 보조 저장 장치(HDD/SSD) – 비휘발성, 데이터를 영구 저장하는 장치. 2. 사용자 프로세스가 운영체제 메모리 영역에 침범하지 못하도록 만든 레지스터• 베이스 레지스터(Base Register): 프로세스의 메모리 시작 주소 저장.• 한계 레지스터(Limit Register): 프로세스가 접근할 수 있는 최대 범위 설정.• 이 두 개를 사용하여 운영체제 메모리를 보호함. 3. 가변 분할 방식 vs. 고정 분할 방식 가변 분할 방식고정 분할 방식장점메모리를 효율적으로 사용 가능내부 단편화 없음단점외부 단편화 발생 가능고정 크기로 인해 메모리 낭비 발생 4. CPU 사용률이 0%에 가까워지는 현상• 스레싱(Thrashing)• 이유: 멀티프로그래밍을 너무 많이 실행하여 페이지 부재(Page Fault)가 증가하고, 스왑(Swap)이 빈번하게 발생하여 CPU가 거의 사용되지 않음. 5. HDD나 SSD는 컴퓨터 실행에 필수인가?• 필수는 아님.• 이유: 운영체제(OS)가 RAM에서 실행되면 부팅이 가능하므로, HDD/SSD 없이도 실행 가능. 다만, OS를 저장할 공간이 필요하므로 일반적으로 사용됨. 6. 파일을 삭제해도 포렌식으로 복구할 수 있는 이유• 파일을 삭제해도 실제 데이터는 삭제되지 않음.• 운영체제는 단순히 파일의 메타데이터(인덱스)만 삭제하고, 기존 데이터는 그대로 남아 있음.• 새로운 데이터가 덮어쓰기 전까지 복구 가능.

[인프런 워밍업 클럽 3기 CS] 자료구조와 알고리즘 / 운영체제 회고2

운영체제 요약 FIFO 스케줄링의 장단점• 장점: 구현이 간단하고 공정함.• 단점: 긴 작업이 먼저 오면 짧은 작업이 지연되는 Convoy Effect 발생. SJF를 사용하기 어려운 이유• 실행 시간을 미리 알기 어려움.• 긴 작업이 계속 뒤로 밀려 기아 상태(Starvation) 발생 가능. RR에서 타임 슬라이스가 작을 때 문제• 문맥 전환 비용 증가 → 성능 저하 발생. MLFQ에서 CPU Bound vs. I/O Bound 구분 방법• I/O Bound: 짧은 CPU 사용 후 대기 → 높은 우선순위 유지• CPU Bound: CPU 사용이 길어짐 → 낮은 우선순위로 강등 공유 자원이란?• 여러 프로세스가 동시에 접근하는 자원 (파일, 메모리, CPU 등). 교착 상태(Deadlock) 발생 조건1. 상호 배제 – 한 번에 한 프로세스만 사용 가능.2. 점유 및 대기 – 자원을 점유한 채 추가 자원 대기.3. 비선점 – 자원을 강제로 빼앗을 수 없음.4. 순환 대기 – 프로세스들이 서로 자원을 기다리는 순환 구조. 자료구조와 알고리즘 요약재귀 함수에서 기저 조건 오류 문제• 잘못 설정하면 무한 재귀 → Stack Overflow 발생. 0부터 n까지 홀수의 합 구하는 재귀 함수 (JavaScript)function sumOdd(n) { if (n 재귀를 이용한 디렉토리 탐색 코드 (JavaScript)const fs = require("fs"); const path = require("path"); function traverseDirectory(directory) { const files = fs.readdirSync(directory); for (const file of files) { const filePath = path.join(directory, file); const fileStatus = fs.statSync(filePath); if (fileStatus.isDirectory()) { console.log('디렉토리:', filePath); traverseDirectory(filePath); } else { console.log('파일:', filePath); } } } traverseDirectory(".");기존 반복문 방식 → 재귀 함수로 변환하여 모든 파일 및 폴더 탐색.

[인프런 워밍업 클럽 3기 CS] 자료구조 및 알고리즘 2주 차 미션

자료구조와 알고리즘1. 재귀함수에서 기저 조건을 만들지 않거나 잘못 설정했을 때 발생하는 문제• 무한 루프(무한 재귀) 발생 → 스택이 계속 쌓이며 Stack Overflow(스택 오버플로우) 발생• 잘못된 결과 반환 → 기저 조건을 잘못 설정하면 원하는 값을 반환하지 못함 2. 0부터 입력 n까지 홀수의 합을 구하는 재귀 함수function sumOdd(n) { if (n 3. 재귀를 이용한 디렉토리 탐색 코드const fs = require("fs"); // 파일 시스템 모듈 const path = require("path"); // 경로 관련 모듈 function traverseDirectory(directory) { const files = fs.readdirSync(directory); // 현재 디렉토리의 파일 목록 for (const file of files) { const filePath = path.join(directory, file); // 현재 파일 경로 const fileStatus = fs.statSync(filePath); // 파일 상태 정보 가져오기 if (fileStatus.isDirectory()) { console.log('디렉토리:', filePath); traverseDirectory(filePath); // 재귀 호출 } else { console.log('파일:', filePath); } } } traverseDirectory("."); // 현재 디렉토리부터 탐색 시작재귀를 사용하여 모든 하위 디렉토리를 탐색하면서 파일과 폴더를 출력함.

[인프런 워밍업 클럽 3기 CS] 운영체제 2주 차 미션

운영체제1. FIFO 스케줄링의 장단점장점:• 구현이 간단하고 직관적이다.• 공정한 스케줄링 방식으로, 먼저 도착한 프로세스가 먼저 실행된다. 단점:• Convoy Effect(호위 효과)가 발생할 수 있다. → 실행 시간이 긴 프로세스가 먼저 도착하면 짧은 프로세스들이 오래 대기해야 한다.• 응답 시간이 일정하지 않아 실시간 시스템에 부적합하다. 2. SJF(Shortest Job First)를 사용하기 어려운 이유• 프로세스의 실행 시간을 미리 알 수 없다. (CPU Burst Time 예측이 어렵다.)• 새로운 작업이 짧은 실행 시간을 가진다면, 긴 실행 시간의 작업이 계속 뒤로 밀리는 기아 상태(Starvation)가 발생할 수 있다.• 동적 우선순위 조정을 위해 예측 기법(Exponential Averaging 등)을 적용해야 하는데, 오버헤드가 발생할 수 있다. 3. RR 스케줄링에서 타임 슬라이스가 아주 작으면 발생하는 문제• 문맥 전환(Context Switching) 비용 증가 → CPU가 프로세스를 너무 자주 교체하면 성능 저하 발생• CPU 사용률 감소 → 실행보다 문맥 전환에 더 많은 시간이 소비됨• 오버헤드 증가 → 캐시 효율성이 떨어지고, 프로세스 실행이 지연됨 4. MLFQ에서 CPU Bound Process와 I/O Bound Process를 구분하는 방법• I/O Bound Process: 자주 입출력을 수행하기 때문에 짧은 CPU Burst 후 대기 상태로 전환됨 → 높은 우선순위 큐에 머무름• CPU Bound Process: CPU를 길게 사용하는 프로세스 → 시간이 지나면서 우선순위가 낮은 큐로 이동• MLFQ는 시간 제한(Time Quantum)과 큐 강등을 통해 CPU Bound와 I/O Bound 프로세스를 자동으로 분리함 5. 공유 자원이란?• 여러 프로세스가 동시에 접근할 수 있는 자원• 예: 파일, 데이터베이스, 프린터, 메모리, CPU 등• 공유 자원을 잘못 관리하면 경쟁 상태(Race Condition), 데드락(Deadlock) 등의 문제가 발생할 수 있음 6. 교착 상태(Deadlock) 발생 조건교착 상태가 발생하려면 다음 4가지 조건이 동시에 만족해야 함:1. 상호 배제(Mutual Exclusion): 한 번에 한 프로세스만 자원을 사용할 수 있음2. 점유 및 대기(Hold and Wait): 이미 자원을 가진 프로세스가 추가 자원을 기다림3. 비선점(Non-preemption): 자원을 강제로 빼앗을 수 없음4. 순환 대기(Circular Wait): 프로세스들이 자원을 서로 기다리는 순환 구조를 가짐 교착 상태를 예방하려면 위 조건 중 하나 이상을 제거해야 함.

[인프런 워밍업 클럽 3기 CS] 자료구조와 알고리즘 / 운영체제 회고

1. 프로세스와 쓰레드 프로세스 (Process) • 실행 중인 프로그램으로, 독립적인 메모리 공간(Code, Data, Heap, Stack)을 가짐. • 운영체제(OS)에서 하나의 작업 단위로 취급. • 프로세스 간 자원 공유가 어렵고, 문맥 교환(Context Switching) 비용이 큼. 쓰레드 (Thread) • 프로세스 내에서 실행되는 작업 단위로, 프로세스의 Code, Data, Heap을 공유하지만 Stack은 독립적으로 가짐. • 같은 프로세스 내에서는 빠른 데이터 공유가 가능하지만, 동기화 문제가 발생할 수 있음. • 멀티쓰레딩을 활용하면 응답성을 높이고 자원을 효율적으로 사용할 수 있음. 프로세스 vs. 쓰레드 비교 항목 프로세스 쓰레드 메모리 독립적 공유 (Code, Data, Heap) 문맥 교환 비용 높음 (PCB 교체) 낮음 (TCB 교체) 자원 공유 어려움 (IPC 필요) 쉬움 독립성 강함 약함 (같은 프로세스에 종속) 2. CPU 스케줄링 • CPU를 여러 프로세스가 효율적으로 사용할 수 있도록 운영체제가 결정하는 방식. • 목적: CPU 이용률 및 시스템 성능 향상, 응답 시간 단축, 공정한 CPU 분배. 스케줄링 방식 1. 비선점형 (Non-preemptive) • 한 프로세스가 CPU를 점유하면 작업이 끝날 때까지 다른 프로세스가 CPU를 사용할 수 없음. • 예: FCFS(First-Come, First-Served), SJF(Shortest Job First) 2. 선점형 (Preemptive) • 특정 조건에서 프로세스가 CPU를 양보하고 다른 프로세스가 실행될 수 있음. • 예: RR(Round Robin), SRTF(Shortest Remaining Time First), Priority Scheduling 대표적인 스케줄링 알고리즘 알고리즘 방식 특징 FCFS 비선점형 먼저 도착한 순서대로 실행 (대기 시간 증가 가능) SJF 비선점형 실행 시간이 가장 짧은 프로세스부터 실행 SRTF 선점형 남은 실행 시간이 가장 짧은 프로세스부터 실행 RR 선점형 일정 시간(Time Quantum)마다 프로세스를 교체 Priority Scheduling 혼합 우선순위가 높은 프로세스부터 실행 3. 자료구조 1) 배열 (Array) • 고정된 크기의 연속된 메모리 공간을 사용. • 인덱스를 통한 빠른 접근(O(1)) 가능하지만, 삽입/삭제가 어려움(O(n)). 2) 연결 리스트 (Linked List) • 노드(Node)들이 포인터를 이용해 연결된 자료구조. • 삽입/삭제가 O(1)로 빠르지만, 인덱스 접근이 O(n)으로 느림. 3) 스택 (Stack) • LIFO(Last In, First Out) 방식. • 함수 호출 스택, 되돌리기(Undo) 기능 등에 활용. 4) 큐 (Queue) • FIFO(First In, First Out) 방식. • 작업 스케줄링, 네트워크 패킷 처리 등에 활용. 5) 해시 테이블 (Hash Table) • Key-Value 형태로 데이터를 저장하는 자료구조. • 빠른 검색(O(1))이 가능하지만, 해시 충돌이 발생할 수 있음. 6) 트리 (Tree) • 계층 구조를 이루는 자료구조. • 이진 탐색 트리 (BST): O(log n)의 탐색 속도를 가짐. • 힙 (Heap): 우선순위 큐 구현에 사용됨. • 트라이 (Trie): 문자열 검색 최적화. 7) 그래프 (Graph) • 정점(Vertex)과 간선(Edge)으로 구성된 자료구조. • 최단 경로 탐색 (Dijkstra), 최적 경로 찾기 (A*) 등에 활용.

[인프런 워밍업 클럽 3기 CS] 운영체제 1주 차 미션

운영체제1. 폴링 방식을 대체할 수 있는 방법은? 폴링 방식은 CPU를 불필요하게 사용하므로 이벤트 기반 방식 또는 인터럽트 방식으로 개선할 수 있습니다.• 이벤트 기반 방식: 특정 이벤트가 발생할 때만 실행되도록 설정 (예: 버튼 클릭 이벤트)• 인터럽트 방식: CPU가 특정 조건이 발생했을 때만 중단하고 처리 (예: 하드웨어 인터럽트, 소프트웨어 인터럽트) ➡ 해결 방법 예시:document.addEventListener("skillActivated", () => { console.log("Skill used!");});이렇게 하면 skillActivated 이벤트가 발생할 때만 실행됩니다.2. 프로그램과 프로세스의 차이점• 프로그램: 실행 가능한 파일 (코드, 데이터, 리소스 포함)• 프로세스: 실행 중인 프로그램 (CPU, 메모리, 리소스를 할당받음) ➡ 프로그램은 정적인 파일, 프로세스는 동적으로 실행되는 개체입니다.3. 멀티프로그래밍 vs 멀티프로세싱• 멀티프로그래밍: 하나의 CPU에서 여러 개의 프로그램을 실행하기 위해 CPU 스케줄링을 사용• 예: 한 프로세스가 I/O 작업을 할 때, 다른 프로세스가 CPU 사용• 멀티프로세싱: 여러 개의 CPU(코어)에서 여러 프로세스를 동시에 실행• 예: 멀티코어 CPU를 활용한 병렬 처리 ➡ 멀티프로그래밍은 CPU를 최대한 활용, 멀티프로세싱은 성능을 극대화하는 방식입니다.4. 운영체제의 프로세스 관리 기법• PCB(Process Control Block): 프로세스 정보를 저장하는 데이터 구조• 스케줄러: 프로세스 실행 순서를 결정하는 시스템 (예: FCFS, RR, SJF)• 인터럽트: 프로세스의 상태를 변경하는 시스템 이벤트• 메모리 관리: 프로세스의 주소 공간을 관리 (예: 가상 메모리, 페이징) ➡ 운영체제는 PCB, 스케줄링, 메모리 관리 등을 활용하여 프로세스를 제어합니다.5. 컨텍스트 스위칭이란?• CPU가 실행 중인 프로세스를 변경할 때, 기존 프로세스의 상태를 저장하고 새로운 프로세스를 로드하는 과정• PCB에 레지스터, 스택 포인터, 프로그램 카운터 등을 저장했다가 복원 ➡ 컨텍스트 스위칭은 멀티태스킹의 필수 요소이지만, 오버헤드(비용)가 발생합니다.

[인프런 워밍업 클럽 3기 CS] 자료구조와 알고리즘 1주 차 미션

자료구조와 알고리즘 1. 학생 정보를 저장할 자료구조 선택• 해시맵(HashMap) 또는 딕셔너리(Dictionary)• 이유: 학생 정보를 (학번 → 객체) 형태로 저장하고 빠르게 검색할 수 있음• 예제:let studentRecords = new Map();studentRecords.set(2023001, { name: "홍길동", age: 20, grade: "A" });console.log(studentRecords.get(2023001)); // { name: "홍길동", age: 20, grade: "A" } • 검색 속도: O(1) (빠름) ➡ 학생 정보를 빠르게 조회할 필요가 있으므로 해시맵 사용2. 주문 처리를 위한 자료구조 선택• 큐(Queue)• 이유: 주문은 선입선출(FIFO, First In First Out) 방식으로 처리됨• 예제:class OrderQueue { constructor() { this.orders = []; } enqueue(order) { this.orders.push(order); } dequeue() { return this.orders.shift(); }} let orderQueue = new OrderQueue();orderQueue.enqueue("햄버거");orderQueue.enqueue("콜라");console.log(orderQueue.dequeue()); // 햄버거 • 삽입, 삭제 시간 복잡도: O(1) ➡ 주문은 들어온 순서대로 처리해야 하므로 큐(Queue) 사용이 적절3. 스택을 마지막 인덱스로 삽입, 삭제하도록 변경• 기존: 0번 인덱스에서 push()와 pop() 수행• 변경: 배열의 마지막 인덱스에서 삽입(push())과 삭제(pop()) 수행class Stack { constructor() { this.stack = []; } push(value) { this.stack.push(value); // 마지막 인덱스에 삽입 } pop() { return this.stack.pop(); // 마지막 인덱스에서 제거 }} let stack = new Stack();stack.push(1);stack.push(2);console.log(stack.pop()); // 2➡ 시간 복잡도: push() 및 pop() 연산은 O(1) 4. 이름을 이용한 해시 함수 구현 이름을 유니코드 값(charCodeAt)으로 변환하여 해시 키를 생성합니다.function hashFunction(name) { let hash = 0; for (let i = 0; i hash += name.charCodeAt(i); } return hash % 100; // 100개의 해시 버킷 사용} // 테스트console.log(hashFunction("이운재")); console.log(hashFunction("홍길동")); ➡ 유니코드 값을 사용하면 충돌 가능성이 낮아지고 해시 테이블의 분포가 개선됨