inflearn logo
강의

강의
N
챌린지

챌린지
멘토링

멘토링
N
클립

클립
로드맵

로드맵
지식공유

[인프런 워밍업 클럽 스터디 3기 - CS전공지식] 3주차 발자국

이태경
1

운영체제

가상메모리 개요

세그멘테이션(배치정책)

페이징(배치정책)

페이지드 세그멘테이션(배치정책)

페이지 교체 정책

스레싱과 워킹셋

주변장치(I/O디바이스와 저장장치)

마우스와 키보드

하드디스크와 플래쉬메모리

파일과 파일 시스템

디렉토리

파일과 디스크

자료구조와 알고리즘

정렬 - 삽입정렬

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

let arr = [4, 1, 5, 3, 6, 2];
console.log("===== 정렬전 =====");
console.log(arr);

InsertionSort(arr);

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

정렬 - 병합정렬

function MergeSort(arr, leftIndex, rightIndex) {
    // leftIndex가 0, rightIndex가 7로 가정,
    if (leftIndex < rightIndex) { // 기저 조건 ⇒ 배열의 원소가 1개일 때까지 분할하기 위함
        // 0 < 7 참
        let midIndex = parseInt((leftIndex + rightIndex) / 2); // 3
        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 = [];
    tempArr.length = rightIndex + 1;
    tempArr.fill(0, 0, rightIndex + 1);
  
    let tempArrIndex = leftIndex;
    
    while (leftAreaIndex <= midIndex && rightAreaIndex <= rightIndex) {
        if (arr[leftAreaIndex] <= arr[rightAreaIndex]) {
            tempArr[tempArrIndex] = arr[leftAreaIndex++];
        } else {
            tempArr[tempArrIndex] = arr[rightAreaIndex++];
        }
        tempArrIndex++;
    }

    if (leftAreaIndex > midIndex) {
        // 만약 오른쪽 배열 병합이 덜 끝났으면,
        for (let i = rightAreaIndex; i <= rightIndex; i++) {
            tempArr[tempArrIndex++] = arr[i];
        }
    } else {
        // 만약 왼쪽 배열 병합이 덜 끝났으면,
        for (let i = leftAreaIndex; i <= midIndex; i++) {
            tempArr[tempArrIndex++] = arr[i];
        }
    }
    
    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 && pivot >= arr[leftStartIndex]) { // 왼쪽 영역의 작은값인지 확인
            leftStartIndex++;
        }

        while (rightStartIndex >= left + 1 && pivot <= arr[rightStartIndex]) { // 오른쪽 영역의 큰값인지 확인
            rightStartIndex--;
        }

        if (leftStartIndex <= rightStartIndex) {
            // 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);

동적 프로그래밍 - 메모이제이션

// 메모이제이션 적용 전 -> O(n2)
function fibonacci1(n) {
    if (n === 0 || n === 1) return n;
    return fibonacci1(n - 2) + fibonacci1(n - 1);
}

// 메모이제이션 적용 후 -> O(n)
function fibonacci2(n, memo) {
    if (n === 0 || n === 1) return n;

    if (memo[n] == null) {
        memo[n] = fibonacci2(n - 2, memo) + fibonacci2(n - 1, memo);
    }

    return memo[n];
}

동적 프로그래밍 - 타뷸레이션

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

    let table = [0, 1];

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

    return table[n];
}

회고

인프런워밍업클럽스터디3기 CS전공지식

답변 0