[인프런 워밍업 클럽 스터디 3기 - CS전공지식] 3주차 과제 - 자료구조와 알고리즘

자료구조와 알고리즘1. 지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.1) 버블정렬 : O(n²)장점 : 이해와 구현이 쉬움단점 : 성능이 O(n²)으로 좋지 않음2) 선택정렬 : O(n²)장점 : 이해와 구현이 쉬움단점 : 성능이 O(n²)으로 좋지 않음3) 삽입정렬 : O(n²)장점 : 이해와 구현이 쉬움단점 : 성능이 O(n²)으로 좋지 않음4) 병합정렬 : O(nlogn)장점 : O(nlogn)으로 성능이 좋음단점 : 이해와 구현이 어려움5) 퀵정렬 : O(nlogn)장점 : O(nlogn)으로 성능이 좋음단점 : 이해와 구현이 어려움2. 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.✨️ 타뷸레이션을 사용할 것 같습니다. 재귀로 쉽게 구현이 가능하더라도 메모리가 부족한 상황에서, 메모리를 사용하여 성능을 올리는 메모이제이션은 오히려 성능을 더 떨어 뜨릴 것으로 보이기 때문에 적합하지 않아 보입니다. 타뷸레이션은 상향식이지만, 메모제이션보다 적은 메모리와 빠른 속도로 빠르게 해결할 수 있기 때문입니다.

[인프런 워밍업 클럽 스터디 3기 - CS전공지식] 3주차 과제 - 운영체제

운영체제1. 메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.✨️ 레지스터휘발성 메모리메모리중 가장 빠름✨️ 캐시레지스터와 메인 메모리 사이의 속도 차이를 극복하기 위해 필요할 것 같은 데이터를 미라 저장 시킴✨️ 메인 메모리휘발성 메모리보조저장장치에 비해 빠르지만 비싸기 때문에 실행하는 프로그램만 올림✨️ 보조저장장치비휘발성 메모리메인메모리보다 저렴함 2. 사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?✨️ 경계 레지스터사용자 프로세스가 경계 레지스터의 값을 벗어났는지 감시하고 벗어났다면 프로세스을 강제 종료 시킴.3. 메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?✨️ 가변 분할 방식장점 : 프로세스의 크기만큼 할당 하기 때문에 공간 낭비가 없음.단점 : 외부 단편화 발생함.외부 단편화 : 프로세스가 작업을 끝내고 메모리에서 내려오면 메모리는 그 프로세스 크기만큼 공백이 발생하는데, 다음에 할당 요청을 하는 프로세스의 크기가 공백의 크기보다 커서 프로세스에게 할당하지 못하는 것✨️ 고정 분할 방식장점 : 구현이 간단하고 오버헤드가 적고 같은 크기로 나누기 때문에 관리하기 쉬움단점 : 내부 단편화 발생4. CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?✨️ 스레싱5. HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요? 이유를 함께 적어주세요.✨️ 네. 꼭 필요합니다.전원 공급 관점 : 보조저장장치(HDD나 SSD)는 전원이 공급되지 않아도 데이터가 유지 되는 비휘발성 메모리이지만, 메인 메모리(RAM)는 전원이 공급되지 않으면 데이터가 날라가는 휘발성 메모리이기 때문에 데이터를 유지할 수 없습니다.비휘발성 메모리엔 ROM 메모리도 있긴 하지만, ROM 메모리는 한번 쓰면 수정이 불가능하기 때문에 적합하지 않습니다.비용 관점 : 보조저장장치가 메인메모리보다 훨씬 저렴하기 때문에 비용면에서 효율적입니다.크기 관점 : 메인메모리 하나로 컴퓨터를 실행 시킨다면, 데이터 저장도 해야 하고, 프로세스가 올라갈 공간도 필요하기 때문에 아주 큰 크기가 필요할 것임. 또한 프로세스의 당장 실행 하지 않아도 될 부분까지 모두 올가야 하기 때문에 cpu 사용률도 떨어질 것이라 생각합니다.6. 파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?✨️ 파일을 삭제 할때 파일 테이블의 헤더만 삭제 되고 블록의 데이터는 남아 있기 때문에 포렌식으로 파일을 복구할 수 있습니다.

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

운영체제가상메모리 개요운영체제나 프로세스가 메모리의 크기보다 클 때 실행되지 않는 문제를 해결하기 위해 나옴.메모리보다 크기가 큰 운영체제와 프로세스들을 처리할 때, 가상 메모리 시스템은 물리 메모리 내용의 일부를 하드 디스크의 스왑 영역으로 옮기고 처리가 필요할 때 물리 메모리로 가져와 처리함.메모리 관리자는 물리 메모리와 스왑영역을 합쳐서 프로세스가 사용하는 가상 주소를 물리주소로 변환해줌.가상 메모리 시스템에서는 운영체제 영역을 제외한 나머지 영역을 일정한 크기로 나누어서 프로세스에게 할당함.가상 메모리 분할 방식에는 가변 분할 방식(세그멘테이션)과 고정 분할 방식(페이징)이 있음.메모리 관리자는 가상주소와 물리주소를 일대일 매핑 테이블로 관리함.세그멘테이션(배치정책)메모리 관리자는 세그멘테이션 테이블로 관리를 함세그멘테이션 테이블은 Base Address와 Bound Address가 저장되고, 이걸 이용해 물리 메모리 주소를 계산함.CPU가 논리주소 123번지 요청 → 메모리 관리자는 123번지가 몇번 세그먼트인지 알아냄 → Segment Table Base Register(메모리 관리자 내)를 이용해서 세그멘테이션 테이블(물리 메모리내)을 찾음 → 세그멘테이션 테이블에서 세그먼트 번호를 인덱스로 Base Address와 Bound Address를 찾음. → 메모리 관리자는 논리 주소와 Bound Address의 크기를 비교함.→ 논리주소 → 논리주소 > Bound Address ⇒ 메모리 침범, 에러 발생시키고 종료 시킴.운영체제는 컨텍스트 스위칭을 할 때마다 Segment Table Base Register를 해당 프로세스의 것으로 바꿔줘야 하기 때문에 컨텍스트 스위칭은 무거운 작업임장점메모리를 가변적으로 분할할 수 있음코드 영역/데이터 영역/스택 영역/힙 영역을 모듈로 처리할 수 있기 때문에 공유와 각 영역에 대한 메모리 접근 보호가 편리함단점외부 단편화 발생외부 단편화 : 프로세스의 크기별로 할당된 메모리에 프로세스가 작업을 종료하고 메모리에서 내려가고 메모리에 공백이 생겼을 때, 공백된 크기보다 큰 크기의 프로세스가 메모리 할당 요청을 할 때 연속된 공간이 아니기 때문에 새로운 프로세스에게 할당 할 수 없는 현상을 말함.조각모음으로 해결할 수 있지만, 오버헤드가 발생하는 큰 작업임.페이징(배치정책)메모리를 할당 할 때, 정해진 크기의 페이지로 나누는 방식.모든 페이지는 크기가 같기 때문에 관리가 굉장히 쉽고 또한 일정한 크기로 나눴기 때문에 외부 단편화가 발생하지 않음.페이지 : 논리 주소 공간을 일정한 크기로 균일하게 나눈 것프레임 : 물리 주소 공간을 페이지의 크기와 동일하게 나눈 것메모리 관리자는 페이지 테이블을 가지고 있음.페이지 테이블에는 인덱스와 프레임이 있음.CPU에서 논리 주소 전달 → 메모리 관리자는 논리주소가 몇번 페이지인지, 오프셋은 얼마인지 알아냄. → Page Table Base Register(메모리 관리자내)를 이용해서 페이지 테이블(물리 메모리)을 찾음 → 페이지 테이블에서 페이지 번호를 인덱스로 프레임 번호를 알아내고, 오프셋을 이용해 물리주소로 변환함.물리 주소 = 프레임 번호 + 오프셋페이지 테이블에 Invalid로 표시되어 있으면 하드디스크의 스왑 영역에 저장되어 있다는 의미Page Table Base Register는 운영체제가 컨텍스트 스위칭을 할 때마다 해당 프로세스의 것으로 업데이트 해줌세그멘테이션과의 차이점세그멘테이션프로세스마다 크기가 달라 Bound Address를 가지고 있음논리적인 영역별로 크기를 다르게 세그먼트를 나눌 수 있음.페이징페이지의 크기가 동일해서 크기를 표현하는 Bound Address가 필요 없음크기가 고정되어 있어 논리적인 영역별로 나눌 수 없음.페이징에서 가장 신경 써야 하는 것은 페이지 테이블의 크기 각 프로세스마다 페이지 테이블을 가지고 있는데, 프로세스가 많아질 수록 페이지 테이블도 많아지기 때문에 프로세스가 실제로 사용할 수 있는 메모리 영역이 줄어듬.메모리 관리자가 참조하는 페이지 테이블도 물리 메모리의 운영체제 영역에 저장되어 있기 때문에 페이지 테이블 크기가 너무 크면 사용자 영역이 부족해짐이때문에 페이지 테이블의 크기를 적절하게 유지하는 것이 중요함.장점 : 외부단편화가 발생하지 않음단점 : 내부단편화가 발생함내부단편화 : 정해진 크기의 페이징보다 프로세스의 정보가 작으면 낭비되는 공간이 발생하는 것페이지드 세그멘테이션(배치정책)세그멘테이션과 페이징을 혼합해 장점을 취한 방식메모리 접근 권한메모리의 특정 번지에 부여된 권한 코드 영역 : 프로그램 그 자체 -> 읽기/실행 권한 O 데이터 영역 : 일반변수, 전역변수, 상수로 선언한 변수가 저장 -> 읽기(쓰기) 권한 O / 실행 권한 X 힙 영역 : 읽기/쓰기 권한 O / 실행 권한 X 스택 영역 : 읽기/쓰기 권한 O / 실행 권한 X메모리 접근 권한에 대한 검사 가상주소 → 물리주소로 변환될 때 마다 일어나는데, 만약 권한을 위반한다면, 에러를 발생 시키고 종료 시킴.페이지드 세그멘테이션 : 세그멘테이션 테이블(세그먼트 번호 / Base Address / Bound Address) + 페이지 테이블(인덱스 / 프레임)세그멘테이션 테이블에서권한 비트 추가Base Address → 페이지 넘버 : 이름 변경Bound Address → 페이지 개수 : 이름 변경논리 주소 0x12300번지 접근 요청시,논리 주소를 이용해 몇 번 세그먼트인지 알아냄.세그멘테이션 테이블에서 1번 인덱스를 참조해당 세그먼트가 메모리 접근 권한을 위반하는지 검사접근 권한 위반시 → 프로세스 종료위반 하지 않으면 → 페이지 넘버와 페이지 개수 가져옴페이지 넘버로 페이지 테이블에 접근해서 프레임 번호 가져옴논리 주소에서 오프셋을 알아내고오프셋 + 프레임 번호 위치 = 물리 주소물리 메모리에 해당 프레임이 없다면, 스왑 영역에서 물리 메모리로 가져옴.단점 : 물리 메모리에 접근 하기 위해서 메모리에 접근을 2번 해야함.세그멘테이션 테이블 참조할 때페이지 테이블 참조 할 때디맨드 페이징(가져오기 정책)프로세스가 실행 될때 프레세스를 이루고 있는 코드/데이터/힙/스택과 같은 모듈 중 필요한 모듈만 메모리에 올라와서 실행됨.지역성 이론 2가지공간의 지역성 : 현재 위치에서 가까운 데이터에 접근할 확률이 높음시간의 지역성 : 현재 기준으로 최근 접했던 데이터가 오래 전에 접근했던 데이터보다 접근할 확률이 높음지역성 이론은 조만간 쓸 데이터만 메모리에 올리고 당분간 필요하지 않을 것 같은 데이터는 스왑 영역으로 보내 성능을 향상 시킴디맨드 페이징 : 조만간 필요할 것 같은 데이터를 메모리고 가져오고 쓰지 않을 것 같은 데이터는 스왑 영역으로 이동 시키는 정책메모리 계층 구조에는 레지스터/캐시/메인메모리/보조저장장치가 있고, 왼쪽에서 오른쪽으로 갈수록 느리다.디맨드 페이징은 스왑영역을 보조저장장치에 저장하는데 성능 향상을 위해선 스왑영역으로 데이터를 이동시키는 것을 최소화 시켜야 함.가상 메모리의 크기 = 물리 메모리 크기 + 스왑 영역스왑인 : 스왑 영역에서 물리 메모리로 데이터를 가져 오는 것스왑아웃 : 물리 메모리에서 스왑 영역으로 데이터를 보내는 것CPU에서 논리 주소를 요청하면, 메모리 관리자는 페이지 테이블을 참조해서 물리 메모리가 있는 프레임을 알아내거나 스왑영역의 위치를 알아냄페이지 테이블에는 프레임 넘버 외에도 여러가지 비트가 있음접근 비트 : 페이지가 메모리에 올라온 후 데이터에 접근이 있었는지 알려주는 비트변경 비트 : 페이지가 메모리에 올라온 후 데이터에 변경이 있었는지 알려주는 비트유효 비트 : 페이지가 물리 메모리에 있는지 알려주는 비트읽기/쓰기/실행 비트 : 권한 비트, 해당 메모리에 접근 권한이 있는지 검사하는 비트프로세스가 가상 메모리에 접근 요청을 했을 때 메모리 관리자는 페이지 테이블을 보고 물리 메모리의 프레임을 찾아내는데, 물리 메모리에 없다면 Page Fault 라는 인터럽트를 발생 시킴Page Fault가 발생하면,보조저장장치의 스왑영역에 접근하게 되고, 해당 프로세스는 대기상태가 됨.스왑 영역에 있는 데이터가 메모리에 올라가는 작업을 시작하고메모리에 올라갔다면 대기 상태에 있던 프로세스는 실행하게 됨스왑인과 스왑아웃을 할 때 어떤게 적절한지는 운영체제가 판단함. 판단 하는 것을 페이지 교체 알고리즘이라 부름페이지 교체 정책프로세스는 데이터 접근을 위해 메모리를 참조하는데, 해당 데이터가 메모리 없으면 Page Fault가 발생함.페이지 교체 정책 : 메모리에 있는 페이지를 스왑 영역으로 옮길 때 어떤 페이지를 선택할지 결정하는 정책페이지 교체 정책의 여러가지 방법Random무작위로 선택하는 방법자주 사용되는 페이지가 선택 될 때가 있어 성능에 별로 좋지 않음많이 사용되지 않음FIFO메모리에 들어온지 가장 오래 된 페이지를 선택하는 방법장점 : 구현이 간단하고 성능도 꽤 괜찮음단점 : 자주 쓰이는 페이지가 먼저 들어왔다는 이유로 해당 페이지가 교체 되면 공평하지 않음.조금 변형해서 많이 쓰임Optimum앞으로 가장 오랫동안 쓰이지 않을 페이지를 선택하는 방법사실상 구현이 불가능함다른 알고리즘과 성능 비교를 할 때 참조용으로 쓰임LRU최근에 가장 사용이 적은 페이지를 선택하는 방법지역성 이론의 시간의 지역성에 따르면 최근 사용한 데이터가 앞으로 사용될 확률이 높기 때문에 최근에 가장 사용을 적게 한 페이지가 앞으로도 사용될 확률이 적다는 결론이 나옴Optimum 알고리즘에 근접한 성능을 보임단점프로그램이 지역성을 뛰지 않을 땐 성능이 떨어지게 됨.페이지 테이블 엔트리는 여러 개의 비트와 페이지 넘버가 저장된다고 했는데 이곳에 시간을 기록하려면 비트가 많이 필요하게 됨.LRU를 구현할 때는 접근 비트를 이용해서 LRU에 근접하게 구현함.많은 비트가 필요하기 때문에 오버 플로우 발생함빌레이디의 역설Page Fault를 줄이려고 메모리를 더 늘려서 프레임의 수를 늘렸는데 오히려 Page Fault가 더 많이 발생하는 현상FIFO에서만 발생함클락 알고리즘LRU와 유사하게 구현하는 방법을 고안한 알고리즘접근 비트 하나만 이용함일정 시간 간격마다 모든 페이지의 접근 비트를 0으로 초기화함.접근 비트의 초기값은 0으로 되어 있고, 페이지가 참조되었다면 1로 설정함.일정 시간 간격마다 페이지가 참조되었는지 참조되지 않았는지 확인할 수 있음.페이지를 원형으로 연결함.스왑영역으로 옮길 페이지를 포인터로 가르키는데 이 포인터를 클락 핸드라고 함클락핸드는 시계방향으로 돌고 있음.만약 page fault가 발생해서 스왑 영역으로 보내야 하는 상황이 나오면,클락 핸드는 현재 참조하고 있는 페이지의 접근 비트를 봄.해당 페이지의 접근 비트가 1이라면 0으로 바꾸고 클락 핸드가 다음 페이지를 가르킴.그렇게 반복하다가 접근 비트가 0인 페이지를 발견 하면 해당 페이지를 스왑 영역으로 보냄향상된 클락 알고리즘접근 비트만 이용하는 것이 아니라 변경 비트도 보는 알고리즘스왑영역으로 보내지는 높은 순위접근 비트 0, 변경 비트 0인 페이지접근 비트 0, 변경 비트 1인 페이지접근 비트 1, 변경 비트 0인 페이지접근 비트 1, 변경 비트 1인 페이지부득이하게 FIFO를 사용해야 하는 경우하드웨어적으로 접근비트를 지원하지 않는 시스템에서 사용FIFO 성능 높이는 방법 고안2차 기회 페이지 교체 알고리즘자주 사용되는 페이지에게는 또 한번의 기회를 주는 것임.만약 Page Fault 없이 페이지 접근에 성공했다면, 해당 페이지를 큐의 맨 뒤로 이동 시켜 수명을 연장 시키는 방식.성능 : LRU보다 안좋고, FIFO보다 좋음.스레싱과 워킹셋멀티프로그래밍 정도가 늘어날 수록 프로세스를 메모리에 올릴 공간이 부족해짐그럼 당장 실행되지 않는 프레임은 스왑 영역에 저장되고 Page Fault가 많이 발생하게 됨.그럼 CPU가 작업하는 시간보다 스왑 작업의 시간이 더 길어지고 CPU사용률이 떨어짐스레싱CPU 사용률을 높이려 했지만 오히려 더 떨어지는 상황원인 : 물리 메모리의 크기 부족하드웨어적 해결 : 물리 메모리 늘리기 / 스레싱이 발생하지 않으면 다른 점이 없음소프트웨어적 해결 : 프로세스가 실행되면, 일정량의 페이지를 할당하고 Page Fault의 발생 빈도수에 따라 페이지의 크기를 조절함.워킹셋현재 메모리에 올라온 페이지는 다시 사용할 확률이 높기 때문에 하나의 세트로 묶어서 메모리에 올림프로세스가 준비상태에서 실행상태가 되는 실행 컨텍스트를 할 때 사용됨.주변장치(I/O디바이스와 저장장치)주변장치 : 그래픽카드, 하드디스크, SSD, 키보드, 마우스, ...주변장치는 메인보드에 있는 버스로 연결됨.하나의 버스(I/O버스) 구성 : Address 버스, Data 버스, Control 버스레지스터 : 장치의 상태와 데이터 보관, 입출력 작업시 데이터 저장 역할, 값들은 CPU가 사용하기 위해 메모리로 이동 되기도 함.주변장치 데이터의 전송단위에 따라 2가지로 나눌수 있음.캐릭터 디바이스 : 캐릭터(글자) → 마우스, 키보드, 사운드 카드, 직병렬포트상대적으로 적은 양의 데이터 전송블록 디바이스 : 블록 → 하드디스크, SSD, 그래픽카드많은 양의 데이터 전송예전에는 주변장치들을 하나의 버스에 연결해서 사용했기 때문에 I/O 명령을 만나면 작업을 처리하는 중에는 다른 작업이 불가능하여 CPU 사용률이 떨어졌음.CPU사용률을 높이고자, 입출력 제어기와 여러 개의 버스가 추가 되면서 I/O명령을 만나 작업을 처리하는 중에 다른 작업을 할 수 있게 됨.입출력 제어기는 2개의 채널이 있음시스템 버스 : 고속으로 작동하는 CPU와 메모리 사용입출력 버스 : 주변장치가 사용 / 세부적으로 느린장치와 빠른장치를 구분하기 위해 두개의 채널로 나눠짐고속 입출력 버스 : HDD저속 입출력 버스 : 마우스, 키보드두개의 채널을 이용하여 속도 차이로 인한 병목현상 해결함그래픽카드가 다루는 데이터는 매우 대용량이라, 고속 입출력으로도 감당이 되지 않기 때문에 시스템 버스에 바로 연결하여 사용함입출력 제어기는 입출력 버스에서 온 데이터를 메모리로 옮김입출력 제어기가 CPU의 도움이 필요 없도록 DMA 제어기가 추가됨입출력 제어기는 DMA로 데이터를 직접 메모리에 저장하거 가져올 수 있음CPU와 DMA가 사용하는 메모리 영역이 겹치지 않도록 메모리 영역을 나눔마우스와 키보드마우스볼마우스 : 마우스 안에 있는 볼의 회전을 감지해서 움직임을 처리함광학마우스아래에 작은 카메라가 있고, 사진을 찍어 마우스 디바이스 컨트롤내에 DSP로 보냄 → 그 사진을 기반으로 마우스의 x축 좌표와 y축 좌표 움직임을 캐치함DSP가 마우스의 움직임과 클릭 같은 데이터를 감지 → 디바이스 컨트롤러가 CPU에게 인터럽트를 보내고 마우스 드라이버가 동작해서 데이터를 읽어감.마우스 드라이버는 운영체제에게 이벤트 신호를 줌 → 운영체제는 이 이벤트를 Foreground 애플리케이션으로 전달 → 해당 애플리케이션은 받은 마우스 이벤트 처리키보드사용자가 키보드 버튼 누르면 → 키보드의 디바이스 컨트롤러가 어떤 키를 입력 받았는지 알아냄 → CPU에게 인터럽트를 보냄 → 키보드 드라이버는 운영체제에게 이벤트를 보냄 → 운영체제는 이 이벤트를 Foreground 애플리케이션으로 전달 → 해당 애플리케이션은 받은 키보드 이벤트 처리하드디스크와 플래쉬메모리하드디스크단점느림자기적으로 처리하기 때문에, 자석을 갖다대면 데이터가 손상됨.충격에 매우 약함플래시 메모리(SSD)전기적으로 읽기 때문에 조용하고 빠름단점특정한 지점의 데이터를 썼다면 덮어쓰기가 불가능함똑같은 지점에 데이터를 쓰려면 기존에 있는 데이터를 지우고 다시 써야 하는데, 지우기 횟수가 정해져 있음. 똑같은 지점에 지우기/쓰기를 반복하면 망가짐파일과 파일 시스템사용자가 저장 요청을 하면 운영체제가 안전하게 저장해줌운영체제는 파일을 관리하기 위해 파일 관리자를 둠 → 파일 시스템파일 관리자는 파일 테이블을 이용해서 파일을 관리함파일 시스템의 기능파일과 디렉토리 생성파일과 디렉토리 수정/삭제파일 권한 관리무결성 보장백업과 복구암호화파일 시스템은 HDD나 플래시 메모리(SSD)에 저장되기 때문에 전송 단위가 블록임사용자는 바이트 단위로 접근 해야 하기 때문에 파일 관리자가 중간에서 변환해줌.확장자로 파일의 성격을 알 수 있음파일의 구조헤더 : 파일의 속성이 담겨져 있음데이터파일 디스크립터 : 운영체제가 파일을 관리하기 위해 정보를 보관하는 파일 제어 블록(FCB)파일마다 독립적으로 존재저장 장치에 존재하다가 파일이 오픈 되면 메모리로 이동함파일 시스템(운영체제)이 관리함파일 : 데이터의 집합데이터의 집합 어떻게 구성하느냐에 따라 종류가 달라짐순차 파일 구조파일의 내용이 연석적으로 이어진 형태ex) 카세트 테이프 -> 1번부터 100번까지 순차적으로 곡을 실행함장점 : 모든 데이터가 순서대로 기록되기 때문에 공간의 낭비가 없고 구조가 단순함단점 : 특정 지점에 바로 이동이 어려워 데이터 삽입/삭제시 탐색하는데 시간이 많이 걸림직접 파일 구조저장하려는 데이터를 해시함수를 통해 저장 위치를 결정하는 파일 구조장점 : 해시함수를 이용하기 때문에 데이터 접근이 빠름단점 : 해시함수의 선정이 굉장히 중요하고 저정공간이 낭비 될 수 있음.인덱스 파일 구조순차 접근과 직접 접근의 장점을 취한 것으로 두 가지 방식 모두 가능ex) 음악 재생 프로그램의 재생 목록재생 목록 : 순차 데이터로 저장2번 노래 듣고 싶음 -> 인덱스 테이블의 2번에 접근해 블록 번호 알아냄 -> 순차 데이터의 해당 블록 데이터로 이동해 재생함디렉토리관련 있는 파일의 집합체1개 이상의 파일을 가질 수 있고, 자식 디렉토리도 가질 수 있음최상위 디렉토리 = 루트 디렉토리유닉스와 리눅스최상위 디렉토리 표시 : "/"디렉토리와 디렉토리 구분 : "/"윈도우최상위 디렉토리 표시 : 파티션 이름으로 함 ex) "C:"디렉토리와 디렉토리 구분 : "\"디렉토리 헤더 : 디렉토리 정보가 시작하는 위치를 가르킴초기에는 단순 구조로 루트에만 하위 디렉토리가 생성 가능했다가 다단계 디렉토리 구조 등장했다.어떠한 디렉토리에서도 하위 디렉토리 생성 가능 ⇒ 트리 구조바로 가기 기능 때문에 순환이 있는 트리 구조임파일과 디스크파일 시스템은 메모리와 비슷하게 디스크를 일정한 크기로 공간을 나눔.일정한 크기로 나눈 공간을 블록이라고 함. (블록 크기 : 1~8KB 정도)파일 시스템은 파일 정보를 파일 테이블로 관리함.파일 제어 테이블파일 정보위치 정보(블록 포인터) : 파일이 시작하는 블록 정보하나의 파일은 여러 개의 블록으로 이루어져 있음.블록을 어떻게 연결 하는지에 따라 2가지로 나뉨연속 할당파일을 구성하는 블록을 디스크에 연속적으로 저장하는 방식장점 : 파일의 시작 지점만 알면 파일의 전체를 찾을 수 있음단점 : 메모리의 세그멘테이션 기법처럼 외부단편화가 발생함 → 사용되지 않음불연속 할당디스크에 비어있는 공간에 데이터를 분산해 저장하는 방식분산된 블록은 파일 시스템이 관리함.불연속 할당은 또 2가지로 나눠짐.연결 할당자료 구조의 연결 리스트로 관리파일 테이블에는 시작 블록에 대한 정보만 저장, 나머지는 연결 리스트를 이용해 다른 블록에 접근하는 방식인덱스 할당파일 제어 테이블의 블록 포인터가 데이터들의 인덱스를 가지고 있는 인덱스 블록을 연결함.데이터가 많아서 테이블이 꽉 찬 경우 인덱스 블록을 더 만들어 연결하기 때문에, 테이블 확장 가능파일 크기가 작다면 → 데이터를 바로 참조하는 블록 포인터 이용파일 크기가 크다면 → 간접 포인터를 이용해 많은 데이터에 접근 가능더 큰 데이터가 필요하다면 → 이중 간접 포인터, 삼중 간접 포인터 이용 가능디스크의 블록을,1KB로 나누면 → 낭비 되는 공간 줄일 수 있음, 관리해야 할 블록 수 증가8KB로 나누면 → 관리해야 할 블록 수는 적지만, 내부 단편화로 낭비되는 공간이 많아짐디스크에 파일을 저장할 때 마다 빈 공간을 찾으려 모든 공간을 탐색하는 방식은 비효율적임.파일시스템은 효율적인 관리를 위해 빈 공간을 모아둔 free block list를 가지고 있음.파일 삭제시 → 파일 테이블의 헤더 삭제, free block list에 추가함.사용했던 블록의 데이터는 남아 있기 때문에, 범죄를 저질러 파일을 삭제하였다고 하더라도 포렌식으로 파일을 복구 할 수 있음.자료구조와 알고리즘정렬 - 삽입정렬정렬되지 않은 영역에서 데이터를 하나씩 꺼내서 정렬된 영역 내 적절한 위치에 "삽입"해서 정렬하는 알고리즘정렬되지 않은 영역의 가장 앞에 있는 원소를, 정렬된 영역의 가장 뒤에 있는 원소부터 역순으로 비교함배열 [4, 1, 5, 3, 6, 2]이 있다.가장 첫 번째 수인 4만 정렬되어 있다고 가정함.정렬된 영역의 마지막 데이터인 4 와, 정렬되지 않은 영역의 첫번째 데이터인 1을 비교함.4는 1보다 크므로 4를 오른쪽 인덱스에 덮어쓰기 해줌.더 비교할 대상이 없다면, 4의 자리에 1을 덮어 쓰기 해줌.반복해줌function InsertionSort(arr) { for (let i = 1; i = 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);삽입 정렬의 성능 : O(n)의 성능장점 : 이해가 쉽고 구현이 간단함단점 : 성능이 좋지 못함.정렬 - 병합정렬분할 정복 알고리즘재귀로 정렬하는 알고리즘배열을 반으로 계속 나눠 중간을 기준으로 원소를 비교하여 작은 값이 앞에 오도록 정렬하여 병합 시켜줌function MergeSort(arr, leftIndex, rightIndex) { // leftIndex가 0, rightIndex가 7로 가정, if (leftIndex midIndex) { // 만약 오른쪽 배열 병합이 덜 끝났으면, for (let i = rightAreaIndex; i 각 단계를 거칠 때마다 영역의 수가 반으로 줄기 때문에, logn으로 말할 수 있음.병합 정렬의 성능 : O(nlogn)장점 : 성능이 O(nlogn)으로 버블정렬과 선택정렬, 삽입정렬보다 좋음.단점 : 이해와 구현이 어려움정렬 - 퀵정렬분할 정복 알고리즘에 속함정렬하기 전에 배열에 있는 숫자 중 하나를 "피벗"으로 설정함.피벗을 정하는 방법에는 여러가지가 있음.피벗을 제외한 배열의 양쪽에서 값을 비교하여,오른쪽으로 이동하는 인덱스의 값이 피벗보다 크다면 멈추고왼쪽으로 이동하는 인덱스의 값이 피벗보다 작다면 멈추고각 인덱스가 멈추면 두 인덱스의 값을 교환함.반복하다가 값을 비교하는 인덱스가 서로를 지나치면 피벗과 왼쪽으로 이동하는 인덱스의 값을 교환 해주는 방식function quickSort(arr, left, right) { if (left = arr[leftStartIndex]) { // 왼쪽 영역의 작은값인지 확인 leftStartIndex++; } while (rightStartIndex >= left + 1 && pivot 퀵 정렬의 성능피벗이 매번 배열의 반을 가르는 평균적인 경우 → O(nlogn)피벗이 한쪽으로 치우치는 경우(최악의 경우) → O(n²)최악의 경우가 발생할 확률이 극히 낮기 때문에 평균적인 성능을 말함병합 정렬이 더 좋아 보이지만, 실제로 비교하면 퀵정렬이 더 적은 비교와 더 적은 메모리 공간을 차지하기 때문에 더 좋은 알고리즘으로 평가됨.장점 : 성능이 O(nlogn)으로 버블정렬과 선택정렬, 삽입정렬보다 좋음.단점 : 이해와 구현이 어려움동적 프로그래밍 - 메모이제이션계산 결과를 저장해서 여러 번 계산하지 않도록 하는 기법계산하려는 데이터가 있는지 "검색"하고, 없다면 함수를 호출해 계산을 하고 그 결과를 "저장"시키면 됨.자료구조 중 데이터 검색과 삽입이 빠른 해시 테이블을 사용하는 것이 적절함.// 메모이제이션 적용 전 -> 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]; }메모이제이션을 적용 전의 성능 → O(n²)메모이제이션을 적용 후의 성능 → O(n)메모이제이션의 장단점장점 : 재귀적인 기법으로 하향식 계산 방식으로 어려운 문제를 간단하게 해결할 수 있고, 중복 계산을 하지 않아 속도가 빠름.단점 : 속도를 위해서 메모리 영역을 사용함. 재귀함수를 사용하는 것이기 때문에 오버헤드가 큼동적 프로그래밍 - 타뷸레이션상향식 계산 방식으로 계산에 필요한 모든 값을 전부 계산 후 테이블에 저장해둠 function fibonacci3(n) { if (n 적은 메모리 사용임에도 불구하고 앞에 만들었던 fibonacci2보다 빠른 시간을 보임.메모이제이션과 타뷸레이션 방식중 어느것이 좋은가?상황에 따라 다름.분할 정복을 해결할 때, 재귀가 더 직관적이라면, 메모이제이션을 사용하는 것이 더 유리함재귀가 직관적이지 않을 땐 타뷸레이션을 사용하면, 메모리도 절약하고 속도도 빠르게 해결할 수 있음.회고칭찬하고 싶은 점 : 인프런 워밍업 클럽을 포기하지 않고 완주했다!아쉬웠던 점 : 재귀를 이해했다고 생각했는데, 아니었다🥲보완하고 싶은 점 : 강의를 다시 여러번 들어보려고 한다. 특히 병합정렬이 여전히 이해가 되지 않는다

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

운영체제프로세스 간 통신프로세스간 통신은 1) 한 컴퓨터 내에서 파일과 파이프를 이용하는 방법과 2) 한 프로세스 내에서 데이터 영역과 힙 영역을 이용하여 쓰레드간 통신 하는 방법과 3) 소켓이나 다른 컴퓨터에 있는 함수를 호출하는 네트워크를 이용하는 방법이 있다.공유자원과 임계구역공유자원 : 프로세스 간 통신을 할 때 공동으로 이용하는 변수나 파일을 말한다.여러 프로세스가 공유하다보니 문제점이 발생하는데, 각 프로세스의 접근 순서에 따라 결과값이 달라지거나, 어떤 프로세스가 먼저 실행될지 예측하기 힘들기 때문에 연산 결과를 예측하기 힘든 동기화 문제가 발생한다임계구역 : 여러 프로세스가 동시에 사용하면 안되는 영역경쟁조건 : 공유자원을 서로 사용하기 위해 경쟁하는 것임계구역 문제를 해결하기 위해 상호 배제 메커니즘을 사용한다.상호 배제 메커니즘의 요구사항은 3가지 1) 임계 영역엔 동시에 하나의 프로세스만 접근한다.2) 여러 요청에도 하나의 프로세스의 접근만 허용한다.3) 임계구역에 들어간 프로세스는 빠르게 나와야 한다.세마포어상호배제 메커니즘 중 한가지이다.세마포어를 가진 프로세스만 공유자원에 접근하는 방법.사용자(프로세스)가 프린터(공유자원)을 사용하기 위해 프린터실 앞 대기실(대기큐)에서 대기하고 있다가, 열쇠관리자(운영체제)에게 열쇠(세마포어)를 받아서 들어가서 사용한다. 프린터실에는 열쇠(세마포어)를 가진 한 사람만 들어갈 수 있다.세마포어는 여러개를 가질 수 있다.장점 : 공유자원에 여러 프로세스가 동시에 접근하지 못하기 때문에 동기화 문제가 발생하지 않는다.단점 : 세마포어를 요청/반납 하는 함수의 순서를 이상하게 호출하면, 세마포어를 잘못 사용할 가능성이 있다.모니터세마포어의 단점을 해결한 상호배제 메커니즘운영체제가 처리하는 것이 아니라, 프로그래밍 언어 차원에서 지원하는 방법이다.대표적으로 자바에서 모니터를 지원한다.자바에서 synchronized키워드가 붙으면 동시에 여러 프로세스에서 실행시킬 수 없다.synchronized키워드가 붙은 함수를 호출했다면, 어떠한 프로세스에서도 synchronized키워드가 붙은 어떠한 함수도 호출 할 수 없다.교착상태(데드락)교착상태 : 여러 프로세스가 서로 다른 프로세스의 작업이 끝나기를 기다리다가 아무도 작업을 진행하지 못하는 상태교착상태가 발생하는 원인은 공유자원이다.교착상태의 필요조건 (한가지라도 충족되지 않으면, 교착 상태가 발생하지 않음.)1. 상호배제 : 프로세스에게 점유 당한 리소스는 다른 프로세스에게 공유되면 안 된다.2. 비선점 : 프로세스에게 점유 당한 리소스는 다른 프로세스가 강제로 빼앗을 수 없다.3. 점유와 대기 : 어떤 프로세스가 리소스A를 가지고 있는 리소스B를 원하는 상태여야 한다.4. 원형 대기 : 점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있다.데드락 해결교착상태 회피 : 프로세스들에게 자원을 할당 할 때 어느정도 자원을 할당해야 교착 상태가 발생하는지 파악해서 교착상태가 발생하지 않는 수준의 자원할당 하는 것전체자원의 수와 할당된 자원의 수를 기준으로 안정상태와 불안정상태로 나누어진다.불안정상태에 있더라도 무조건 교착 상태에 빠지는 것이 아니라, 교착상태에 빠질 확률이 높아짐.은행원 알고리즘 : 운영체제는 프로세스들에게 자원을 할당하기 전에 자기가 가지고 있는 전체 자원의 수를 알고 있어야 하고, 프로세스들은 각자 자기가 필요한 자원의 최대 숫자를 운영체제에게 알려줘야 한다. 이 숫자를 기반으로 안정상태와 불안정상태를 확인 할수있다.단점 : 비용이 비싸고 비효율적이다.교착상태를 검출하는 법가벼운 교착 상태 검출타이머를 이용하는 방식프로세스가 일정시간 동안 작업을 진행하지 않는다면 교착상태가 발생했다고 간주한다.교착 상태를 해결하기 위해 일정 시점마다 체크포인트를 만들어 작업을 저장하고 타임 아웃으로 교착상태가 발생하면 마지막으로 저장했던 체크포인트로 롤백한다.무거운 교착 상태 검출자원 할당 그래프를 이용하는 방법운영체제에서 프로세스가 어떤 자원을 사용하는지 지켜보고, 만약 순화구조가 생겼다면 교착상태가 발생했다고 간주한다.교착상태를 해결하기 위해 교착상태를 일으킨 프로세스를 강제 종료하고 다시 실행 시킬 때 체크포인트로 롤백한다.장점 : 가벼운 교착 상태 검출에서 교착상태가 발생할때 전체 프로세스가 종료되는 현상은 발생하지 않음.단점 : 운영체제가 지속적으로 자원 할당 그래프를 유지하고 검사해야 하기 때문에 오버헤드가 발생함컴파일과 프로세스프로그래밍 언어컴파일 언어 : 개발자가 코드를 작성하고 컴파일을 거쳐 0과 1로 된 기계어로 실행파일을 만듬기계어이기 때문에 속도가 빠름인터프리터 언어 : 개발자가 작성한 코드를 실행시 코드를 한 줄 씩 해석해 실행하는 언어실행시 오류 날 수도 있고, 컴파일언어와 비교하면 느림프로세스의 메모리 구조CODE영역 : 실행해야 할 코드DATA영역 : 전역변수나 배열HEAP영역 : 프로세스가 실행될 때 할당되는 메모리. 유동적인 공간STACK영역 : 프로세스가 실행될 때 할당되는 메모리. 지역변수와 함수 관련 값컴파일 언어의 컴파일 과정 : test.c → 전처리기 → test.i → 컴파일러 → test.s → 어셈블러 → test.o → 링커 → test.exe메모리 종류레지스터 : 가장 빠른 기억 장소, 휘발성메모리메인메모리(RAM) : 운영체제와 다른 프로세스들이 올라가는 장소, 휘발성메모리보조저장장치(HDD, SSD) : 비휘발성 메모리. 메인메모리에 비해서 훨씬 저렴함.메모리와 주소주소 : 운영체제는 메모리를 관리하기 위해서 1바이트 크기로 구역을 나누고 숫자를 매기는 것물리주소공간 : 메모리를 컴퓨터에 연결하면 0번째부터 시작하는 주소 공간논리주소공간 : 사용자 관점에서 바라본 주소공간사용자는 논리주소로 물리주소에 접근할 수 있음.메모리에는 운영체제를 위한 공간이 따로 있고, 메모리 관리자가 경계 레지스터로 사용자 프로세스가 경계레지스 터의 값을 벗어났는지 검사하고 만약 벗어났다면 그 프로세스를 종료 시킨다.절대주소 : 메모리관리자가 바라보는 주소공간(물리주소)상대주소 : 사용자가 바라보는 주소공간 상대주소(논리주소)재배치 레지스터 : 프로그램의 시작 주소가 저장되어 있고, CPU가 데이터를 요청하면 메모리 관리자가 재배치 레지스터에 있는 프로그램의 시작 주소와 CPU가 데이터를 요청한 주소를 더하여 데이터를 가져와 전달하게 된다.만약 프로그램의 시작 위치가 바뀌어도 재배치 레지스터만 수정해주면 되기 때문에 굉장히 유연하다.메모리 할당방식유니프로그래밍 환경에서 메모리보다 더 큰 프로그램을 실행 시킬때 메모리 오버레이 방식을 사용한다.메모리 오버레이 방식 : 큰 프로그램을 메모리 위에 잘라서 올리고, 남은 조각은 하드디스크의 스왑영역에 저장시키는 방식스왑 : 스왑영역에 있는 데이터 일부를 메모리로 가져오고 메모리에 있는 데이터를 스왑영역으로 옮기는 것멀티프로그래밍 환경에서 메모리 관리가변 분할 방식 : 프로세스의 크기에 따라 메모리를 나누는 방식장점 : 메모리에 연속된 공간에 할당되기 때문에 더 크게 할당되서 낭비되는 공간인 내부 단편화가 없음단점 : 외부 단편화가 발생함.고정 분할 방식 : 프로세스의 크기와 상관없이 메모리를 정해진 크기로 나누는 방식장점 : 구현이 간단하고 오버헤드가 적음단점 : 작은 프로세스도 큰 영역에 할당되서 공간이 낭비되는 내부 단편화가 발생함.외부 단편화 : 메모리에 서로 다른 크기를 가지고 있는 여러개의 프로세스중 작업을 마친 프로세스가 메모리에서 내려가면 그 프로세스들이 있는 공간은 빈공간이 된다. 이때, 그 빈 메모리를 전부 합친 공간이 필요한 프로세스가 있을때, 연속된 공간이 아니기 때문에 새로운 프로세스에게 메모리를 할당할 수 없다.외부단편화의 해결법으로 조각모음을 해주면 되지만, 현재 메모리에서 실행되고 있는 프로세스들의 작업을 일시 중지하고, 메모리 공간을 이동시키는 작업을 해야하기 때문에 오버헤드가 발생함.내부 단편화 문제는 분할된 크기를 조절해서 내부 단편화를 최소화 하는 방법밖에 없다.버디 시스템 : 2의 승수로 메모리를 분할해 메모리를 할당하는 방식메모리의 크기가 2048바이트라고 가정할 때, 크기가 500바이트인 프로세스가 할당을 원하면, 먼저 2의 승수로 500바이트보다 작은 바이트를 만날 때까지 메모리를 나누고, 512바이트에 할당 한다. 이때 내부 단편화가 발생하지만, 12바이트밖에 낭비가 생기지 않는다.장점 : 프로세스 크기에 따라 할당되는 메모리 크기가 달라지고, 외부 단편화를 방지하기 위해 메모리 공간을 확보하는 것이 간단하다. 내부 단편화가 발생하기는 하지만, 많은 공간의 낭비가 발생하지 않는다. 자료구조와 알고리즘재귀어떠한 것을 정의할 때 자기 자신을 참조하는 것재귀 함수는 기저조건(탈출조건)이 반드시 있어야 한다.기저조건이 없이 실행된다면, 콜스택이 가득차서 메모리가 부족하여 자동으로 종료된다.for문으로 해결할 수 있는 작업을 재귀함수로 해결하면 비효율적이다.재귀함수는 더 복잡한 문제를 쉽게 해결하기 위해 사용된다. (대표적으로 팩토리얼)재귀적으로 생각하기패턴1 : 단순히 반복 실행하는 패턴 → 성능 안좋음function myFunction(number) { if (number > 3) return; // 기저조건 console.log(number); myFunction(number + 1); } myFunction(1);패턴2 : 하위 문제의 결과를 기반으로 현재 문제를 계산하는 것하향식 계산 방식은 재귀 방식으로만 구현할 수 있다.function factorial(number) { if (number === 1 || number === 0) { return 1; } return number * factorial(number - 1); } console.log(factorial(5));재귀 - 하노이탑하노이탑 규칙1. 한 번에 하나의 원반을 움직 일 수 있다.2. 가장 위에 있는 원반만 옮길 수 있다.3. 아래에 작은 원반이 올 수 없다.function hanoi(count, from, to, temp) { if (count === 0) return; hanoi(count - 1, from, temp, to); console.log(`원반 ${count}를 ${from}에서 ${to}로 이동`); hanoi(count - 1, temp, to, from); } hanoi(3, "A", "C", "B"); // 원반3개, A기둥(from)에서 C기둥(to)로 이동하는데, B기둥(temp)도 사용함하노이탑을 재귀로 접근하기(하향식 접근 방식)기둥A에 있는 원반1,2,3을 기둥C로 옮기기원반1, 기둥C 이동 → 원반2, 기둥B 이동 → 원반1, 기둥B 이동 → 원반3, 기둥C 이동원반1, 기둥A 이동 → 원반2, 기둥C 이동 → 원반1, 기둥C 이동 정렬 - 버블 정렬앞에 있는 숫자와 옆에 있는 숫자를 비교해서 자리를 바꾸는 알고리즘. 정렬이 완료된 범위는 제외한다.버블 정렬의 성능 : O(n²)장점 : 가장 쉽게 생각할 수 있는 정렬 방법으로 이해와 구현이 간단하다.단점 : 성능이 O(n²)으로 좋지 않음.정렬 - 선택정렬배열의 정렬되지 않은 영역의 첫 번째 원소를 시작으로 마지막 원소까지 비교 후 가장 작은 값을 첫 번째 원소로 가져온다. 배열의 끝에 다다를때까지 반복하는데, 정렬이 완료된 범위는 제외한다.선택 정렬의 성능 : O(n²)장점 : 이해와 구현이 간단하다단점 : 성능이 O(n²)으로 좋지 않다.회고칭찬하고 싶은 점 : 진도표 대로 따라가지는 못했지만, 벼락치기로 한주를 마무리 한건 아니어서 만족한다.아쉬웠던 점 : 재귀를 이해하려고 노력했는데, 아직은 조금 이해가 부족한 것 같다. 인프런 워밍업 클럽에 출석체크 방이 있다는 것을 이제야 알았다..!보완하고 싶은 점 : 여러 재귀함수 예시를 찾아보려고 한다.다음주의 목표 : 밀리지 않고, 진도표대로 따라가기. 늦었지만, 출석체크 꼬박꼬박 하기.

[인프런 워밍업 클럽 스터디 3기 - CS전공지식] 2주차 과제 - 자료구조와 알고리즘

자료구조와 알고리즘1. 재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?✨ 재귀함수를 탈출하지 못하고, 콜스택이 가득 차서 메모리가 부족하여 자동으로 종료됩니다.2. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function sumOdd(n) { if (n === 0) return 0; // 기저 조건 const isOdd = n % 2 ? n : 0; return isOdd + sumOdd(n - 1); } console.log(sumOdd(10)); // 253. 다음 코드는 매개변수로 주어진 파일 경로(.는 현재 디렉토리)에 있는 하위 모든 파일과 디렉토리를 출력하는 코드입니다. 다음 코드를 재귀 함수를 이용하는 코드로 변경해보세요.const fs = require("fs"); // 파일을 이용하는 모듈 const path = require("path"); // 폴더와 파일의 경로를 지정해주는 모듈 // before 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("."); // 현재 경로의 모든 하위 경로의 파일, 디렉토리 출력✨ 코드function traverseDirectory2(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); traverseDirectory2(filePath); // 재귀함수 호출 } else { console.log("파일:", filePath); } } } traverseDirectory2(".");✨ 출력화면✨예시 코드가 출력되는 순서와는 좀 다르지만, (아마 pop() 때문인거로 추측됨) 하위 경로의 파일, 디렉토리 출력은 잘 된다. 기저 조건이 필요 없을거 같긴 한데, 재귀함수니깐 추가하였다.

[인프런 워밍업 클럽 스터디 3기 - CS전공지식] 2주차 과제 - 운영체제

운영체제1. FIFO 스케줄링의 장단점이 뭔가요?✨장점 : 단순하고 직관적입니다✨단점 : 대기시간이 길고, I/O 작업 요청이라면, 작업이 끝날때까지 CPU가 쉬고 있기 때문에 CPU 사용율이 떨어집니다.2. SJF를 사용하기 여러운 이유가 뭔가요?✨어떤 프로세스가 어느 시간만큼 실행될지 예측이 불가능하고, 실행 시간이 긴 프로세스는 실행되지 않을 수 있습니다.3. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?✨타임 슬라이스가 작으면, 프로세스들이 동시에 동작하는 것처럼 느껴지지만, 컨텍스트 스위칭이 너무 잦게 일어나고, 프로세스의 처리량보다 컨텍스 스위칭을 처리하는 양이 훨씬 커져 오버헤드가 발생합니다.4. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?✨스스로 CPU 할당을 반납하면 I/O Bound Process일 확률이 높고, 강제로 CPU 할당을 해제당하면 CPU Bound Process일 확률이 높습니다.5. 공유자원이란무엇인가요?✨프로세스 간 통신을 할 때 공동으로 이용하는 변수나 파일을 말합니다.6. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?✨공유자원을 한 프로세스가 점유 했다면,1. 그 공유자원을 공유 해서도 안되고,2. 그 공유자원을 빼앗을수 없어야 하며,3. 공유자원을 가지고 있는 프로세스가 다른 공유자원을 원하는 상태여야 하고,4. 점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있어야 합니다.이 중 한가지라도 충족되지 않으면 교착상태가 발생하지 않습니다.

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

운영체제운영체제에 대하여운영체제가 하는 일에는 프로세스/메모리/하드웨어/파일 시스템 관리가 있다.운영체제의 핵심은 커널이고, 커널은 프로세스와 메모리, 저장장치를 관리하는 핵심적인 기능을 담당한다.커널에는 직접 접근할 수 없기 때문에, 사용자와 어플리케이션은 인터페이스로 시스템 콜을, 하드웨어는 인터페이스로 드라이버를 사용한다.CPU는 중앙처리장치로, 산술논리연산장치, 제어장치, 레지스터로 구성되어 있다.메모리의 종류는 RAM과 ROM 두가지가 있는데,RAM : 전력이 끊기면 데이터를 잃어버리기 때문에, 메인 메모리로 사용된다.ROM : 전력이 끊겨도 데이터를 보관하기 때문에, 컴퓨터 부팅과 관련된 바이오스가 저장된다.인터럽트 : 입출력 작업을 진행할때, 입출력 작업이 완료되면, CPU에게 신호를 주고 CPU는 그 신호를 받아 인터럽트 서비스 루틴을 실행시켜 작업을 완료하는 방식.비동기적으로 동작하기 때문에 성능면에서 폴링방식보다 훨씬 좋다. 프로세스와 쓰레드프로그램 : 어플리케이션/앱/.exe 파일과 같은 것.프로세스 : 하드디스크에 저장된 프로그램이 메모리에 올라갔을 때 실행 중인 프로그램.프로세스의 구조 : Code 영역 / Data 영역 / Heap 영역 / Stack 영역멀티프로그래밍 : 메모리에 여러개의 프로세스를 올려서 처리 하는 것멀티프로세싱 : 여러개의 CPU에 여러개의 프로세스를 올려서 처리하는 것PCB : 프로세스의 정보를 가지고 있음.연결리스트 자료구조로 저장되어 있음.PCB구조 : 포인터 / 프로세스 상태 / 프로세스 ID / 프로그램 카운터 / 레지스터 정보 / 메모리 관련 정보 / CPU 스케줄링 정보프로세스 상태는 생성/준비/실행/대기/완료의 다섯가지 상태를 가지고 있다.컨텍스트 스위칭 : 프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행중인 프로세스의 상태를 저장하고 다른 프로세스의 상태값으로 교체하는 작업스위칭이 일어날때 PCB 변경되는 값은 프로세스 상태/프로그램 카운터/레지스터 정보/메모리 관련 정보가 있다.컨텍스트 스위칭 발생 이유 : CPU 점유 시간이 끝나거나, I/O 요청이 있거나, 다른 종류의 인터럽트가 있을때 발생한다.프로세스의 생성 과정은 프로그램의 코드영역과 데이터영역을 메모리에 로드하고 빈 Stack과 빈 Heap을 만들어 공간을 확보하고 PCB를 만들어 값을 초기화해준다. 운영체제가 부팅이 되고 0번 프로세스가 생성될때 딱 한번만 실행된다.나머지 모든 프로세스는 0번 프로세스를 복사하여 사용한다.쓰레드 : 프로세스 내에 존재하고 1개 이상이 있을 수 있다.프로세스 내의 PCB, 코드, 데이터, 힙 영역을 공유하고, 스택은 각각 가지고 있다.운영체제가 작업을 처리하는 단위다.CPU스케줄링CPU스케줄링 : 운영체제가 프로세스에게 CPU의 할당과 해제를 하는 것.운영체제는 PCB의 우선순위를 참고하여 준비상태의 다중큐에 넣는다. 이때 CPU스케줄러는 준비상태의 다중큐를 참조해서 어떤 프로세스를 실행시킬지 결정한다.FIFO : 먼저 들어온 프로세스가 먼저 실행되는 방식장점 : 단순하고 직관적단점 : 대기시간이 길고, CPU 사용율이 떨어짐SJF : 짧은 작업 먼저 실행하는 방식. 프로세스의 작업 시간을 추정하기 힘든 문제점 때문에 구현하기 힘들다.RR : CPU가 일정한 시간만 부여하여 그 시간만큼만 실행되게 하는 알고리즘. CPU할당 시간이 끝나면 해당 프로세스는 강제로 큐의 가장 마지막으로 밀려남.FIFO의 단점을 해결하여 나온 알고리즘FIFO와 RR의 평균대기시간이 비슷하다면, RR 알고리즘이 좀 더 비효율적임.MLFQ : 우선순위를 가진 큐를 여러개 준비, 우선순위가 높으면 타임슬라이스 크기가 작고, 우선순위가 낮으면 타임 슬라이스 크기가 큼. 타임 슬라이스 크기를 오버해서 강제로 CPU를 뺏긴다면 해당 프로세스의 우선순위를 한 단계식 아래로 내림. 운영체제에서 가장 일반적으로 쓰이는 알고리즘.자료구조와 알고리즘개요자료구조 : 데이터가 어떤 구조로 저장되고 어떻게 사용되는지를 나타냄알고리즘 : 어떤 문제를 해결하기 위한 확실한 방법시간복잡도 : 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간시간을 측정하는 방식이 아닌 코드에서 성능에 많은 영향을 주는 부분을 찾아서 실행 시간을 예측하는 것.코드에서 성능에 많은 영향을 주는 부분은 "반복문"이다.자료구조배열 : 모든 프로그래밍 언어에서 기본적으로 제공하는 자료구조장점 : 읽기 쓰기와 같은 참조에는 O(1)의 성능을 가짐단점 : 크기 예측이 힘들기 때문에 메모리 낭비가 발생할 수 있음. 데이터 삽입과 삭제가 비효율적연결리스트 : 메모리 공간에 데이터와 다음 노드를 가리키는 Next를 가지는 노드를 분산해 할당하고, 이 데이터를 서로 연결해주는 것장점 : 배열의 초기 크기를 알아야할 필요가 없다.단점 : 배열의 인덱스 참조처럼 접근하려면, O(n)의 성능을 가짐.스택 : 먼저 들어간 데이터가 나중에 나오는 규칙을 가지고 있는 자료 구조큐 : 먼저 들어간 데이터가 가장 먼저 나오는 규칙을 가지고 있는 자료 구조덱 : 데이터 삽입과 제거를 head와 tail 두군데서 자유롭게 할 수 있는 자료 구조해시테이블 : 해시함수로 테이블의 인덱스를 새로 만드는 것해시함수 : 어떠한 계산을 하여 인덱스를 부여하는 함수장점 : 빠른 데이터 읽기, 삽입, 삭제메모리를 많이 차지함, 좋은 해시 함수의 구현이 필수셋 : 데이터의 중복을 허용하지 않는 자료 구조 회고칭찬하고 싶은 점 : 자료구조의 코드를 이해하려고 혼자 직접 그려보고 코드도 작성해보면서 노력하였다.아쉬웠던 점 : 이번주는 일정 조율을 좀 잘못하여, 거의 벼락치기마냥 공부해서 정신이 없었다. 그래서인지 원래도 정리를 못하지만 더욱더 정리가 되지 않아 좀 답답했다.보완하고 싶은 점 : 다음엔 좀 더 정리를 깔끔하게 하고 싶다.다음주의 목표 : 다음주는 벼락치기식이 아닌 스케줄대로 차근차근히 공부해서 지식을 흡수하고 싶다.

[인프런 워밍업 클럽 스터디 3기 - CS전공지식] 1주차 과제 - 자료구조와 알고리즘

자료구조와 알고리즘 1. 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다. 이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.✨연결리스트✨학생의 정원이 고정이 아니고, 상황에 따라 처음/중간/마지막에 삽입될 수도 있기 때문에 연결리스트로 선택할 것 같습니다.2. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.✨큐✨연결리스트로도 충분히 할 수 있을거 같지만, 시간복잡도를 생각해보았을때 연결리스트로는 O(n)의 성능이 나오기 때문에 O(1)으로 처리 가능한 큐를 선택할 것 같습니다.3. 우리가 구현한 스택은 0번 인덱스, 즉 입구쪽으로 데이터가 삽입되고 나오는 구조입니다. 반대로 마지막 인덱스, 즉 출구쪽으로 데이터가 삽입되고 나오는 구조로 코드를 변경해주세요.import { LinkedList } from "./LinkedList.mjs"; class Stack { constructor() { this.list = new LinkedList(); } push(data) { this.list.insertLast(data); } pop() { try { return this.list.deleteLast(); } catch (error) { return null; } } peak() { return this.list.getNodeAt(0); } isEmpty() { return this.list.count == 0; } } export { Stack };4. 해시테이블의 성능은 해시 함수에 따라 달라집니다. 수업 시간에 등번호를 이용해 간단한 해시 함수를 만들어봤습니다. 이번엔 등번호가 아닌 이름을 이용해 데이터를 골고루 분산시키는 코드로 수정해주세요.힌트: charCodeAt() 함수를 이용예시: name1 = "이운재";name1.charCodeAt(0); // 51060 이운재의 0번 인덱스 ‘이’의 유니코드 출력hashFunction(name){ return name.charCodeAt(0) % 10 }

[인프런 워밍업 클럽 스터디 3기 - CS전공지식] 1주차 과제 - 운영체제

1주차 과제 제출 - 운영체제 while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다.이 방식은 폴링방식입니다.1초마다 체크하기 때문에 성능에 좋지 않습니다.이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?✨인터럽트 방식.입출력 작업을 진행할때, 입출력 작업이 완료되면, CPU에게 신호를 주고 CPU는 그 신호를 받아 인터럽트 서비스 루틴을 실행시켜 작업을 완료하는 방식.비동기적으로 동작하기 때문에 성능면에서 폴링방식보다 훨씬 좋다.2. 프로그램과 프로세스가 어떻게 다른가요?✨프로그램 : 하드디스크 등과 같은 저장 장치에 저장된 명령문의 집합체. (어플리케이션/앱/.exe) / 하드 디스크와 같은 저장 장치만 사용하는 수동적인 존재✨프로세스 : 하드디스크에 저장된 프로그램이 메모리에 올라갔을 때 실행 중인 프로그램 / 메모리도 사용하고, 운영체제의 CPU 스케줄링 알고리즘에 따라서 CPU도 사용하고, 필요에 따라 I/O도 사용하기 때문에 능동적인 존재.3. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?✨멀티프로그래밍 : 하나의 CPU에 여러개의 프로세스를 올려 처리하는 것.✨멀티프로세싱 : 여러개의 CPU로 프로세스를 처리하는 것.4. 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?✨"준비 상태의 다중큐"를 참조하여 프로세스의 우선순위를 보고 CPU할당과 해제를 하는 CPU 스케줄링을 사용함.5. 컨텍스트 스위칭이란 뭔가요?✨CPU 점유 시간이 끝나거나, I/O요청이 있거나, 다른 종류의 인터럽트가 있을때, 현재 실행중인 프로세스의 상태를 저장하고, 다른 프로세스의 상태값으로 교체하는 작업