[워밍업 클럽 3기] CS 3주차 - 운영체제 미션

메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.1) 레지스터가장 빠른 기억 장소로 CPU 내 존재컴퓨터가 꺼지면 데이터가 사라지기 때문에 휘발성 메모리라고 부름CPU는 계산할 때 메인 메모리에 있는 값을 레지스터로 가져와서 계산 → 결과는 메인 메모리에 저장2) 캐시휘발성 메모리레지스터는 빠르고, 메인메모리는 느린데 여기서 데이터를 가져오기에는 오래 걸림 → 미리 가져온 데이터를 저장하는 곳이 캐시CPU가 값을 요청해 레지스터로 값을 옮겨야 한다면 단계에 따라 가장 속도가 빠른 L1 캐시를 보고, 없으면 L2 캐시, 여기도 없다면 메인 메모리에서 값 가져옴3) 메인메모리(RAM)실제 운영체제와 다른 프로세스들이 올라가는 공간전원이 공급되지 않으면 데이터가 사라지기 때문에 휘발성 메모리하드디스크나 SSD 보다 속도는 빠르지만 가격이 비쌈데이터 저장 보단 실행중인 프로그램만 올림4) 보조저장장치(HDD, SSD)가격 저렴전원이 공급되지 않아도 데이터가 지워지지 않은 비휘발성 메모리사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?경계 레지스터메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?가변 분할 방식프로세스 크기에 따라 메모리를 가변적으로 분할할 수 있어 내부 단편화가 발생하는 것이 적음메모리 공간보다 프로세스의 크기가 더 커서 외부 단편화 발생 가능고정 분할 방식메모리 할당 시 정해진 크기로 분할하기 때문에 관리, 구현 간단프로세스 크기보다 큰 공간이 할당되면서 내부 단편화 발생 가능CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?스레싱(Thrashing)HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요?CPU, RAM 만으로도 프로그램 실행 가능하기 때문에 필수는 아니지만 운영체제, 프로그램, 데이터 저장을 하기 위해서는 꼭 필요하다고 생각다른 메모리들은 휘발성 메모리로전원 끄면 데이터 모두 사라지기 때문에저장장치 없이는 지속적 사용 불가능또한 비휘발성, 가격이 저렴한 보조 저장 장치는 필요하다고 생각파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?파일 삭제 시 파일 테이블에서 해당 파일의 헤더만 삭제되고, 삭제된 파일 자체는 free block list에 추가실제 디스크의 데이터 블록은 그대로 존재하고 새로운 파일이 해당 위치에 덮어쓰기 전까지는 데이터가 남아 있음해당 이유로 포렌식으로 파일 복구 가능

[워밍업 클럽 3기] CS 3주차 - 자료구조와 알고리즘 미션

지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.1) 버블 정렬(Bubble Sort)앞에 있는 숫자와 옆에 숫자를 비교해서 자리를 바꾸는 알고리즘장점: 이해 및 구현 간단단점: 성능이 좋지 않음성능 - O(n^2)(n-1) + (n-2) + (n-3) … + 2 + 1 → 등차수열n(n-1)/2 → (n^2 - n)/2 2) 선택 정렬(Selection Sort)배열의 정렬되지 않은 영역의 첫 번째 원소를 시작으로 마지막 원소까지 비교 후 가장 작은 값을 첫 번째 원소로 가져옴장점: 이해 및 구현 간단단점: 성능이 좋지 않음성능 - O(n^2)(n-1) + (n-2) + (n-3) … + 2 + 1 → 등차수열n(n-1)/2 → (n^2 - n)/2 3) 삽입 정렬(Insertion Sort)정렬되지 않은 영역의 처음 데이터를 꺼내서, 정렬된 영역 뒤에서 부터 비교하고 적절한 위치에 삽입하여 정렬장점: 이해 및 구현 간단단점: 성능이 좋지 않음성능 - O(n^2) 4) 병합 정렬(Merge Sort)배열을 반 씩 분할하고, 가장 작은 단계까지 분할 후 순서에 맞게 병합 - 재귀로 정렬하는 알고리즘장점: 성능이 좋음단점: 이해 및 구현이 어려움성능 - O(nlogn)하나의 데이터 + 하나의 데이터 → 두 개로 합쳐질 때 비교연산 두 번두 개의 데이터 + 두 개의 데이터 → 네개로 합쳐질 때 비교 네 번각 단계를 거칠 때마다 영역의 수 반으로 줌 → log(n)분할 된 배열을 병합할 때는 n개의 데이터를 n번 비교 → n * logn = O(nlogn) 5) 퀵 정렬(Quick Sort)분할 정복 알고리즘(재귀 사용)장점: 성능이 좋음 (퀵 > 병합)단점: 이해 및 구현이 어려움성능 - Θ(nlogn) / O(n^2)데이터가 한 개가 될 때까지 피벗을 기준으로 반을 나눔 → logn나눠진 단계를 배열의 원소수 n 만큼 진행 → n * logn = nlogn피벗이 매번 배열의 반을 가르는 경우 ⇒ Θ(nlogn)최악의 경우는 피벗이 중간이 아닌 한쪽으로 치우친 경우 ⇒ O(n^2)퀵 정렬은 대부분 좋은 피벗을 선택하고 최악의 경우가 발생할 확률이 극히 낮아 평균적인 성능을 말함 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.타뷸레이션 이용'재귀 호출 + 캐시 저장'으로 스택 메모리 사용하는 메모이제이션과 다르게, 타뷸레이션은 반복문을 이용하여 테이블에 저장하기 때문에 스택 메모리를 사용하지 않음 -> 메모리가 부족한 시스템에선 메모리를 덜 쓰는 타뷸레이션이 적합하다고 생가

[워밍업 클럽 3기] CS 3주차 - 발자국

삽입 정렬(Insertion Sort)정렬되지 않은 영역의 처음 데이터를 꺼내서, 정렬된 영역 뒤에서 부터 비교하고 적절한 위치에 삽입하여 정렬장점: 이해 및 구현 간단단점: 성능이 좋지 않음성능 - O(n^2) 병합 정렬(Merge Sort)배열을 반 씩 분할하고, 가장 작은 단계까지 분할 후 순서에 맞게 병합 - 재귀로 정렬하는 알고리즘장점: 성능이 좋음단점: 이해 및 구현이 어려움성능 - O(nlogn)하나의 데이터 + 하나의 데이터 → 두 개로 합쳐질 때 비교연산 두 번두 개의 데이터 + 두 개의 데이터 → 네개로 합쳐질 때 비교 네 번각 단계를 거칠 때마다 영역의 수 반으로 줌 → log(n)분할 된 배열을 병합할 때는 n개의 데이터를 n번 비교 → n * logn = O(nlogn) 퀵 정렬(Quick Sort)분할 정복 알고리즘(재귀 사용)장점: 성능이 좋음 (퀵 > 병합)단점: 이해 및 구현이 어려움성능 - Θ(nlogn) / O(n^2)데이터가 한 개가 될 때까지 피벗을 기준으로 반을 나눔 → logn나눠진 단계를 배열의 원소수 n 만큼 진행 → n * logn = nlogn피벗이 매번 배열의 반을 가르는 경우 ⇒ Θ(nlogn)최악의 경우는 피벗이 중간이 아닌 한쪽으로 치우친 경우 ⇒ O(n^2)퀵 정렬은 대부분 좋은 피벗을 선택하고 최악의 경우가 발생할 확률이 극히 낮아 평균적인 성능을 말함 동적 프로그래밍메모이제이션(memoization)계산 결과를 저장해서 여러 번 계산하지 않도록 하는 기법 → 데이터가 있는지 검색, 없으면 저장하향식 계산 방식재귀적인 기법으로 어려운 문제를 단순히 풀 수 있음O(n)의 성능계산 결과를 해시 테이블(key - 계산하는 값, value - 결과 값)에 저장하고 재사용 하기 때문에 속도가 빠름(속도를 위한 메모리 / 캐시 사용)함수 하나를 호출 하는 것 보다 오버헤드가 클 수밖에 없음 타뷸레이션상향식 계산 방식계산에 필요한 모든 값을 전부 계산 후 테이블에 저장

[워밍업 클럽 3기] CS 2주차 - 운영체제 미션

FIFO 스케줄링의 장단점이 뭔가요? 장점단순하고 직관적단점한 프로세스가 완전히 끝나야 다음 프로세스가 진행되므로, 실행시간이 짧고 늦게 도착한 프로세스가 실행시간이 길고 빨리 도착한 프로세스의 작업을 기다려야 함I/O 작업이 있다면, CPU는 I/O 작업이 끝날 때까지 쉬고있기 때문에 CPU 사용률이 떨어짐 2. SJF를 사용하기 어려운 이유가 뭔가요?어떤 프로세스가 얼마나 실행될지 예측하기 어려움Burst Time이 긴 프로세스는 아주 오래동안 실행되지 않을 수 있음-> SJF는 Burst Time이 짧은 프로세스가 먼저 실행되기 때문에 긴 프로세스는 뒤로 밀려남 3. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?오버헤드가 너무 커진다. 컨텍스트 스위칭이 자주 일어나게 되고, 타임 슬라이스에서 실행되는 처리량보다 컨텍스트 스위칭을 처리하는 양이 더 많아지기 때문 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?CPU를 사용하는 프로세스가 실행하다가 스스로 CPU를 반납하면 CPU 사용이 적음 -> I/O Bound Process 확률 증가타임 슬라이스 크기를 오버해서 CPU 스케줄러에 의해 강제로 CPU를 뺏기는 상황 -> CPU Bound Process 확률 증가 공유자원이란 무엇인가요?프로세스 간 통신을 할 때 공동으로 이용하는 변수나 파일 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야 할까요?상호 배제: 어떤 프로세스가 한 리소스를 점유했다면, 그 리소스는 다른 프로세스에게 공유되면 안 된다.비선점: 다른 프로세스가 리소스를 뺏을 수 없어야 한다.점유와 대기: 어떤 리소스를 가지고 있을 때, 다른 리소스를 원하는 상태여야 한다. 원형 대기: 점유와 대기를 하는 프로세스들의 관계가 원형을 이룬다. (원하는 리소스의 방향이 원형을 이룸)

[워밍업 클럽 3기] CS 2주차 - 자료구조와 알고리즘 미션

재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?스택 오버플로우 발생무한 재귀로 인해 함수가 호출될 때마다 새로운 스택 생성 -> 시스템 메모리 한계 넘음 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function sumOdd(n){ if (n == 0) return 0; return (n % 2 == 1 ? n : 0) + sumOdd(n - 1); } console.log(sumOdd(10)) 다음 코드는 매개변수로 주어진 파일 경로(.는 현재 디렉토리)에 있는 하위 모든 파일과 디렉토리를 출력하는 코드입니다. 다음 코드를 재귀 함수를 이용하는 코드로 변경해보세요.import fs from "fs"; import path from "path"; function traverseDirectory(directory) { const files = fs.readdirSync(directory); for (const file of files) { const filePath = path.join(directory, file); const fileStatus = fs.statSync(filePath); if (fileStatus.isDirectory()) { console.log('디렉토리:', filePath); traverseDirectoryRecursive(filePath); } else { console.log('파일:', filePath); } } } traverseDirectory(".");

[워밍업 클럽 3기] CS 2주차 - 발자국

재귀어떠한 것을 정의할 때 자기 자신을 참조하는 것재귀적으로 정의된 함수 → 재귀함수 콜스택함수가 호출되면서 올라가는 메모리 영역 → 스택이라고도 부름First In Last Outfor문으로 처리할 수 있는 작업을 재귀함수로 처리한다면 더 비효율적인 상황이 생김→ 재귀함수가 더 많은 메모리 공간 차지대신, 재귀함수를 사용하면 처리하기 쉬운 예도 있음. ex) 팩토리얼패턴 1. 단순 반복 실행반복문 구현보다 큰 이점은 없음. 콜스택 공간을 많이 차지해 오히려 성능 저하패턴 2. 하위 문제 결과를 기반으로 현재 문제 계산예) 팩토리얼, 하노이탑for 문을 이용한 계산 - 상향식 계산재귀를 이용해 하위 문제 계산 - 하향식 계산 (상향식도 구현 가능하지만 성능 발휘는 딱히 X)// 재귀를 이용한 상향식 계산 function factorial2(number, i = 1, sum = 1) { if (i > number) return sum; return factorial2(number, i + 1, sum * i); } 정렬 알고리즘버블 정렬(Bubble Sort)앞에 있는 숫자와 옆에 숫자를 비교해서 자리를 바꾸는 알고리즘장점: 이해 및 구현 간단단점: 성능이 좋지 않음성능 - O(n^2)(n-1) + (n-2) + (n-3) … + 2 + 1 → 등차수열n(n-1)/2 → (n^2 - n)/2 선택 정렬(Selection Sort)배열의 정렬되지 않은 영역의 첫 번째 원소를 시작으로 마지막 원소까지 비교 후 가장 작은 값을 첫 번째 원소로 가져옴장점: 이해 및 구현 간단단점: 성능이 좋지 않음성능 - O(n^2)(n-1) + (n-2) + (n-3) … + 2 + 1 → 등차수열n(n-1)/2 → (n^2 - n)/2

[워밍업 클럽 3기] CS 1주차 - 운영체제 미션

while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?인터럽트폴링 방식은 일정 간격마다 상태를 확인하므로 불필요한 CPU 리소스를 낭비 -> 인터럽트 방식을 사용하여하드웨어 또는 소프트웨어에서 발생하는 신호로, 이벤트가 발생했을 때 운영체제가 즉시 반응하도록 함 프로그램과 프로세스가 어떻게 다른가요?프로그램: 실행 파일이나 코드와 같은 정적인 개념. 하드디스크 등에 저장된 실행 가능한 파일.프로세스: 프로그램이 실행될 때 운영체제로부터 메모리를 할당받아 동작하는 개체. 실행 중인 프로그램 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?멀티프로그래밍: 여러 개의 프로그램이 메모리에 올라가 있지만 CPU는 한 번에 하나씩 실행하며, 빠르게 전환하면서 실행하는 방식멀티프로세싱: 두 개 이상의 CPU 또는 코어가 여러 프로세스를 동시에 실행하는 방식. 실제 병렬 처리 가능 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?프로세스의 실행과 스케줄링을 위해 PCB(Process Control Block), 스케줄러, 컨텍스트 스위칭 등을 사용PCB: 프로세스의 정보를 저장하는 데이터 구조로, 프로세스 ID, 상태, 레지스터 값, 메모리 정보 등을 포함스케줄러: CPU 할당 순서를 결정하는 알고리즘을 사용하여 프로세스의 실행을 조율컨텍스트 스위칭: 실행 중인 프로세스의 상태를 저장하고, 다른 프로세스를 실행하기 위해 이전 상태를 복원하는 과정 컨텍스트 스위칭이란 뭔가요? 운영체제가 현재 실행 중인 프로세스를 중단하고 다른 프로세스를 실행하기 위해 레지스터, 프로그램 카운터, 메모리 정보 등을 저장하고 복구하는 과정

[워밍업 클럽 3기] CS 1주차 - 자료구조와 알고리즘 미션

여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다.이때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.HashMap일반적으로 학생 정보를 관리할 때는 '학번(아이디), 이름' 으로 관리하기 때문에, key는 학번, value는 이름을 저장하는 key-value 형식의 해쉬맵을 사용학번(key)으로 빠르게 조회가 가능. 수정/삭제 시에도 학번으로 조회하여 데이터 처리를 하면 되기 때문에 효율 적일 것 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요. 큐(Queue)주문은 들어온 순서대로 처리되기 때문에 큐의 선입선출(FIFO) 구조와 일치 우리가 구현한 스택은 0번 인덱스, 즉 입구쪽으로 데이터가 삽입되고 나오는 구조입니다. 반대로 마지막 인덱스, 즉 출구쪽으로 데이터가 삽입되고 나오는 구조로 코드를 변경해주세요.class Stack { constructor() { this.list = new LinkedList(); } push(data) { this.list.insertLast(data); } pop() { try { return this.list.deleteLast(); } catch (e) { return null; } } } 해시테이블의 성능은 해시 함수에 따라 달라집니다. 수업 시간에 등번호를 이용해 간단한 해시 함수를 만들어봤습니다. 이번엔 등번호가 아닌 이름을 이용해 데이터를 골고루 분산시키는 코드로 수정해주세요.function hashFunction(name) { let hash = 0; for (let i = 0; i

[워밍업 클럽 3기] CS 1주차 - 발자국

자료구조데이터가 어떤 구조로 저장되고, 어떻게 사용되는지 나타냄가장 단순한 자료구조 변수숫자나 문자열 저장을 위해 변수 사용저장한 숫자, 문자열 접근을 위해 변수 참조사용 방법 단순 배열숫자, 문자열 등 연속적으로 저장해당 숫자, 문자열 접근을 위해 인덱스를 이용하여 참조 알고리즘어떤 문제를 해결하기 위한 확실한 방법알고리즘은 자료구조에 따라 많은 영향을 받음(e.g. 자료구조 성적 평균 구하기)같은 자료구조에 대해서도 여러 알고리즘이 존재프로그램 개발 시어떻게 저장 및 사용할 것인지 자료구조 선택 → 데이터를 가공할 알고리즘 사용적절한 자료구조 선택, 적절한 알고리즘 사용을 할 줄 알아야 한다.더 좋은 알고리즘은 무엇인가? → 사용자에 따라 다를 것이다.메모리를 더 적게 사용하고 싶은 사용자메모리 사용을 적게하는 알고리즘속도를 우선으로 하는 사용자메모리 사용량이 많아도, 빠른 알고리즘일반적으로 알고리즘 속도를 성능의 척도로 사용 → 시간복잡도! 시간복잡도특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간같은 알고리즘이라도 컴퓨터 성능에 따라 처리 시간 상이→ 알고리즘 평가 시 시간 측정이 아닌 코드에서 성능에 많은 영향을 주는 부분을 찾아 실행 시간을 예측 → 반복문이 가장 많은 영향! Big-Ω: 최선의 경우 (한 번에 찾음)Big-O: 최악의 경우 (배열의 길이만큼)Big-Θ: 평균 (배열 길이의 중간) Big-O: 최악의 경우 (O(n))선형시간 알고리즘 O(n)데이터가 증가할 수록 계산량 증가상수시간 알고리즘 O(1)입력 크기 상관 없이 상수 시간 소요계산량이 한번일 필요가 없음빅오 표기법은 성능을 정확하게 측정하진 못한다.