[인프런 워밍업 클럽_3기 CS] 두번째 발자국 🐾🐾

2025-03-16T11:36:09.145Z

동동

📌 이 글은 워밍업 클럽 3기 감자님의 CS 강의인 ‘그림으로 쉽게 배우는 자료구조와 알고리즘’과 ‘그림으로 쉽게 배우는 운영체제’를 학습하며 정리한 내용을 담고있습니다. 🙇‍♂

1⃣ 자료구조와 알고리즘

📌 1. 재귀 (Recursion)

재귀 개념

재귀란, 자기 자신을 호출하는 방식으로 문제를 해결하는 기법
콜 스택 (Call Stack)을 사용하여 함수 호출을 관리
대표적인 예 : 팩토리얼 계산, 하노이 탑 문제

하노이 탑 (Tower of Hanoi)

원반을 규칙에 맞게 기둥 사이로 이동시키는 문제
재귀 호출을 활용하여 해결 가능

const hanoi = (count, from, to, temp) => {
    if (count == 0) return;
    
    hanoi(count - 1, from, temp, to);
    console.log(`원반 ${count}를 ${from}에서 ${to}로 이동`);
    hanoi(count - 1, temp, to, from);
};

hanoi(3, 'A', 'C', 'B');

재귀적으로 생각하는 두 가지 패턴

단순히 반복 실행하는 방식
하위 문제의 결과를 기반으로 현재 문제를 계산하는 방식 (하향식 계산)

📌 2. 정렬 알고리즘

버블 정렬 (Bubble Sort)

인접한 두 데이터를 비교하며 정렬하는 방식
시간 복잡도 : O(n²) (비효율적)
장점 : 이해하기 쉽고 구현이 간단함
단점 : 성능이 좋지 않음

for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
            let temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
    }
}

선택 정렬 (Selection Sort)

가장 작은 값을 선택하여 앞으로 이동
시간 복잡도 : O(n²)
장점 : 이해하기 쉽고 구현이 간단함
단점 : 성능이 좋지 않음

for (let i = 0; i < arr.length - 1; i++) {
    let minValueIndex = i;
    
    for (let j = i + 1; j < arr.length; j++) {
        if (arr[j] < arr[minValueIndex]) {
            minValueIndex = j;
        }
    }
    
    let temp = arr[i];
    arr[i] = arr[minValueIndex];
    arr[minValueIndex] = temp;
}

2⃣ 운영체제

📌 1. 운영체제 개요

운영체제의 역할

프로세스 관리 : CPU 스케줄링, 멀티태스킹
메모리 관리 : 프로세스 메모리 할당
파일 및 입출력 관리 : 파일 시스템, 장치 드라이버 제어

컴파일 과정

test.c -> 전처리기 -> test.i -> 컴파일러 -> test.s -> 어셈블러 -> test.o -> 링커 -> test.exe

전처리기 : #include, #define 등을 처리
컴파일러 : C 코드를 어셈블리 코드로 변환
어셈블러 : 어셈블리 코드를 기계어로 변환
링커 : 실행 가능한 바이너리 파일 생성

📌 2. 프로세스 스케줄링

FIFO (First In First Out)

도착 순서대로 CPU를 할당
장점 : 구현이 간단하고 공정함
단점 : 실행 시간이 긴 프로세스가 먼저 도착하면 대기 시간이 증가

SJF (Shortest Job First)

실행 시간이 짧은 프로세스를 우선 실행
단점 : 프로세스의 실행 시간을 미리 예측하기 어려움

RR (Round Robin)

타임 슬라이스(Time Slice)를 사용하여 프로세스를 순환 실행
타임 슬라이스가 너무 작으면 문맥 전환 비용이 증가하여 비효율적

MLFQ (Multi-Level Feedback Queue)

CPU Bound Process와 I/O Bound Process를 구분하여 처리
CPU Bound Process : CPU 사용 시간이 길면 낮은 우선순위 큐로 이동
I/O Bound Process : CPU를 짧게 사용하며 높은 우선순위 큐 유지

📌 3. 프로세스 간 통신

공유 자원과 임계 구역

공유 자원 : 여러 프로세스가 공동으로 사용하는 변수, 메모리, 파일
임계 구역 (Critical Section) : 한 번에 하나의 프로세스만 접근해야 하는 구역

임계 구역 문제 해결을 위한 3가지 조건

하나의 프로세스만 접근 가능
여러 요청이 있을 경우 순차적으로 접근 허용
임계 구역에 들어간 프로세스는 빠르게 종료해야 함

세마포어 (Semaphore)

동기화 기법으로 공유 자원에 대한 접근을 제한

모니터 (Monitor)

세마포어의 단점을 보완한 기법
프로그래밍 언어 수준에서 지원 (synchronized 키워드 사용)

📌 4. 데드락 (교착 상태)

여러 프로세스가 서로 자원을 기다리며 작업이 멈추는 상태

데드락 발생 조건 (4가지)

상호 배제 (Mutual Exclusion) : 한 번에 하나의 프로세스만 자원 사용 가능
비선점 (No Preemption) : 자원을 강제로 빼앗을 수 없음
점유와 대기 (Hold and Wait) : 자원을 점유한 상태에서 추가 자원을 기다림
원형 대기 (Circular Wait) : 프로세스들이 서로 자원을 기다리며 원형 구조 형성

데드락 해결 방법

교착 상태 회피 (Deadlock Avoidance)
1. 자원 할당 시 교착 상태 발생 여부를 예측
2. 은행원 알고리즘 (Banker’s Algorithm) 사용하여 안전 상태 유지
교착 상태 검출 및 해결
1. 가벼운 교착 상태 검출 : 일정 시간 동안 프로세스가 멈춰 있으면 강제 종료
2. 무거운 교착 상태 검출 : 운영체제가 직접 프로세스의 자원 사용을 모니터링 후 해결