인프런 워밍업 클럽 CS 2기 - 3주차 발자국
자료 구조 및 알고리즘 삽입 정렬배열을 정렬된 부분, 정렬되지 않은 부분 총 두 영역으로 나누어, 정렬되지 않은 부분에서 데이터를 하나씩 꺼내어 정렬된 부분에 삽입하는 정렬 알고리즘이다.시간 복잡도는 O(n²)이다.function insertionSort (arr) { for (let i=1; i<arr.length; i++) { const memoried = arr[i]; let j; for (j=i-1; j>=0; j--) { if (arr[j] > memoried) arr[j+1] = arr[j]; else break; } arr[j+1] = memoried; } return arr; } console.log(insertionSort([4,1,3,5])) // [1,3,4,5] 병합 정렬병합 정렬은 분할 정복을 이용하여 재귀적으로 정렬하는 알고리즘이며, 배열을 반으로 분할하고 다시 병합한다.분할은 log n, 병합할 때 비교는 n이 걸리므로, 시간 복잡도는 O(n log n)이다.function mergeSort(arr) { if (arr.length <= 1) return arr; const mid = Math.floor(arr.length / 2); const leftArr = mergeSort(arr.slice(0, mid)); const rightArr = mergeSort(arr.slice(mid)); const sorted = []; let left = 0; let right = 0; while (left < leftArr.length && right < rightArr.length) { if (leftArr[left] < rightArr[right]) { sorted.push(leftArr[left]); left++; } else { sorted.push(rightArr[right]); right++; } } while (left < leftArr.length) { sorted.push(leftArr[left]); left++; } while (right < rightArr.length) { sorted.push(rightArr[right]); right++; } return sorted; } console.log(mergeSort([3,5,2,4,1,7,8,6])) 퀵 정렬병합 정렬은 분할 정복을 이용하여 재귀적으로 정렬하는 알고리즘이며, 배열에서 하나의 숫자를 '피벗'으로 선택한 뒤 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할 다시 병합한다.시간복잡도의 평균은 O(n log n)이지만, 피벗에 따라 O(n²) 일 수도 있다.퀵 정렬은 병합 정렬보다 더 적은 메모리와 비교하는 횟수가 더 적어서 효율적인 경우가 있다.function quickSort (arr, left = 0, right = arr.length - 1) { if (left < right) { const pivotIndex = partition(arr, left, right); quickSort(arr, left, pivotIndex - 1); quickSort(arr, pivotIndex + 1, right); } return arr; } function partition (arr, left, right) { const pivot = arr[left]; let low = left + 1; let high = right; while (low <= high) { while (low <= high && arr[low] < pivot) { low++ } while (low <= high && pivot < arr[high]) { high--; } if (low < high) { [arr[low], arr[high]] = [arr[high], arr[low]]; } } [arr[left], arr[high]] = [arr[high], arr[left]]; return high; } console.log(quickSort([3,5,2,4,1,7,8,6])) // [ 1, 2, 3, 4, 5, 6, 7, 8 ] 동적 프로그래밍 - 메모이제이션재귀 함수는 중복된 계산을 여러 번 수행하여 성능이 좋지 않다.메모이제이션은 계산된 값을 저장하고 이를 다시 사용하여 성능을 높일 수 있다.function fibonacci(n ,memo = {}) { if (n <= 1) return n; if (!memo[n]) { memo[n] = fibonacci(n - 2, memo) + fibonacci(n - 1, memo) } return memo[n] } console.log(fibonacci(5)) 동적 프로그래밍 - 타뷸레이션타뷸레이션은 상향식 접근 방식으로, 필요하지 않는 결과값도 계산하여 재귀를 사용하지 않기 때문에 메모제이션보다 더 빠를 수 있다.특히 재귀적이지 않기 때문에 메모리를 절약할 수 있다.function fibonacciTabulation(n) { const table = [0, 1] for (let i=2; i<=n; i++) { table[n] = fibonacciTabulation(n - 2) + fibonacciTabulation(n - 1) } return table[n] } console.log(fibonacciTabulation(5)) 미션1지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.버블 정렬장점: 구현이 간단하고, 이미 정렬된 경우 시간 복잡도가 O(n)이다.단점: 평균 및 최악의 경우 시간 복잡도가 O(n²)이다.시간 복잡도:최선: O(n)평균: O(n²)최악: O(n²)선택 정렬장점: 구현이 간단하다.단점: 항상 시간 복잡도가 O(n²)이다.시간 복잡도:최선: O(n²)평균: O(n²)최악: O(n²)삽입 정렬장점: 작은 데이터 집합에 대해 빠르게 동작하며, 안정적인 정렬 알고리즘이다.단점: 평균 및 최악의 경우 시간 복잡도가 O(n²)이다.시간 복잡도:최선: O(n)평균: O(n²)최악: O(n²)병합 정렬장점: 분할 병합 방식으로 시간 복잡도가 O(n log n)이다.단점: 추가적인 메모리 공간이 필요하여, 공간 복잡도가 O(n)이다.시간 복잡도:최선: O(n log n)평균: O(n log n)최악: O(n log n)퀵 정렬장점: 분할 병합 방식으로 O(n log n)의 시간 복잡도를 가지고, 메모리 사용이 효율적이다.단점: 최악의 경우 O(n²)이다.시간 복잡도:최선: O(n log n)평균: O(n log n)최악: O(n²)메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.타뷸레이션을 선택할거 같습니다.메모이제이션의 경우 재귀적으로 함수를 호출하기 때문에 함수를 생성하면 메모리를 차지하고, 함수가 종료되기 전까지 점유합니다. 반면에 타뷸레이션의 경우 재귀적으로 함수를 호출하지 않기 때문에 하나의 함수에 해당되는 메모리만 차지하기 때문에 메모리가 부족한 시스템에 더 적합합니다. 운영체제 및 CS 가상메모리물리메모리의 크기보다 프로세스가 요구하는 메모리 크기가 클 경우에 보조저장장치의 스왑 영역을 활용하여 메모리의 크기를 늘리는데, 물리메모리 + 스왑영역을 합쳐서 가상메모리라고 부른다.만약 CPU의 비트가 32bit인 경우, 가상메모리의 크기는 4GB까지 가능하다. 메모리 관리자는 프로세스가 메모리의 논리주소를 요구할 경우 물리 메모리의 물리주소를 전달해주는데, 이를 동적 주소 변환이라고 한다.메모리 관리자가 매핑 테이블을 이용하여 논리주소를 물리주소로 변환할 수 있다. 세그먼테이션(배치 정책)프로세스에 메모리를 할당해주는 배치 정책 중 가변적으로 메모리를 할당해준다고 해서 세그먼테이션이라고 한다. 메모리 관리자는 논리주소를 세그먼테이션 테이블에서 물리주소로 변환할 수 있는 정보를 가지고 물리주소로 변환한다.세그먼테이션 테이블에는 세그먼트 번호, Base Address, Bound Address 가 있다. 논리주소를 물리주소로 변환하는 과정프로세스가 논리주소를 요청할 때, 메모리관리자는 세그먼트 번호를 찾아낸다.메모리 관리자는 Segment Table Base Register를 이용해 물리메모리에 있는 세그먼테이션 테이블을 찾는다.세그먼테이션 테이블에서 세그먼테이션 번호와 일치되는 행의 정보를 얻는다.Bound Address보다 논리주소가 클 경우 메모리 침범 인터럽트를 발생시켜 프로그램을 종료시키고, 크지 않을 경우 Base Address + 논리 주소를 합쳐 물리주소를 변환하여 프로세스에게 전달한다. 세그멘테이션은 메모리를 가변적으로 분할 할 수 있고, 코드영역, 힙영역, 데이터영역, 스택 영역 등을 모듈로 관리할 수 있어 메모리 접근 보호가 편리한 장점이 있다.반면, 외부 단편화가 발생하기 때문에 분할되어 있는 메모리의 공간보다 큰 메모리를 요구하는 프로세스가 있는 경우, 메모리 공간을 합쳐여하는 오버헤드가 발생하는 단점이 있다. 페이징(배치 정책)프로세스에 메모리를 할당해주는 배치 정책 중 고정적으로 메모리를 할당해준다고 해서 페이징이라고 한다. 논리 주소 공간에서 페이징은 페이지라고 불리고, 물리 주소 공간에서 페이징은 프레임이라고 불린다. 메모리 관리자는 논리주소를 페이지 테이블에서 물리주소로 변환할 수 있는 정보를 가지고 물리주소로 변환한다.페이지 테이블에는 인덱스, 프레임이 있다. 논리주소를 물리주소로 변환하는 과정프로세스가 논리주소를 요청할 때, 메모리관리자는 인덱스와 오프셋을 구한다.인덱스는 (논리주소 / 페이지 크기)의 몫오프셋은 (논리주소 / 페이지 크기)의 나머지메모리 관리자는 Page Table Base Register를 이용해 물리메모리에 있는 페이지 테이블을 찾는다.세그먼테이션 테이블에서 세그먼테이션 번호와 일치되는 행의 정보를 얻어 프레임을 얻는다.프레임의 물리주소과 오프셋을 합산하여 실제 물리주소를 계산하여 프로세스에게 물리주소를 전달한다. 페이징은 메모리를 세그먼테이션보다 쉽게 구현할 수 있는 장점이 있다.반면, 내부단편화가 발생하기 때문에 낭비되는 메모리 공간이 발생하고, 코드영역, 힙영역, 데이터영역, 스택 영역 등을 메모리에 할당해야하기 때문에 논리적으로 분할 할 수 없고, 메모리 접근 보호가 어려우며, 프로세스가 많아지면 페이지 테이블이 많아지고 메모리 공간을 차지 하기 때문에 사용자 메모리 공간이 줄어드는 단점이 있다. 페이지드 세그멘테이션(배치 정책)세그멘테이션과 페이지의 혼합한 배치정책이다. 메모리 관리자는 논리주소를 페이지드 세그멘테이션 테이블에서 물리주소로 변환할 수 있는 정보를 가지고 물리주소로 변환한다.페이지드 세그멘테이션은 2개의 테이블을 가지는데, 세그멘테이션 테이블과 페이지 테이블이다.세그멘테이션 테이블은 세그먼트번호, 권한비트, 페이지넘버, Bound Address를 가진다.페이지 테이블은 인덱스, 프레임을 가진다. 메모리 접근권한은 읽기, 쓰기, 실행 권한이 있다.프로세스의 영역별 권한은 아래와 같다.코드 영역: 읽기와 실행 가능, 수정 불가데이터 영역: 읽기와 쓰기 가능, 실행 불가능스택 & 힙 영역: 읽기와 쓰기 가능, 실행 불가능 페이지드 세그멘테이션에서 논리주소를 물리주소로 변환할 때 권한도 확인한다. 논리주소를 물리주소로 변환하는 과정프로세스가 논리주소를 요청할 때, 메모리관리자는 세그멘테이션 번호를 찾아낸다.세그먼테이션 테이블에서 세그먼테이션 번호와 일치되는 행의 정보를 얻어 권한이 위반하면 인터럽트를 발생시켜 프로그램을 종료시키고, 위반하지 않으면 페이지넘버와 페이지 개수를 얻는다.페이지 테이블에서 접근한 페이지 넘버와 일치되는 행의 프레임을 얻는다.프레임과 페이지 개수를 합산한 물리 주소를 프로세스에 전달한다. 테이블을 확인하기 위해 메모리에 2번 접근해야하는 단점이 있어 현대에서는 페이징과 페이지드 세그멘테이션을 적절하게 사용하고 있다. 디멘드 페이징(가져오기 정책)메모리에 사용할것 같은 프로세스를 메모리에 올리고, 그렇지 않은 프로세스는 스왑영역에 위치시켜 메모리를 효율적으로 사용하는 정책이다. 지역성 이론시간적 지역성: 최근에 접근한 데이터는 다시 접근할 가능성이 높다.공간적 지역성: 현재 접근한 데이터와 가까운 위치에 있는 데이터가 곧 접근될 가능성이 높다. 스왑영역에서 메모리로 가져오는 것을 스왑인, 반대로 메모리에서 스왑영역으로 내보내는 것을 스왑아웃이라고 한다. 페이지 테이블의 한 행을 페이지 엔트리(PTE)라고 불리고, 여러 비트를 통해 물리메모리의 프레임 또는 스왑영역의 위치를 알 수 있다.접근 비트: 페이지가 메모리에 올라온 후 접근 유무변경 비트: 페이지 데이터의 변경 유무유효 비트: 페이지가 물리 메모리에 있는지 스왑 영역에 있는지 유무(1은 스왑영역에 있다는 뜻)읽기/쓰기/실행 비트: 페이지에 대한 접근 권한 Page Fault프로세스가 가상주소를 요청하고 메모리 관리자가 페이지 테이블을 통해 프레임이 물리 메모리에 없으면 Page Fault 인터럽트가 발생한다.그리고 프로세스는 대기 상태에 들어가고, 메모리 관리자는 스왑인을 통해 물리 메모리에 프레임을 옮기고 다시 재시작된다. 페이지 교체 정책메모리 공간이 부족할 때 어떤 페이지를 스왑 영역으로 보낼지 결정하는 중요한 알고리즘이다. 주요 페이지 교체 정책1. Random- 페이지를 랜덤으로 교체한다.- 지역성 이론을 고려하지 않고 자주 사용되는 페이지도 보낼 수 있기 때문에 거의 사용되지 않는다.2. FIFO(First In First Out)- 가장 먼저 메모리에 들어온 페이지 교체한다.- 구현이 간단하지만 자주 사용되는 페이지도 교체될 수 있다.3. Optimum- 앞으로 오랫동안 사용되지 않을 페이지 교체한다.- 이상적인 알고리즘이나 구현하기 어렵다.4. LRU(Least Recently Used)- 가장 최근에 사용되지 않은 페이지 교체한다.- 최근 사용된 페이지가 다시 사용될 확률이 높다는 가정에 따라 동작한다.LRU를 유사하게 구현하기 위한 알고리즘1. Clock Algorithm페이지 테이블의 접근 비트를 사용하여, 일정 시간 동안 참조된 페이지인지 아닌지 확인한다.클락 핸드가 시계 방향으로 움직이며, 접근 비트가 0인 페이지를 교체한다.Enhanced Clock Algorithm은 변경 비트까지 고려한다.2. Second Chance AlgorithmFIFO 방식의 문제점을 보완하여 맨 처음 페이지가 최근에 사용된 경우 큐의 맨 뒤로 이동시켜 수명 연장한다.스레싱과 워킹셋스레싱은 CPU 사용률이 떨어지는 현상이다.Page Falut가 발생하면 CPU 사용하는 것보다 스왑인, 스왑아웃 동작하는데 자원을 소모하여 CPU 사용률이 떨어지고, 그렇다고 메모리에 페이지를 많이 올리게 되면 프로세스가 사용해야할 페이지가 줄어들어 CPU 사용률이 떨어진다. 워킹셋(Working Set)현재 메모리에 올라와 있는 페이지는 자주 사용할 확률이 높기 때문에 하나의 세트로 묶는데 이를 워킹셋이라고 한다.프로세스가 준비상태에서 컨텍스트 스위칭을 통해 실행상태로 변경할 때 사용한다.주변장치(I/O, 디바이스, 저장장치)그래픽카드, 마우스, 키보드, 하드디스크 등을 주변장치라고 한다. 주변장치는 메인보드의 버스를 통해 연결되고, Address 버스, data 버스, control 버스가 있다.주변장치의 레지스터는 입출력 데이터를 저장하는 역할을 한다. 주변장치는 캐릭터 디바이스, 블록 디바이스로 나뉜다.캐릭터 디바이스는 적은 양의 데이터(문자)를 전송하는 장치로, 마우스나 키보드가 있다.블록 디바이스는 많은 양의 데이터를 전송하는 장치로, 하드디스크가 있다.초기에는 CPU가 I/O 요청을 대기해야해서 CPU 사용률이 떨어졌고, 이를 해결하기 위해 입출력 제어기가 도입되어 I/O 작업을 CPU 대신 관리한다.입출력 제어기는 CPU와 메모리를 연결하는 시스템 버스, 주변장치를 연결하는 입출력 버스로 구성되어 있다.그래픽카드는 빠른 속도를 위해 시스템 버스에 연결한다.입출력 버스는 고속과 저속으로 나뉘는데, 고속은 하드디스크과 연결하고 저속은 마우스, 키보드와 연결한다.입출력 데이터를 저장하기 위해서 CPU 도움이 필요한데, DMA 를 통해 CPU 도움없이 주변장치가 메모리에 접근가능하다.CPU로 접근하는 메모리와 DMA로 접근하는 메모리는 다른데, DMA로 접근하는 메모리는 Memory Mapped I/O 라고 한다.마우스, 키보드볼 마우스는 잔 고장이 많았다.광학 마우스는 마우스 아래에 달린 카메라를 통해 1500회 이상을 사진으로 촬영해 마우스 좌표값을 얻는다.마우스 이벤트 전달마우스의 디바이스 컨트롤러의 DSP를 통해 좌표값을 얻는다.마우스 드라이버가 DSP에서 좌표값을 가져간다.마우스 드라이버가 CPU에 인터럽트를 보내고, 좌표 데이터 또는 클릭 이벤트를 전달해준다.운영체제가 Foreground로 프로세스에게 이벤트를 전달해준다.키보드도 마우스와 유사하게 사용자가 입력한 키를 디바이스 컨트롤러가 감지해 CPU로 인터럽트를 보내고, 운영체제가 Foreground로 프로세스에게 이벤트를 전달해준다. 하드디스크하드디스크는 Spindle이 있고, 여러개의 Platter가 있다.Platter는 disk arm에 달린 read/write head를 통해 읽고 쓰며, 자성을 띄기 때문에 N극은 0 S극은 1이다.여러개의 Platter에 track이 같은 위치에 있는 것을 Cylinder라고 한다.Sector는 하드디스크의 가장 작은 단위이다.하드디스크는 헤드를 통해 읽고, 데이터를 읽는 시간을 Seek Time이라고 한다.헤드를 통해 데이터를 찾기 때문에 찾는 시간이 오래걸린다. SSD는 HDD와 달리 물리적으로 데이터를 읽는 것이 아니라 전기적으로 읽고 쓰기 때문에 빠르고, 조용하다. 파일과 파일시스템파일은 사용자가 운영체제에 관리를 요청하면, 운영체제는 파일시스템을 통해 파일을 관리한다. 파일 시스템은 아래의 기능을 제공한다.파일 및 디렉토리 생성,수정, 삭제파일 접근 권한 관리데이터 무결성 보장백업 및 복구암호화파일은 블록 디바이스인데, 사용자가 바이트 단위로 읽으려면 파일 시스템을 통해 읽을 수 있다.파일의 정보는 FCB가 있는데 FCB를 통해 사용자는 시스템 콜인 open(), close() 함수를 통해 파일을 열고 닫을 수 있다. 순차 파일 구조는 카세트 테이프처럼 데이터가 연속적으로 저장되는 구조이며 구조가 단순하여 공간 낭비가 적다. 만약 특정 위치로 이동하려면 lseek() 시스템 콜 함수를 통해 접근할 수 있고, 이는 단점으로 데이터 수정 및 삭제하는데 시간이 오래걸린다.직접 파일 구조는 해시 함수를 이용해 데이터를 저장하는 방식으로, 해시 함수에 따라 성능에 영향을 준다.인덱스 파일 구조: 순차 접근과 직접 접근의 장점을 결합한 방식으로, 인덱스 테이블을 이용해 빠른 접근이 가능하다. 디렉토리파일은 데이터를 갖고 있고, 디렉토리는 파일 정보를 갖고 있는 파일이다. 파일과 디스크파일이 저장될 때, 디스크는 일정 크기로 나뉜 블록으로 데이터를 저장한다.데이터 저장방식은 연속할당, 불연속할당이 있다.연속 할당은 연속적으로 데이터를 저장하며 외부 단편화가 발생한다.불연속 할당은 분산하여 데이터를 저장하며 내부 단편화가 발생한다.연결 할당은 연결 리스트 자료구조로 데이터를 연결하여 접근한다.인덱스 할당은 별도의 인덱스 블록을 통해 데이터에 접근한다. 파일시스템은 비어있는 블록을 별도로 관리하는데, 이를 free block list라고 한다.파일을 삭제할 때 실제 파일이 삭제되는 것이 아니라, 파일의 헤더만 삭제하고 사용했던 블록을 free block list에 추가한다.그래서 포렌식으로 데이터를 복구할 때 실제 데이터는 존재하기 때문에 복구가 가능하다. 미션2메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.레지스터CPU가 처리하기 위해 메인메모리에 있는 값을 레지스터로 가져와 계산을 하고, 결과값을 메인메모리에 저장한다. 레지스터는 CPU에 존재한다.전력이 끊기면 데이터가 사라지는 휘발성 메모리이다.캐시메인메모리의 있는 값을 레지스터로 가지고 올 때, 성능을 위해 미리 값을 가져온다.캐시는 CPU에 L1, L2, L3... 등으로 존재한다.전력이 끊기면 데이터가 사라지는 휘발성 메모리이다.메인메모리(RAM)운영체제나 프로세스가 올라가는 공간이다.전력이 끊기면 데이터가 사라지는 휘발성 메모리이다.보조저장장치(HDD, SDD)전력이 끊겨도 데이터가 유지되는 비휘발성 메모리이다.파일, 데이터를 저장하는 공간이다. 가격 : 레지스터 > 캐시 > 메인메모리 > 보조저장장치용량 : 레지스터 < 캐시 < 메인메모리 < 보조저장장치속도 : 레지스터 > 캐시 > 메인메모리 > 보조저장장치사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?경계 레지스터메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요? 가변 분할 방식 장점은 낭비되는 메모리 공간이 없다.(내부 단편화 없음)단점은 메모리 할당된 2개의 프로세스가 종료되고 2개의 프로세스의 요구하는 만큼 메모리 공간을 요구하는 프로세스가 발생할 경우, 실행중인 프로세스를 종료하고 메모리를 합쳐야하는 오버헤드가 발생한다.(외부 단편화)고정 분할 방식장점은 구현이 단순하고 오버헤드가 적다단점은 낭비되는 메모리 공간이 있다.(내부 단편화)CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?스레싱5. HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요? 이유를 함께 적어주세요.초기의 컴퓨터는 필수적인 장치가 아니었습니다. 그러나 컴퓨터가 발전하면서 운영체제를 통해 컴퓨터를 효율적으로 관리하고, 개인 데이터를 저장하기 위해서 오늘날에는 거의 필수로 필요한 저장장치가 되었습니다.파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?파일 삭제시 파일의 헤더만 삭제하고 실제 데이터는 존재하기 때문에, 포렌식으로 파일을 복구할 수 있습니다.
