[인프런 워밍업 클럽 스터디 3기] CS - 3주차 미션

운영체제1. 메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.컴퓨터에서 사용하는 메모리는 레지스터, 캐시, 메인메모리(RAM), 보조저장장치(HDD, SSD) 등이 있다.- 레지스터는 CPU 내에 있는 가장 빠른 휘발성 메모리로, 비싼 가격과 작은 용량을 가지고 있다.- 캐시는 미리 RAM에서 자주 사용하는 데이터를 가져와서 한다. 레지스터는 빠르나 RAM은 느리기 때문에 캐시에 데이터를 저장한다.- RAM은 비싼 가격으로 인해 실행 중인 프로그램만 올라가는 공간으로 휘발성 메모리이다.- 보조 저장장치는 용량이 크고 가격이 저렴하며 비휘발성 메모리이다. 사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?경계 레지스터이다.경계 레지스터는 CPU 내에 위치하며, 하드웨어적으로 운영체제 영역과 사용자 영역을 분리한다. 메모리 관리자는 사용자 프로세스가 경계값을 벗어났는 지 감시하고, 벗어났을 경우 그 프로세스를 종료한다. 메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?가변 분할 방식의 장점은 프로세스 크기에 따라 메모리를 가변적으로 분할할 수 있어 내부 단편화가 발생하는 것이 적다. 단점은 메모리 공간보다 프로세스의 크기가 더 커서 외부 단편화가 발생할 수 있다.고정 분할 방식의 장점은 메모리 할당 시 정해진 크기로 분할하기 때문에 관리와 구현이 간단하다. 단점은 프로세스 크기보다 큰 공간이 할당되면서 내부 단편화가 발생할 수 있다는 것이다. CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?CPU 사용률을 높이려 했지만 잦은 스왑으로 인해 CPU 사용율이 오히려 더 떨어지는 현상을 스레싱이라고 한다. HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요? 이유를 함께 적어주세요.HHD와 SSD는 컴퓨터를 실행시키는 데 반드시 필요하다. 이들은 운영체제와 프로그램을 저장하기 때문에 없을 경우 부팅에 실패하거나 소프트웨어를 실행할 수 없다. 파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?파일을 삭제하면 파일 테이블에서 해당 파일의 헤더만 삭제되고, 삭제된 파일 자체는 free block list에 추가된다. 사용자는 파일 삭제 시 완전히 삭제된 것처럼 느끼나 실제로는 새 데이터로 덮어 쓰여질 때 까지 디스크에 남아있어 포렌식으로 파일을 복구할 수 있다. 알고리즘 & 자료구조지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.버블 정렬 - O(n), 최악 O(n²)구현하기 쉬우나 이중 for문으로 인해 성능이 좋지 않다.선택 정렬 - O(n²)구현하기 쉬우나 데이터가 많아질수록 비효율적이다.퀵 정렬 - O(NlogN), 최악 O(n²)병합 정렬보다 더 적은 비교를 하고 더 적은 메모리 공간 차지하지만 피벗 선택이 잘못되었을 경우 최악의 시간 복잡도를 가질 수 있다.병합 정렬 - O(NlogN)분할 정복 방식을 적용했다는 장점이 있지만 구현이 복잡하다.삽입 정렬 - O(n²)구현하기 쉽고, 이미 정렬되어있을 경우 효과적이다. 그러나 배열 크기가 커질수록 성능이 저하된다. 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.타뷸레이션 방식을 사용할 것이다.타뷸레이션은 도출된 모든 중간 값을 테이블에 저장하지만, 일반 재귀나 메모이제이션과 비교했을 때 성능이 더 우수하다. 또한, 반복문으로 한 번에 계산을 처리할 수 있기 때문에 메모리가 부족한 시스템에서 더 적합할 수 있다.

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

학습 내용운영체제프로세스는 메모리 관리자를 통해 메모리에 접근 메모리 관리자: 프로세스 요청이 있을 때 그에 맞는 물리 메모리로 연결시켜줌가상 메모리 운영체제(0x0) 영역을 제외한 나머지 영역을 일정한 크기로 분리가변 분할 방식 (세그멘테이션)단점: 외부 단편화고정 분할 방식 (페이징)단점: 내부 단편화단점 보완: 세그멘테이션-페이징 혼용 기법 사용세그멘테이션 장점: 메모리를 가변적으로 분할할 수 있음, 각 영역에대한 편리한 메모리 접근 보호 단점:내부 단편화 발생 변환 과정 CPU에서 논리 주소 전달 메모리 관리자가 이 주소가 몇 번째 값인 확인 베이스 레지스터를 이용해 물리 메모리 내 세그멘테이션 테이블 탐색 세그멘테이션 번호를 인덱스로 베이스 어드레스와 바운드 어드레스 검색 페이징외부 단편화 문제를 해결하기 위해 고안메모리 할당 시 정해진 크기로 나눔장점:관리 쉬움,외부 단편화 현상이 일어나지 않음세그멘테이션 vs 페이징대표 차이점: 페이지 크기가 다름세그멘테이션은 논리 영역별로 나눔. 코드, 데이터, 스택, 힙 영역을 나눌 수 있음각 영역에 대한 공유 쉬움, 메모리 접근 보호 쉬움페이징은 페이지로 나눔. 특정 영역만 공유 및 권한 부여 어려움,오버헤드가 적음 메모리 접근 권한메모리 접근 권한: 메모리의 특정 번지에 부여된 권환 (rwx)코드 영역은 프로그램 그 자체 ⇒ r-x데이터 영역은 일반, 전역, 상수로 선언한 변수 포함 ⇒ rw?x스택/힙 영역 ⇒ rx-페이지드 세그멘테이션 기법세그멘테이션 테이블에 권한 비트 추가 (RW, R, RWE 등) 과정 가상 주소로 몇 번 세그먼트인지 탐색 세그먼테이션 테이블에서 해당 세그먼트의 인덱스 참조 해당 세그먼트가 메모리 접근 권한을 위반하는 지 검사 접근 권한 위반 시 프로세스 종료 위반하지 않으면 페이지 넘버와 페이지 개수를 가져옴 페이지 넘버로 페이지 테이블 접근, 프레임 번호 가져옴 물리 메모리 내 해당 프레임에 접근 그 위치에 페이지 개수를 더해 물리 주소 구함 물리메모리에 해당 프레임이 없다면 스왑 영역에서 물리메모리로 가져옴 지역성 이론공간의 지역성: 현재 위치에서 가까운 데이터에 접근할 확률이 높음시간의 지역성: 최근 접근했던 데이터가 오래 전에 접근했던 데이터보다 접근할 확률이 높음 디멘드 페이징: 조만간 필요할 것 같은 데이터를 메모리로 가져오고 쓰이지 않을 것 같은 데이터는 스왑영역으로 이동함메모리 계층 구조 (CPU 접근 순):레지스터 -> 캐시 -> 메인 메모리 -> 보조 저장 장치스왑가상 메모리 크기 = 물리 메모리 크기 + 스왑 영역스왑 인: 스왑 영역 → 물리 메모리스왑 아웃: 물리 메모리 → 스왑 영역페이지 테이블 기반하여 물리 메모리에서 프레임을 찾을 때 없으면 Page Fault 인터럽트 발생스왑이 필요없는 경우프로세스가 페이지 요청 → 인덱스로 유효 비트와 프레임 넘버 확인 ⇒ 이를 기반으로 물리 메모리 확인 ⇒ 물리 메모리의 프레임 접근 ⇒ 데이터 참조스왑 영역에 있는 데이터 참조프로세스가 페이지 요청 → 인덱스로 유효 비트와 프레임 넘버 확인 → 이를 기반으로 스왑 영역 확인 →물리 메모리에서 빈 공간 확인 → 스왑 영역에 저장된 데이터를 물리 메모리의 빈 프레임에 저장 → 페이지 테이블에서 해당 엔트리의 유효 비트와 프레임 업데이트 → 프로세스에게 데이터 참조 가능하게 함물리 메모리에 빈 공간 없음 → 물리 메모리에서 필요 없는 영역을 스왑 영역으로 이동 → 필요 없는 영역의 페이지 테이블의 유효 비트와 프레임 업데이트 → 물리 메모리에 공간 생김 → 스왑 영역에서 데이터를 물리 메모리로 이동 → 페이지 테이블의 유효 비트와 프레임 업데이트 → 프로세스에게 데이터 참조 가능하게 함페이지 교체 정책메모리가 꽉 찼을 때 어떤 페이지를 스왑 영역으로 보낼 지 결정하는 정책방법1: 무작위로 선택지역성을 고려하지 않아 자주 사용되는 페이지가 선택될 수도 있다성능이 좋지 않다FIFO 방법2: 메모리에 들어온 가장 오래된 페이지 선택FIFO는 공평하지 않음 → 변형해서 쓰임구현 간단, 성능 꽤 괜찮다OPT 방법3: 앞으로 가장 오랫동안 쓰이지 않을 페이지 선택구현이 불가능한 이론적인 방법, 다른 알고리즘과의 성능 비교 시 사용LRU 방법4: 최근 사용이 가장 적은 페이지 선택시간 지역성에 따라 선택,OPT 알고리즘에 근접한 성능 실제 구현 시 접근 비트를 이용해서 LRU에 근접하게 구현빌레이디의 역설: Page Fault를 줄이려고 메모리를 늘려서 프레임 수도 늘렸는데 오히려 Page Fault가 더 많이 발생하는 현상Clock AlgorithmLRU와 가장 비슷하게 구현하는 알고리즘일정 시간마다 모든 페이지의 접근 비트 초기화 (0), 페이지 참조 시 (1)일정 시간마다 페이지의 참조 여부 확인Enhanced Clock Algorithm접근 비트 + 변경 비트까지 사용2차 기획 페이지 교체 알고리즘: 자주 사용되는 페이지에게 기회를 주는 것Page Fault 없이 접근했다면 페이지를 큐의 맨 뒤로 이동시켜 수명을 연장 시켜 줌 (한번만)스레싱: CPU 사용률을 높이려 했지만 오히려 더 떨어지는 상황워킹셋: 메모리에 올라온 페이지는 다시 사용할 가능성 많음 → 하나의 세트로 묶어서 메모리에 올림캐릭터 디바이스 vs 블록 디바이스 캐릭터 디바이스마우스, 키보드, 사운드카드, 직렬/병렬 포트 등데이터 전송 단위: 캐릭터상대적으로 크기가 작음블록 디바이스하드디스크, SSD, 그래픽 카드 등데이터 전송 단위: 블록 (범위)상대적으로 크기가 큼입출력 제어기I/O 명령 → 입출력 제어기에 입출력 작업 맡김, 다른 작업 시버스시스템 버스: 고속으로 작동 (CPU, 메모리 등)입출력 버스: 주변 창지 사용 (고속 입출력 버스 & 저속 입출력 버스 → 속도 차이로 인한 병목 현상 해결)DMA 제어기 Direct Memory Access: 입출력 제어기가 메모리에 접근하기 위해 필요데이터를 직접 메모리 저장, 가져옴Memory Mapped I/O: CPU가 사용하는 메모리 영역과 DMA가 사용하는 메모리 영역을 나누는 것하드디스크구성요소스핀들: 원판(플래터)을 회전시키는 축플래터: 데이터를 저장하는 자기 원판 (2개 이상 존재)헤드: 데이터를 읽고 쓰는 장치, 플래터 표면과 가까이 위치디스크함: 플래터와 헤드가 들어 있는 본체동작 원리플래터는 자성을 이용해 데이터를 0과 1로 저장헤드는 디스크함과 함께 움직이며 데이터를 읽고 씀데이터를 읽기 위해서는:헤드를 원하는 실린더로 이동회전하면서 해당 섹터에 도달하면 데이터 접근플래시 메모리: 블록 디바이스의 또 다른 종류로, 하드디스크보다 더 자주 사용됨장점: 전기적 처리(조용함), 자석에 영향 없음, 내구성 좋음단점: 특정 지점에 데이터 덮어쓰기 불가, 데이터 덮어쓰려면 데이터를 지워야함, 지우기 가능 횟수 제한 등등 파일 시스템파일은 저장장치에 저장됨파일 관리를 위해 파일 시스템이라는 파일 관리자를 둠파일 시스템 기능파일/디렉토리 생성, 파일/디렉토리 수정/삭제,파일 권한 관리,무결성 보장,백업과 복구,암호화데이터 집합 구성에 따른 분류순차 파일 구조, 직접 파일 구조, 인덱스 파일 구조파일 내 블록의 연결에 따른 분류연속 할당:블록들을 디스크에 연속적으로 저장 (실제 사용 X)불연속 할당:디스크의 비어있는 공간에 데이터를 분산 저장 연결 할당:파일의 데이터를 연결 리스트로 관리 인덱스 할당:테이블의 블록 포인터가 인덱스 블록을 연결 (i-node) 자료구조 & 알고리즘삽입 정렬: 정렬되지 않은 영역에서 가장 앞에 있는 데이터를 꺼내 영역에 삽입하는 것 복잡하지는 않지만 성능이 좋지 않음 class InsertionSort(arr) { for (let i = 1; i = 0; j--) { if (arr[j] > insertingData) { arr[j + 1] = arr[j] } else { break; } } } } const arr = [4, 1, 5, 3, 6, 2] console.log(arr) // [4, 1, 5, 3, 6, 2] console.log(InsertionSort(arr)) // [1, 2, 3, 4, 5, 6]병합 정렬: 분할 정복 divide and conquer: 큰 문제를 작은 문제로 나누어서 해결재귀와 비슷한 모양 function mergeSort(arr, left, right) { if (left 퀵 정렬: 분할 정복 알고리즘의 일종성능: O(NlogN), 최악의 경우 O(N^2)더 적은 비교와 적은 메모리 공간을 차지하지 때문에 병합 정렬보다 좋음 function quickSort(arr, left, right) { if (left = arr[leftStartIndex]) { leftStartIndex++ } while(rightStartIndex >= left + 1 && pivot 다이나믹 프로그래밍 - 메모이제이션하향식 계산, 계산하려는 데이터가 없으면 값을 저장하고 있다면 가져다쓰는 방식일반 재귀 시간복잡도: O(N^2), 다이나믹 프로그래밍 시간복잡도: O(N)메모이제이션 장점: 재귀적 기법으로 단순히 풀 수 있음, 재사용으로 속도가 빠름메모이제이션 단점: 재귀, 오버헤드 큼 function fibonacci2(n, memo) { if (n 다이나믹 프로그래밍 - 타뷸레이션상향식 계산, 사용하지 않아도 계산에 필요한 모든 값을 테이블에 저장하고 가져다 쓰는 방식일반 재귀 > 메모이제이션 > 타뷸레이션 순으로 타뷸레이션 방식이 가장 좋음 function fibonacci3(n) { if (n 회고지난 3주를 생각해보니 마지막 주에는 조금 해이해지지는 않았는지 아쉬움이 든다. 그래도 혼자 공부할 때는 제대로 공부하고 있는 게 맞는 지 고민했었는데, 다른 사람들과 같이 학습하고 또 미션도 풀면서 한 주를 마무리하니까 정말 참여하기 잘했다는 생각이 들었다.3주 동안 학습한 내용을 바탕으로 감자님의 알고리즘/네트워크 강의도 들으면서 부족한 CS를 조금 더 채워야겠다.

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

학습 내용운영체제프로세스 동기화컴퓨터 내 프로세스 간 통신동일 프로세스 내 통신: 운영체제가 생성한 파이프로 데이터를 읽고 씀스레드 간 통신: 데이터 영역이나 힙 영역 사용 시 통신 가능동일 네트워크 내 프로세스 간 통신소켓 통신, RPC(원격 프로시저 호출)공유 자원: 프로세스 통신 시 공동으로 이용하는 변수나 파일임계구역 (Critical Section): 여러 프로세스가 동시에 사용하는 영역해결책: 상호 배제의 매커니즘경쟁 조건 (Race Condition): 공유 자원을 서로 사용하기 위해 경쟁하는 것상호 배제의 요구사항임계 영역에는 동시에 하나의 프로세스만 접근여러 요청에도 하나의 프로세스의 접근만 허용임 영역에 들어간 프로세스는 빠르게 나와야함.세마포어공유자원이 하나 이상일 때 처리하는 동기화 방법예) 프린터 실을 예시로 들때직원: 프로세스기존 프린터: 공유자원프린터실: 임계구역대기줄: 대기큐열쇠 관리자: 운영체제열쇠: 세마포어자바스크립트는 멀티 스레드 환경이 아니라서 비동기 코드에서 적용할 수 있음모니터:세마포어의 단점을 해결한 상호배제 매커니즘교착 상태 (데드락)여러 프로세스가 서로 다른 프로세스의 작업을 기다리다가 아무도 작업을 진행하지 못하는 상태필요 조건 (모두 충족 시 교착 상태 발생)상호 배제: A가 리소스 점유 시 B에게 공유될 수 없음 (즉, 한 번에 하나의 프로세스만 특정 자원을 사용할 수 있음)비선점: A 프로세스는 B가 점유한 리소스를 뺏을 수 없음점유와 대기: 리소스 A를 가지고 있는 상태에서 리소스 B를 원하는 상태 (무한정 대기)원형 대기: 점유와 대기를 하는 프로세스가 원형을 이룸 (서로 교차해서 자원을 기다리고 있는 상태, 모든 프로세스가 영원히 자원을 획득할 수 없음)회피 방법은행원 알고리즘: 교착 상태를 피하기 위해 상태 확인 뒤 실행안정 상태: 자원 요청을 했으나 사용 가능한 자원이 더 적을 경우 요청 거부불안정 상태: 모든 프로세스에 자원을 공급할 수 없는 경우교착상태 검출가벼운 교착 상태 검출: 일정시간동안 작업하지 않을 시 교착 상태 발생으로 간주과정: 일정 시간마다 체크포인트 생성 -> 작업 저장 -> 타임 아웃으로 교착 상태 발생 시 마지막 지점으로 롤백무거운 교착 상태 검출: 운영체제가 자원 사용 여부를 지켜보고 교착 상태 발생 시 해결과정: 자원 할당 그래프 사용 -> 교착 상태 발생 시 순환 구조 형성 -> 교착 상태 해결을 위해 순환 구조 단절 -> 해결 후 재실행 시 체크포인트 롤백컴파일 과정: 문법 오류 확인, CPU에서 처리 가능한 기계어로 실행 파일 생성 => 속도 빠름대표 언어: C, C++, C#인터프리터 과정: 코드를 한 줄씩 해석 후 변환 (미리 검사하지 않음) => 속도 느림, 오류 발생 가능성 높음대표 언어: JavaScript, Python, Ruby1. test.c → 전처리기 → 전처리 구문 처리 → test.i → 컴파일러로 어셈블리어로 변환 → test.s → 어셈블러로 오브젝트 파일 변환 → test.o → 링커에서 실행 파일로 생성 → test.exe2. test.exe 프로그램 실행 → 운영체제가 프로세스 생성 → PCB 생성 → 프로그램 카운터를 코드 영역의 첫번째 주소로 설정 → CPU 스케줄링에 따라 프로세스 실행 → 종료메모리 종류: 레지스터, 캐시, 메인메모리(RAM), 보조저장장치(HDD, SSD)레지스터가장 빠른 기억장소, CPU 내 존재, 휘발성 메모리, 빠름RAM의 값을 레지스터로 가져와서 계산 -> 계산 결과는 다시 RAM에 저장캐시레지스터에서 쓸 법한 데이터를 RAM에서 미리 가져와서 저장, 사용 완료 후 다시 RAM에 저장보조 저장장치: 가격 저렴, 비휘발성 메모리휘발성 메모리: 전원 공급이 없으면 데이터가 사라짐비휘발성 메모리: 전원 공급이 없어도 데이터가 사라지지 않음메인 메모리 RAM운영체제에 프로세스가 올라가는 공간, 휘발성 메모리, 가격 비쌈멀티 프로그래밍 환경에서 여러 프로그램을 올리다 보니 복잡해짐운영체제는 메모리 관리를 위해 1바이트 구역으로 나누고 숫자(주소)를 매김32bit 메모리레지스터 크기, 산술논리연산장치, 데이터 이동 버스 === 32bit가능한 메모리: 2³² ⇒ 4GB64bit 메모리레지스터 크기, 산술논리연산장치, 데이터 이동 버스 === 64bit가능한 메모리: 2⁶⁴ ⇒ 거의 무한대32bit에 비해 한 번에 처리할 수 있는 양이 많음 → 속도가 더 빠름물리주소 공간(절대 주소): 0x0번지부터 시작하는 주소공간메모리 관리자가 바라본 실제 주소논리 주소 공간(상대 주소): 사용자 관점에서 바라본 주소, 물리주소를 몰라도 접근 가능메모리 어디선가 실행되겠지~~하고 컴파일러는 0번지에서 실행한다고 가정하고 컴파일함경계 레지스터: 하드웨어적으로 운영체제 공간과 사용자 공간 분리CPU 내 존재사용자 프로세스가 경계 레지스터의 값을 벗어났는지 감시 (메모리 관리자)벗어났을 경우 프로세스 종료유니 프로그래밍에서의 메모리 분리당장 실행해야하는 부분만 잘라서 메모리에 올리고 나머지는 하드디스크의 스왑 영역에 저장스왑: 스왑영역에 있는 데이터 일부를 메모리로 가져오고 메모리에 있는 데이터를 스왑영역으로 이동멀티 프로그래밍에서의 메모리 분리가변 분할 방식 (Segmentation)프로세스의 크기에 따라 메모리를 나누는 방식연속 메모리 할당: 프로세스가 연속된 메모리 공간에 할당장점: 낭비 공간인 내부 단편화가 없음단점: 외부 단편화 발생고정 분할 방식 (Paging)메모리를 정해진 크기로 나누는 방식예) 고정 크기가 2MB인 경우 5MB인 프로세스는 2MB + 2MB + 1MB + 낭비 공간 1MB비연속 메모리 할당: 프로세스가 여러 개로 쪼개어 여러 곳에 할당됨장점: 구현 간단, 오버헤드 적음단점: 낭비 공간 내부 단편화 발생현대 운영체제는 가변 분할 방식과 고정 분할 방식을 혼합함외부 단편화메모리의 공간보다 프로세스의 크기가 더 큰 경우해결책: 조각 모음단점: 현재 사용 중인 프로세스 전체 일시 중지, 메모리 공간을 이동시키는 작업을 해야함 ⇒ 오버헤드 발생내부 단편화메모리 공간보다 프로세스의 크기가 더 작은 경우해결책: 없음버디 시스템: 2의 승수로 메모리 분할 및 할당방법2의 승수로 프로세스 크기보다 작은 값이 나올때 까지 분리 (예: 1024 - 1024(512 - 512(256 - 256)))비슷한 크기의 프로세스에 할당 (예: 512byte에 할당 (내부 단편화가 적게 발생, 실행이 끝나고 근접한 메모리와 합치기 쉬움))2의 승수로 분할했기 때문에 조립만 하면 큰 공간이 만들어짐 (조각모음보다 간단함)장점가변 분할: 프로세스 크기에 따라 할당되는 메모리 크기가 다름외부 단편화 방지를 위해 메모리 공간 확보가 간단함내부 단편화가 발생하나 많은 공간이 낭비되지 않음 자료구조 & 알고리즘재귀 함수: 자기 자신을 호출하여 문제를 해결하는 함수필수: 기저 조건기저 조건이 없으면 반복되는 출력으로 호출 스택의 메모리 공간이 가득 차서 자동으로 종료됨기본 패턴단순 반복 계산 (예: 누적합, 누적곱, DFS 등)하위 문제의 결과를 기반으로 현재 문제 계산 (예: 팩토리얼, 피보나치 등)상향식 계산: for문, 재귀 함수하향식 계산: 재귀 함수만 가능호출 스택함수가 호출되면서 올라가는 메모리 영역, FILO재귀함수는 모든 호출이 콜 스택에 올라가고 for문은 1개만 올라감예) 팩토리얼function factorial(number) { if (number 예) 모든 원소의 합function sumArray(arr){ if (arr.length == 1) return arr[0]; return sumArray(arr.slice(0, -1)) + arr[arr.length - 1] } const arr = [1,2,3,4,5] const sum = sumArray(arr); console.log(sum)예) 하노이 탑규칙1. 한 번에 하나의 원반을 움직일 수 있다.2. 가장 위에 있는 원반만 옮길 수 있다3. 아래에 작은 원반이 올 수 있다.function hanoi(count, start, target, tmp) { if (count === 0) return; hanoi(count - 1, start, tmp, target) hanoi(count - 1, tmp, target, start) } hanoi(3, 'A', 'C', 'B')1. count - 1개의 작은 원반을 start → tmp로 옮긴다. (임시: target)2. 가장 큰 원반을 start → target으로 옮긴다.3. count - 1개의 작은 원반을 tmp → target으로 옮긴다 (임시: start)4. 이전 과정을 반복하며 모든 원반을 start에서 target으로 옮긴다.5. 모든 원반을 옮겨 count가 0이 되면 재귀를 종료한다.버블 정렬장점: 구현하기 쉬움단점: 성능이 좋지 않음방법: 근접한 두 개의 숫자를 비교하여 정렬되어있지 않다면 오름차/내림차 순으로 정렬한다.시간 복잡도: O(n²)버블 정렬 구현function bubbleSort(arr) { for (let i = 0; i arr[j + 1]) { let temp = arr[j] arr[j] = arr[j + 1] arr[j + 1] = temp } } } } const arr = [4, 2, 3, 1] // ===== 정렬 전 ===== console.log(arr) // ==== 정렬 후 ===== console.log(bubbleSort(arr)선택 정렬장점: 구현하기 쉬움단점: 성능이 좋지 않음방법: 정렬되지 않은 영역의 첫번째 원소와 가장 작은 값의 위치 교환시간 복잡도: O(n²)선택 정렬 구현function selectionSort(arr) { for (let i = 0; i 회고Keep시간표에 따라 매일 CS 지식을 학습했다. 뿌듯나머지 한 주를 잘 마무리하면 좋겠다.Problem없다Try재귀를 구현할 때 더 작은 문제로 나누는 연습을 해야할 것 같다. 기저 조건과 점화식은 바로 이해되는데 나머지가 약간 알쏭달쏭하다.

[인프런 워밍업 클럽 스터디 3기] CS - 2주차 미션

운영체제1. FIFO 스케줄링의 장단점이 뭔가요?FIFO는 먼저 들어간 프로세스가 먼저 실행되는 스케줄링 방법이다. 프로세스가 도착한 순서대로 실행이 되기 때문에 직관적이고 단순하다. 반면 먼저 들어온 프로세스가 완전히 끝나야 다음 프로세스를 실행할 수 있기 때문에 대기 시간이 증가할 수 있다는 단점이 있다. 또한, 프로세스가 들어온 순서에 따라 실행하기 때문에 실행 시간이 짧은 프로세스들은 오래 기다려야한다는 불편함도 있을 수 있다. 따라서, 현대 운영체제에서는 더 효율적인 스케줄링 방식이 사용되고, FIFO는 단순 일괄 처리 시스템에서 사용할 수 있다. SJF를 사용하기 여러운 이유가 뭔가요?SJF는 Shortest Job First로, 도착 시간과 상관 없이 실행 시간이 짧은 프로세스가 먼저 실행되는 방식이다. 새로운 프로세스가 도착할때마다 실행 순서가 달라질 수 있기 때문에 프로세스의 정확한 종료 시간을 예측하기 어려워 어떤 프로세스가 얼마나 실행될지 알 수 없다. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?타임 슬라이스는 프로세스에게 할당된 고정 시간이다.타임 슬라이스가 아주 작으면 CPU를 점유하는 시간이 짧아져 컨텍스트 스위칭이 빈번하게 발생하고, 오버헤드가 증가할 수 있다. 또한, 컨텍스트 스위칭 과정이 실제 실행 시간보다 더 많은 시간을 차지하는 경우 성능 저하가 발생할 수도 있다. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?타임 슬라이스 사용 방식에 따라 구분한다.CPU Bound Process는 작업량이 많아 CPU를 오래 사용하기 때문에 할당된 타임 슬라이스를 모두 사용하며, CPU 스케줄러에 의해 강제로 CPU를 빼앗길 수 있다. 반면, I/O Bound Process는 이름 그대로 입출력 작업이 많아 상대적으로 짧게 CPU를 사용하고 스스로 CPU를 반납하는 경우가 많다. 공유자원이란 무엇인가요?공유자원이란 어려 프로세스가 공유하여 사용하는 자원을 의미한다. 여러 프로세스가 동시에 자원을 사용할 수 있기 때문에, 자원에 접근할 때 경쟁 조건이 발생할 수 있다. 이를 해결하기 위해 동시에 자원을 사용할 수 없는 최소한의 영역인 임계 구역을 정의하고, 상호 배제 매커니즘을 적용해야 한다. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?교착 상태는 아래의 4가지 조건을 충족해야한다.1. 상호 배제: 상호 배제 조건은 한 번에 하나의 프로세스만 자원을 사용해야한다는 것을 의미한다. 여러 프로세스가 동시에 자원을 사용하게 되면, 경쟁 조건이나 예상치 못한 결과가 발생할 수 있다.2. 비선점: 한 프로세스가 자원을 점유하고 있을 때 다른 프로세스는 그 자원을 빼앗을 수 없다는 것을 의미한다. 자원을 반환하기 전까지는 다른 프로세스가 사용할 수 없다.3. 점유와 대기: 한 프로세스가 이미 자원을 점유한 상태에 다른 자원을 원해 대기하고 있는 상태이다. 점유와 대기가 지속된다면 특정 프로세스는 자원을 받을 때까지 무한정 기다려야하기 때문에 교착 상태가 발생한다.4. 원형 대기: 원의 형태로 서로가 서로의 자원을 기다리는 상태여야 한다. 이 경우, 모든 프로세스가 영원히 자원을 획득할 수 없다. 알고리즘 & 자료구조재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?기저 조건이 없거나 잘못 설정했을 경우 재귀 함수는 무한으로 호출된다. 이후 콜 스택이 가득 채워져 더 이상 무한 호출을 처리할 수 없어 자동으로 종료되고, Maximum Call Stack Size 에러를 출력한다. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function sumOdd(n) { // 재귀 로직 if (n 1. 현재 값이 홀수인 경우, 이전 홀수 값(n - 2)과 더한다.→ 예) n = 11인 경우, 11 + 9 + 7 + 5 + 3 + 1 순으로 더하게 됨.2. 현재 값이 짝수인 경우, 바로 이전 홀수 값(n - 1)을 호출하여 다음 재귀부터 이전 홀수 값과 더한다.→ 예) n = 10인 경우, 재귀를 통해 10 -> 9로 변경, 9 + 7 + 5 + 3 + 1 순으로 더하게 됨.기저 조건: 현재 값이 1보다 작을 경우 0을 반환하여 재귀 호출을 종료한다. 다음 코드는 매개변수로 주어진 파일 경로(.는 현재 디렉토리)에 있는 하위 모든 파일과 디렉토리를 출력하는 코드입니다. 다음 코드를 재귀 함수를 이용하는 코드로 변경해보세요.import { LinkedList } from './LinkedList.mjs' class Stack { // ... push(data) { // 마지막 인덱스에 데이터 삽입 // insertAt(0, data) -> insertLast(data) this.list.insertLast(data) } pop() { try { // 마지막 인덱스의 데이터 삭제 // deletedAt(0) -> deleteLast() return this.list.deleteLast() } catch (e) { return null; } } peek() { // 마지막 노드 확인 // getNode(0) -> getNode(this.list.count - 1) return this.list.getNode(this.list.count - 1); } } export { Stack }; 해시테이블의 성능은 해시 함수에 따라 달라집니다. 수업 시간에 등번호를 이용해 간단한 해시 함수를 만들어봤습니다. 이번엔 등번호가 아닌 이름을 이용해 데이터를 골고루 분산시키는 코드로 수정해주세요. const fs = require("fs"); // 파일을 이용하는 모듈 const path = require("path"); // 폴더와 파일의 경로를 지정해주는 모듈 function traverseDirectory1(directory){ const stack = [directory]; // 순회해야 할 디렉토리를 저장할 스택 while (stack.length > 0) { // 스택이 빌 때까지 반복 const currentDir = stack.pop(); // 현재 디렉토리 const files = fs.readdirSync(currentDir); // 인자로 주어진 경로의 디렉토리에 있는 파일or디렉토리들 for (const file of files) { // 현재 디렉토리의 모든 파일or디렉토리 순회 const filePath = path.join(currentDir, file); //directory와 file을 하나의 경로로 합쳐줌 const fileStatus= fs.statSync(filePath); // 파일정보 얻기 if (fileStatus.isDirectory()) { // 해당 파일이 디렉토리라면 console.log('디렉토리:', filePath); stack.push(filePath); } else { // 해당 파일이 파일이라면 console.log('파일:', filePath); } } } } traverseDirectory1("."); // 현재 경로의 모든 하위 경로의 파일, 디렉토리 출력const fs = require("fs"); const path = require("path"); function traverseDirectory(directory) { const files = fs.readdirSync(directory); if (files.length === 0) return; for (const file of files) { const filePath = path.join(directory, file); const fileStatus = fs.statSync(filePath); if (fileStatus.isDirectory()) { console.log('디렉토리:', filePath); traverseDirectory(filePath); } else { console.log('파일:', filePath); } } } traverseDirectory(".");AS-IS 처음에 stack을 정의해 탐색할 디렉토리를 저장하고, 마지막 값을 뽑아 files에 저장TO-BE directory 자체를 재귀 호출의 매개변수로 사용// 기존 코드 function traverseDirectory1(directory){ const stack = [directory]; while (stack.length > 0) { const currentDir = stack.pop(); const files = fs.readdirSync(currentDir); // ... } } // 변경된 코드 function traverseDirectory(directory) { const files = fs.readdirSync(directory); // ... }AS-IS 파일이 디렉토리라면, 다시 stack에 추가해 순회 수행TO-BE 파일이 디렉토리라면, 재귀 함수를 호출하여 매개변수로 그 파일을 사용, 확인 후 하위 디렉토리 탐색 수행// 기존 코드 if (fileStatus.isDirectory()) { stack.push(filePath); } // 변경된 코드 if (fileStatus.isDirectory()) { traverseDirectory(filePath); }AS-IS stack에 요소가 존재하지 않을 때까지, 즉 최상단 디렉토리의 하위에 더 이상 디렉토리가 없을 때까지 반복TO-BE 더 이상 디렉토리가 없을 때 재귀 종료// 기존 코드 while (stack.length > 0) { // ... } // 변경된 코드 if (files.length === 0) return;

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

학습 내용운영체제폴링 방식: 주기적으로 CPU를 확인하여 I/O 완료 확인인터럽트 방식: I/O 완료 시 CPU에게 신호를 주고, ISR을 실행 시켜 작업 완료프로세스: 하드 디스크에 저장된 프로그램이 메모리에 올라간 상태프로세스 구조: 코드 영역, 데이터 영역, 힙 영역, 스택 영역C 언어에서 프로그램이 되는 과정:C언어 -> 전처리기 -> 컴파일 -> 링커 -> .exe 파일 프로그래밍과 프로세싱유니 프로그래밍: 메모리에 하나의 프로세스만 처리하는 것, I/O 작업동안 CPU는 쉼멀티 프로그래밍: 메모리에 여러 프로세스를 처리하는 것, I/O 작업동안 다른 프로세스 처리멀티 태스킹: 모든 프로세스를 번갈아가면서 실행하는 것멀티 프로세싱: CPU를 여러개 사용해서 작업을 처리하는 것PCB프로세스의 정보를 저장하는 블록, 연결리스트로 PCB 연결구조: 포인터, 프로세스 상태, 프로세스 ID, 프로그램 카운터, 레지스터 정보 등프로세스 상태: 생성 New -> 준비 Ready -> 대기 Waiting -> 실행 Running -> 종료 Terminated컨텍스트 스위칭프로세스 실행 중 다른 프로세스를 실행하기 위해 현재 상태를 저장하고 새 프로세스의 상태값으로 교체하는 작업 스위칭 이유: CPU 점유 시간 오버, Input 요청, 인터럽트 등스레드프로세스 내부에서 실행되는 가장 작은 작업 단위스레느는 프로세스 내 1개 이상, PCB와 코드, 데이터, 힙 영역 공유CPU 스케줄링:프로세스를 우선순위에 따라 CPU에 할당하는 방법FIFO(First In First Out): 먼저 들어온 작업이 먼저 나가는 것단점: 비효율적, 프로세스 작업이 완전히 끝나는 걸 기다려야함SJF(Shortest Job First): Burst Time이 짧은 프로세스를 먼저 실행단점: 프로세스 종료 시간 예측 어려움RR(Round Robin): 모든 프로세스에게 일정 시간만큼 할당MLFQ(Multi Level Feedback Queue): 우선 순위에 따라 프로세스 할당 알고리즘 & 자료구조시간 복잡도: 특정 알고리즘이 문제를 해결하는 데 걸리는 시간 (Big-O로 표시)컴퓨터 사양이 모두 다르기 때문에 시간을 직접적으로 평가하기는 쉽지 않음배열:연속적으로 메모리에 할당되는 자료구조 연결 리스트:모든 노드가 연결되어있는 자료구조 스택:FILO LIFO 먼저 들어온 요소가 나중에 나가는 형태 큐:FIFO 먼저 들어온 요소가 먼저 나가는 형태 덱:tail, head에서 삽입/삭제가 가능한 형태 해시테이블:키-값 구조로 데이터를 저장하는 자료구조해시 함수: 입력값으로 고정된 길이의 해시값을 출력하는 함수 셋:데이터의 중복을 허용하지 않는 자료구조 회고Keep매일 시간표대로 강의를 수강하고, 학습한 내용을 꼼꼼히 노션에 정리했다.[미션] 노션에 정리한 내용을 토대로 미션을 해결했다.Problem해시테이블에 대해 이해가 부족하다는 생각이 들었다. 객체와 맵, 해시테이블의 차이점이 뭔지 정확히 알고 있어야 할 것 같다.[미션] 해시 함수 작성할 때 해시값에 현재 배열의 길이를 나눈 나머지를 사용했는데, 이걸 더 깔끔한 방식으로 풀어야하는지 아직도 고민중이다. Try이번 주차 내용 복습하기[미션] 이번 주차 미션 다시 풀어보기

[인프런 워밍업 클럽 스터디 3기] CS - 1주차 미션

운영체제while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }1. 위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?인터럽트 방식을 사용해야 한다.인터럽트 방식은 I/O 등에서 상태가 변경되었거나 이벤트가 발생한 경우에 CPU에게 알리는 방식이다. 비동기적으로 동작하며, 인터럽트가 발생 했을 때 인터럽트 서비스 루틴(ISR)을 실행하여 이벤트를 처리한다. CPU는 주기적으로 상태를 체크하지 않아도 되기 때문에 폴링 방식과는 성능 측면에서 큰 이점이 있다. 프로그램과 프로세스가 어떻게 다른가요?프로그램은 코드와 데이터로 이루어진 파일이며 하드디스크에 저장된 정적 파일이다. 소스 코드를 컴파일하여 실행 파일 .exe로 만들면 프로그램이라고 볼 수 있다.반면 프로세스는 하드디스크에 저장된 프로그램이 메모리에 올라갔을 때의 상태이다. 프로그램 파일을 클릭하면 운영체제는 이를 메모리에 추가한 다음 프로세스가 실행된다. 프로세스는 CPU와 RAM, I/O 등을 사용하며 능동적으로 동작한다. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?멀티 프로그래밍은 메모리에 여러 개의 프로세스를 올려놓고 실행하는 것이다. I/O 작업을 수행하는 동안 다른 프로세스를 먼저 실행하여 시간을 효율적으로 사용할 수 있다.반면 멀티 프로세싱은 여러 개의 CPU를 사용하여 동시에 여러 프로세스를 처리하는 방식으로, 각 프로세스가 독립적인 메모리 공간을 가진다. 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?PCB(Process Control Block)을 사용한다.프로세스가 생성될 때 해당 프로세스의 정보를 저장하기 위해 PCB를 생성한다. PCB에는 프로세스의 현재 상태를 나타내는 ‘프로세스 상태’, 프로세스를 식별하기 위한 고유 아이디인 ‘프로세스 ID’, 이전 명령어를 다시 실행할 수 있도록 명령어 주소를 저장하는 ‘프로그램 카운터’ 등이 있다. 컨텍스트 스위칭이란 뭔가요?컨텍스트 스위칭(Context Switching)은 프로세스의 상태를 교환하는 작업이다.다른 프로세스를 실행하기 위해 현재 프로세스의 상태를 PCB에 저장하고, 다른 프로세스의 상태 값을 PCB에서 가져와 교체한다. 여러 프로세스를 번갈아 가며 실행하는 멀티 프로그래밍, 멀티 프로세싱에서 컨텍스트 스위칭이 사용된다.CPU를 너무 오래 차지하게 되면 다른 프로세스를 위해 컨텍스트 스위칭이 필요하고, 인터럽트가 발생하면 현재 프로세스의 실행이 중단되기 때문에 다른 프로세스로의 전환을 위해 컨텍스트 스위칭이 필요하다. 알고리즘 & 자료구조여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다. 이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.해시테이블(HashTable)을 사용할 것이다.해시 테이블은 key-value 쌍으로 데이터를 저장하므로, 학번을 고유한 키로 사용해 학생 정보에 쉽게 접근할 수 있다.let students = new HashTable() hashTable(123456, { name: '홍길동', studentId: 1 }) console.log(hashTable.get(123456)) // { name: '홍길동', studentId: 1 } 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.큐(Queue) 자료구조를 사용할 것이다.큐는 먼저 들어온 요소가 먼저 나가는 선입선출(FIFO) 방식을 사용하기 때문에 주문이 들어온 순서대로 처리하기 적합하다. 우리가 구현한 스택은 0번 인덱스, 즉 입구쪽으로 데이터가 삽입되고 나오는 구조입니다. 반대로 마지막 인덱스, 즉 출구쪽으로 데이터가 삽입되고 나오는 구조로 코드를 변경해주세요.import { LinkedList } from './LinkedList.mjs' class Stack { // ... push(data) { // 마지막 인덱스에 데이터 삽입 // insertAt(0, data) -> insertLast(data) this.list.insertLast(data) } pop() { try { // 마지막 인덱스의 데이터 삭제 // deletedAt(0) -> deleteLast() return this.list.deleteLast() } catch (e) { return null; } } peek() { // 마지막 노드 확인 // getNode(0) -> getNode(this.list.count - 1) return this.list.getNode(this.list.count - 1); } } export { Stack }; 해시테이블의 성능은 해시 함수에 따라 달라집니다. 수업 시간에 등번호를 이용해 간단한 해시 함수를 만들어봤습니다. 이번엔 등번호가 아닌 이름을 이용해 데이터를 골고루 분산시키는 코드로 수정해주세요.힌트: charCodeAt() 함수를 이용`예시: name1 = "이운재"; name1.charCodeAt(0); // 51060 이운재의 0번 인덱스 ‘이’의 유니코드 출력hashFunction(name){ let hash = name.charCodeAt(0) return hash % 10 // 현재 배열의 길이 0 ~ 9 }import { HashTable } from './HashTable.mjs' let hashTable = new HashTable() hashTable.set('이운재', 1) hashTable.set('최진철', 4) hashTable.set('홍명보', 20) console.log(hashTable.get('이운재')) // 1 hashTable.remove('이운재') console.log(hashTable.get('이운재')) // null console.log(hashTable.get('최진철')) // 4