3주차 학습 내용 - 발자국

자료구조 & 알고리즘

삽입정렬

function InsertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let cnt = arr[i];
    let j;
    for (j = i - 1; j >= 0; j--) {
      if (arr[j] > cnt) {
        arr[j + 1] = arr[j];
      } else {
        break;
      }
    }
    arr[j + 1] = cnt;
  }
  return arr;
}

console.log(InsertionSort([4, 1, 5, 3, 6, 2]));

• 시간복잡도: O(N²)

• 이해와 구현이 간단하고 직관적,

  하지만 성능은 좋지 않아서 작은 데이터나 거의 정렬된 데이터에 적합

병합정렬

function MergeSort(arr, leftIndex, rightIndex) {
  if (leftIndex < rightIndex) {
    let midIndex = Math.floor((leftIndex + rightIndex) / 2);
    MergeSort(arr, leftIndex, midIndex);
    MergeSort(arr, midIndex + 1, rightIndex);
    Merge(arr, leftIndex, midIndex, rightIndex);
  }
}

function Merge(arr, leftIndex, midIndex, rightIndex) {
  let leftAreaIndex = leftIndex;
  let rightAreaIndex = midIndex + 1;

  let tempArr = new Array(arr.length).fill(0);

  let tempArrIndex = leftIndex;
  while (leftAreaIndex <= midIndex && rightAreaIndex <= rightIndex) {
    if (arr[leftAreaIndex] <= arr[rightAreaIndex]) {
      tempArr[tempArrIndex++] = arr[leftAreaIndex++];
    } else {
      tempArr[tempArrIndex++] = arr[rightAreaIndex++];
    }
  }

  while (leftAreaIndex <= midIndex) {
    tempArr[tempArrIndex++] = arr[leftAreaIndex++];
  }

  while (rightAreaIndex <= rightIndex) {
    tempArr[tempArrIndex++] = arr[rightAreaIndex++];
  }

  for (let i = leftIndex; i <= rightIndex; i++) {
    arr[i] = tempArr[i];
  }
}

let arr = [3, 5, 2, 4, 1, 7, 8, 6];

console.log("==== 정렬 전 ====");
console.log(arr);

MergeSort(arr, 0, arr.length - 1);

console.log("==== 정렬 후 ====");
console.log(arr);

• 시간복잡도: O(n log n)

• 재귀 기반 정렬이라 이해와 구현은 조금 어렵지만, 성능은 안정적이고 좋다.

퀵정렬

function quickSort(arr, left, right) {
  if (left < right) {
    let pivot = divide(arr, left, right);
    quickSort(arr, left, pivot - 1);
    quickSort(arr, pivot + 1, right);
  }
}

function divide(arr, left, right) {
  let pivot = arr[left];
  let leftStartIndex = left + 1;
  let rightStartIndex = right;

  while (leftStartIndex <= rightStartIndex) {
    while (leftStartIndex <= right && arr[leftStartIndex] <= pivot) {
      leftStartIndex++;
    }

    while (rightStartIndex >= left + 1 && arr[rightStartIndex] >= pivot) {
      rightStartIndex--;
    }

    if (leftStartIndex < rightStartIndex) {
      swap(arr, leftStartIndex, rightStartIndex);
    }
  }

  swap(arr, left, rightStartIndex);
  return rightStartIndex;
}

function swap(arr, index1, index2) {
  let temp = arr[index1];
  arr[index1] = arr[index2];
  arr[index2] = temp;
}

let arr = [5, 3, 7, 2, 6, 4, 9, 1, 8];

console.log("==== 정렬 전 ====");
console.log(arr);

quickSort(arr, 0, arr.length - 1);

console.log("==== 정렬 후 ====");
console.log(arr);

• 시간복잡도: 평균적으로 Θ(n log n)

• 재귀 기반 정렬이라 이해와 구현은 어렵게 느껴질 수 있지만, 실제로는 굉장히 빠르고 효율적인 정렬 알고리즘이다.

메모이제이션

function fibonacci2(n, memo) {
  if (n == 0 || n == 1) return n; // ✅ 기본 조건(Base Case)

  if (memo[n] == null) {
    // ✅ 이전에 계산된 값이 없으면 계산
    memo[n] = fibonacci2(n - 2, memo) + fibonacci2(n - 1, memo);
  }

  return memo[n]; // ✅ 저장된 값이 있으면 재사용
}

console.log(fibonacci2(5, {})); // ✅ 초기 memo 객체를 전달

• 한 번 계산한 값을 저장해두고, 같은 계산이 필요할 때는 다시 계산하지 않고 저장된 값을 재사용하는 기법

• 중복 계산을 줄여 알고리즘 속도를 최적화 함.

• 예제에서는 피보니치를 재귀로 구현하고 있음, 하지만 일반 재귀로는 불필요한 중복계산이 많아 효율이 좋지 않음.

• 그래서 n의 값에 따라 그 값을 기억하는 memo를 만들어서 n이 실행될때 이전에 저장한게 있으면 바로 값 대입함.

   

타뷸레이션

function fibonacci3(n) {
  if (n <= 1) return n;

  let table = [0, 1];

  for (let i = 2; i <= n; i++) {
    table[i] = table[i - 2] + table[i - 1];
  }
  return table[n];
}

console.log(fibonacci3(5));

• 타뷸레이션은 하향식인 재귀 방식이 아니라, 상향식으로 배열을 채워나가는 방식이다.

• 아무래도 재귀보다 코드가 직관적이고, 이해하기 쉽다.

   

• 타뷸레이션은 재귀 없이도 효율적인 풀이가 가능한 방식이라, 초보자에게 훨씬 부담이 적고 실전에서도 유용하다고 느꼈다.

운영체제

가상 메모리

• 운영체제가 물리적 메모리(RAM)가 부족할 때, 하드디스크(또는 SSD)를 이용하여 추가적인 메모리를 제공하는 기술

• RAM이 부족하면 일부 데이터를 디스크(하드디스크, SSD)에 저장했다가 필요할 때 다시 불러오는 방식

페이지 폴트: 프로그램이 필요한 데이터를 RAM에서 찾지 못할 때 발생하는 현상 -> 운영체제가 디스크에서 해당 데이터를 RAM으로 불러오는 작업을 수행

스왑 영역: 물리 RAM이 부족할 때, 디스크의 일부를 메모리처럼 사용하는 영역

세그멘테이션

• 프로그램을 논리적인 단위(세그먼트)로 나누어 메모리를 할당하는 방식

• 동작 방식

  • 프로그램이 메모리를 요청하면 운영체제는 세그먼트 번호를 할당함.

  • 세그먼트 테이블을 참고하여, 해당 세그먼트의 시작 주소를 찾음.

  • 세그먼트 시작 주소 + 오프셋(offset)을 더하여 실제 메모리 주소를 계산함.

• 장점: 내부 단편화 X, 메모리를 논리적 단위로 관리 가능

• 단점: 외부 단편화O

페이징

• 메모리를 "고정된 크기(페이지 단위)"로 나누어 관리하는 메모리 할당 기법

• 프로세스를 작은 단위(페이지)로 나누어 메모리에 배치

• 동작 방식

  • 프로그램이 실행되면, 프로세스를 동일한 크기의 페이지로 나눔.

  • 메모리도 같은 크기의 프레임으로 나누고, 각 페이지를 빈 프레임에 적재.

  • CPU가 메모리에 접근할 때, 페이지 테이블을 이용하여 페이지 번호 → 프레임 번호로 변환.

• 장점: 외부 단편화 없음, 메모리를 효율적으로 사용 가능

• 단점: 내부 단편화 발생, 페이지 테이블을 계속 참조해야 해서 오버헤드 존재

세그멘테이션 vs 페이징

• 둘 중에 뭐가 더 좋다, 이렇게 단정 짓긴 어려움. 결국 사용 목적과 상황에 따라 선택하면 됨.

• 세그멘테이션

  • 프로그램이 서로 다른 크기의 논리적 블록(세그먼트)으로 나뉘어 있을 때 유리함

  • 함수, 배열, 변수 등 논리 단위로 나뉘는 구조에 적합

  • 유연하게 메모리를 할당하고 싶을 때 사용하기 좋음

• 페이징

  • 메모리를 고정된 크기(페이지 단위)로 균등하게 나눔

  • 운영체제에서 일괄적으로 메모리를 관리하고 싶을 때 적합

  • 외부 단편화가 더 신경 쓰이는 경우 페이징이 더 효과적임ㅍ

페이지 세그멘테이션

세그멘테이션 + 페이징의 장점을 섞은 방식

• 세그먼트마다 다시 페이지 단위로 쪼갬

• 논리적으로는 세그먼트로 구분하고, 물리적으로는 페이지처럼 관리함

• 단점도 줄이고, 장점도 살리는 구조

디맨드 페이징

실제로 필요한 페이지만 메모리에 올리는 방식

• 프로그램 실행 시, 전체를 메모리에 올리지 않고 조만간 필요할 것 같은 페이지만 로딩

• 나머지 페이지는 스왑 영역(보조 기억장치)에 남겨둠

• 실제 사용될 때만 메모리에 적재 → 효율적인 메모리 사용

지역성 이론

프로그램이 실행될 때 특정 메모리 영역에 집중적으로 접근하는 성질을 지역성이라고 한다.

공간의 지역성: 현재 위치와 가까운 데이터에 접근할 확률이 높음

• ex) 배열이나 함수 코드처럼 서로 인접한 메모리 위치를 차례로 접근하는 경우

• 이 특성을 기반으로, 근처 데이터까지 한 번에 메모리에 올려두고, 필요 없어 보이는 데이터는 스왑 영역으로 보내서 성능을 높이는 방식이 사용됨

시간의 지역성: 최근 접근했던 데이터가 오래 전에 접근했던 데이터보다 접근할 확률이 높음

• ex) 방금 쓴 변수나 반복문에서 쓰인 코드들이 다시 사용되는 경우

• 이 특성을 활용해서, 캐시나 페이지 교체 알고리즘에서 최근 사용 여부를 판단하는 데 쓰임

페이지 교체 정책

• 프로세스가 어떤 데이터를 사용하려고 할 때, 그 데이터가 메모리에 없다면 스왑 영역(디스크)에서 가져와야 한다.

• 근데 메모리 공간이 꽉 차 있다면, 기존에 있던 데이터를 하나 꺼내고, 새 데이터를 그 자리에 넣어야 함.

• 이때 어떤 데이터를 꺼낼지 정하는 기준이 바로 페이지 교체 정책이다.
  

1. 무작위로 선택하는 방법

• 지역성을 전혀 고려하지 않기 때문에, 자주 쓰는 데이터가 교체될 수 있어서 성능이 안 좋음

• 하지만 구현은 제일 간단함
  

2. 메모리에서 가장 오래된 페이지를 선택하는 방법(FIFO)

• 자주 쓰는 페이지라도 먼저 들어왔다는 이유로 교체될 수 있음

• 단점은 있지만, 구현이 쉬워서 변형을 거쳐 실제로 많이 사용됨
  

3. 앞으로 가장 오랫동안 쓰이지 않을 페이지를 선택하는 방법(Optimum)

• 이론적으로 가장 완벽한 방식이지만,

  미래를 예측할 수 없기 때문에 실제 구현은 불가능함

• 다른 알고리즘과 성능 비교할 때 기준점으로 사용함
  

4. 최근에 가장 사용이 적은 페이지를 선택하는 방법(LRU)

• 최근에 사용된 데이터를 우선적으로 보존하는 방식이라 지역성에 잘 맞음

• 단점은, 언제 사용됐는지를 추적하기 위해 시간 정보나 카운터, 비트 등이 필요함 → 구현이 복잡하고 성능 부담이 생길 수 있음

• 시간이 지나면 오버플로우 문제도 발생 가능
  

5. Clock Algorithm

• LRU의 단점을 보완한 방식

• 각 페이지에 참조 비트를 붙이고,

  일정 시간마다 비트를 확인하며 시계 방향으로 스캔

• 참조되지 않은 페이지를 교체하고, 참조된 페이지는 기회를 한 번 더 줌

• 구조는 단순하고 성능도 괜찮아서 실제 운영체제에서 자주 사용됨

6. 2차 기회 페이지 교체 알고리즘

• FIFO의 단점을 개선한 방식

• FIFO는 자주 쓰는 페이지라도 먼저 들어왔으면 교체됨 → 이걸 해결함

• 페이지가 교체 대상이 되었는데 최근 사용된 페이지라면, 그 페이지를 맨 뒤로 보내고 한 번 더 기회를 주는 방식

• 간단하면서도 성능이 괜찮은 알고리즘

스레싱

• 프로세스들이 계속 스왑만 하느라 정작 일은 못 하는 상태

• 멀티프로그래밍 수준을 너무 높이면, 한정된 메모리를 너무 많은 프로세스가 나눠 쓰게 된다.

• 이때 필요한 페이지가 자꾸 메모리에 없어서, 운영체제는 디스크와 메모리 사이에서 페이지를 계속 교체(스왑) 하게 된다.

• 결과적으로 CPU는 일은 안 하고, I/O 대기만 계속하면서 놀게 된다.

주변 장치

• 그래픽 카드, HDD, SDD, 키보드, 마우스 등 컴퓨터 외부와 연결되는 장치들을 말함.

캐릭터 디바이스

• 마우스, 키보드, 사운드카드 등

• 데이터 전송 단위가 '문자 단위(캐릭터)'로 상대적인 크기가 작다

블록 디바이스

• HDD, SSD, 그래픽카드 등

• 데이터 전송 단위가 '블록 단위(범위)'로 상대적인 크기가 크다

입출력 제어기

• 예전에는 주변 장치를 CPU가 직접 관리했기 때문에, I/O 명령을 만나면 CPU가 멈춰버리고 입출력이 끝날 때까지 기다려야 했음 → 비효율적

  이걸 보완하기 위해 입출력 제어기가 생김.

• 이제는 I/O 명령을 만나면, 제어기가 입출력 작업을 대신 맡고, CPU는 다른 작업을 계속 실행할 수 있게 됨 → CPU 사용률이 올라감

3주차 회고

벌써 3주차가 되어버렸다..

이번 주는 뭔가 유독 어렵게 느껴졌다.
아무래도 점점 이전 강의 위에 지식이 쌓여가다 보니, 강의를 봐도 이해가 잘 안 되는 순간들이 많았다.
그래서 같은 영상을 계속 반복해서 보면서 겨우겨우 따라갔던 것 같다.

특히 재귀는 진짜 어렵다.
자주 보려고는 하지만, 어렵다 보니 손이 잘 안 간다… 하하
(타뷸레이션 짱😀)

3주 전, 아무것도 모르던 나는 그냥 "CS 한 번 배워보자!"는 마음으로 신청했었다.
그런데 막상 3주 동안 공부하면서 내가 몰랐던 걸 많이 알게 됐고,
동시에 더 꾸준히 공부해야겠다는 자극도 받았다.

코드를 직접 치고, 프레임워크나 기술을 익히는 것도 물론 중요하지만,
이런 이론적인 부분(CS)도 기초 체력을 길러주는 느낌이라 꼭 필요하다고 생각하게 됐다.

아마 완주 포인트를 받으면… 감자님의 알고리즘 상버전을 결제하러 가지 않을까 싶다 😎

이 강의를 듣고 싶거나, 워밍업 클럽에 참여할까 고민 중이라면 망설이지 말고 그냥 해보는 걸 추천한다.
나는 CS 강의는 처음이라 다른 강의랑 비교할 순 없지만,
지금까지는 충분히 만족이다.

그리고 솔직히 말해서, 워밍업 클럽이 아니었다면 3주 동안 완강 못 했을 거다.
혼자였다면 진작에 놓았을지도…

 

 

 

마지막으로 우리 모두 파이팅! 🔥🔥