2주차 학습 내용 - 발자국

자료구조 & 알고리즘

재귀함수

function sum(n) {
  if (n === 1) return 1; // ✅ 기본 조건(Base Case): n이 1이면 재귀 종료
  return n + sum(n - 1); // 🔁 재귀 호출(Recursive Case): sum(n-1) 호출
}

console.log(sum(5)); // 5 + 4 + 3 + 2 + 1 = 15

• 함수 내부에서 자기 자신을 다시 호출하는 구조를 가진 함수

기본조건

• 재귀 함수가 계속 반복되지 않도록 종료 조건(기저 조건)을 설정해야 함.

• 없으면 무한 루프가 발생하여 Stack Overflow(스택 오버플로우) 오류가 발생함.

재귀 호출

• 재귀 호출을 통해 문제를 점점 더 단순하게 만들어 Base Case에 도달하도록 함.

하노이 탑(재귀)

function 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"); 

• 재귀문제의 기본으로 알려진 하노이탑 문제의 원리

  • 큰 원반을 옮기기 전에, 그 위에 있는 원반들을 다른 기둥으로 옮긴다.

  • 가장 아래에 있는 큰 원반을 목표 기둥으로 이동한다.

  • 다른 기둥에 옮겨둔 원반들을 다시 목표 기둥으로 옮긴다.

• hanoi 함수의 매개변수는 (원반개수, 시작위치, 도착위치, 거치는위치)4개로 구성된다. 

버블정렬

function bubbleSort(arr) {
  let n = arr.length;
  for (let i = 0; i < n - 1; i++) { // 전체 반복 횟수
    for (let j = 0; j < n - 1 - i; j++) { // 점점 줄어드는 비교 범위
      if (arr[j] > arr[j + 1]) { // 오름차순 정렬
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // Swap (교환)
      }
    }
  }
  return arr;
}

let arr = [5, 3, 8, 4, 2];
console.log(bubbleSort(arr)); // [2, 3, 4, 5, 8]

• 배열을 반복하면서 인접한 두 요소를 비교하고 조건에 따라 서로의 위치를 바꿈

• 구현하기는 쉽지만 성능면(O(n²))에서는 그렇게 좋지 않음.

   

선택정렬

function selectionSort(arr) {
  let n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    let minIndex = i; // 현재 정렬된 부분 이후에서 가장 작은 값의 인덱스 저장

    for (let j = i + 1; j < n; j++) { // i 이후 요소들과 비교
      if (arr[j] < arr[minIndex]) {
        minIndex = j; // 더 작은 값이 발견되면 minIndex 갱신
      }
    }

    // 최소값을 현재 위치(i)와 교환 (swap)
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }

  return arr;
}

let arr = [5, 3, 8, 4, 2];
console.log(selectionSort(arr)); // [2, 3, 4, 5, 8]

• 배열영역의 첫 번째 원소를 시작으로 마지막 원소까지 비교 후 가장 작은 값을 첫 번째 원소로 가져온다.

• 버블정렬과 같은 경우로 구현하기는 쉽지만 성능면(O(n²))에서는 그렇게 좋지 않음.

운영체제

프로세스 간 통신

• 한 컴퓨터내에 있는 다른 프로세스와 통신하는 방법 ex) 파일, 파이프

  • 파일: 프로세스 간 데이터를 저장하고 읽을 수 있음.

  • 파이프: 한 프로세스의 출력이 다른 프로세스의 입력이 되는 방식.

• 네트워크로 연결된 다른 컴퓨터에 있는 프로세스와 통신을 하는 방법 ex) 소켓통신, RPC

  • 소켓통신: 네트워크를 통해 데이터를 주고받는 방식

  • RPC: 원격 프로시저 호출을 이용하여 다른 컴퓨터에서 실행되는 함수 호출.

쓰레드 간 통신

• 같은 프로세스 내에서 실행되는 여러 개의 쓰레드 간의 통신 방법

• 쓰레드는 코드, 데이터, 힙을 공유하며, 각자의 스택만 별도로 가짐.

• 전역 변수(Global Variable)나 힙(Heap)을 이용하면 쓰레드 간 데이터 공유 가능.

공유자원

• 프로세스나 쓰레드 간의 통신에서 공동으로 사용하는 변수나 파일을 의미한다.

임계구역

• 여러 프로세스가 동시에 접근하면 안 되는 공유 자원의 영역

세마포어

• 공유자원을 함께 쓰는 프로세스 간의 충돌을 막기 위해 프로세스가 사용하는 동안 다른 프로세스는 동작하지 않고 기다리는 것

모니터

• 세마포어의 단점을 개선한 방법

• 운영체제(OS) 차원이 아니라, 프로그래밍 언어에서 제공하는 동기화 방법

• 내부적으로 뮤텍스(Mutex)와 조건 변수(Condition Variable)를 사용하여 동기화 수행

• 여기부터

교착상태(데드락)

• 프로세스들이 서로가 가진 자원을 기다리면서 아무것도 실행되지 않는 상태

• 각 프로세스가 다른 프로세스의 작업이 끝나기를 기다리지만, 아무도 자원을 해제하지 않음

• 교착상태가 발생하려면 다음 4가지 조건이 모두 충족되어야 한다.

1. 상호배제: 자원은 한 번에 하나의 프로세스만 사용할 수 있어야 한다.

2. 비선점: 점유한 자원을 강제로 빼앗을 수 없다.

3. 점유와 대기: 이미 자원을 점유한 상태에서 추가적인 자원을 기다려야 한다.

4. 원형 대기: 프로세스들이 서로 다음 프로세스의 자원을 기다리는 원형 구조가 형성되어야 한다.

• 하지만 필요조건을 지켜도 교착상태는 발생한다는 것을 깨달았고, 교착상태를 예방하기보단 교착상태가 발생했을때 해결하는 방법을 찾으려고 했다.

교착상태 해결방안

교착상태 회피

• 프로세스들에게 자원을 할당할 때 어느정도 자원을 제공해야 교착상태가 발생하는지 파악해서 교착상태가 발생하지 않는 선에서 할당해주는 것

• 전체 자원의 수와 할당된 자원의 수를 비교해서 안정상태와 불안정 상태로 나눔

• 시스템의 총 자원과 각 프로세스간의 최대 요구자원을 계산해서 여유분의 자원을 남기고 프로세스에게 제공해야 안정상태를 유지할 수 있다.

교착상태 검출

• 가벼운 교착 상태 검출: 타이머를 이용해 프로세스가 일정시간 동안 작업을 진행하지 않으면 교착상태가 일어났다고 생각하고 해결함(해결 방법은 주기적으로 상황을 업데이트해서 만약 교착이라고 느끼면 롤백해서 이전으로 되돌아감)

• 무거운 교착 상태 검출: 자원 할당 그래프를 이용하며, 교착 상태를 발견하면(발견은 자원이 순환하면 교착상태임) 해결함.

• 해결방법은 교착상태를 인지하면 교착을 일으킨 프로세스를 강제종료하고 다시 실행할때 이전 업데이트로 롤백함.

컴파일 언어

• 소스 코드 전체를 한 번에 기계어(0과 1)로 변환한 후 실행하는 언어

• 속도가 빠름.

• 언어: C, C++, C# 등

컴파일에서 실행파일로 변환 과정

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

1⃣ test.c → 전처리기(Preprocessor) → test.i (주석 제거, 매크로 처리 등)
2⃣ test.i → 컴파일러(Compiler) → test.s (어셈블리 코드 생성)
3⃣ test.s → 어셈블러(Assembler) → test.o (목적 파일 생성)
4⃣ test.o → 링커(Linker) → test.exe (최종 실행 파일 생성)

인터프리터 언어

• 코드를 한 줄씩 읽고 실행하는 방식의 언어

• 컴파일 과정 없이 즉시 실행되지만, 실행 속도는 컴파일 언어보다 느림

• 언어: JS, Python, Ruby 등

메모리 종류

레지스터

• CPU 내부에 존재하는 가장 빠른 기억장소

• 매우 빠른 연산을 위해 사용되며, CPU가 직접 접근할 수 있음

• 휘발성(Volatile) 메모리 → 전원이 꺼지면 데이터가 사라짐

캐시

• 메인 메모리(RAM)와 CPU(레지스터) 사이에 위치하는 고속 메모리

• CPU가 자주 사용하는 데이터를 미리 저장하여 접근 속도를 높임

메인메모리(RAM)

• 운영체제(OS)와 실행 중인 프로그램이 올라가는 공간

• 휘발성 메모리

• 가격이 비싸기 때문에, 데이터 저장보다는 실행 중인 프로그램을 로드하는 용도로 사용

• HDD(하드디스크)나 SSD보다 훨씬 빠르지만, 레지스터나 캐시보다는 느림

보조저장장치(HDD,SSD)

• 가격이 저렴하며, 데이터를 영구적으로 저장하는 용도로 사용됨

• 비휘발성(Non-Volatile) 메모리 → 전원이 꺼져도 데이터가 유지됨

메모리 할당 방식

메모리 오버레이

• 프로그램이 메모리보다 클 경우, 실행에 필요한 부분만 메모리에 로드하는 방식

• 나머지 코드는 하드디스크에 저장되며, 필요할 때만 메모리에 불러옴

가변 분할 방식

• 프로세스 크기에 맞춰 메모리를 동적으로 분할하는 방식

• 외부단편화 발생: 여러 개의 작은 빈 공간이 생겨 새로운 프로세스를 할당하기 어려운 문제

고정 분할 방식

• 프로세스 크기와 상관없이 미리 정해진 크기로 메모리를 나누는 방식

• 장점: 구현이 간단하고 오버헤드가 적음

• 단점: 작은 프로세스는 큰 영역에 할당되서 공간이 낭비되는 내부단편화 발생

버디 세스템

• 가변 분할 방식과 고정 분할 방식을 혼합하여 단점을 최소화한 메모리 할당 방식

• 메모리를 2의 승수 크기로 분할하여 할당

2주차 회고

재귀가 너무 어렵다.. 정렬은 그래도 예전에 공부해본적이 있어서 한두번 더 보니까 이해가 되는데 재귀는 봐도봐도 이해가 어려움..

특히 하노이ㅋㅋㅋㅋ 새로운 벽이였다. 그래도 자주 보다보니 적응이 되는것 같기도 하고 아닌거 같기도하고,,,
그렇다 보니 미션 3번째 문제는 도무지 이해가 쉽지 않았다. 그래서 GPT의 도움과 함께 계속 이해해려하고 있고 지금도 하고있다,,ㅎ

그리고 2주차때는 중간점검을 통해 다같이 구글밋을 했다. 주 내용은 운영체제같은 CS지식이 있으면 다른 프레임워크나 컴퓨터 쪽의 지식을 쌓고 배울때 지식이 없는사람에 비해 더 빠르게 습득할 수 있고, 흡수하는게 빠르다고 했다. 벌써 다음주가 3주차라서 CS는 마지막 주 인데 마무리 잘해서 수료하고, 수료 이후에도 강의 반복해서 듣고 자료구조 & 알고리즘은 심화버전이 있어서 그걸 들어야 할 것 같다.