📌 이 글은 워밍업 클럽 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');

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

1. 단순히 반복 실행하는 방식

2. 하위 문제의 결과를 기반으로 현재 문제를 계산하는 방식 (하향식 계산)

📌 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가지 조건

1. 하나의 프로세스만 접근 가능

2. 여러 요청이 있을 경우 순차적으로 접근 허용

3. 임계 구역에 들어간 프로세스는 빠르게 종료해야 함

세마포어 (Semaphore)

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

모니터 (Monitor)

• 세마포어의 단점을 보완한 기법

• 프로그래밍 언어 수준에서 지원 (synchronized 키워드 사용)

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

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

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

1. 상호 배제 (Mutual Exclusion) : 한 번에 하나의 프로세스만 자원 사용 가능

2. 비선점 (No Preemption) : 자원을 강제로 빼앗을 수 없음

3. 점유와 대기 (Hold and Wait) : 자원을 점유한 상태에서 추가 자원을 기다림

4. 원형 대기 (Circular Wait) : 프로세스들이 서로 자원을 기다리며 원형 구조 형성

데드락 해결 방법

1. 교착 상태 회피 (Deadlock Avoidance)

    

   1. 자원 할당 시 교착 상태 발생 여부를 예측

   2. 은행원 알고리즘 (Banker’s Algorithm) 사용하여 안전 상태 유지

2. 교착 상태 검출 및 해결

   1. 가벼운 교착 상태 검출 : 일정 시간 동안 프로세스가 멈춰 있으면 강제 종료

   2. 무거운 교착 상태 검출 : 운영체제가 직접 프로세스의 자원 사용을 모니터링 후 해결

📌 5. 메모리 관리

메모리 종류

• 레지스터 : CPU 내부의 가장 빠른 기억 장치 (휘발성)

• 캐시 메모리 : CPU가 미리 가져온 데이터를 저장하는 고속 메모리

• 메인 메모리 (RAM) : 실제 운영체제와 프로세스가 올라가는 공간 (휘발성)

• 보조 저장 장치 (HDD, SSD) : 비휘발성 메모리

메모리 할당 방식

1. 가변 분할 방식 (Segmentation) : 프로세스 크기에 맞게 메모리를 할당

2. 고정 분할 방식 (Paging) : 프로세스 크기와 관계없이 일정한 크기로 할당

버디 시스템 (Buddy System)

• 2의 승수 단위로 메모리를 분할하여 할당

• 내부 단편화 최소화 & 프로세스 크기에 따라 유동적 할당 가능

3⃣ 회고

첫 주차에 듣지 못했던 강의를 들으면서 다시 정상적으로 강의를 듣기 시작했다. 🙇‍♂

재귀함수 강의 중 하노이 탑 내용은 혼자서 시도를 해보면 절대 구현을 못해낼 거 같다... 이 부분을 다시 공부해야할 것 같습니다 ㅠㅠ..

이번 2주차 강의를 들으면서 자료구조와 알고리즘은 되게 묵직한 그런 느낌이고, 운영체제는 뭔가 이 컴퓨터란 존재에 대해서 다시 생각해보는 강의였던 것 같습니다..! 🐾🐾