인프런 워밍업 클럽 스터디 2기 CS (특별미션)

function quickSort(arr, left, right) { if (left = arr[leftStart].count) { leftStart += 1; } while (rightStart >= left + 1 && pivot

인프런 워밍업 클럽 스터디 2기 CS 3주차 과제

운영체제 Q. 메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.CPU 레지스터: CPU에서 임의에 변수를 담는 장소로 주기억장치에 데이터를 가져와 레지스터에 저장한다.CPU 캐시(L1, L2, ~): 주기억장치에서 데이터를 가져와 레지스터에 담을 때, 지역성이론에 따라 자주 사용되는 데이터를 캐시에 저장한다.주기억장치(RAM): 주기억장치라고 불리우는 RAM은 어떠한 주소로 데이터를 가져와도 동일한 성능으로 데이터를 가져올 수 있다. 프로세스와 운영체제가 주기억장치에 올라와 실행되는 공간이다. RAM의 또다른 특성은 전원이 공급되지 않으면 데이터가 지워지는 휘발성 메모리이다.보조기억장치: 휘발성 메모리인 RAM은 데이터를 저장하기 보다는 실행되는 데이터를 저장하는데 유용하다. 때문에 작업중인 파일이나 프로그램의 데이터를 보조기억장치에 저장하여 필요할 때 RAM에 올려 사용한다. Q. 사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?경계 레지스터: MMU가 경계 레지스터에 침범하려고 하는 프로세스를 강제 종료시킨다. Q. 메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?가변 분할 방식(세그멘테이션): 세그멘테이션은 프로세스의 크기에 맞게 적절한 메모리 크기를 할당하여 불필요한 내부 단편화로 낭비되는 메모리 영역이 없다. 또한, 프로세스 크기에 맞는 메모리 영역을 할당하기 때문에 프로세스 영역별로 권한 등의 관리가 쉽다. 단, 외부 단편화 문제가 있는데, 예를 들어, 프로세스 A가 종료되어 메모리 영역에 구멍이 생길 경우, 새롭게 실행될 프로세스 B가 프로세스 A보다 큰 메모리를 요구한다면 구멍난 메모리 영역에 할당할 수 없게 된다. 이를 외부 단편화 문제라고 부르며 외부 단편화 문제를 해결하기 위해서는 메모리 조각 모음을 실행해야 한다. 하지만, 메모리 조각 모음은 실행중인 프로세스들을 종료하고 구멍난 메모리 영역을 매꿔야하기 때문에 오버헤드가 발생한다.고정 분할 방식(페이징): 페이징은 세그멘테이션과 다르게 고정된 메모리 크기를 분할하여 프로세스들에게 할당하는 방식이다. 때문에 고정된 크기보다 작은 프로세스를 실행하려 한다면 메모리 낭비가 발생하게 되는데 이를 내부 단편화라 부른다. 하지만, 항상 고정된 크기의 메모리를 분할하여 프로세스에게 할당하여 세그멘테이션의 외부 단편화 문제가 없다. Q. CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?정답: 스레싱, 이를 해결하기 위해 지역성이론에 따라 다시 현재 사용중인 페이지들은 다시 사용될 확률이 높다. 이러한 페이지를 하나로 묶어 메모리에 올리는데 이를 워킹셋이라고 부른다. Q. HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요? (이유를 함께 적어주세요.)HDD나 SSD와 같은 보조기억장치가 필요한 이유는 다음과 같다.CPU 레지스터나 캐시, 주기억장치는 휘발성 메모리이다. 때문에 작업했던 문서나 프로그램의 데이터 등 유지시킬 필요가 있는 상태들은 전원 공급 없이도 보조기억장치를 통해 상태를 저장해야 한다.또한, 메모리는 가격이 매우 비싸기 때문에, 메모리보다 저렴한 보조기억장치에 문서나 데이터를 저장하고 프로그램이 실행될 때 프로세스로 메모리에 올리는 방식이 효율적이다.보조기억장치에는 운영체제 프로그램을 담고 있다. 컴퓨터가 실행하면 보조기억장치에 있는 운영체제를 메모리에 올려 프로세스로 실행하게 된다.Q. 파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?이는 파일을 삭제할 때 파일의 헤더만 삭제하기 때문이다. 때문에 사용했던 블록의 데이터는 그대로 남아있어 포렌식을 통해 데이터를 복구할 수 있게 된다.파일을 삭제할 때 헤더만을 삭제하여 Free Block List에 추가한다. 그리고 해당 블록은 "사용 가능" 상태로 두어, 새로운 파일을 작성할 때 해당 영역에 덮어쓰기하게 된다. 이러한 방식을 통해 모든 파일을 지울 때 발생하는 디스크 입출력에 대한 부담을 줄여주어 성능을 끌어올리고, 데이터 복구 가능성 또한 열어두는 것이다. 자료구조와 알고리즘 Q. 지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.버블정렬: 현재 요소와 다음 요소를 비교하며 정렬하는 알고리즘으로 구현이 쉽지만 중첩 for 문을 사용하기 때문에 성능이 좋지 않다. 단, 정렬하려는 요소의 다음 요소를 비교하기 떄문에 안정적인 정렬 알고리즘이다. | O(n^2) |선택정렬: 정렬된 영역과 정렬되지 않은 영역을 나누어, 정렬되지 않은 영역에서 가장 작은 (또는 가장 큰) 값을 선택해 정렬한다. 구현이 쉽지만 버블정렬과 마찬가지로 중첩 for 문을 사용하기 때문에 성능이 좋지 않다. 단, 버블 정렬보다 교환 횟수가 상대적으로 적은데 이는 큰 배열에서 선택 정렬이 상대적으로 빠르다. | O(n^2) |삽입정렬: 정렬되지 않은 영역의 요소를 정렬된 영역의 적절한 위치에 삽입하는 알고리즘으로 구현이 쉽다는 장점이 있지만 중첩 for 문을 사용하기 때문에 성능이 좋지 않다. | O(n^2) |병합정렬: 정렬할 배열을 반으로 나누는데 더 이상 나눌 수 없을 때까지 반으로 나눈 후, 다시 역순으로 비교하며 병합하는 알고리즘이다. 재귀적으로 해결하기 때문에 이해 및 구현이 어렵다. 또한, 배열을 반으로 나누는 방식으로 비교적 많은 메모리 공간을 사용한다. 단, 버블/선택/삽입 정렬보다 빠른 성능을 가진다는 장점이있다. | O(nlogn) |퀵정렬: '피벗'이라는 배열의 기준이 되는 요소를 선택한 후 재귀적 호출을 통해 정렬하는 알고리즘이다. 퀵정렬은 어떤 피벗을 선택하느냐에 따라 최악의 성능인 O(n^2)이 나올 수 있다. 하지만, 매번 최악의 피벗 선택을 하는 것은 극히 낮으며, 병합정렬보다 메모리 공간을 덜 사용하기 때문에 병합정렬보다 퀵정렬이 더 좋은 평가를 받는다. | O(nlogn) | Q. 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.재귀적으로 호출하는 상황에서 메모리 부족 문제를 해결하기 위해서는, 이미 해결한 문제를 저장하여 불필요한 연산과 콜스택 낭비를 해결할 수 있다. 이를 메모이제이션이라고 부른다. 메모이제이션으로 메모리 부족 문제를 해결하는 방식은 값을 저장할 해시 테이블을 두고 재귀적으로 해결할 문제를 해시 테이블의 키 값으로 저장한다. 이후 같은 문제가 재귀적으로 호출 될 때 해시 테이블을 조회하여, 이미 해결된 문제라면 해당 키에 해당하는 값을 이용하여 메모리 낭비를 해결할 수 있다. 이러한 방식에서 해시 테이블을 이용하는 이유는, 해시 테이블의 특성상 키를 이용한 조회가 O(1) 시간으로 빠르게 값을 찾을 수 있기 때문이다.

인프런 워밍업 클럽 스터디 2기 CS 2주차 과제

운영체제FIFO 스케줄링의 장단점이 뭔가요?선입선출로 구현이 쉽고 오버헤드가 적다. 단, 매우 긴 CPU 연산 시간이 필요한 프로세스가 먼저 실행된다면, CPU 평균 실행 시간이 높아져 다른 프로세스 작업 시간에 악영향을 끼친다.SJF를 사용하기 여러운 이유가 뭔가요?Short Job First는 CPU 작업 시간이 짧은 프로세스를 먼저 실행시키지만, 프로세스의 CPU 작업 시간을 예측할 수 없기 때문에 현실적으로 불가능에 가깝다.RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?CPU가 실행중인 프로세스를 교체하는 작업인 컨텍스트 스위칭 비용이 빈번하게 발생하여 오버헤드가 크다.운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?주어진 타입 슬라이스보다 프로세스의 버스트 타임이 많다면 CPU 사용률과 처리량이 중요한 프로세스이다. 반대로 버스트 타임이 짧다면 I/O 응답속도가 중요한 프로세스이다.공유자원이란 무엇인가요?같은 컴퓨터에서 프로세스가 통신할 때 사용하는 파일 또는 파이프, 그 밖에 여러 작업들이 공유하여 사용하는 모든 것들은 공유 자원이라고 부른다.교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?임계구역에 하나의 프로세스만 접근한다.프로세스의 공유자원을 강제로 다른 프로세스가 선점할 수 없다.공유자원을 선점한 프로세스와 이를 기다리는 프로세스가 있다.서로에 작업을 기다리는 구조가 순환 구조를 이룬다. 자료구조와 알고리즘재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?재귀적 호출을 탈출하지 못한다. 때문에 완료하지 못한 실행중인 함수를 메모리 콜스택에 추가되기만 한다. (사용 가능한 메모리를 초과)0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function sumOdd(n){ if (n === 0) return 0; while (n % 2 === 0) { n -= 1; } return sumOdd(n - 1) + n; }

인프런 워밍업 클럽 스터디 2기 CS 1주차 과제

운영체제while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다.이 방식은 폴링방식입니다.1초마다 체크하기 때문에 성능에 좋지 않습니다.이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?(답): 인터럽트프로그램과 프로세스가 어떻게 다른가요?(답): 프로그램은 하드디스크와 같은 저장장치에 저장된 명령문에 집합체이고, 프로세스는 프로그램이 메모리에서 실행중인 상태를 말한다.멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?(답): 멀티프로그래밍은 메모리에 여러 프로세스가 올라온 것을 말하고, 멀티프로세싱은 CPU가 여러 프로세스를 처리하는 것을 말한다. 즉, 멀티프로그래밍은 메모리 관점이고 멀티프로세싱은 CPU 관점이다.운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?(답): CPU 스케줄링컨텍스트 스위칭이란 뭔가요?(답): CPU가 현재 실행중인 프로세스의 상태를 저장하고 다른 프로세스의 상태로 교체하여 실행하는 것을 말한다.자료구조와 알고리즘여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다. 이때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? (이유를 함께 적어주세요.)(답): 해시테이블, 이유는 학생 이름을 이용하여 상수시간(O(1))의 성능으로 빠르게 학생 정보를 열람할 수 있기 때문이다.연결리스트 또는 배열로 구현할 경우..- 연결리스트로 구현한다면 저장/삭제에 용이하지만, 조회는 해당 인덱스까지 노드를 찾아가야 하기 때문에 O(n)의 성능이 발생 - 배열로 구현한다면, 조회는 인덱스를 이용하여 메모리 주소에 바로 접근이 가능하기 때문에 O(1), 저장/삭제에는 배열 특성상 새로운 메모리 공간을 확보해야 하기 때문에 연결리스트에 비해 불리하다.여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요. (답): 큐, 이유는 큐 자료구조의 특성인 FIFO이기 때문이다. 처음 들어온 자료(First In)가 먼저 나가기(First Out) 때문