CS 전공지식 스터디 3기 [3주차] 자료구조와 알고리즘 미션

CS 전공지식 스터디 3기 [3주차] 자료구조와 알고리즘 미션Q. 지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요. A.버블 정렬 (Bubble Sort)장점:구현이 매우 간단하고 직관적입니다.데이터가 거의 정렬되어 있으면 성능이 좋습니다.안정적인 정렬 알고리즘입니다.단점:시간 복잡도가 O(n²)로, 대규모 데이터에 대해 비효율적입니다.최악의 경우에도 개선되지 않는 성능을 가집니다.시간 복잡도:최선: O(n) (데이터가 이미 정렬된 경우)평균: O(n²)최악: O(n²)선택 정렬 (Selection Sort)장점:구현이 매우 간단하고 직관적입니다.추가적인 메모리 공간이 필요하지 않으며, 인플레이스 정렬입니다.단점:시간 복잡도가 O(n²)로, 대규모 데이터에 대해 비효율적입니다.안정적이지 않으며, 항상 일정한 성능을 보입니다.시간 복잡도:최선: O(n²)평균: O(n²)최악: O(n²)삽입 정렬 (Insertion Sort)장점:구현이 간단하고 직관적입니다.거의 정렬된 데이터에 대해 성능이 뛰어나며, 최선의 경우 시간 복잡도는 O(n)입니다.안정적인 정렬 알고리즘입니다.단점:최악의 경우(역순 정렬) 시간 복잡도가 O(n²)로 비효율적입니다.데이터가 많을 경우 성능이 저하됩니다.시간 복잡도:최선: O(n)평균: O(n²)최악: O(n²)병합 정렬 (Merge Sort)장점:O(n log n)의 시간 복잡도로 안정적이고 빠릅니다.데이터의 양이 많을 때 일관된 성능을 제공합니다.안정적인 정렬 알고리즘입니다.단점:O(n)의 추가 공간을 필요로 하므로, 메모리 사용이 큽니다.시간 복잡도:최선: O(n log n)평균: O(n log n)최악: O(n log n)퀵 정렬 (Quick Sort)장점:평균적으로 O(n log n)의 시간 복잡도를 가집니다.추가적인 공간이 거의 필요하지 않으며, 인플레이스 정렬입니다.대규모 데이터에서 빠른 성능을 보입니다.단점:최악의 경우(이미 정렬된 데이터에 대해 피벗을 잘못 선택한 경우) O(n²)의 시간 복잡도를 가집니다.안정적이지 않습니다.시간 복잡도:최선: O(n log n)평균: O(n log n)최악: O(n²)Q. 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요. A.메모이제이션 (Memoization)과 타뷸레이션 (Tabulation)은 모두 동적 프로그래밍(Dynamic Programming)의 기법으로, 문제를 작은 부분 문제로 나누어 해결하고 그 결과를 저장하여 중복 계산을 피하는 방법입니다.두 방법은 다음과 같은 차이점이 있습니다.메모이제이션은 재귀적으로 해결하며, 각 부분 문제의 결과를 함수 호출 시점에 계산하고 저장합니다.타뷸레이션은 반복문을 사용하여 부분 문제를 해결하고, 모든 하위 문제의 결과를 테이블에 저장합니다.메모이제이션을 선택할 경우:장점:문제의 일부만 계산하고 나머지는 재사용하는 방식으로, 필요한 부분만 계산하므로 메모리를 더 효율적으로 사용할 수 있습니다.직관적이고, 코드가 재귀적으로 작성되므로 구현이 간단할 수 있습니다.단점:재귀 호출로 인한 스택 오버플로우 문제가 발생할 수 있습니다. 특히, 큰 문제에서 많은 재귀 호출이 일어날 때 문제가 될 수 있습니다.타뷸레이션을 선택할 경우:장점:반복문을 사용하므로 재귀 호출이 없고, 스택 오버플로우 문제가 발생하지 않습니다.문제를 bottom-up 방식으로 해결하기 때문에 결과가 모두 테이블에 저장되어 메모리 상에서의 효율성이 좋습니다.단점:코드가 길어질 수 있고, 어떤 순서로 문제를 해결할지를 잘 계획해야 합니다.메모이제이션과 타뷸레이션 중 선택하는 이유:메모리가 부족한 시스템에서는 타뷸레이션을 선택하는 것이 더 바람직할 수 있습니다. 타뷸레이션은 스택을 사용하지 않고, 반복문을 사용하여 문제를 해결하므로 재귀 호출로 인한 메모리 사용이 없습니다.메모리 오버헤드를 줄이기 위해, 메모이제이션처럼 깊은 재귀 호출을 피할 수 있습니다.따라서 메모리가 부족한 시스템에서는 타뷸레이션을 사용하는 것이 더 적합할 수 있습니다.

CS 전공지식 스터디 3기 [3주차] 운영체제 미션

CS 전공지식 스터디 3기 [3주차] 운영체제 미션Q. 메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.A.주기억장치 (Primary Memory)RAM (Random Access Memory):데이터를 임시로 저장하며, 휘발성 메모리입니다. 컴퓨터가 실행 중일 때 사용됩니다.특징: 빠른 속도, 휘발성, CPU와 직접적으로 연결되어 있음.ROM (Read Only Memory):데이터를 읽기 전용으로 저장하며, 비휘발성 메모리입니다. 주로 펌웨어를 저장합니다.특징: 비휘발성, 읽기만 가능, 시스템 시작 시 필요한 코드나 데이터 저장.보조기억장치 (Secondary Memory)HDD (Hard Disk Drive):자기 디스크에 데이터를 저장하는 비휘발성 메모리입니다. 대용량 데이터를 저장할 수 있지만 속도는 상대적으로 느립니다.특징: 비휘발성, 대용량, 상대적으로 느린 속도.SSD (Solid State Drive):플래시 메모리를 이용한 저장 장치로, HDD보다 빠른 속도를 자랑합니다.특징: 비휘발성, 빠른 속도, 가격이 상대적으로 비쌈.캐시 메모리 (Cache Memory)CPU와 주기억장치 사이에 위치하며, CPU의 작업 효율을 높이기 위해 자주 사용되는 데이터를 임시 저장합니다.특징: 매우 빠른 속도, CPU와 밀접하게 연동됨. Q. 사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?A.기본 레지스터 (Base Register): 메모리 영역을 보호하는 데 사용되며, 프로세스가 접근할 수 있는 메모리의 범위를 설정합니다.한계 레지스터 (Limit Register): 프로세스가 접근할 수 있는 메모리 범위의 크기를 설정합니다. 이 두 레지스터를 조합하여 운영체제는 프로세스가 할당된 메모리 영역을 벗어나지 않도록 제어합니다. Q. 메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?A.고정 분할 방식 (Fixed Partitioning)장점:구현이 간단하고 빠르며, 관리가 용이합니다.단점:메모리의 일부가 낭비될 수 있습니다. 각 파티션이 고정되어 있어 프로세스 크기가 크거나 작아도 불필요한 공간이 발생할 수 있습니다.메모리의 유연성이 떨어집니다.가변 분할 방식 (Dynamic Partitioning)장점:메모리 사용이 효율적이며, 공간을 필요에 맞게 할당할 수 있습니다.단점:할당과 해제를 반복할 때 외부 단편화가 발생할 수 있습니다.메모리 할당과 해제의 관리가 복잡할 수 있습니다. Q. CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요? A.스래싱 (Thrashing):프로세스들이 메모리 부족으로 인해 자주 스왑되어 CPU가 대부분의 시간을 스왑 작업에 소모하게 되는 현상입니다. 이로 인해 실제로 실행되는 작업이 거의 없고, 시스템 성능이 급격히 저하됩니다. Q. HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요? 이유를 함께 적어주세요.A.필수적입니다.컴퓨터를 부팅하고 운영체제와 프로그램을 실행하려면 저장 장치가 필요합니다. HDD나 SSD는 운영체제, 파일 시스템, 애플리케이션 등을 저장하는 데 필수적인 역할을 하며, 컴퓨터의 영구적 저장을 담당합니다. RAM은 휘발성이기 때문에 컴퓨터가 종료되면 모든 데이터가 사라지지만, HDD나 SSD는 데이터를 영구적으로 저장할 수 있습니다. Q. 파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?A.삭제된 파일의 실제 데이터는 지워지지 않기 때문입니다.파일을 삭제하면 운영체제에서 그 파일이 저장된 공간을 "빈 공간"으로 표시하고, 새로운 파일이 그 공간을 덮어쓸 때까지 실제 데이터는 하드 디스크에 남아있습니다. 따라서 포렌식 도구는 삭제된 파일의 데이터를 찾을 수 있는 방법을 제공하며, 특별한 덮어쓰기 작업이 없다면 파일을 복구할 수 있습니다.

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

인프런 워밍업 클럽 스터디 3기 - CS 전공지식 섹션8가상 메모리가 나오게 된 이유?물리 메모리(RAM)의 한계를 극복하기 위해 가상 메모리(Virtual Memory)가 등장함초창기 컴퓨터에서는 실행 가능한 프로그램의 크기가 물리 메모리(RAM) 크기보다 작거나 같아야 했음하지만 프로그램이 커지면서 RAM 용량을 초과하는 프로그램 실행이 필요해짐이를 해결하기 위해 디스크(하드 디스크 등)를 이용하여 RAM처럼 사용할 수 있도록 만든 개념이 가상 메모리가상 메모리란?물리 메모리보다 더 큰 주소 공간을 제공하기 위해 디스크를 활용하는 기술프로세스가 실행될 때, 필요한 데이터만 RAM에 적재하고, 나머지는 하드디스크의 가상 메모리 영역(스왑 영역)에 저장프로세스가 참조하는 데이터가 RAM에 없으면 페이지 폴트(Page Fault) 발생 → 디스크에서 해당 데이터를 RAM으로 불러옴쉽게 말하면→ RAM이 부족할 때, 하드 디스크를 추가적인 메모리처럼 활용하는 기술가상 메모리 크기는 어떻게 결정될까?가상 메모리의 크기는 주로 운영체제(OS)와 CPU 아키텍처에 의해 결정됨.CPU의 주소 지정 방식32비트 시스템: 최대 4GB (2³²)64비트 시스템: 이론적으로 최대 16EB (2⁶⁴) (실제 OS마다 제한 다름)운영체제의 정책OS 설정에 따라 가상 메모리 크기 조절 가능 (ex. Windows에서는 "가상 메모리 크기 변경" 설정 가능)하드 디스크 용량가상 메모리는 RAM 일부 + 하드 디스크의 스왑 공간으로 구성됨하드 디스크 용량이 작으면 가상 메모리 크기도 제한됨일반적인 가상 메모리 크기 설정:Windows: RAM의 1.5배 ~ 2배 정도가 기본 설정Linux: 스왑 영역(Swap Partition) 크기를 RAM 크기의 2배로 설정하는 경우 많음가상 메모리를 사용하는 과정프로세스가 주소(가상 주소)를 요청CPU는 MMU(메모리 관리 장치, Memory Management Unit)를 통해 가상 주소를 물리 주소로 변환변환된 주소가 RAM에 존재하면 그대로 사용만약 RAM에 없으면?페이지 폴트(Page Fault) 발생디스크에서 해당 페이지를 RAM으로 가져옴 (스왑)필요 없어진 페이지는 디스크로 내보냄 (페이징 기법 활용)가상 메모리 시스템이란?운영체제가 가상 메모리를 관리하는 시스템페이지 테이블을 이용하여 가상 주소 → 물리 주소 변환페이지 교체 알고리즘(LRU, FIFO 등)을 사용하여 필요한 데이터만 RAM에 유지스왑 영역을 활용하여 필요 없는 페이지는 디스크로 이동하드 디스크의 스왑 영역(Swap Area)이란?RAM이 부족할 때, 데이터를 저장하는 하드 디스크의 공간Linux에서는 Swap Partition, Windows에서는 Pagefile.sys라고 함RAM이 꽉 차면 덜 중요한 데이터를 Swap 영역으로 이동하지만 하드 디스크는 RAM보다 속도가 훨씬 느리므로 성능 저하가 발생할 수 있음즉, RAM의 부족을 보완하지만 속도가 느려서 주의해야 함!메모리 관리자란?운영체제(OS)에서 메모리를 효율적으로 관리하는 역할을 하는 모듈메모리 관리자의 역할?프로세스가 사용할 메모리를 할당 및 해제가상 주소를 물리 주소로 변환페이지 교체 및 스왑 관리외부 단편화와 내부 단편화 해결동적 주소 변환이란?프로세스가 실행 중일 때, 논리 주소(가상 주소)를 물리 주소로 변환하는 과정CPU의 MMU(메모리 관리 장치)가 논리 주소 → 물리 주소 변환 수행페이지 테이블을 이용하여 매핑실행 중인 프로그램이 직접 물리 주소를 알 필요 없음 (OS가 관리)즉, 프로그램이 실제 메모리 주소를 신경 쓰지 않아도 실행 가능하도록 하는 기술!가상 메모리 시스템에서 가변 분할 방식과 고정 분할 방식가변 분할 방식(Variable Partitioning) - 세그멘테이션(Segmentation)프로세스 크기에 맞춰 메모리를 동적으로 할당하는 방식장점메모리를 효율적으로 사용할 수 있음 (공간 낭비 최소화)단점외부 단편화(External Fragmentation) 발생고정 분할 방식(Fixed Partitioning) - 페이징(Paging)고정된 크기의 페이지 단위로 메모리를 나누어 할당장점외부 단편화 없음 (고정된 크기의 페이지 사용)단점내부 단편화(Internal Fragmentation) 발생 가능운영체제에서는 보통 "세그멘테이션 + 페이징"을 혼합하여 사용페이징(Paging)이란?가상 메모리를 일정한 크기(페이지)로 나누어, 물리 메모리에 적재하는 메모리 관리 기법고정된 크기의 블록(페이지) 단위로 메모리를 할당하여 단편화를 줄이고, 효율적인 메모리 사용을 가능하게 함쉽게 말하면:프로세스가 사용하는 메모리를 일정한 크기의 페이지(Page)로 나누고, 이를 물리 메모리의 프레임(Frame)에 매핑하는 방식페이징의 장단점장점외부 단편화(External Fragmentation) 없음페이지 크기가 고정되어 있어 메모리의 작은 빈 공간을 효율적으로 활용 가능메모리 할당이 쉽고 빠름모든 페이지 크기가 동일하므로 메모리 할당 및 해제가 간단가상 메모리를 효율적으로 관리 가능프로세스의 전체 메모리를 한 번에 로드할 필요 없이, 필요한 페이지만 로드 가능→ 요구 페이징(Demand Paging) 가능단점내부 단편화(Internal Fragmentation) 발생 가능프로세스가 페이지 크기보다 작은 메모리를 필요로 할 경우 남는 공간이 낭비됨페이지 테이블의 오버헤드(Overhead) 발생페이지 테이블이 클수록 메모리를 많이 차지하고, 주소 변환 속도가 느려질 수 있음주소 변환 시간이 증가할 수 있음TLB(변환 색인 버퍼, Translation Lookaside Buffer)를 사용하여 속도 향상 가능페이지(Page)란?프로세스의 가상 메모리를 일정한 크기로 나눈 블록각 페이지는 동일한 크기를 가짐 (ex. 4KB, 8KB 등)운영체제가 메모리를 관리하기 쉽게 만들어줌프레임(Frame)이란?물리 메모리(RAM)를 페이지와 동일한 크기의 블록으로 나눈 단위하나의 페이지는 하나의 프레임에 매핑됨즉, "페이지(Page)는 가상 메모리 단위", "프레임(Frame)은 물리 메모리 단위"페이징의 주소 변환 과정프로세스가 가상 주소(논리 주소)를 요청가상 주소를 페이지 번호(Page Number)와 오프셋(Offset)으로 분리페이지 번호를 페이지 테이블(Page Table)에서 찾아서 물리 메모리의 프레임 번호(Frame Number)로 변환프레임 번호 + 오프셋을 조합하여 물리 주소(Physical Address)를 계산변환된 물리 주소를 이용해 메모리에 접근즉, 페이지 테이블을 통해 가상 주소 → 물리 주소로 변환됨!페이지 테이블(Page Table)이란?각 페이지 번호(Page Number)와 해당하는 물리 메모리의 프레임 번호(Frame Number)를 매핑하는 데이터 구조운영체제가 프로세스의 메모리를 관리하는 데 사용됨메모리 관리자가 페이지 테이블을 사용하는 방법페이지 테이블을 참조하여 가상 주소를 물리 주소로 변환각 프로세스마다 개별적인 페이지 테이블을 가짐변환 색인 버퍼(TLB, Translation Lookaside Buffer)를 이용해 주소 변환 속도 향상 가능페이지 넘버(Page Number)란?가상 주소를 페이지 크기로 나눈 몫페이지 테이블에서 참조할 때 사용하는 값페이지 넘버 구하는 공식 페이지 크기가 4KB(4096B)일 경우, 가상 주소 8192라면8192÷4096=2→ 페이지 번호 = 2번 페이지오프셋(Offset)이란?해당 페이지 내에서의 위치(몇 번째 바이트인지)페이지 내부에서 데이터를 찾을 때 사용오프셋 구하는 공식Offset=가상 주소mod 페이지 크기\text{Offset} = \text{가상 주소} \mod \text{페이지 크기}Offset=가상 주소mod페이지 크기페이지 크기가 4KB(4096B)일 경우, 가상 주소 8192라면8192mod 4096=08192 \mod 4096 = 08192mod4096=0→ 0번째 위치 (페이지의 첫 번째 바이트)세그멘테이션(Segmentation)과 페이징(Paging)의 차이점운영체제는 보통 "세그멘테이션 + 페이징"을 함께 사용하여 단점 보완페이지 크기의 중요성작은 페이지 크기 (ex. 4KB)장점: 내부 단편화 줄어듦단점: 페이지 테이블 크기 증가 → 관리 오버헤드 증가큰 페이지 크기 (ex. 64KB, 2MB)장점: 페이지 테이블 크기 감소 → 주소 변환 속도 빨라짐단점: 내부 단편화 증가페이지 크기는 내부 단편화와 페이지 테이블 크기 사이에서 균형을 맞춰야 함내부 단편화(Internal Fragmentation)란?페이지 크기보다 작은 메모리를 할당할 때, 남는 공간이 낭비되는 문제예: 4KB 페이지에 3.8KB 데이터 저장 → 0.2KB 낭비외부 단편화(External Fragmentation)란?메모리가 사용 가능한 공간으로 남아 있지만, 필요한 크기의 연속된 공간이 부족하여 할당할 수 없는 문제페이징 기법을 사용하면 외부 단편화를 방지할 수 있음!페이지 테이블 크기에 따른 장단점페이지 테이블이 작을 경우장점: 메모리 공간 절약단점: 페이지 크기가 커서 내부 단편화 증가페이지 테이블이 클 경우장점: 페이지 크기가 작아져 내부 단편화 감소단점: 페이지 테이블이 너무 크면 메모리 관리 오버헤드 증가결론적으로, 페이지 크기와 페이지 테이블 크기 사이에서 최적의 균형을 찾는 것이 중요함! 1. 페이지 교체 정책(Page Replacement Policy)페이지 교체 정책은 메모리가 꽉 찼을 때 어떤 페이지를 스왑 영역으로 보낼지 결정하는 방식이다.가상 메모리 시스템에서 페이지 폴트가 발생하여 새로운 페이지를 로드해야 하지만, 물리 메모리에 빈 공간이 없는 경우 기존 페이지를 제거해야 하는데, 이때 어떤 페이지를 선택할지를 결정하는 알고리즘이다.2. 페이지 폴트(Page Fault)란?프로그램이 가상 메모리의 페이지를 요청했으나, 해당 페이지가 물리 메모리에 없는 경우 발생하는 인터럽트이다.이때 운영체제(OS)는 페이지 폴트를 처리하기 위해 디스크에서 해당 페이지를 읽어와 물리 메모리에 로드한다.3. 페이지 폴트가 발생하는 이유실행 중인 프로그램이 처음으로 특정 페이지를 참조할 때실행 중인 프로그램이 스왑 영역에 저장된 페이지를 다시 참조할 때메모리가 부족하여 페이지를 교체해야 하는 상황4. 페이지 교체 정책 종류1) 무작위(Random) 페이지 교체 알고리즘교체할 페이지를 랜덤하게 선택하여 제거하는 방법.구현이 단순하지만 성능이 좋지 않음.장점: 구현이 쉬움.단점: 성능이 낮고, 비효율적인 교체가 발생할 수 있음.2) FIFO(First-In, First-Out) - 가장 오래된 페이지 교체메모리에 가장 먼저 들어온 페이지를 제거하는 방식.큐(Queue)를 이용하여 가장 앞쪽에 있는 페이지를 제거함.장점: 구현이 간단함.단점: 오래된 페이지가 자주 사용되는 경우에도 교체될 수 있음. (Belady’s anomaly 발생 가능)FIFO 과정페이지 요청이 들어오면, 메모리에 없으면 페이지 폴트 발생.물리 메모리에 빈 공간이 없으면, 가장 먼저 들어온 페이지를 제거.새로운 페이지를 해당 공간에 삽입.3) OPT(Optimal) - 앞으로 가장 오랫동안 사용되지 않을 페이지 교체앞으로 가장 오랫동안 사용되지 않을 페이지를 제거하는 방식.이론적으로 가장 효율적인 방법이지만, 미래의 메모리 접근 패턴을 알아야 하므로 현실적으로 구현이 불가능함.장점: 이론적으로 페이지 폴트 발생 횟수가 가장 적음.단점: 실제로 구현이 불가능함.4) LRU(Least Recently Used) - 최근 가장 적게 사용된 페이지 교체최근 가장 오랫동안 사용되지 않은 페이지를 제거하는 방식.과거의 페이지 참조 기록을 기반으로 가장 오랫동안 사용되지 않은 페이지를 선택함.장점: 자주 사용하는 페이지는 유지할 가능성이 높음.단점: 구현이 다소 복잡하고, 최근 사용 정보를 저장하는데 추가적인 메모리 비용이 발생.LRU 과정페이지 요청이 들어오면, 메모리에 없으면 페이지 폴트 발생.메모리에 빈 공간이 없으면, 가장 오랫동안 사용되지 않은 페이지를 제거.새로운 페이지를 해당 공간에 삽입.5. 페이지 테이블 엔트리(Page Table Entry, PTE)페이지 테이블의 각 항목(엔트리)으로, 가상 주소와 물리 주소의 매핑 정보를 저장하는 데이터 구조.포함되는 주요 정보페이지 프레임 번호 (어떤 물리적 주소에 해당하는지)유효(Valid) 비트 (페이지가 물리 메모리에 존재하는지 여부)읽기/쓰기 권한 정보페이지가 수정되었는지(Dirty 비트)페이지 테이블 엔트리에 데이터를 저장할 때 발생하는 단점페이지 테이블 크기가 커질 수 있음 → 메모리 낭비 발생.페이지 테이블 검색 시간이 증가 → 성능 저하 발생.추가적인 TLB(Translation Lookaside Buffer) 캐시 필요 → 성능 향상을 위한 추가 하드웨어 비용 발생.P4 방식이란?P4 방식은 4단계 페이지 테이블 구조를 사용하는 메모리 관리 방식으로, 주로 64비트 운영체제에서 사용됨.P4 페이지 테이블 구조P4 Directory → P3 Directory → P2 Directory → P1 Table → 물리 메모리가상 주소를 4단계에 걸쳐 변환하여 물리 메모리를 찾음.장점큰 메모리 공간(64비트 주소 공간)을 효율적으로 관리 가능.페이지 테이블을 계층적으로 나누어 메모리 낭비를 줄임.단점주소 변환 과정이 4단계로 늘어나므로 속도가 느릴 수 있음.TLB 캐시 미스가 발생할 경우 성능 저하 가능성.정리페이지 교체 정책: 메모리가 꽉 찼을 때 교체할 페이지를 선택하는 방법.FIFO: 가장 먼저 들어온 페이지 제거 (단순하지만 성능 낮음).OPT: 앞으로 가장 오랫동안 사용되지 않을 페이지 제거 (이론적 최적, 실제 구현 불가능).LRU: 최근 가장 사용이 적은 페이지 제거 (성능 좋지만 구현 복잡).P4 방식: 4단계 페이지 테이블 구조를 사용하는 메모리 관리 기법 (64비트 운영체제에서 사용).스레싱(Thrashing)이란?스레싱(Thrashing)은 운영체제가 대부분의 시간을 페이지 교체 작업에 소비하여 실제 작업 수행이 거의 이루어지지 않는 현상을 의미한다.즉, 페이지 폴트가 너무 자주 발생하여 CPU가 계속해서 페이지 교체만 수행하고, 유효한 작업을 처리하지 못하는 상태를 말한다.스레싱이 일어나는 과정프로세스가 증가하면서 메모리 사용량이 많아짐물리 메모리가 부족하여 페이지 폴트가 빈번하게 발생운영체제가 페이지 교체를 계속 수행하면서 CPU가 대부분의 시간을 페이지 교체 작업에 소모실제 프로그램 실행 속도가 크게 저하됨CPU 이용률이 낮아지고, 전체 시스템 성능이 급격히 저하됨스레싱이 발생하는 이유프로세스의 워킹 셋(Working Set) 크기가 물리 메모리보다 클 때과도한 멀티태스킹으로 인해 메모리가 부족할 때운영체제가 너무 많은 프로세스를 동시에 실행할 때잘못된 페이지 교체 정책이 사용될 때 (ex. FIFO가 Belady's anomaly를 유발하는 경우)지역성(Locality) 특성이 약한 경우 (즉, 프로그램이 너무 많은 서로 다른 페이지를 반복적으로 참조하는 경우)운영체제가 스레싱을 해결하기 위한 방법1) 워킹 셋(Working Set) 알고리즘 적용각 프로세스가 일정 시간 동안 참조하는 페이지 집합(워킹 셋)을 유지하도록 제한필요 이상의 페이지 교체를 방지하여 스레싱을 감소2) 페이지 부하 조절(Page Load Control) - 다중 프로그래밍 수준 조정실행 중인 프로세스 수를 줄여서 각 프로세스에 할당되는 메모리를 증가시킴즉, 프로세스의 개수를 줄이면 남은 프로세스가 더 많은 메모리를 사용 가능3) 프레임 할당 정책 개선최소한의 페이지 프레임을 보장하는 페이지 할당 정책을 개선하여 스레싱을 예방예: LRU(Least Recently Used) 알고리즘 사용하여 효율적인 페이지 교체 수행4) 페이지 폴트 빈도(Page Fault Frequency, PFF) 제어페이지 폴트가 너무 자주 발생하면, 프로세스에게 더 많은 페이지를 할당페이지 폴트가 너무 적으면, 불필요한 페이지를 회수하여 다른 프로세스에 할당5. 워킹 셋(Working Set)이란?워킹 셋(Working Set)이란, 프로세스가 일정 시간 동안 자주 참조하는 페이지들의 집합이다.워킹 셋 개념의 핵심프로그램은 지역성(Locality) 원칙을 따르므로, 일정 시간 동안 특정한 페이지들만 집중적으로 참조함따라서 해당 페이지들을 메모리에 유지하면 페이지 폴트를 줄일 수 있음워킹 셋을 기준으로 메모리 할당을 조절하면 스레싱을 방지할 수 있음정리스레싱(Thrashing): CPU가 대부분의 시간을 페이지 교체에 소비하여 실제 작업이 거의 수행되지 않는 현상발생 원인: 프로세스 증가, 메모리 부족, 잘못된 페이지 교체 정책, 지역성 부족해결 방법:워킹 셋 알고리즘 적용프로세스 개수 조절(다중 프로그래밍 수준 조정)효율적인 페이지 교체 정책 적용페이지 폴트 빈도(Page Fault Frequency) 조절섹션 09 주변 장치(Peripheral Device) 내부 구조주변 장치는 컴퓨터 시스템의 입출력(I/O) 작업을 수행하는 장치이며, 내부적으로 다음과 같은 구조를 가진다. 주변 장치의 기본 내부 구조제어(Control) 회로CPU나 메모리와 신호를 주고받으며 입출력 요청을 처리I/O 작업을 수행하는 동안 상태를 유지데이터 버퍼(Data Buffer)데이터를 임시 저장하여 CPU와의 통신을 원활하게 함블록 단위 또는 스트림 단위로 데이터 처리입출력 인터페이스CPU와 주변 장치 간 데이터 전송을 담당하는 인터페이스예: USB, PCIe, SATA, I2C 등주변 장치 종류(1) 입력 장치 (Input Devices)컴퓨터에 데이터를 입력하는 장치예: 키보드, 마우스, 스캐너, 터치스크린, 조이스틱(2) 출력 장치 (Output Devices)컴퓨터의 처리 결과를 사용자에게 보여주는 장치예: 모니터, 프린터, 스피커(3) 저장 장치 (Storage Devices)데이터를 저장하고 읽는 장치예: HDD, SSD, USB, SD 카드(4) 네트워크 장치 (Network Devices)네트워크 통신을 담당하는 장치예: LAN 카드, Wi-Fi 모듈, 블루투스 장치캐릭터 디바이스(Character Device)와 블록 디바이스(Block Device)(1) 캐릭터 디바이스(Character Device)바이트 단위로 데이터를 읽고 쓰는 장치스트림 기반으로 동작하며, 데이터가 순차적으로 처리됨예: 키보드, 마우스, 시리얼 포트, 터미널(2) 블록 디바이스(Block Device)데이터를 블록 단위(예: 512B, 4KB 등)로 읽고 쓰는 장치랜덤 액세스 가능, 즉 특정 블록을 바로 읽고 쓸 수 있음예: HDD, SSD, USB, CD/DVD고속 입출력 버스와 저속 입출력 버스(1) 고속 입출력 버스(High-Speed I/O Bus)대용량 데이터 전송이 필요한 장치에 사용CPU와 직접 연결되어 빠른 속도로 데이터를 주고받음예: PCIe, SATA, NVMe(2) 저속 입출력 버스(Low-Speed I/O Bus)상대적으로 낮은 대역폭을 요구하는 장치에 사용주로 센서, 키보드, 마우스 등 저속 장치에 사용예: I2C, SPI, UART, USB(2.0 이하)Direct Memory Access (DMA)란?DMA(Direct Memory Access, 직접 메모리 접근)는 CPU의 개입 없이 주변 장치가 메모리와 직접 데이터를 주고받을 수 있도록 하는 기술이다. DMA의 동작 과정CPU가 DMA 컨트롤러(DMAC)에게 메모리 주소와 데이터 크기를 설정DMA 컨트롤러가 직접 I/O 장치 ↔ 메모리 간 데이터 전송 수행데이터 전송이 완료되면 DMA 컨트롤러가 CPU에게 인터럽트(Interrupt) 발생 DMA의 장점CPU 부하 감소 → CPU가 데이터 이동 작업에서 해방됨빠른 데이터 전송 → CPU 개입 없이 고속 데이터 처리 가능효율적인 입출력 성능 향상 DMA를 사용하는 대표적인 장치HDD, SSD, 그래픽 카드(GPU), 네트워크 카드(NIC)대용량 데이터를 빠르게 전송하는 장치에 주로 사용됨DSP(Digital Signal Processor)란?DSP(Digital Signal Processor, 디지털 신호 처리기)는 디지털 신호를 빠르게 처리하는 특수 목적의 마이크로프로세서이다.DSP의 역할아날로그 신호(소리, 영상, 센서 데이터 등)를 디지털 신호로 변환하여 연산빠른 실시간 신호 처리가 가능하여 오디오, 영상, 통신, 의료 장비 등에 사용됨일반 CPU보다 병렬 연산(동시 연산)에 특화됨DSP의 활용 분야오디오/영상 처리 → MP3 플레이어, 스마트폰 음성 인식, 영상 코덱통신 시스템 → 5G, Wi-Fi 신호 처리, 모뎀의료 장비 → MRI, 초음파 영상 처리자동차 → 차량 내 음성 인식, 레이더 신호 처리DSP vs 일반 CPU 차이점키보드와 마우스를 통한 애플리케이션 동작 과정입력 장치(Keyboard & Mouse)의 동작 과정사용자가 키보드/마우스 입력키보드의 키를 누르거나 마우스를 이동/클릭입력 장치의 컨트롤러가 신호 처리키보드: 스캔코드(Scan Code) 생성마우스: 위치 정보(x, y) 및 버튼 클릭 이벤트 생성입력 신호가 운영체제(OS)로 전달됨키보드/마우스 입력은 인터럽트(Interrupt) 방식으로 OS에 전달됨OS가 입력을 애플리케이션에 전달운영체제(Windows, Linux, macOS 등)가 이벤트를 감지적절한 애플리케이션에 입력 이벤트 전달(이벤트 큐 활용)애플리케이션이 입력을 처리하여 동작 수행키보드 입력 → 텍스트 입력, 단축키 실행마우스 입력 → 버튼 클릭, 드래그, UI 조작예시: 웹 브라우저에서 키보드와 마우스를 통한 동작 과정사용자가 Google 검색창에 "DSP란?" 입력키보드 이벤트 → 웹 브라우저가 입력을 감지하여 텍스트 표시엔터 키 입력 → 웹 브라우저가 검색 요청을 서버에 전달마우스 클릭 → 검색 버튼을 클릭하면 검색 결과 페이지 로드하드 디스크 구조하드 디스크(HDD, Hard Disk Drive)는 데이터를 저장하는 자기 저장 장치로, 내부적으로 여러 개의 플래터(Platter)가 회전하며 데이터를 저장하고 읽는다.하드 디스크 주요 구성 요소플래터(Platter): 데이터를 저장하는 원형 디스크스핀들(Spindle): 플래터를 회전시키는 중심축헤드(Head): 데이터를 읽고 쓰는 장치암(Arm): 헤드를 이동시키는 기구액추에이터(Actuator): 헤드의 움직임을 제어하는 장치플래터(Platter)란?플래터(Platter)는 HDD 내부에서 데이터를 저장하는 원형 디스크이다.특징자성을 띤 표면을 갖고 있어 데이터를 저장여러 개의 플래터가 수직으로 겹쳐진 형태로 배치고속 회전(RPM 단위, 보통 5,400~7,200 RPM)플래터 구조트랙(Track): 플래터의 원형 경로섹터(Sector): 트랙을 나눈 최소 저장 단위클러스터(Cluster): 여러 섹터가 모인 데이터 저장 단위실린더(Cylinder): 여러 플래터의 같은 위치에 있는 트랙들의 집합시크 타임(Seek Time)이란?시크 타임(Seek Time)은 헤드가 원하는 트랙으로 이동하는 데 걸리는 시간을 의미한다.하드 디스크의 속도를 결정하는 중요한 요소보통 밀리초(ms) 단위로 측정됨짧을수록 HDD 속도가 빠름시크 타임 최적화 방법파일 조각 모음(Defragmentation): 파일을 연속된 클러스터에 배치하여 헤드 이동 최소화캐시(Buffer) 사용: 자주 사용하는 데이터를 미리 로드플래시 메모리(Flash Memory)란?플래시 메모리(Flash Memory)는 전원이 없어도 데이터가 유지되는 반도체 저장 장치비휘발성(Non-volatile) 메모리로, 전원이 꺼져도 데이터 유지기계적 움직임이 없는 반도체 기반 저장 장치HDD보다 빠르고, SSD(솔리드 스테이트 드라이브)에 사용됨플래시 메모리의 종류플래시 메모리 구조플래시 메모리는 '셀(Cell)'이라는 단위로 구성됨페이지(Page): NAND 플래시의 최소 저장 단위블록(Block): 여러 개의 페이지로 구성됨플래시 컨트롤러: 데이터 읽기/쓰기 및 관리 담당플래시 메모리의 동작 방식쓰기(Program): 전압을 가해 데이터를 저장읽기(Read): 저장된 데이터를 읽음삭제(Erase): 데이터를 삭제할 때 블록 단위로 초기화플래시 메모리의 특징기계적 움직임이 없어 내구성이 뛰어남빠른 데이터 액세스 속도수명이 제한됨(특정 횟수 이상 덮어쓰기하면 성능 저하)HDD vs SSD (플래터 기반 vs 플래시 메모리 기반) 섹션 10파일 시스템(File System)이란?파일 시스템은 운영체제가 데이터를 저장하고 관리하는 방식이다.하드디스크, SSD, USB 등 저장 장치에서 파일을 생성, 삭제, 수정, 검색하는 기능을 담당한다.파일 시스템의 기능파일과 디렉토리 관리: 생성, 수정, 삭제접근 권한 관리: 읽기/쓰기/실행 권한 설정무결성 보장: 데이터 손상 방지백업과 복구: 데이터 보호 및 복원파일 암호화: 보안 강화블록 디바이스(Block Device)하드디스크(HDD)와 플래시 메모리(SSD)는 블록 디바이스이다.블록 단위로 데이터를 저장하고 처리하는 저장 장치.블록 단위로 접근하여 데이터를 읽고 쓰므로 빠른 속도와 효율적인 관리 가능.윈도우 파일 확장자(예시)파일 확장자는 파일의 형식과 실행 프로그램을 결정한다.파일 디스크립터(File Descriptor)란?운영체제가 파일을 관리하는 식별자(정수형 값)파일이 열리면, 운영체제는 파일 디스크립터(파일 번호)를 할당함프로세스는 이 디스크립터를 이용해 파일을 읽고, 쓰고, 닫음시스템 콜(System Call)이란?운영체제의 서비스(파일 조작, 프로세스 관리 등)를 요청하는 인터페이스유저 모드 → 커널 모드 전환을 통해 하드웨어 접근 가능파일 시스템 관련 시스템 콜 예시open() → 파일 열기read() → 파일 읽기write() → 파일 쓰기close() → 파일 닫기7. 파일의 데이터 집합 종류파일 시스템에서 데이터를 저장하는 방식(파일 구조)에 따라 3가지로 분류됨(1) 순차 파일 구조 (Sequential File Organization)데이터를 순차적으로 저장하는 방식테이프(Tape) 저장 방식과 유사과정데이터를 순서대로 저장읽거나 검색할 때 처음부터 순서대로 접근수정 시 새로운 파일을 만들어 다시 저장장점저장 방식이 간단하고 구현이 쉬움연속적으로 데이터 처리 시 속도가 빠름단점특정 데이터 검색 시 시간이 오래 걸림삽입/삭제 작업이 비효율적(2) 직접 파일 구조 (Direct File Organization)키 값(해시 함수 등)을 이용해 직접 접근하는 방식HDD, SSD 같은 랜덤 액세스가 가능한 저장 장치에 적합과정키 값(해시 함수 등)을 통해 특정 위치에 바로 저장데이터를 검색할 때 키 값을 이용해 즉시 접근장점데이터 검색 속도가 빠름대량의 데이터 관리에 적합단점키 값 충돌(Hash Collision) 문제가 발생할 수 있음데이터 저장 공간이 비효율적으로 사용될 수 있음(3) 인덱스 파일 구조 (Indexed File Organization)데이터 위치를 저장하는 인덱스를 별도로 관리하는 방식데이터와 별도로 인덱스 파일을 유지하여 빠른 검색 가능과정데이터의 위치 정보를 인덱스 테이블에 저장검색 시 인덱스를 먼저 조회하여 해당 데이터를 빠르게 찾음장점검색 속도가 빠름 (특히 대량의 데이터에서 효과적)삽입/삭제가 비교적 효율적단점인덱스를 추가로 저장해야 하므로 메모리 공간이 필요함데이터 변경이 많으면 인덱스 유지 비용이 발생 '그림으로 쉽게 배우는 자료구조와 알고리즘(기본편)' 3주차알고리즘 삽입 정렬 (Insertion Sort)삽입정렬이란?삽입정렬은 정렬되지 않은 데이터를 하나씩 골라, 이미 정렬된 부분에 적절한 위치에 삽입하는 방식입니다.작은 데이터에서 효율적이지만, 데이터가 많아질수록 비효율적입니다.시간복잡도, 장단점시간복잡도: 평균 및 최악 시간 복잡도는 O(n²) (최악의 경우는 모든 원소를 하나씩 비교해야 함)장점:간단하고 구현이 용이정렬이 거의 되어 있는 배열에서는 빠른 속도추가 메모리 필요 없음 (In-place 정렬)단점:데이터가 많아질수록 비효율적최악의 경우 O(n²)의 시간 복잡도C++ 예시 구현 코드#include using namespace std; void insertionSort(int arr[], int n) { for (int i = 1; i = 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } } int main() { int arr[] = {12, 11, 13, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); insertionSort(arr, n); cout 병합 정렬 (Merge Sort)병합정렬이란?병합정렬은 분할 정복 알고리즘을 사용하여 배열을 반으로 나누고, 나눈 배열을 재귀적으로 정렬한 후, 두 배열을 병합하는 방식입니다.시간복잡도, 장단점시간복잡도: 항상 O(n log n) (배열을 계속 반으로 나누고 합치는 과정에서 시간이 걸림)장점:항상 O(n log n)의 성능을 보장안정적 정렬 (같은 값이 있으면 원래의 순서를 유지)단점:추가 메모리가 필요 (O(n))복잡한 구현C++ 예시 구현 코드 #include using namespace std; void merge(int arr[], int left, int right) { if (left 퀵 정렬 (Quick Sort)퀵정렬이란?퀵정렬은 분할 정복 알고리즘을 사용하며, 기준값(pivot)을 정해 배열을 두 부분으로 분할한 후, 각 부분에 대해 재귀적으로 정렬하는 방식입니다.시간복잡도, 장단점시간복잡도: 평균 시간 복잡도는 O(n log n), 최악의 경우는 O(n²) (배열이 이미 정렬된 경우)장점:빠른 정렬 속도 (평균 O(n log n))메모리 사용 효율적 (In-place 정렬)단점:최악의 경우 O(n²) 시간이 걸릴 수 있음 (피벗 선택에 따라)불안정한 정렬 (같은 값이 있으면 순서가 달라질 수 있음)C++ 예시 구현 코드#include using namespace std; int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j 동적 프로그래밍 - 메모이제이션 (Memoization)메모이제이션이란?메모이제이션은 이미 계산된 값을 캐시하여 재사용하는 방법입니다. 주로 재귀 함수에서 많이 사용됩니다.시간복잡도, 장단점시간복잡도: 중복 계산을 방지하여 시간 복잡도를 O(n)으로 줄일 수 있음장점:재귀적 문제 해결 시 성능 향상중복 계산 방지단점:메모리 사용량 증가 (캐시를 저장해야 하므로)C++ 예시 구현 코드 (피보나치 수열)#include #include using namespace std; unordered_map memo; int fib(int n) { if (n 동적 프로그래밍 - 타뷸레이션 (Tabulation)타뷸레이션이란?타뷸레이션은 하향식 문제 해결 방식입니다. 하위 문제를 먼저 계산하고, 이를 기반으로 상위 문제를 해결합니다.시간복잡도, 장단점시간복잡도: 보통 O(n) (배열을 채우는 과정에서)장점:메모리 사용 효율적중복 계산을 제거단점:재귀적 사고가 아닌 반복적 방법 (문제를 재귀적으로 풀고 싶을 때 불편)C++ 예시 구현 코드 (피보나치 수열) #include using namespace std; int fib(int n) { int dp[n + 1]; dp[0] = 0; dp[1] = 1; for (int i = 2; i 완주 후기:혼자서 강의를 듣기 시작했다면 두 강의를 완주하지 못했을 것 같다. 커리큘럼 따라서 완주를 하고, 감자님이 내주신 문제들에 대한 답변들을 풀이하면서 더 찾아보게 되는 것 같았습니다.3주차에 수강한 강의 내용들은 너무 어려워서 다시 한번 돌려보고 후에, 전체적으로 모든 강의를 다시 볼 생각입니다.좋은 강의 제공해주셔서 감사합니다.

CS 전공지식 스터디 3기 [2주차] 자료구조와 알고리즘 미션

CS 전공지식 스터디 3기 [2주차] 자료구조와 알고리즘 미션Q. 재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?A.재귀 함수란 자기 자신을 호출하는 함수를 재귀 함수라고 합니다.문제를 작은 부분으로 나누어 해결하는 방식으로, 주로 반복적인 구조의 문제를 해결할 때 사용됩니다.재귀 함수에서 기저 조건(Base Case)을 만들지 않거나 잘못 설정했을 때 발생하는 문제는무한 루프(무한 재귀 호출) 발생기저 조건이 없으면 함수가 끝없이 자기 자신을 호출하게 되어 스택 오버플로우(Stack Overflow)가 발생합니다.잘못된 결과 반환기저 조건이 부정확하면 예상한 결과를 얻지 못할 수 있습니다.Q. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function sumOdd(n){ // 재귀 로직 } console.log(sumOdd(10)) // 25 A.function sumOdd(n) { if (n Q. 다음 코드는 매개변수로 주어진 파일 경로(.는 현재 디렉토리)에 있는 하위 모든 파일과 디렉토리를 출력하는 코드입니다. 다음 코드를 재귀 함수를 이용하는 코드로 변경해보세요.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("."); // 현재 경로의 모든 하위 경로의 파일, 디렉토리 출력 A.const fs = require("fs"); const path = require("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); traverseDirectory(filePath); // 재귀 호출 } else { console.log("파일:", filePath); } } } traverseDirectory("."); // 현재 경로의 모든 하위 파일과 디렉토리 출력

CS 전공지식 스터디 3기 [2주차] 운영체제 미션

CS 전공지식 스터디 3기 [2주차] 운영체제 미션Q. FIFO 스케줄링의 장단점이 뭔가요?A.FIFO(First In, First Out) 스케줄링은 먼저 도착한 프로세스가 먼저 실행되는 방식의 스케줄링 알고리즘입니다.이는 큐(Queue) 구조를 사용하며, 도착한 순서대로 실행되기 때문에 공평하지만 비효율적인 경우가 발생할 수 있습니다. 장점:공정성: 먼저 도착한 프로세스를 먼저 처리하기 때문에 기아(Starvation) 현상이 발생하지 않음간단한 구현: 큐(Queue) 자료구조를 사용하여 구현이 간단함비선점(Non-Preemptive) 방식: 한 프로세스가 CPU를 점유하면 끝날 때까지 다른 프로세스가 실행되지 않음단점:긴 작업이 먼저 도착하면 대기 시간이 증가예를 들어, 긴 실행 시간을 가진 프로세스가 먼저 들어오면 뒤의 짧은 프로세스들이 오래 대기해야 함이를 Convoy Effect(호위 효과)라고 부름 응답 시간이 일정하지 않음짧은 작업이 있어도 먼저 도착한 긴 작업이 끝날 때까지 기다려야 함 FIFO 스케줄링 수행 과정P1 → P2 → P3 순서로 실행됨P1이 먼저 CPU를 점유하고 끝날 때까지 P2와 P3는 기다려야 함 Q. SJF를 사용하기 여러운 이유가 뭔가요?A.SJF(Shortest Job First) 스케줄링은 CPU 실행 시간이 가장 짧은 프로세스를 먼저 실행하는 방식입니다.즉, Burst Time(실행 시간)이 짧은 순서대로 프로세스를 실행하기 때문에 평균 대기 시간(AWT)이 최소화되는 장점이 있습니다. SJF 스케줄링의 종류비선점형 SJF (Non-Preemptive SJF)실행 중인 프로세스가 끝날 때까지 CPU를 점유 (중간에 빼앗기지 않음) 선점형 SJF (Preemptive SJF, SRTF: Shortest Remaining Time First)새로운 프로세스가 도착하면 현재 실행 중인 프로세스와 실행 시간을 비교하여 더 짧은 실행 시간이 남은 프로세스가 있으면 CPU를 빼앗김 실행 순서먼저 도착한 P1 실행 (7ms)다음으로 P3 실행 (1ms)P2 실행 (4ms)마지막으로 P4 실행 (4ms)SJF를 사용하기 어려운 이유실행 시간이 가장 짧은 작업을 먼저 실행해야 하는데, 프로세스의 CPU Burst Time(실행 시간)을 정확히 예측하기 어렵습니다.I/O Bound 프로세스와 CPU Bound 프로세스를 구분하기 쉽지 않습니다.비선점(Non-Preemptive) 방식이라 실시간 시스템에 적합하지 않을 수 있습니다. Q. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?A.RR(Round Robin) 스케줄링은 각 프로세스가 일정한 시간(Time Quantum) 동안만 실행되며, 시간이 지나면 다음 프로세스로 넘어가는 방식입니다.즉, 모든 프로세스가 공평하게 CPU를 사용할 수 있도록 설계된 선점형(Preemptive) 방식입니다.RR스케줄링의 타임 슬라이스가 아주 작으면 아래와 같은 문제가 발생합니다.Context Switching 증가:타임 슬라이스가 너무 작으면 프로세스가 자주 CPU에서 교체되므로 컨텍스트 스위칭(Context Switching) 비용이 증가하여 오버헤드가 커진다.CPU 사용률 저하:CPU가 실제 작업을 수행하는 시간보다 문맥 전환(Context Switching) 처리에 더 많은 시간을 사용하게 되어 효율성이 떨어진다.하지만 RR 스케줄링은 모든 프로세스가 공평하게 실행되고, 응답 시간이 빨라서 실시간 시스템에 적합하다는 장점이 있습니다. Q. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?A.MLFQ(Multi-Level Feedback Queue, 다단계 피드백 큐) 스케줄링은 여러 개의 큐를 사용하여 프로세스를 우선순위별로 분류하고, 프로세스의 실행 시간이나 행동 패턴에 따라 다른 큐로 이동시키는 방식입니다.즉, CPU 사용 시간에 따라 우선순위가 조정되며, 프로세스가 낮은 우선순위로 이동할 수도 있고 다시 높은 우선순위로 복귀할 수도 있는 유동적인 스케줄링 방식입니다.운영체제는 프로세스의 행동 패턴을 기반으로 CPU Bound Process와 I/O Bound Process를 구분합니다.CPU Bound Process:CPU를 오래 사용하는 프로세스계산량이 많고, 연산이 많은 작업 (예: 영상 처리, 데이터 분석)CPU를 길게 사용하여 타임 퀀텀을 초과하면 하위 큐로 이동 I/O Bound Process:I/O 작업(디스크 접근, 네트워크 요청 등)이 잦은 프로세스키보드 입력, 파일 읽기 등의 작업이 많음 (예: 웹 브라우저, 텍스트 편집기)자주 I/O 요청을 하면 다시 상위 큐로 이동즉 운영체제는 프로세스가 얼마나 자주 I/O 요청을 하는지 모니터링하며 CPU Bound와 I/O Bound를 자동으로 구분합니다.Q. 공유자원이란무엇인가요?A.공유 자원이란 여러 개의 프로세스가 동시에 접근할 수 있는 자원을 의미합니다.예시:메모리 (공유 메모리 영역)파일 시스템 (파일 접근)프린터, 네트워크 소켓 등 Q. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야 할까요?A.교착 상태는 4가지 조건을 모두 만족해야 교착 상태에 빠지게 됩니다.아래 4가지 중 한가지라도 만족하지 않는다면, 교착 상태에 빠지지 않게 됩니다.교착 상태 4가지 조건상호 배제 (Mutual Exclusion):한 번에 하나의 프로세스만 자원을 사용할 수 있어야 한다.점유와 대기 (Hold and Wait):하나의 자원을 점유한 프로세스가 다른 자원을 기다리는 상태여야 한다.비선점 (No Preemption):프로세스가 강제로 자원을 빼앗기지 않는다.순환 대기 (Circular Wait):프로세스들이 원형(사이클)으로 자원을 서로 점유하고 대기한다.

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

'그림으로 쉽게 배우는 운영체제 2주차'[섹션 04]프로세스 동기화CPU 스케줄링에서 고려해야 할 사항CPU 스케줄러가 고려해야 할 요소는 다음과 같습니다.프로세스에게 CPU 리소스를 줘야 하는가?실행 가능한 프로세스 중에서 어떤 프로세스에 CPU를 할당할 것인지 결정.우선순위가 높은 프로세스를 먼저 실행할 것인지 고려해야 함.CPU를 할당받은 프로세스가 얼마 동안 실행되어야 하는가?특정 프로세스가 너무 오랫동안 CPU를 독점하지 않도록 타임 퀀텀(Time Quantum) 을 설정.선점형(Preemptive) 스케줄링과 비선점형(Non-preemptive) 스케줄링 방식 중 선택.CPU Burst와 I/O BurstCPU Burst: 프로세스가 연속적으로 CPU에서 실행되는 시간.I/O Burst: 프로세스가 I/O 작업을 수행하는 시간.CPU 작업과 I/O 작업이 번갈아 가며 실행됨.프로세스 간 통신 (IPC, Inter-Process Communication) 종류파일과 파이프(Pipe) 이용파일: 프로세스 간 데이터를 파일을 통해 공유하는 방식.파이프: 한 프로세스가 데이터를 쓰고 다른 프로세스가 읽는 구조 (ex. | 연산자).스레드(Thread) 이용같은 프로세스 내의 여러 스레드가 메모리를 공유하면서 데이터를 주고받는 방식.네트워크 이용소켓(Socket) 통신, 원격 프로시저 호출(RPC) 등을 사용하여 원격 프로세스와 데이터 교환.RPC (Remote Procedure Call, 원격 프로시저 호출)네트워크를 통해 다른 시스템에서 동작하는 프로세스의 함수를 호출하는 기법.클라이언트가 마치 로컬 함수처럼 호출하면, 원격 서버에서 실행되고 결과가 반환됨.공유 자원 & 동기화 문제공유 자원(Shared Resource): 여러 프로세스가 동시에 접근할 수 있는 자원 (예: 변수, 파일).동기화 문제(Synchronization Issue): 여러 프로세스가 공유 자원에 접근할 때 데이터 충돌이 발생할 위험이 있음.임계구역 (Critical Section)공유 자원에 접근하는 코드 영역.한 번에 하나의 프로세스만 임계구역에 접근해야 함.상호 배제(Mutual Exclusion) 매커니즘 요구사항 3가지단일 접근 원칙: 주어진 시간에 오직 하나의 프로세스만 임계구역에 접근 가능.동시 요청 처리: 여러 프로세스가 동시에 요청해도 한 개의 프로세스만 진입 가능.빠른 실행 보장: 임계구역에 들어간 프로세스는 최대한 빠르게 나와야 함.세마포어 (Semaphore)공유 자원의 접근을 제한하는 동기화 기법.프로세스 간 상호 배제(Mutual Exclusion) 를 보장함.세마포어 메커니즘P(S) (wait 연산): 세마포어 값을 감소시키고, 0이면 대기(block).V(S) (signal 연산): 세마포어 값을 증가시키고, 대기 중인 프로세스가 있으면 깨움.C++ 예제#include #include #include sem_t semaphore; void* worker(void* arg) { sem_wait(&semaphore); // P(S) 연산 (진입) std::cout 세마포어를 잘못 사용할 경우 발생할 위험성데드락(Deadlock)여러 프로세스가 세마포어를 무한정 대기하면 교착 상태 발생.기아 상태(Starvation)특정 프로세스가 세마포어를 계속 점유하면, 다른 프로세스는 계속 대기해야 함.우선순위 반전(Priority Inversion)낮은 우선순위 프로세스가 세마포어를 점유하면, 높은 우선순위 프로세스가 대기할 수 있음.모니터(Monitor)란?세마포어의 단점을 해결한 상호 배제(Mutual Exclusion) 매커니즘.프로그래머가 wait()과 signal()을 직접 사용하지 않고, 자동으로 동기화를 제공.Java에서 모니터 예제class SharedResource { synchronized void print() { System.out.println(Thread.currentThread().getName() + " 실행 중..."); } } class MyThread extends Thread { SharedResource sr; MyThread(SharedResource sr) { this.sr = sr; } public void run() { sr.print(); } } public class MonitorExample { public static void main(String[] args) { SharedResource sr = new SharedResource(); Thread t1 = new MyThread(sr); Thread t2 = new MyThread(sr); t1.start(); t2.start(); } }synchronized 키워드를 사용하면, 임계구역에 하나의 스레드만 진입할 수 있음.프로그래머가 직접 세마포어를 관리할 필요 없이 안전한 동기화를 제공.[섹션 05]데드락 데드락(Deadlock)이란?정의:데드락(교착 상태)은 두 개 이상의 프로세스가 서로 상대방의 작업이 끝나기를 기다리면서 무한히 멈춰 있는 상태를 의미예제:식사하는 철학자 문제다섯 명의 철학자가 둥근 테이블에서 식사를 하려면 양옆의 포크 두 개를 동시에 집어야 한다.모든 철학자가 왼쪽 포크를 집고 오른쪽 포크를 기다리면 교착 상태(Deadlock)가 발생하여 아무도 식사를 할 수 없게 된다. 교착 상태 (Deadlock)정의:여러 프로세스가 서로 다른 프로세스의 작업이 끝나기를 기다리다가 아무도 작업을 진행하지 못하는 상태교착 상태 발생 조건 (4가지 필요조건)데드락이 발생하려면 다음 4가지 조건이 동시에 만족해야 함이 중 하나라도 충족되지 않으면 데드락은 발생하지 않음!! 상호 배제 (Mutual Exclusion)한 번에 하나의 프로세스만 특정 자원을 사용할 수 있어야 함예: 한 개의 프린터를 여러 프로세스가 사용할 경우, 한 프로세스가 사용하는 동안 다른 프로세스는 대기해야 함.2. 점유와 대기 (Hold and Wait)프로세스가 이미 할당받은 자원을 보유한 채로 추가적인 자원을 기다려야 한다.예: 프로세스 A는 프린터를 가지고 있고, 프로세스 B가 사용하는 스캐너를 기다리는 상황비선점 (No Preemption)할당된 자원을 강제로 빼앗을 수 없음즉, 자원을 점유한 프로세스가 스스로 해제할 때까지 다른 프로세스는 기다려야 한다.순환 대기 (Circular Wait)프로세스들이 서로 원형(사이클) 형태로 자원을 점유하고 대기한다.예:A → B가 가진 자원을 기다림B → C가 가진 자원을 기다림C → A가 가진 자원을 기다림이처럼 순환 구조가 형성되면 데드락 발생! 데드락 해결 방법데드락을 해결하기 위해 예방, 회피, 검출 및 복구 방법이 존재 데드락 예방 (Prevention)데드락 필요조건 4가지 중 하나 이상을 제거하여 방지하는 방법방법:상호 배제 제거: 여러 프로세스가 동시에 자원을 공유하도록 설계점유와 대기 방지: 모든 자원을 한 번에 요청하도록 함비선점 가능하게 변경: 자원을 강제로 회수할 수 있도록 설정순환 대기 방지: 자원에 우선순위를 부여하여 순환이 생기지 않도록 설계 데드락 회피 (Avoidance)시스템이 미리 안전 상태(Safe State)를 유지하며 자원 할당을 조절하는 방법대표적인 알고리즘:은행원 알고리즘 (Banker’s Algorithm)프로세스가 최대 자원 요청량을 미리 선언해야 함시스템은 프로세스가 요청하는 자원을 할당했을 때 데드락이 발생하지 않는지 검토한 후 할당장점교착 상태 예방 가능안전 상태에서만 자원 할당 → 시스템 안정성 증가 단점프로세스가 최대 요구량을 미리 선언해야 함시스템이 항상 가능한 상태를 계산해야 하므로 오버헤드 발생 교착 상태 검출 및 복구이미 발생한 데드락을 감지하고 해결하는 방법방법:자원 할당 그래프(Resource Allocation Graph, RAG) 분석교착 상태 발생 시 체크포인트로 롤백교착 상태 프로세스 강제 종료 또는 자원 선점교착 상태 검출1) 가벼운 교착 상태 검출시스템이 주기적으로 자원 할당 그래프를 분석하여 교착 상태 가능성을 확인2) 체크포인트 롤백 (Checkpoint Rollback)마지막으로 저장한 체크포인트(Checkpoint)로 프로세스를 되돌려 교착 상태 해소[섹션 06]컴파일과 프로세스프로그램이 실행되는 과정 소스 코드 작성 (C, Java, Python 등)컴파일 (Compile)소스 코드를 기계어(바이너리 코드)로 변환링크 (Link)여러 개의 오브젝트 파일(.o, .obj)을 합쳐 실행 가능한 파일(.exe) 생성로드 (Load)실행 파일을 메모리에 로드실행 (Execute)CPU가 프로그램 명령어 실행[섹션 07] 메모리 메모리의 종류 메모리 주소1) 물리 주소 (Physical Address)실제 RAM의 주소CPU가 직접 접근하는 주소2) 논리 주소 (Logical Address)프로그램이 보는 가상의 주소OS가 논리 주소를 물리 주소로 변환재배치 레지스터 (Relocation Register)논리 주소를 물리 주소로 변환하는 데 사용되는 레지스터프로그램을 다른 메모리 위치로 이동해도 주소 수정 없이 실행 가능메모리 오버레이 (Memory Overlay)큰 프로그램을 작은 조각(Overlay)으로 분할하여 필요한 부분만 메모리에 적재하는 기법초창기 컴퓨터에서 메모리가 부족할 때 사용메모리 할당 방식 (2가지)1. 고정 분할 방식 (Fixed Partitioning)메모리를 고정된 크기의 블록(파티션)으로 나누고, 프로세스를 할당하는 방식각 파티션 크기는 시스템 부팅 시 미리 정해짐단순한 구조이지만 메모리 낭비(내부 단편화)가 발생할 수 있음특징프로세스가 할당된 크기보다 작으면 남은 공간이 낭비됨 (내부 단편화 발생)파티션 크기를 변경할 수 없음작은 프로세스가 들어가야 할 공간에 큰 프로세스가 오면 메모리 낭비가 발생관리가 쉬운 대신 유연성이 부족장점관리가 단순함 (구현 쉬움)메모리 할당/해제 속도가 빠름CPU 스케줄링이 단순해짐단점내부 단편화(Internal Fragmentation) 발생 → 프로세스보다 큰 파티션을 할당받으면 남는 공간이 낭비됨파티션 크기를 미리 설정해야 함 → 크기 조정 불가능큰 프로그램을 실행하기 어려움 (적절한 크기의 파티션이 없으면 실행 불가)예시2.가변 분할 방식 (Variable Partitioning)프로세스가 요청하는 크기만큼 메모리를 할당하는 방식동적 메모리 할당 방식 → 프로세스가 들어올 때마다 필요한 만큼만 메모리를 할당메모리를 효율적으로 사용할 수 있지만, 외부 단편화 문제 발생특징메모리 크기에 맞게 프로세스를 할당하므로 내부 단편화가 없음하지만 메모리가 여러 개의 작은 조각으로 나뉘어 외부 단편화 발생메모리를 동적으로 관리할 수 있어 유연성이 높음장점내부 단편화 없음 → 프로세스 크기에 맞춰 메모리를 할당큰 프로그램도 실행 가능 → 고정된 크기 제한이 없음메모리 활용률이 높음단점외부 단편화(External Fragmentation) 발생 → 메모리 사이에 작은 빈 공간이 많아져 사용 불가메모리 관리가 복잡 → 동적 할당을 위해 추가적인 관리 필요메모리 검색 시간 증가 → 적절한 크기의 공간을 찾기 위해 시간이 오래 걸릴 수 있음 예시메모리 단편화1) 외부 단편화 (External Fragmentation)메모리가 남아 있지만, 연속된 공간이 부족하여 할당 불가능한 상태해결 방법: 메모리 압축(Compaction) 또는 페이징(Paging) 기법 사용2) 내부 단편화 (Internal Fragmentation)고정 분할 방식에서 할당된 공간보다 작은 프로그램이 로드될 때 남는 공간해결 방법: 가변 분할 방식 사용 '그림으로 쉽게 배우는 자료구조와 알고리즘(기본편)' 2주차[섹션 03]알고리즘 재귀함수 (Recursive Function)란?자기 자신을 호출하는 함수를 재귀 함수라고 함문제를 작은 부분으로 나누어 해결하는 방식으로, 주로 반복적인 구조의 문제를 해결할 때 사용재귀 함수의 탈출 조건 (Base Case)이란?재귀 호출이 무한히 반복되지 않도록 종료되는 조건을 기저 조건(Base Case) 이라고 함만약 기저 조건이 없으면 무한 루프에 빠져 프로그램이 멈추지 않는 문제가 발생할 수 있음재귀함수 예시: 팩토리얼 계산 c++#include using namespace std; // 팩토리얼 함수 (재귀) int factorial(int n) { if (n == 0) return 1; // 기저 조건 (탈출 조건) return n * factorial(n - 1); // 재귀 호출 } int main() { cout factorial(0)의 경우 1을 반환하면서 재귀 호출이 종료 재귀적으로 생각하는 방법?작은 문제로 나눈다 → 현재 문제를 더 작은 문제로 분할2. 탈출 조건을 찾는다 → 가장 작은 입력에 대한 결과를 명확하게 정의3. 점화식(재귀 관계식)을 찾는다 → 현재 상태와 작은 문제 사이의 관계 정의4. 재귀 호출을 구현한다 → 주어진 입력에서 자기 자신을 호출하는 구조예제: 피보나치 수열int fibonacci(int n) { if (n fibonacci(0) = 0, fibonacci(1) = 1 → 기저 조건을 만족하면 종료 하노이 탑 문제 (Hanoi Tower)세 개의 기둥과 여러 개의 원반이 있음한 번에 하나의 원반만 이동 가능작은 원반이 큰 원반 위에 올라가면 안 됨재귀적 풀이1. 가장 큰 원반을 제외한 나머지를 보조 기둥으로 이동2. 가장 큰 원반을 목표 기둥으로 이동3. 보조 기둥의 원반들을 다시 목표 기둥으로 이동#include using namespace std; void hanoi(int n, char from, char to, char aux) { if (n == 1) { cout 정렬 알고리즘버블 정렬 (Bubble Sort)인접한 두 개의 값을 비교하여 정렬가장 큰 값이 점점 오른쪽으로 이동하는 방식시간 복잡도최선(O(n)) → 이미 정렬된 경우최악(O(n²)) → 완전히 뒤집힌 경우 장점 & 단점구현이 간단함안정 정렬(Stable Sort)시간 복잡도가 높아 비효율적C++ 코드#include using namespace std; void bubbleSort(int arr[], int n) { for (int i = 0; i arr[j + 1]) { swap(arr[j], arr[j + 1]); } } } } int main() { int arr[] = {5, 2, 9, 1, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); bubbleSort(arr, n); for (int i : arr) cout 선택 정렬 (Selection Sort)가장 작은 값을 찾아서 앞쪽에 배치하는 방식정렬된 부분과 정렬되지 않은 부분으로 나눠 진행시간 복잡도O(n²) (최선, 최악 동일) 장점 & 단점비교 횟수가 일정하여 안정적추가적인 메모리 사용이 적음시간 복잡도가 높아 비효율적안정 정렬이 아님 (같은 값의 순서가 바뀔 수 있음) C++ 코드#include using namespace std; void selectionSort(int arr[], int n) { for (int i = 0; i 삽입 정렬 (Insertion Sort)현재 원소를 정렬된 부분에 적절히 삽입하는 방식버블, 선택 정렬보다 효율적작은 데이터에서 성능이 좋음시간 복잡도최선(O(n)) → 거의 정렬된 경우최악(O(n²)) → 역순 정렬된 경우 장점 & 단점 정렬된 부분을 활용하여 효율적으로 정렬 가능비교적 빠른 알고리즘 (특히 데이터가 거의 정렬된 경우)큰 데이터에서는 비효율적C++ 코드#include using namespace std; void insertionSort(int arr[], int n) { for (int i = 1; i = 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } } int main() { int arr[] = {5, 2, 9, 1, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); insertionSort(arr, n); for (int i : arr) cout 정렬 알고리즘 비교배우고 느낀점한 주가 지났다고 벌써 운영체제 앞부분의 기억이 희미해져서 강의를 보면서 다시 앞부분 내용을 일부 확인하는 과정이 있었습니다.. 복습을 다시 해야겠다는 생각을 하게 됐습니다.CS를 알아야 컴퓨터의 모든 실행 과정(메모리 할당 및 컴파일 과정)을 알 수 있다는 것을 다시 한번 느끼게 되었습니다.처음 접한 단어들이 많아서 다시 한번 학습해야 할 것 같습니다. 어려웠던 점수학 지식이 부족해서 시간복잡도를 이해하기 힘들었습니다. (어떤게 빠르고 어떤게 느린건지)전 주에 들었던 강의 내용을 일부만 기억해서 이번 과정을 이해하는데 힘들었습니다. 앞으로 개선할 점운영체제 초반부분부터 다시 복습하기..코드 구현 시 혼자 생각하면서, 구현 절차를 먼저 생각하는 데에 시간을 많이 소모한 후 구현하기=> 먼저 구현하면서 구현 과정 중 생각하기 X

CS 전공지식 스터디 3기 [1주차] 자료구조와 알고리즘 미션

CS 전공지식 스터디 3기 [1주차] 자료구조와 알고리즘 미션 Q1. 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다. 이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요. A1.학생의 정보는 이름, 학번, 성적 등의 필드를 포함하므로, 효율적인 검색과 관리를 위해 해시테이블을 사용하는 것이 적절합니다.그 이유는 학생은 학번이라는 고유 ID를 갖고 있기 때문에, 학번을 키로 사용한다면, 시간복잡도가 평균 O(1)이 되므로 빠른 탐색이 가능해집니다. Q2. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요. A2.주문은 FIFO(First-In-First-Out) 방식으로 처리되어야 하므로 큐(Queue)를 사용하는 것이 적절합니다.이유는 스택과 다르게 큐는 먼저 들어온 데이터가 먼저 처리되는 구조이기 때문입니다.주문 처리 과정도 먼저 들어온 주문이 먼저 처리되어야 하는 구조이기 때문에 큐 자료구조를 사용해야 한다고 생각합니다. Q3. 우리가 구현한 스택은 0번 인덱스, 즉 입구쪽으로 데이터가 삽입되고 나오는 구조입니다. 반대로 마지막 인덱스, 즉 출구쪽으로 데이터가 삽입되고 나오는 구조로 코드를 변경해주세요. A3.기존코드#include #include class Stack { private: std::vector data; public: void push(int value) { data.insert(data.begin(), value); // 0번 인덱스에서 삽입 } void pop() { if (!data.empty()) { data.erase(data.begin()); // 0번 인덱스에서 삭제 } } int top() { return data.front(); } }; 변경된 스택 코드#include #include class Stack { private: std::vector data; public: void push(int value) { data.insert(data.begin(), value); // 0번 인덱스에서 삽입 } void pop() { if (!data.empty()) { data.erase(data.begin()); // 0번 인덱스에서 삭제 } } int top() { return data.front(); } }; Q4. 해시테이블의 성능은 해시 함수에 따라 달라집니다. 수업 시간에 등번호를 이용해 간단한 해시 함수를 만들어봤습니다. 이번엔 등번호가 아닌 이름을 이용해 데이터를 골고루 분산시키는 코드로 수정해주세요. 힌트: charCodeAt() 함수를 이용 예시: name1 = "이운재"; name1.charCodeAt(0); // 51060 이운재의 0번 인덱스 ‘이’의 유니코드 출력hashFunction(name){ } A4.기존 해시 함수는 등번호를 사용했지만, 이름을 기반으로 해시값을 생성해야 합니다.이름의 각 문자에 charCodeAt() (C++에서는 ASCII 변환) 값을 활용해 해시값을 생성합니다.#include #include int hashFunction(std::string name, int tableSize) { int hashValue = 0; for (char c : name) { hashValue = (hashValue * 31 + c) % tableSize; // 31은 일반적으로 좋은 해시 인수 } return hashValue; } int main() { std::string name = "이운재"; int tableSize = 100; // 해시 테이블 크기 std::cout 이름의 각 문자를 ASCII 값으로 변환하여 해시값 계산하였습니다.

CS 전공지식 스터디 3기 [1주차] 운영체제 미션

CS 전공지식 스터디 3기 [1주차] 운영체제 미션 Q1. while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다.1초마다 체크하기 때문에 성능에 좋지 않습니다.이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요? A1.폴링 방식은 일정 주기마다 지속적으로 CPU가 입출력 관리자에게 입출력이 왔는지 확인하는 방식입니다.하지만 일정 주기마다 지속적으로 CPU가 확인하기 때문에 성능이 좋지 않다는 단점이 존재합니다. 이를 해결하기 위해선 폴링 방식을 보완한 인터럽트 방식을 적용해야 합니다. 인터럽트 방식은 출력이 완료되었을 때 CPU에게 신호를 주어 인터럽트 서비스 루틴을 실행하는 방식입니다.인터럽트 여기서 서비스 루틴이란 특정 인터럽트가 들어오면 그 인터럽트를 처리하는 함수입니다.인터럽트 방식을 적용하면 일정 주기마다 지속적으로 CPU가 입출력 관리자에게 입출력이 왔는지 확인하는 것이 아니라,입출력이 올 때마다 CPU에게 신호를 주어 인터럽트 서비스 루틴을 실행하기 때문에 CPU의 사용량을 줄일 수 있습니다. Q2. 프로그램과 프로세스가 어떻게 다른가요? A2.프로그램은 하드디스크 등과 같은 저장장치에 저장된 명령문의 집합체입니다.저희가 플레이하는 게임이나, 뮤직 플레이어 같은 것들이 프로그램입니다. 프로세스는 프로그램이 실행되어 하드디스크에 저장되어 있던 프로그램이 메모리에 올라가게된 프로그램을 의미합니다.프로세스는 코드 영역, 데이터 영역, 스택 영역, 킵 영역을 갖고 있습니다.또한 메모리도 사용하고 운영체제의 CPU 스케줄링 알고리즘에 따라서 CPU도 사용하고 필요에 따라 입력과 출력을 하기 때문에 능동적인 존재이기도 합니다. Q3. 멀티 프로그래밍과 멀티 프로세싱이 어떻게 다른가요? A3.멀티 프로그래밍은 하나의 CPU가 여러 프로세스를 번갈아 실행하는 것을 의미합니다.멀티 프로그래밍의 특징으로는 CPU 이용률 극대화하고 병렬 처리가 아닌 시분할 방식을 사용합니다.또한 비선점형 스케줄링에 많이 사용합니다. 멀티 프로세싱은 여러 개의 CPU가 동시에 여러 프로세스를 처리하는 것을 의미합니다.특징으로는 병렬 처리 가능하고 선점형 스케줄링 적용하며, 다중 코어 시스템에서 사용합니다. Q4. 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요? A4.운영체제는 프로세스를 관리하기 위해 PCB(Process Control Block) 를 사용합니다.PCB는 운영체제가 각 프로세스를 관리하기 위해 유지하는 데이터 구조체입니다.PCB의 역할로는 프로세스의 상태, 메모리 정보, CPU 레지스터 정보 등을 저장하는 기능을 수행합니다.PCB 의 구조는PID (Process ID)프로세스 상태프로그램 카운터CPU 레지스터메모리 관리 정보입출력 상태 정보우선순위등으로 구성되어 있습니다. 프로그램 카운터가 필요한 이유는 어떤 프로세스가 실행되다가 다른 프로세스에게 CPU를 뺏기고 다시 실행될 때 원래 실행하던 명령어가 실행되어야 하기 때문에 프로그램 카운터가 꼭 있어야 합니다. Q5. 컨텍스트 스위칭이란 뭔가요? A5.컨텍스트 스위칭은 실행 중인 프로세스의 상태(레지스터, 스택, 프로그램 카운터 등)를 저장하고, 새로운 프로세스로 전환하는 과정입니다.주로 CPU가 여러 프로세스를 처리하는 환경에서 발생합니다.하지만 오버헤드가 존재하기 때문에, 빈번한 컨텍스트 스위칭은 성능 저하를 유발할 수 있습니다.

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

'그림으로 쉽게 배우는 운영체제'[섹션 01]운영체제란??컴퓨터의 하드웨어적인 요소들과 소프트웨어적인 요소들을 효율적으로 운영하여 관리함으로써 사용자가 시스템을 이용하는데에 편리함을 제공하는 시스템 소프트웨어를 말합니다.운영체제 종류 및 특징 유닉스/리눅스대화식 운영체제사용자가 명령을 입력하면 시스템이 명령을 수행다중작업한번에 하나 이상의 작업을 수행할 수 있음다중 사용자여러 사람이 동시에 각각 작업을 수행할 수 있음이식성90%이상 C언어로 구성, 시스템이 모듈화 되어 있어 다른 하드웨어 기종에 쉽게 이식 가능계층적 파일 시스템 제공계층적 트리 구조를 가짐유닉스와 리눅스의 차이점리눅스는 대부분 무료이지만 유닉스는 대부분 유료리눅스는 개발자 및 일반 사용자가 사용, 유닉스는 대형 시스템 관리자가 사용리눅스는 오픈 소스 개발, 유닉스는 사업자에 의해 배포 비용 수반리눅스는 BASH 쉘 사용, 유닉스는 커맨드 기반 윈도우그래픽 사용자 인터페이스(GUI) 제공키보드없이 마우스로 아이콘이나 메뉴를 선택하여 작업 수행 가능선점형 멀티 태스킹 방식 제공동시에 여러개의 프로그램을 실행하며, 운영체제가 각 작업의 CPU 이용시간 제어자동 감지 기능 (Plug & Play)하필요한 시스템 환경을 운영체제가 자동으로 구성OLE(Object Linking and Embedding) 사용개체를 현재 작성 중인 문서에 자유롭게 연결 또는 삽입 가능 IOSiOS는 사용자 경험과 인터페이스에 매우 중점을 둠하드웨어 및 소프트웨어 최적화강력한 보안 및 프라이버시 기능OS는 앱스토어를 통해 다양한 애플리케이션을 제공하며, 개발자들에게 큰 수익 창출의 기회를 제공 운영체제 특징사용자 편리성한정된 시스템 자원을 효과적으로 사용할 수 있도록 관리 및 운영인터페이스 기능컴퓨터 시스템과 사용자를 연결스케줄링자원의 현재 상태를 파악, 자원 분배를 위한 스케줄링을 담당자원관리프로세스 관리메모리 관리하드웨어 관리파일 시스템 관리입출력 프로그램 관리제어기능입출력 장치와 사용자 프로그램을 제어 운영체제 역사 1940년도애니악 개발애니악 특징운영체제가 없는 최초의 컴퓨터응용 프로그램이 시스템 자원을 제어스위치와 배선을 연결해서 프로그래밍문제 발생 시 종이에 작업 후 테스트 마침 => 기간이 많이 소모되는 단점30톤으로 수많은 진공관으로 구성되어 있기 때문에, 하드웨어 비용이 굉장히 비쌈 1950년대 초진공관과 전선으로 만들어진 논리 회로를 아주 작은 크기로 만든 직접회로 개발CPU와 메모리가 존재하지만 키보드와 모니토는 존재하지 않음펀치 카드에 프로그래머가 카드의 구멍을 뚫어 프로그래밍컴퓨터가 카드를 읽고 계산 후 결과를 라인 프린터로 출력기존 스위치 배선 작업보다 편해짐 1950년도 중후반이전 작업은 오퍼레이터의 오버헤드가 너무 큼싱글 스트림 배치 시스템 개발여러개의 프로그램을 순서대로 실행해서 결과를 한번에 확인할 수 있는 시스템 I/O Device 컨트롤러를 만들어 입출력 중에도 CPU가 계산할 수 있도록 만듦입출력 작업이 끝나면 CPU에게 인터럽트 신호를 주고 인터럽트를 받은 CPU는 다시 처리를 하는 식으로 발전입출력에도 CPU를 기다려야 하는 작업이 필요하다는 단점이 있음 1960년도 이후메모리 침범 이슈 발생다중 프로그램으로 인한 메모리 주소 이슈 발생하드웨어적으로 베이스 레지스터라는 것을 추가해서 프로그램의 시작 주소를 저장하고 모든 프로그램은 영번지에서 실행한다고 가정CPU의 사용률과 효율성을 중요한 문제로 인식 1970년도 이후개인용 컴퓨터의 시대가 시작저렴해진 컴퓨터의 개인 소유가 쉬워짐애플의 매킨토시와 마이크로소프트의 MS-DOS가 많이 사용매킨토시는 GUI를 도입해서 굉장한 인기CPU 사용률과 비용 절감을 위한 노력으로 오늘날의 운영체제가 탄생 운영체제의 구조커널운영체제의 핵심 기능들이 모여있는 컴퓨터 프로그램커널의 기능프로세스 관리기억 장치 관리주변장치 관리파일 관리사용자로부터 자신을 보호하기 위한 시스템 콜이라는 인터페이스 보유시스템 콜을 이용하면 커널에서 제공하는 write() 함수를 쓰게 되는데 하드디스크의 빈 공간에 저장 인터페이스GUI그래픽 사용자 인터페이스의 약자로 말 그대로 그래픽으로 된 인터페이스윈도우나 맥OS와 같이 그래픽으로 커널과 상호작용하기 때문에 일반 사용자도 사용하기가 쉬움 CLI명령줄 인터페이스의 약자요즘은 리눅스는 GUI 환경을 제공하지만 많은 사용자들이 리눅스의 CLI를 선호 컴퓨터 하드웨어와 구조현재 컴퓨터는 프로그램 내장 방식의 폰 노이만 구조폰 노이만은 CPU와 메모리 사이를 버로 연결함버스는 데이터를 전달하는 통로프로그램 내장 방식은 프로그램을 메모리에 올려서 실행시키는 방식메인보드다른 하드웨어를 연결하는 장치다양한 단자가 있음ex) 출력단자, 그래픽 카드 단자, USB 단자, 사운드 단자 등등장치간의 데이터를 전송하는건 메인보드의 버스가 담당CPU1. 산술논리 연산 장치데이터 연산 담당2. 제어 장치모든 장치들의 동작 지시 및 제어3. 레지스터CPU 내에서 계산을 위해 임시적으로 보관하는 장소 RAM랜덤으로 데이터를 읽어도 저장된 위치와 상관 없이 읽는 속도가 동일전력이 끊기면 데이터를 잃어버리기 때문에 메인 메모리로 사용 ROM전력이 끊겨도 데이터 영구 보관데이터를 한번 쓰면 수정 불가 컴퓨터 부팅 과정ROM에 저장된 BIOS 가 실행됨바이오스 - BIOS (Basic Input Output System)메모리와 CPU 레지스터를 초기화 시킨다.디스크로부터 부트 로더를 불러 온다바이오스는 롬에 저장되어 있기 때문에 램에 저장된 정보와는 달리, 컴퓨터를 끄더라도 그 내용이 지워지지 않음 주요 하드웨어에 이상이 없는지 확인 후 부팅 이상이 있을 경우 경고음을 내면서 부팅이되지 않음운영체제가 2개 설치되어 있을 경우, 운영체제를 선택하는 화면이 활성화됨 부팅 후 실행되는 모든 프로그램은 램에 올라와서 운영체제에 의해 관리 폴딩주기적으로 CPU가 입출력 관리자에게 주기적이고 지속적으로 입출력이 왔는지 확인폴링 방식의 단점은 주기적으로 CPU가 확인해줘야 하니 성능이 좋지 않다는 단점이 존재 인터럽트폴링 방식의 단점을 해결한 방식입출력이 완료되었을 때 CPU에게 신호를 주어 인터럽트 서비스 루틴을 실행하는 방식서비스루틴 이란?특정 인터럽트가 들어오면 그 인터럽트를 처리하는 함수 [섹션 02]프로그램이란?하드디스크 등과 같은 저장장치에 저장된 명령문의 집합체 프로세스란?하드디스크에 저장된 프로그램이 메모리에 올라갔을 때 실행중인 프로그램메모리도 사용하고 운영체제의 CPU 스케줄링 알고리즘에 따라서 CPU도 사용하고 필요에 따라 입력과 출력을 하기 때문에 능동적인 존재코드 영역, 데이터 영역, 스택 영역, 킵 영역을 갖고 있음코드 영역자신을 실행하는 코드가 저장되어 있고 데이터 영역은 전역 변수와 스태틱 변수가 저장스택 영역지역 변수와 함수 호출을 했을 때 필요한 정보들이 저장힙 영역프로그래머가 동적으로 메모리를 할당ex) C언어에서 malloc, free 함수를 호출하면 힙 영역에 자원을 할당, 해제 컴파일 과정고급 언어(예: C, C++)로 작성된 소스 코드를 기계어(바이너리 코드)로 변환하는 과정4단계(전처리 → 컴파일 → 어셈블 → 링크)로 진행 1. 전처리 (Preprocessing)소스 코드에서 전처리 지시문(#으로 시작하는 문장)을 처리하는 단계생성 파일 : .i 로 끝남 2. 컴파일 (Compilation)전처리된 코드를 어셈블리 코드(assembly language)로 변환하는 단계생성 파일 : .s 로 끝남주요 작업문법 검사 및 오류 확인최적화 수행어셈블리 코드 생성 3.어셈블 (Assembling)어셈블리 코드를 기계어(오브젝트 파일, .o 또는 .obj)로 변환하는 단계입니다.생성 파일 : .o 로 끝남주요 작업명령어를 바이너리 코드로 변환오브젝트 파일 생성4. 링크 (Linking)여러 개의 오브젝트 파일과 라이브러리를 결합하여 실행 파일(Executable, .exe 또는 a.out)을 생성하는 단계생성 파일 : .exe, .out 로 끝남 멀티 프로그래밍과 멀티 프로세싱 멀티 프로그래밍하나의 CPU가 여러 프로세스를 번갈아 실행특징CPU 이용률 극대화비선점형 스케줄링에 많이 사용병렬 처리가 아닌 시분할 방식 멀티 프로세싱여러 개의 CPU가 동시에 여러 프로세스를 처리특징병렬 처리 가능선점형 스케줄링 적용다중 코어 시스템에서 사용PCB (Process Control Block)운영체제가 각 프로세스를 관리하기 위해 유지하는 데이터 구조체프로세스의 상태, 메모리 정보, CPU 레지스터 정보 등을 저장구성 요소PID (Process ID)프로세스 상태프로그램 카운터CPU 레지스터메모리 관리 정보입출력 상태 정보우선순위 프로그램 카운터가 필요한 이유는 어떤 프로세스가 실행되다가 다른 프로세스에게 CPU를 뺏기고 다시 실행될 때 원래 실행하던 명령어가 실행되어야 하기 때문에 프로그램 카운터가 꼭 있어야 함 프로세스 상태1. 생성새로운 프로세스 생성 2. 준비CPU 할당을 기다리는 상태 3.실행CPU가 프로세스를 실행 중4.대기/O 작업 등으로 대기 중5. 완료실행이 끝난 상태컨텍스트 스위칭 (Context Switching)CPU가 현재 실행 중인 프로세스를 중단하고, 다른 프로세스로 전환하는 작업PCB에 현재 프로세스의 상태 정보를 저장하고, 다음 프로세스의 상태 정보를 불러옴절차1. 현재 프로세스의 상태 저장 (PCB)2. 새로운 프로세스의 PCB 불러오기3. CPU 레지스터 및 메모리 정보 복원4. 새로운 프로세스 실행 프로세스 생성과 종료프로세스 생성 과정1. 부모 프로세스가 fork() 또는 CreateProcess() 호출2. 운영체제가 PCB 생성3. 메모리 할당 및 초기화4. Ready 상태로 전환프로세스 종료 과정1. 프로세스 작업 완료 또는 오류 발생2. 운영체제가 자원 회수3. PCB 제거4. Terminated 상태로 전환 쓰레드 (Thread)프로세스 내에서 실행 흐름 단위독립적인 스택과 레지스터를 가짐같은 프로세스의 쓰레드는 코드, 데이터, 힙 영역 공유쓰레드 종류커널 레벨 쓰레드: 운영체제에서 관리유저 레벨 쓰레드: 사용자 공간에서 관리 [섹션 03] CPU 스케줄링 이란?CPU 스케줄링은 운영체제가 CPU를 여러 프로세스에게 효율적으로 할당하는 기법이는 시스템 성능을 최적화하고 공정성을 보장하며, 응답 시간과 처리율을 개선하는 역할 2. 스케줄링 목표CPU 이용률CPU를 최대한 활용하도록 함처리량단위 시간당 처리할 수 있는 프로세스 수를 최대화대기 시간 최소화프로세스가 CPU를 기다리는 시간을 줄임응답 시간 최소화사용자의 요청에 빠르게 반응공정성모든 프로세스가 공정하게 CPU를 할당받도록 보장 다중 큐 (Multi-Queue)다중 큐 스케줄링은 프로세스를 여러 개의 큐로 분류하고, 각 큐에 다른 스케줄링 정책을 적용하는 방식ex) 시스템 프로세스는 높은 우선순위를 가진 큐에서 실행되고, 사용자 프로세스는 낮은 우선순위 큐에서 실행 FIFO (First In First Out)먼저 들어온 프로세스가 먼저 실행됨 (큐의 구조와 유사)장점: 구현이 간단함단점: 짧은 작업보다 긴 작업이 먼저 실행되면 Convoy Effect 발생 (짧은 작업이 뒤에서 오래 대기하는 문제) SJF (Shortest Job First)실행 시간이 가장 짧은 프로세스를 먼저 실행장점: 평균 대기 시간을 최소화단점: 실행 시간이 긴 프로세스가 계속 뒤로 밀려 기아 현상(Starvation) 발생 가능 타임 슬라이스 (Time Slice)란?타임 슬라이스는 CPU가 각 프로세스에 할당하는 최대 실행 시간을 의미타임 퀀텀(Time Quantum) 이라고도 부르며, 보통 밀리초(ms) 단위로 설정한 프로세스가 타임 슬라이스만큼 실행된 후, 문맥 전환(Context Switch) 을 통해 다른 프로세스로 넘어감 타임 슬라이스의 특징짧은 타임 슬라이스빠른 응답성을 제공하지만 문맥 전환 비용이 증가긴 타임 슬라이스문맥 전환 비용이 줄지만 응답 시간이 길어짐적절한 타임 슬라이스 값을 설정하는 것이 중요일반적으로 타임 슬라이스는 문맥 전환 비용보다 충분히 커야 효율적 타임 슬라이스가 적용되는 스케줄링 알고리즘1. RR (Round Robin)2. MLFQ (Multi-Level Feedback Queue) RR (Round Robin)일정한 시간동안 프로세스를 실행한 후, 다음 프로세스로 전환 장점: 공정성이 보장됨 (모든 프로세스가 CPU를 일정 시간 동안 사용할 기회 제공)단점: 시간 할당량이 너무 크면 FIFO와 유사해지고, 너무 작으면 문맥 전환(Context Switch) 비용 증가 MLFQ (Multi-Level Feedback Queue)여러 개의 큐를 사용하여, 우선순위를 동적으로 조정하는 방식 처음에는 높은 우선순위 큐에서 실행CPU를 많이 사용하면 낮은 우선순위 큐로 이동I/O 중심 프로세스는 높은 우선순위를 유지 장점: CPU 및 I/O 중심 프로세스를 균형 있게 처리할 수 있음단점: 정책을 잘못 설계하면 특정 프로세스가 기아 상태에 빠질 가능성이 있음 '그림으로 쉽게 배우는 자료구조와 알고리즘(기본편)' 자료구조와 알고리즘이란?자료구조(Data Structure): 데이터를 효율적으로 저장하고 관리하는 방법알고리즘(Algorithm): 문제를 해결하는 절차나 방법 시간 복잡도(Time Complexity)란?알고리즘이 실행되는 연산 횟수를 입력 크기(n)에 따라 분석한 것주로 빅오 표기법(O-notation)으로 표현배열(Array) 개념같은 자료형의 연속된 메모리 공간을 차지하는 데이터 구조빠른 접근(O(1)) 가능, 하지만 삽입/삭제(O(N))이 느림 배열 구현#include using namespace std; int main() { int arr[5] = {1, 2, 3, 4, 5}; cout 연결 리스트(Linked List) 개념노드(Node)들이 포인터로 연결된 구조삽입/삭제가 빠름(O(1)), 접근 속도가 느림(O(N))단일 연결 리스트(Singly Linked List), 이중 연결 리스트(Doubly Linked List) 등이 있음연결리스트 구현#include using namespace std; struct Node { int data; Node* next; Node(int val) : data(val), next(nullptr) {} }; class LinkedList { public: Node* head; LinkedList() : head(nullptr) {} void insert(int data) { Node* newNode = new Node(data); newNode->next = head; head = newNode; } void remove(int data) { Node* temp = head; Node* prev = nullptr; while (temp && temp->data != data) { prev = temp; temp = temp->next; } if (!temp) return; // 삭제할 노드 없음 if (prev) prev->next = temp->next; else head = temp->next; // 첫 번째 노드 삭제 시 delete temp; } void display() { Node* temp = head; while (temp) { cout data "; temp = temp->next; } cout 스택(Stack) 개념LIFO(Last In First Out) 구조push(삽입), pop(제거), top(최상단 요소 확인)스택 구현 (C++)#include #include using namespace std; int main() { stack s; s.push(10); s.push(20); s.push(30); cout 큐(Queue) 개념FIFO(First In First Out) 구조push(삽입), pop(제거), front(첫 요소), back(마지막 요소)큐 구현 (C++)#include using namespace std; class Queue { private: struct Node { int data; Node* next; Node(int val) : data(val), next(nullptr) {} }; Node *frontNode, *rearNode; public: Queue() : frontNode(nullptr), rearNode(nullptr) {} void enqueue(int data) { Node* newNode = new Node(data); if (!rearNode) { frontNode = rearNode = newNode; return; } rearNode->next = newNode; rearNode = newNode; } void dequeue() { if (!frontNode) return; Node* temp = frontNode; frontNode = frontNode->next; if (!frontNode) rearNode = nullptr; delete temp; } int front() { return (frontNode) ? frontNode->data : -1; } bool isEmpty() { return frontNode == nullptr; } }; int main() { Queue q; q.enqueue(10); q.enqueue(20); q.enqueue(30); cout 덱(Deque) 개념양방향 삽입/삭제 가능한 자료구조push_front(), push_back(), pop_front(), pop_back() 제공덱 구현 (C++)#include using namespace std; class Deque { private: struct Node { int data; Node* next; Node* prev; Node(int val) : data(val), next(nullptr), prev(nullptr) {} }; Node *frontNode, *rearNode; public: Deque() : frontNode(nullptr), rearNode(nullptr) {} void push_front(int data) { Node* newNode = new Node(data); if (!frontNode) { frontNode = rearNode = newNode; } else { newNode->next = frontNode; frontNode->prev = newNode; frontNode = newNode; } } void push_back(int data) { Node* newNode = new Node(data); if (!rearNode) { frontNode = rearNode = newNode; } else { newNode->prev = rearNode; rearNode->next = newNode; rearNode = newNode; } } void pop_front() { if (!frontNode) return; Node* temp = frontNode; frontNode = frontNode->next; if (frontNode) frontNode->prev = nullptr; else rearNode = nullptr; delete temp; } void pop_back() { if (!rearNode) return; Node* temp = rearNode; rearNode = rearNode->prev; if (rearNode) rearNode->next = nullptr; else frontNode = nullptr; delete temp; } int front() { return (frontNode) ? frontNode->data : -1; } int back() { return (rearNode) ? rearNode->data : -1; } }; int main() { Deque d; d.push_back(10); d.push_front(20); cout 해시 테이블(Hash Table) 개념키-값(Key-Value) 쌍으로 데이터를 저장하는 자료구조탐색 속도 O(1), 충돌 해결 방법 필요 (체이닝, 개방 주소법 등)해시 테이블 구현 (C++)#include #include using namespace std; class HashTable { private: static const int SIZE = 10; vector> table[SIZE]; int hashFunction(int key) { return key % SIZE; } public: void insert(int key, int value) { int hashIndex = hashFunction(key); table[hashIndex].push_back({key, value}); } int get(int key) { int hashIndex = hashFunction(key); for (auto &p : table[hashIndex]) { if (p.first == key) return p.second; } return -1; } }; int main() { HashTable ht; ht.insert(1, 100); ht.insert(11, 200); cout 셋(Set) 개념중복을 허용하지 않는 집합 자료구조삽입/삭제 O(log N) (Balanced BST 사용) 셋 구현 (C++)#include using namespace std; class Set { private: struct Node { int data; Node* next; Node(int val) : data(val), next(nullptr) {} }; Node* head; public: Set() : head(nullptr) {} void insert(int data) { if (contains(data)) return; Node* newNode = new Node(data); newNode->next = head; head = newNode; } bool contains(int data) { Node* temp = head; while (temp) { if (temp->data == data) return true; temp = temp->next; } return false; } }; int main() { Set s; s.insert(10); s.insert(20); s.insert(10); return 0; }