inflearn logo
강의

강의
N
챌린지

챌린지
멘토링

멘토링
N
클립

클립
로드맵

로드맵
지식공유

인프런 워밍업 클럽 3기 CS - 3주차 발자국

찬우 이
1

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]));

병합정렬

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

 

퀵정렬

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

 

 

메모이제이션

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 객체를 전달

 

타뷸레이션

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에서 찾지 못할 때 발생하는 현상 -> 운영체제가 디스크에서 해당 데이터를 RAM으로 불러오는 작업을 수행
스왑 영역: 물리 RAM이 부족할 때, 디스크의 일부를 메모리처럼 사용하는 영역

 

세그멘테이션

페이징

 

세그멘테이션 vs 페이징

페이지 세그멘테이션

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

 

디맨드 페이징

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

 

지역성 이론

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

 

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

 

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

 

페이지 교체 정책

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

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

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

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

5. Clock Algorithm

 

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

 

스레싱

주변 장치

캐릭터 디바이스
블록 디바이스
입출력 제어기

 

3주차 회고

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

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

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

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

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

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

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

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

 

 

 

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

자료구조 알고리즘 운영체제 인프런워밍업클럽 CS

답변 0