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

지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.버블정렬,선택정렬,삽입정렬,병합정렬,퀵정렬이 있습니다.. 버블정렬성능 : O(n²)의 성능을 가집니다장점 : 구현이 쉽고 단순합니다.단점 : 성능이 좋지않아 대규모 데이터 처리에 좋지않습니다. 선택정렬성능 : O(n²)의 성능을 가집니다장점 : 구현이 쉽고 단순합니다. (버블정렬과 동일)단점 : 성능이 좋지않아 대규모 데이터 처리에 좋지않습니다. (버블정렬과 동일) 삽입정렬성능 : O(n²)의 성능을 가집니다장점 : 구현이 쉽고 단순합니다. (버블정렬과 동일)단점 : 성능이 좋지않아 대규모 데이터 처리에 좋지않습니다. (버블정렬과 동일) 병합정렬성능 : O(n log n)의 성능을 가집니다.장점 : 안정적인 성능을 보여줌단점 : 구현과 이해가 어렵고 메모리 공간을 많이 차지 퀵정렬성능 : 평균적으로 O(n log n)의 성능을 가지고 최악의 경우 피벗이 한쪽으로 치우쳐 O(n²)를 가지지만 보통 최악의경우가 나올 확률은 극히 낮아 좋은 피벗을 선택해 평균적인 성능으로 말해 O(n log n)의 성능을 가집니다.장점 : 속도가 빠르고 추가 메모리 사용이 거의 없음단점 : 최악의 경우 O(n²)의 성능을 가짐 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.재귀로 쉽게 구현할 수 있는 문제라면 메모이제이션을 사용하는 것이 좋습니다메모이제이션은 재귀 기반 방식이라 코드가 직관적이고 분할하여 해결하기도 쉬워 구현이 간단합니다.반면 타뷸레이션은 반복문 기반으로 계산을 순서대로 처리해 안정적이지만 코드가 길어질 수 있습니다. 타뷸레이션과 메모이제이션을 실행했을때 public static int fibonacci1(int n){ // 타뷸레이션 if(n memo){ // 메모이제이션 if(n == 0 || n == 1){ return n; } if (!memo.containsKey(n)) { memo.put(n, fibonacci2(n - 2, memo) + fibonacci2(n - 1, memo)); } return memo.get(n); } public static void main(String[] args) { HashMap memo = new HashMap(); System.out.println("메모이제이션 : " + fibonacci2(5,memo)); System.out.println("타뷸레이션 : " + fibonacci1(5)); }

[인프런 워밍업 클럽 3기 - CS] - 3주차 미션 (운영체제)

메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.레지스터 : 가장 빠른 기억 장소 이고 컴퓨터의 전원이 꺼지면 데이터가 사라져 휘발성 메모리입니다.캐시 : 레지스터와 메인 메모리 사이에 위치해 데이터 접근 속도를 향상시켜주고 cpu가 메인메모리의 데이터를 가져오기전에 L1 -> L2 -> L3 순으로 확인을하고 캐시에 데이터가 없으면 메인 메모리에서 데이터를 가져옴메인메모리 : 운영체제와 프로세스가 사용하는 공간으로 역시 전원이 꺼지면 데이터가 사라지는 휘발성 메모리입니다하드디스크 : 전원이 종료되도 데이터가 유지되는 비휘발성 메모리에 비용이 저렴하지만 속도가느려 보통 실행할 프로그램을 저장하는데 쓰임 사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?base address와 bound address 입니다. 메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?가변 분할 방식장점 : 코드, 데이터, 스택, 힙 등의 영역을 논리적으로 구분하여 모듈 단위로 관리할 수 있어 영역간 접근 권한 설정이 쉬움단점 : 외부 단편화 발생 고정 분할 방식장점 : 외부 단편화가 발생하지 않고 메모리 관리가 단순함단점 : 내부 단편화 발생 CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?스레싱 입니다물리메모리 용량이 적어서 발생하는거라 메모리 크기를 늘리면 해결되지만 무작정 메모리 크기를 늘려도 현재 프로세스가 동작하는데 문제가없어 스레싱이 발생하지 않으면 크기를 늘려도 문제가 발생하지 않음 HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요?꼭 필요합니다.보통 컴퓨터 운영체제를 hdd나sdd에 저장하기 떄문에 필요합니다.ram에도 설치가 가능은 하겠지만 ram은 휘발성 메모리이기 때문에 전원이 종료되면 전부 사라져 비휘발성 메모리인 hdd/ssd에 저장을 하는게 비용적인 면이나 안전성면에서 좋습니다 파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?파일의 데이터가 완전히 지워지지 않기 떄문입니다.파일시스템은 빈 블록 정보를 모은 Free Block List이 존재하는데 파일 삭제시 파일전부를 지우는게아닌 파일의 헤더만 삭제하고 나머지 블록은 Free Block List에 저장해 두기 떄문입니다.

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

1일차가상 메모리 개요 가상 메모리란?프로세스는 물리 메모리의 크기나 운영체제 영역이 어디에 위치하는지를 몰라도 된다. 프로세스는 메모리 관리자(MMU, Memory Management Unit)를 통해 메모리에 접근하며, 가상 메모리를 통해 자신만의 독립적인 주소 공간을 가진다.가상 메모리의 크기는 이론적으로 무한하지만 실제로는 물리 메모리 크기와 CPU 비트 수에 따라 결정된다. 예를 들어, 32비트 CPU에서는 2의 32승(약 4GB) 크기의 가상 주소 공간을 제공할 수 있다.만약 4GB 크기의 프로세스 5개가 실행되면 총 20GB가 필요한데, 이는 실제 물리 메모리보다 훨씬 크다. 이를 가능하게 하려면 물리 메모리의 일부만을 사용하고 나머지는 하드디스크의 스왑 영역에 저장했다가 필요할 때 가져오는 방식이 필요하다. 이 방식을 가상 메모리라고 한다.가상 메모리를 통해 실행 중인 프로세스의 일부만 물리 메모리에 적재하고, 나머지는 스왑 공간에 두어 메모리를 효율적으로 사용할 수 있다. 주소 변환과 메모리 관리 전략메모리 관리자는 가상 주소를 물리 주소로 변환하기 위해 동적 주소 변환(Dynamic Address Translation) 을 수행한다. 프로세스는 논리 주소를 사용하고, 실제 주소 변환은 MMU가 수행한다. 이때 물리 메모리와 스왑 영역을 포함한 공간을 관리해야 하므로 메모리 관리자는 복잡한 구조를 가진다.물리 메모리에서 0x0 주소는 운영체제가 사용하는 공간이므로 일반 사용자 프로세스는 사용할 수 없으며, 나머지 영역은 고정 분할 방식 또는 가변 분할 방식으로 나눠진다.세그멘테이션: 가변 분할 방식 (외부 단편화 발생)페이징: 고정 분할 방식 (내부 단편화 발생)혼합 방식: 세그멘테이션 + 페이징가상 메모리 시스템에서는 가상 주소가 물리 메모리나 스왑 영역의 어느 위치에 있는지를 일대일 매핑 테이블(페이지 테이블 등) 을 통해 관리한다. 세그멘테이션(Segmentation)세그멘테이션은 프로그램을 논리적 단위(코드, 데이터, 힙, 스택 등)로 분리하여 각 영역을 세그먼트로 나누는 방식이다.세그먼트는 물리 메모리상에서 인접할 필요가 없고, 독립적으로 배치될 수 있다.논리 주소는 (세그먼트 번호, 오프셋) 형태로 구성된다.물리 주소 변환은 세그먼트 테이블의 base address와 bound address를 사용한다.실제 물리주소로 변환은 중간에서 메모리 관리자(MMU)가 해줌변환 예시:CPU가 세그먼트 1번의 주소 0x632에 접근 요청해당 세그먼트의 base address = 5200, bound address = 1000오프셋 0x632 오프셋 0x632 물리주소 5832로 접근논리주소가 더 클 경우CPU가 세그먼트 3번의 주소 0x750에 접근 요청해당 세그먼트의 bound address = 500논리 주소 0x750은 500보다 크므로 접근 불가메모리 관리자는 메모리 침범(잘못된 접근)으로 판단하고 인터럽트를 발생시켜 프로세스를 종료시킴장점:코드, 데이터, 스택, 힙 등의 영역을 논리적으로 구분하여 모듈 단위로 관리할 수 있음이로 인해 영역 간 공유와 접근 권한 설정이 쉬움가변 분할 가능단점:외부 단편화 발생 (공간 낭비)페이징(Paging) 페이징은 논리 주소와 물리 주소를 동일한 크기의 단위로 나누어 사용하는 방식이라 외부 단편화가 발생하지 않음.논리 주소 공간과 물리 주소 공간은 각각의 역할이 있다.논리 주소 공간: 사용자와 프로세스가 바라보는 주소 공간물리 주소 공간: 실제 메모리 하드웨어에서 사용되는 주소 공간논리 주소 공간은 페이지(Page) 단위로 나뉘고 물리 주소 공간은 프레임(Frame) 단위로 나뉨 주소 변환 과정:메모리 관리자는 테이블을 가지고 있는데 이를 페이지 테이블(Page Table)이라 부른다. CPU에서 논리 주소를 전달하면, 메모리 관리자는 이 논리 주소가 몇 번 페이지에 해당하는지와 오프셋(offset)을 계산한다.메모리 관리자 내부에는 PTBR(Page Table Base Register) 이 있어, 이를 통해 해당 프로세스의 페이지 테이블이 물리 메모리의 어디에 위치하는지를 알아낸다.페이지 번호는 페이지 테이블의 인덱스가 되고, 해당 인덱스의 값은 실제 물리 메모리 내의 프레임 번호가 된다.오프셋은 프레임 시작 주소에 더해져 최종 물리 주소가 계산된다.만약 페이지 테이블 항목이 invalid(유효하지 않음)로 표시되어 있다면 해당 페이지는 스왑 영역(하드디스크)에 있으며, 필요한 경우 물리 메모리로 로드된다.세그멘테이션과 마찬가지로 PTBR은 컨텍스트 스위칭 시마다 해당 프로세스의 값으로 업데이트된다.논리 주소는 (페이지 번호, 오프셋)으로 나뉨페이지 번호 → 페이지 테이블에서 대응되는 프레임 번호 찾음물리 주소 = 프레임 시작 주소 + 오프셋 32bit cpu가 주소변환하는 과정 :32비트 CPU 기준 주소 공간은 4GB페이지 크기를 16MB(2^24)로 설정하면 32비트 중 상위 8비트가 페이지 번호, 하위 24비트가 오프셋이 됨총 페이지 수는 2^8 = 256개로, 각 페이지가 16MB물리 메모리는 프레임이 128개라고 가정할 경우 약 2GB 크기부족한 메모리는 스왑 처리를 통해 해결 가능메모리 관리자 내 페이지 테이블은 1차원 배열 형태이며, 페이지 번호는 배열의 인덱스로 사용되어 해당 인덱스에서 프레임 번호를 참조CPU가 논리 주소 0x1000에 접근할 때:페이지 번호 = 0x1000 ÷ 16MB = 0 (페이지 크기 기준 몫)오프셋 = 0x1000 (페이지 크기 기준 나머지)페이지 테이블에서 0번 인덱스의 값이 프레임 3이라면, 물리 주소 = 프레임 3의 시작 주소 + 0x1000CPU가 논리 주소 0x1000에 접근할 때: - 0x1000 = 4096 (10진수) - 페이지 크기: 16MB = 16,777,216 bytes - 페이지 번호 = 4096 ÷ 16,777,216 = 0 (페이지 크기 기준 몫) - 오프셋 = 4096 % 16,777,216 = 4096 (또는 0x1000) - 페이지 테이블에서 0번 인덱스의 값이 프레임 3이라면, - 프레임 3의 시작 주소 = 3 × 16MB = 50,331,648 (또는 0x3000000) - 물리 주소 = 프레임 시작 주소 + 오프셋 = 0x3000000 + 0x1000 = 0x3001000 최종 물리 주소 = 0x3001000 장점:외부 단편화 없음관리가 단순함단점:내부 단편화 발생 가능성페이지 테이블의 크기가 커질 수 있으며 이를 해결하기 위해 다단계 페이지 테이블(Multi-level Paging)과 페이지 테이블 압축 기법이 존재함 세그멘테이션 vs 페이징메모리 분할 방식: 세그멘테이션은 가변 크기의 세그먼트를 사용하고, 페이징은 고정 크기의 페이지로 나눈다.주소 구성 방식: 세그멘테이션은 (세그먼트 번호, 오프셋), 페이징은 (페이지 번호, 오프셋)으로 주소를 구성한다.단편화: 세그멘테이션은 외부 단편화가 발생하고, 페이징은 내부 단편화가 발생할 수 있다.메모리 보호 및 공유: 세그멘테이션은 영역별 권한 설정과 공유가 쉬우며, 페이징은 논리 영역 구분이 어려워 공유/권한 제어가 어렵다.메모리 관리 비용: 페이징은 모든 프로세스가 개별 페이지 테이블을 가지므로 테이블이 많아질수록 관리 비용이 증가하고, 프로세스가 실제 사용할 수 있는 메모리 공간이 줄어들 수 있다.이처럼 세그멘테이션은 논리적 구조에 맞는 유연한 관리가 가능하지만 외부 단편화가 단점페이징은 메모리 관리가 간편하지만 내부 단편화와 테이블 크기 문제가 단점 페이지드 세그멘테이션 (Paged Segmentation)페이지드 세그멘테이션은 세그멘테이션과 페이징을 결합한 메모리 관리 기법으로, 두 방식의 장점을 결합하여 메모리를 효율적으로 관리하면서도 공유 및 접근 보호 기능을 강화할 수 있다. 세그멘테이션과 페이징의 역할세그멘테이션:프로그램을 코드, 데이터, 힙, 스택 등 의미 있는 단위(세그먼트)로 나누어 관리프로세스 간 공유 및 메모리 접근 보호가 용이페이징:메모리를 고정된 크기의 페이지 단위로 나누어 관리외부 단편화를 방지하여 메모리를 효율적으로 사용페이지드 세그멘테이션에서는 세그먼트 내부에서 다시 페이징을 적용하여, 세그먼트의 크기가 가변적이지만, 내부 단위는 고정된 크기(페이지)로 관리된다.세그먼트 내부를 다시 페이지 단위로 나누어 관리함세그먼트 테이블에는 권한 비트, 페이지 테이블 정보 포함 주소 변환 방식:세그먼트 테이블은 base address와 bound address로 구성되며, 여기서 base address는 해당 세그먼트의 페이지 테이블이 시작하는 위치(프레임 번호 또는 인덱스)를 의미하고, bound address는 해당 세그먼트에 할당된 페이지 수를 나타낸다권한 비트를 통해 해당 세그먼트의 접근 권한을 검사가상 주소가 주어지면 해당 세그먼트를 찾고, 권한을 확인한 뒤 페이지 번호와 페이지 개수를 확인함페이지 번호를 이용해 페이지 테이블에 접근하고, 해당 프레임 번호를 찾은 후 프레임 시작 주소에 오프셋을 더해 물리 주소를 계산함물리 메모리에 프레임이 존재하지 않으면 스왑 영역에서 메모리로 데이터를 가져옴요약1. 가상 주소에서 세그먼트 번호를 추출2. 세그먼트의 권한을 검사3. 해당 세그먼트의 페이지 테이블에서 프레임 번호 추출4. 프레임 시작 주소 + 오프셋 → 물리 주소 계산 페이지드 세그멘테이션의 장점과 단점장점논리적 관리 + 메모리 효율성: 세그멘테이션을 사용하여 코드, 데이터, 힙, 스택을 논리적으로 구분하면서도, 내부적으로 페이징을 적용하여 메모리 단편화를 줄일 수 있음공유 및 보호 기능 강화: 세그먼트 단위로 다른 프로세스와 특정 영역을 공유하거나, 접근 권한을 제어할 수 있음단점메모리 접근 시 2번 참조가 필요하여 성능 저하첫 번째 참조: 세그먼트 테이블 조회두 번째 참조: 페이지 테이블 조회총 2번의 메모리 접근이 필요하므로 속도가 느려질 수 있음추가적인 하드웨어 지원 필요성능 최적화를 위해 TLB(Translation Lookaside Buffer) 같은 캐시 기법이 필요 현대 운영체제에서의 활용현대 운영체제는 대부분 "페이징 기반 메모리 관리"를 사용하지만, 일부 시스템에서는 페이지드 세그멘테이션 기법을 혼합하여 사용특히 프로세스 간 코드 공유, 메모리 접근 보호가 중요한 경우 페이지드 세그멘테이션 기법이 활용됨성능 최적화를 위해 다단계 페이지 테이블, TLB 캐싱 기법을 함께 사용 메모리 접근 권한메모리 영역별로 접근 권한을 다르게 설정함:코드 영역: 프로그램의 실행 파일이 저장되는 공간 → 읽기 + 실행 가능, 수정(쓰기) 불가데이터 영역: 전역 변수, 상수 등이 저장되는 공간 → 읽기 가능, 쓰기는 선택적, 실행 불가힙, 스택: 동적 메모리 할당 → 영역 읽기, 쓰기 (실행 불가)운영체제는 가상 주소를 물리 주소로 변환할 때 해당 주소에 대한 접근 권한을 검사하며, 위반 시 예외(Exception) 또는 인터럽트를 발생시켜 프로세스를 종료한다. 삽입 정렬 (Insertion Sort)삽입 정렬은 배열을 정렬된 영역과 정렬되지 않은 영역으로 나누고, 정렬되지 않은 값을 하나씩 정렬된 영역에 삽입하는 방식이다.정렬 과정 예시: [4, 1, 5, 3, 6, 2]정렬된 영역: [4], 삽입할 값: 1 → [1, 4, 5, 3, 6, 2]다음 값 5는 4보다 크므로 그대로3은 5보다 작아, 5와 4를 오른쪽으로 밀고 → [1, 3, 4, 5, 6, 2]반복하여 최종 정렬 결과: [1, 2, 3, 4, 5, 6]시간 복잡도: O(n²)장점: 구현이 간단하고, 데이터가 거의 정렬된 경우 빠름단점: 큰 배열에서는 성능이 떨어짐 자바 코드 예시public static void insertion(int[] arr) { for(int i = 1; i = 0; j--){ // 현재 삽입할 데이터(insertingData)와 정렬된 영역 비교 if(arr[j] > insertingData){ // 삽입할 값보다 크면 한 칸 오른쪽으로 이동 arr[j + 1] = arr[j]; } else { break; // 삽입할 위치를 찾으면 루프 종료 } } arr[j + 1] = insertingData; // 찾은 위치에 삽입할 값 저장 } } public static void main(String[] args) { int[] arr = {1, 6, 4, 3, 2, 5}; System.out.println("정렬 전: " + Arrays.toString(arr)); insertion(arr); System.out.println("정렬 후: " + Arrays.toString(arr)); } 2일차 디맨드 페이징(Demand Paging)(가져오기 정책)프로그램이 메모리에 올라와 프로세스로 실행될 때, 코드(Code), 데이터(Data), 힙(Heap), 스택(Stack) 등의 모듈이 모두 메모리에 올라와 실행되는 것처럼 보이지만, 실제로는 필요할 때만 필요한 부분이 메모리에 올라와 실행된다.지역성(Locality) 이론90:10 법칙에 따르면 프로그램이 실행될 때 전체 코드의 10%에서 90%의 시간이 소비된다고 하고 이는 지역성(Locality) 이론과 관련이 있으며, 지역성에는 두 가지 유형이 있다.공간적 지역성(Spatial Locality): 현재 위치와 가까운 데이터에 접근할 확률이 높음.시간적 지역성(Temporal Locality): 현재 기준으로 가까운 시간에 접근한 데이터가 먼 시간에 접근했던 데이터보다 다시 접근될 확률이 높음.운영체제는 이러한 지역성 이론을 활용하여 자주 사용될 데이터만 메모리에 올리고, 필요하지 않은 데이터는 스왑 영역으로 보내 성능을 향상시킨다. 디맨드 페이징(Demand Paging)은 조만간 필요할 것 같은 데이터를 메모리로 가져오고, 사용되지 않을 것 같은 데이터는 스왑 영역으로 이동시키는 정책이다.디맨드 페이징을 사용하는 예가상 메모리를 사용하는 운영체제현대적인 운영체제의 메모리 관리 기법페이지 교체가 필요한 경우 메모리 계층 구조메모리는 속도에 따라 여러 계층으로 나눌 수 있다.레지스터(Register): CPU 내에 존재하며 한 사이클만에 접근 가능하여 가장 빠름.캐시(Cache): CPU에서 수 사이클~수십 사이클에 접근 가능.메인 메모리(Main Memory, RAM): 수백 사이클이 걸림.보조 저장 장치(Storage, HDD/SSD): 수백만 사이클이 걸려 매우 느림.디맨드 페이징에서는 스왑 영역을 보조 저장 장치에 저장하는데, 성능 향상을 위해 스왑 영역으로 데이터를 이동시키는 횟수를 최소화해야 한다. 가상 메모리와 페이지 테이블가상 메모리 크기는 물리 메모리 크기 + 스왑 영역 크기로 정의된다.스왑인(Swap In): 스왑 영역에서 물리 메모리로 데이터를 가져오는 과정.스왑아웃(Swap Out): 물리 메모리에서 스왑 영역으로 데이터를 보내는 과정.가상 주소가 주어지면 운영체제는 **페이지 테이블(Page Table)**을 참조하여 물리 메모리 내의 프레임(Frame) 위치를 찾거나, 스왑 영역 내의 위치를 확인한다.페이지 테이블 엔트리(Page Table Entry, PTE)는 여러 비트 정보를 포함한다.접근 비트: 페이지가 메모리에 올라온 후 접근이 있었는지 나타냄. (읽기 또는 실행 시 1로 변경)변경 비트: 페이지가 메모리에 올라온 후 데이터 변경이 있었는지 나타냄. (쓰기 작업 시 1로 변경)유효 비트: 해당 페이지가 물리 메모리에 있는지 여부를 나타냄. (1이면 물리 메모리에 있음, 0이면 스왑 영역에 있음)읽기/쓰기/실행 비트: 접근 권한을 검사하는 비트.프로세스가 요청하면 운영체제는 페이지 테이블을 참조하여 물리 메모리에 프레임이 존재하는지 확인한다. 만약 페이지가 물리 메모리에 없다면 Page Fault(페이지 폴트) 예외가 발생한다.Page Fault 발생 시 처리 과정운영체제는 페이지 테이블을 참조하여 해당 페이지가 스왑 영역에 있는지 확인.스왑 영역에서 데이터를 메모리로 가져옴 (스왑인).해당 프로세스는 대기 상태가 됨.데이터가 메모리에 올라간 후 프로세스가 다시 실행 상태가 됨. 물리 메모리에서 데이터 참조 과정예제 1: 페이지가 물리 메모리에 있는 경우프로세스가 페이지 0을 요청.페이지 테이블에서 페이지 0의 유효 비트(Valid Bit) = 0, 프레임 넘버 = 1 일떄페이지가 물리 메모리 1번 프레임에 존재하므로 해당 프레임에서 데이터를 참조.예제 2: 페이지가 스왑 영역에 있는 경우프로세스가 페이지 2를 요청.페이지 테이블에서 페이지 2의 유효 비트 = 1, 프레임 넘버 = 2 일때페이지가 스왑 영역 2번에 있음을 의미.물리 메모리에 적절한 공간이 필요하므로 빈 공간(예: 3번 프레임)에 데이터를 올림.페이지 테이블을 업데이트하여 유효 비트 = 0, 프레임 넘버 = 3으로 수정 후 프로세스가 해당 데이터를 참조하게 함. 페이지 교체 알고리즘운영체제는 스왑아웃과 스왑인 시 어떤 페이지를 교체할지 판단해야 하며, 이를페이지 교체 알고리즘(Page Replacement Algorithm)이라 한다.대표적인 알고리즘:FIFO(First In First Out): 가장 먼저 올라온 페이지를 제거.LRU(Least Recently Used): 가장 오랫동안 사용되지 않은 페이지를 제거.LFU(Least Frequently Used): 가장 적게 사용된 페이지를 제거. 병합 정렬(Merge Sort)병합 정렬은 재귀적으로 정렬하는 알고리즘이다.데이터를 반으로 나누어 분할.각각을 정렬한 후 병합하며 정렬.두 개의 데이터가 하나로 합쳐질 때 비교 연산이 두 번 발생.네 개의 데이터가 두 개로 병합될 때 비교 연산이 네 번 발생.단계마다 영역의 수가 반으로 줄어들기 때문에 **O(log n)**의 성능을 가짐.병합할 때 n개의 데이터를 비교하므로 전체 시간 복잡도는 O(n log n).장점O(n log n)의 성능으로 퀵 정렬보다 안정적인 성능을 제공.단점이해와 구현이 어렵고 추가적인 메모리 공간이 필요함. 자바 코드 예시 public static void MergeSort(int[] arr, int leftIndex, int rightIndex) { if(leftIndex midIndex){ // 왼쪽 영역이 먼저 끝났을 경우, 오른쪽 나머지 요소 복사 for(int i = rightAreaIndex; i 3일차 페이지 교체 정책프로세스는 데이터를 접근하기 위해 메모리를 참조하는데, 해당 데이터가 메모리에 없으면 페이지 폴트(Page Fault)가 발생한다. 이 경우, 운영체제는 해당 페이지를 스왑 영역에서 물리 메모리로 불러와야 한다. 하지만 메모리가 가득 차서 공간이 없다면, 기존에 메모리에 있는 페이지 중 하나를 선택하여 스왑 영역으로 옮겨야 하는데 이때 어떤 페이지를 교체할지 결정하는 것이 페이지 교체 정책(Page Replacement Policy)이다. 페이지 교체 정책의 종류랜덤(Random) 교체 알고리즘무작위로 페이지를 선택하여 교체하는 방법.지역성을 고려하지 않아 성능이 낮아 실제로 거의 사용되지 않음. FIFO(First-In First-Out) 교체 알고리즘가장 먼저 메모리에 들어온 페이지를 제거하는 방식.단순하고 구현이 쉬우나, 자주 사용되는 페이지도 오래되었다는 이유로 교체될 수 있어 성능 저하 발생 가능.빌레이디의 역설(Bélády's Anomaly):프레임 수를 증가시켜도 오히려 페이지 폴트가 증가하는 현상이 발생할 수 있음. 최적(Optimal, OPT) 교체 알고리즘앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 방식.이론적으로 최적이지만, 미래의 메모리 접근 패턴을 예측해야 하므로 실제 구현이 불가능.다른 알고리즘의 성능을 평가할 때 비교 기준으로 사용됨. LRU(Least Recently Used) 교체 알고리즘가장 오랫동안 사용되지 않은 페이지를 교체하는 방식.시간적 지역성(Temporal Locality)을 고려하여 자주 사용된 페이지를 유지함.하지만 모든 페이지의 사용 시간을 기록해야 하므로 구현이 어려움.하드웨어적으로 접근 비트(Access Bit)를 지원하지 않는 경우 구현이 불가능하여 다른 대체 기법을 사용해야 함. FIFO의 문제점과 해결책FIFO의 가장 큰 문제는 빌레이디의 역설로 인해 프레임 수를 늘려도 페이지 폴트가 증가하는 경우가 발생할 수 있음.하지만 LRU에서는 빌레이디의 역설이 발생하지 않음.LRU에선 접근비트를 이용하는데 하드웨어적으로 접근비트를 지원하지않으면 FIFO를 쓸수밖에없음FIFO 개선 방법: 2차 기회 알고리즘(Second-Chance Algorithm)FIFO 방식과 유사하지만, 자주 사용되는 페이지는 한 번 더 기회를 부여하는 방식.만약 페이지가 참조되었다면 큐의 맨 뒤로 이동시켜 수명을 연장함.LRU보다는 성능이 낮지만, FIFO보다는 성능이 향상됨。 LRU의 한계와 클락(Clock) 알고리즘LRU 구현 문제모든 페이지의 사용 시간을 기록하려면 많은 비트가 필요함.오랜 시간이 지나면 오버플로우 문제가 발생하여 시간을 정확히 기록하기 어려움.따라서 LRU를 근사적으로 구현하는 방식으로 클락(Clock) 알고리즘을 사용함.클락(Clock) 알고리즘접근 비트(Access Bit)를 이용하여 최근 참조 여부를 추적.페이지들을 원형으로 연결하고, 각 페이지를 가리키는 포인터(Clock Hand)를 시계방향으로 회전시키며 검사.이 포인터를 클락 핸드(Clock Hand)라고 부른다.클락 핸드는 페이지 교체가 필요할 때 순차적으로 각 페이지의 접근 비트를 검사한다.접근 비트가 1인 경우, 접근 비트를 0으로 초기화하고 클락 핸드는 다음 페이지로 이동한다.접근 비트가 0인 경우, 해당 페이지를 교체 대상으로 선택한다.FIFO보다 성능이 뛰어나며, LRU에 근접한 성능을 보임.향상된 클락 알고리즘(Enhanced Clock Algorithm)접근 비트 + 변경 비트를 함께 고려.교체 우선순위:접근 비트 = 0, 변경 비트 = 0 (가장 먼저 교체)접근 비트 = 0, 변경 비트 = 1접근 비트 = 1, 변경 비트 = 0접근 비트 = 1, 변경 비트 = 1 (가장 나중에 교체) 스레싱(Thrashing)과 워킹셋(Working Set)스레싱(Thrashing)운영체제가 CPU 사용률을 높이기 위해 멀티프로그래밍 정도를 증가시키면서, 페이지 폴트가 빈번하게 발생하여 CPU가 대부분 스왑 작업에 소비되는 현상.즉, CPU가 실제 작업보다 페이지 교체에 더 많은 시간을 소비하여 성능이 급격히 저하됨.해결 방법: 물리 메모리 크기를 증가시키거나, 적절한 프로세스 수 조절.하지만 무작정 크기를 늘린다고 해결되지는 않는데 현재 메모리가 프로세스들이 작업하는데 충분한 크기라 스레싱이 발생하지않는다면 크기를 늘려도 별 문제가 발생하지않기떄문임워킹셋(Working Set)프로세스가 일정 시간 동안 참조하는 페이지 집합을 워킹셋으로 스레싱을 예방하는 역할을 함페이지 폴트가 발생하면 워킹셋 크기를 증가시켜 추가 페이지를 할당.반대로 페이지 폴트가 거의 발생하지 않으면 워킹셋 크기를 줄여 불필요한 페이지를 회수.지역성(Locality) 원리를 활용하여 성능을 최적화워킹셋은 프로세스가 준비상태에서 실행상태가 되는 컨텍스트스위칭을 할때 사용 퀵 정렬(Quick Sort)병합 정렬(Merge Sort)과 마찬가지로 분할 정복(Divide and Conquer) 알고리즘.정렬 전에 배열에서 하나의 원소를 피벗(Pivot)으로 선택.피벗을 기준으로 작은 값과 큰 값으로 나누어 재귀적으로 정렬 수행.퀵 정렬의 성능평균적인 경우: O(n log n)최악의 경우: O(n²) (피벗이 한쪽으로 치우친 경우)퀵정렬은 대부분 좋은 피벗을 선택하고 최악의 확률이 극히낮아 평균적인 성능을말함적은 비교 연산과 메모리 사용량 덕분에 병합 정렬보다 효율적퀵 정렬이 병합 정렬보다 선호되는 이유병합 정렬은 추가적인 메모리 공간이 필요하지만, 퀵 정렬은 제자리 정렬(in-place sorting)이 가능.대부분의 경우, 퀵 정렬이 더 적은 비교 연산을 수행하여 속도가 빠름 자바 코드 예시 public static void quickSort(int[] arr, int left, int right) { if(left = arr[leftStartIndex]){ // 피벗보다 작거나 같은 값은 이미 왼쪽에 있어야 하니 다음 인덱스로 이동 leftStartIndex++; } while(rightStartIndex >= (left + 1) && pivot 4일차입출력 장치 주변장치 개요주변장치는 그래픽카드, 하드디스크, SSD, 키보드, 마우스 등 다양한 장치들이 있으며, 이들은 메인보드의 버스를 통해 연결된다. 버스는 주소 버스(Address Bus), 데이터 버스(Data Bus), 제어 버스(Control Bus)로 구성되어 있으며, I/O 디바이스는 이를 통해 데이터를 송수신한다.각 주변장치에는 외부 인터페이스와 함께 상태나 데이터를 보관하는 레지스터들이 존재하며, 이 레지스터에 저장된 데이터는 CPU가 사용하기 위해 메모리로 이동되기도 한다.주변장치는 캐릭터 디바이스와 블록 디바이스로 구분된다. 이는 데이터를 전송하는 단위에 따라 나뉘며, 캐릭터 단위인지 블록 단위인지를 기준으로 한다.캐릭터 디바이스: 마우스, 키보드, 사운드 카드, 직렬/병렬 포트 등. 상대적으로 적은 양의 데이터를 전송한다.블록 디바이스: 하드디스크, SSD, 그래픽카드 등. 대용량 데이터를 전송한다. 입출력 구조와 제어 방식예전 시스템에서는 모든 주변장치를 하나의 버스로 연결했으며, CPU가 직접 I/O 장치에 접근하여 데이터를 처리했다. 이 방식은 입출력 중 CPU가 다른 작업을 하지 못해 CPU 사용률이 낮아지는 문제가 있었다.이를 개선하기 위해 **입출력 제어기(I/O Controller)**와 입출력 버스가 도입되었다. CPU는 I/O 명령을 만나면 입출력 제어기에 명령을 위임하고 다른 작업을 수행할 수 있게 되었다.입출력 제어기는 두 채널로 구분된다:시스템 버스: CPU와 메모리가 사용하는 고속 버스입출력 버스: 주변장치가 사용하는 저속 또는 고속 버스입출력 버스는 다시 고속 I/O 버스와 저속 I/O 버스로 나뉘며, 장치 속도에 따라 병목 현상을 방지한다. 예를 들어, 그래픽카드는 매우 빠른 대역폭이 필요하기 때문에 시스템 버스에 직접 연결되기도 한다.하지만 입출력 제어기만으로는 데이터를 메모리에 쓰기 위해 여전히 CPU의 개입이 필요했다. 이를 해결하기 위해 DMA(Direct Memory Access) 제어기가 도입되었다. DMA는 입출력 장치가 CPU를 거치지 않고 직접 메모리에 접근할 수 있게 하여 성능을 향상시킨다.DMA와 CPU가 메모리 충돌 없이 사용할 수 있도록, 메모리를 나눠 관리하는 방식을 Memory Mapped I/O라고 한다. 마우스와 키보드 동작 방식마우스예전에는 볼 마우스를 사용했으며, 내부의 볼이 회전하며 움직임을 감지했다.현재는 광학 마우스를 주로 사용한다. 하단에 있는 카메라가 초당 수천 회 표면을 촬영하고, 내장 DSP가 이미지 변화를 분석하여 X, Y축 좌표를 계산한다.마우스의 동작이나 클릭 등의 이벤트가 발생하면, 디바이스 컨트롤러가 CPU에 인터럽트를 보내고, 마우스 드라이버가 데이터를 읽어 운영체제에 이벤트로 전달한다.운영체제는 이 이벤트를 포그라운드 애플리케이션에 전달하여 동작을 수행하게 한다.키보드사용자가 키를 누르면 키보드 컨트롤러가 어떤 키인지 판단하여 CPU에 인터럽트를 발생시킨다.이후 키보드 드라이버가 운영체제에 이벤트를 전달하고, OS는 해당 이벤트를 포그라운드 애플리케이션에 전달한다.애플리케이션은 해당 키에 맞는 동작을 수행한다. 하드디스크와 플래시 메모리하드디스크 구조하드디스크에는 중심축인 스핀들이 있으며, 여기에 여러 개의 원판(플래터)이 장착되어 있다. 플래터는 자기화된 원판으로, 디스크 암에 고정된 읽기/쓰기 헤드가 데이터를 읽거나 쓴다.플래터는 여러 개의 트랙(원형 경로)으로 구성되며, 각 트랙은 다시 섹터로 나뉜다. 섹터는 하드디스크의 가장 작은 저장 단위이다. 플래터가 여러 개인 경우 같은 위치의 트랙들을 묶은 것을 실린더(Cylinder)라고 한다.플래터 표면에는 자성이 있으며, N극으로 자화된 부분은 0, S극으로 자화된 부분은 1로 인식된다. 이러한 방식으로 디지털 데이터를 저장한다.일반적으로 하드디스크는 2개 이상의 플래터를 사용하고, 각 플래터의 양면에 헤드가 위치해 데이터를 읽는다.헤드는 디스크 암에 고정되어 있으며, 하나의 디스크 암이 여러 헤드를 동시에 움직이기 때문에 모든 헤드는 함께 이동하게 된다.데이터를 읽는 과정 예시:명령: 실린더 C, 트랙 B, 섹터 D를 읽어라디스크 암이 실린더 C로 이동 (이 과정: 시크(Seek))이때 걸리는 시간: 시크 타임(Seek Time)이후 스핀들을 회전시켜 플래터를 돌리고, 섹터 D가 헤드에 닿을떄 까지 기다림섹터 D를 읽은 뒤 작업 완료하드디스크는 이처럼 기계적인 이동이 많기 때문에 느리고, 충격에 약하며, 소음이 발생하는 단점이 있다. 플래시 메모리(SSD)플래시 메모리는 전기적으로 데이터를 처리하기 때문에 빠르고 조용하며, 충격에도 강하다. 또한 자성을 띠지 않으므로 외부 자기장에 영향을 받지 않는다.하지만 플래시 메모리는 특정 영역에 데이터를 다시 쓰기 위해서는 먼저 해당 영역을 지워야 하며, 이 지우기 작업에는 횟수 제한이 존재한다. 같은 지점을 반복해서 지우고 쓰는 작업이 누적되면 해당 셀의 수명이 다해 결국 플래시 메모리가 손상되어 사용할 수 없게 되는 문제가 발생할 수 있다. 또한 자성을 띠지 않으므로 외부 자기장에 영향을 받지 않는다. 동적 프로그래밍과 메모이제이션동적 프로그래밍(Dynamic Programming)은 큰 문제를 작은 문제로 나누어 해결하는 방식으로, 특히 중복 계산을 피하는 데 효과적이다.예를 들어, 피보나치 수열을 재귀로 구현하면 같은 계산을 반복하게 되어 O(n²)의 성능을 가지게 되지만, 메모이제이션(Memoization)을 사용하면 계산 결과를 저장해 중복 연산을 제거하여 O(n)의 성능을 달성할 수 있다.단점으로는, 속도 향상을 위해 메모리를 추가로 사용하게 된다는 점이 있다. 자바코드 예제 public static int fibonacci1(int n) { if(n == 0 || n == 1){ return n; } return fibonacci1(n - 2) + fibonacci1(n - 1); } public static int fibonacci2(int n, HashMap memo){ if(n == 0 || n == 1){ return n; } if (!memo.containsKey(n)) { memo.put(n, fibonacci2(n - 2, memo) + fibonacci2(n - 1, memo)); } return memo.get(n); } public static void main(String[] args) { System.out.println("fibonacci1 : " + fibonacci1(5)); HashMap memo = new HashMap(); System.out.println("fibonacci2 : " + fibonacci2(5,memo)); } 5일차파일과 파일시스템 파일시스템의 역할과 구조메모리처럼 직접 접근이 가능한 장치와는 달리, 하드디스크나 SSD 같은 저장장치는 사용자가 직접 데이터를 저장하거나 수정하게 되면 중요한 정보가 손상될 수 있다. 그래서 사용자는 운영체제를 통해 파일 저장을 요청하고, 운영체제가 이를 안전하게 처리한다.운영체제는 이러한 파일 관리를 위해 파일 관리자를 두며, 이를 파일시스템(File System)이라 부릅니다. 이는 메모리 관리에서 페이지 테이블을 통해 가상 주소를 물리 주소로 변환하듯, 파일 테이블을 통해 파일의 정보와 위치 등을 관리한다. 파일시스템의 주요 기능파일과 디렉토리 생성: 새 파일 및 폴더를 만들 수 있도록 지원함파일과 디렉토리 수정 및 삭제: 기존 데이터를 변경하거나 제거할 수 있음파일 권한 관리: 사용자별 접근 권한을 설정하고 제어함무결성 보장: 파일 손상 없이 안전하게 유지되도록 함백업 및 복구: 데이터 유실에 대비해 저장 및 복원 기능 제공암호화: 파일 내용을 보호하기 위한 암호화 기능 제공 파일시스템과 저장장치의 관계파일시스템은 하드디스크나 플래시 메모리(SSD) 같은 저장장치에 설치된다. 이러한 장치는 데이터를 블록 단위로 전송하지만, 사용자는 바이트 단위로 데이터를 읽고 쓰기 때문에 파일시스템은 중간에서 블록을 바이트 단위로 관리해주는 역할을 한다.주변장치의 관점에서 보면, 하드디스크와 플래시 메모리는 블록 디바이스에 해당하며, 키보드나 마우스처럼 캐릭터 단위로 처리되지 않는다. 파일과 파일 디스크립터파일은 헤더(Header)와 데이터(Data)로 구성되어 있으며, 헤더에는 파일의 속성 정보가 담겨 있다. 운영체제는 파일 정보를 관리하기 위해 파일 제어 블록(File Control Block) 을 유지하며, 사용자가 파일을 열면 파일 디스크립터(File Descriptor) 라는 참조 번호를 통해 파일 제어 블록에 간접적으로 접근할 수 있도록 한다.파일 디스크립터는 파일이 열릴 때 메모리로 로드되며, 사용자는 직접 접근할 수 없다.사용자는 운영체제를 통해 전달받은 디스크립터를 통해 파일에 접근하게 된다. 파일 구조의 종류순차 파일 구조 (Sequential File Structure)데이터가 파일 내에 순서대로 저장됨.C 언어에서는 open() 함수로 파일을 열고, 파일 디스크립터는 파일의 맨 앞을 가리킨다.읽기/쓰기 작업은 처음부터 진행되며, 특정 위치로 이동하려면 lseek() 함수를 사용해야 함.장점: 구조가 단순하고 공간 낭비가 적음.단점: 중간 삽입/삭제가 느림.직접 파일 구조 (Direct File Structure)데이터를 저장할 위치를 해시 함수를 이용해 결정.해시테이블, JSON 등의 구조와 유사.장점: 매우 빠른 접근 속도.단점: 해시 함수 선정이 중요하며, 충돌 및 공간 낭비 가능성 존재.인덱스 파일 구조 (Indexed File Structure)순차 접근과 직접 접근의 장점을 결합.인덱스를 통해 빠른 접근이 가능하고, 순차 처리도 지원함. 디렉토리 구조디렉토리는 파일을 포함할 수 있으며, 하위 디렉토리를 포함할 수도 있다. 디렉토리 구조는 계층형 트리 구조로 발전해 왔으며, 최상위 디렉토리를 루트 디렉토리(Root Directory)라고 부른다.리눅스/유닉스: 루트 디렉토리는 /로 표기되며, 디렉토리 구분자도 / 사용.윈도우: 루트 디렉토리는 보통 파티션 이름(C:\)로 표기되며, 디렉토리 구분자로 \ (역슬래시) 사용.디렉토리는 일반 파일과 동일한 구조를 가지지만, 일반 파일은 데이터를 저장하고 디렉토리는 파일 목록 정보를 저장한다. 디렉토리의 발전초기: 루트 디렉토리만 존재 (단일 디렉토리 구조)이후: 파일이 많아지면서 불편함이 생겨 다단계 디렉토리 구조로 발전 → 모든 디렉토리에서 하위 디렉토리 생성 가능 (트리 구조)순환 참조 문제: 바로가기(Shortcut) 기능으로 인해 트리 구조 내에 사이클이 생길 수 있음 파일과 디스크 할당 방식파일시스템은 파일 정보를 파일 테이블로 관리하고, 이 테이블에는 파일이 저장된 블록의 시작 위치가 기록된다.파일은 여러 블록으로 나뉘어 저장되며, 블록 연결 방식에 따라 아래와 같이 분류된다:연속 할당 (Contiguous Allocation)파일을 연속된 블록에 저장.시작 블록만 알면 전체 파일에 접근 가능 → 매우 빠름.단점: 외부 단편화 발생, 파일 크기 예측 어려움, 실제로는 사용하지않는 방식불연속 할당 (Non-contiguous Allocation)디스크의 빈 블록에 데이터를 분산 저장.연결할당과 인덱스할당으로 나눠짐연결 할당 (Linked Allocation)각 데이터 블록이 다음 블록의 위치를 가리킴 (연결 리스트 방식)파일 테이블에는 시작 블록만 저장됨인덱스 할당 (Indexed Allocation)파일마다 인덱스 블록을 두고, 그 안에 데이터 블록의 포인터를 저장인덱스 블록이 꽉 차면 다른 인덱스 블록을 추가 연결 (확장 가능)파일의 크기가 작다면 데이터를 바로 참조하는 블록 포인터를 이용크다면 간접 포인터를 이용해 많은데이터를 참조유닉스/리눅스에서는 이 구조를 i-node라고 함 디스크 블록과 공간 관리디스크는 일정한 크기의 블록 단위로 나뉘며, 보통 1KB ~ 8KB 사이블록이 작으면 공간 낭비는 적지만, 관리할 블록 수가 많아짐블록이 크면 블록 수는 줄지만 내부 단편화로 인해 일부 공간 낭비 발생 Free Block List매번 빈 블록을 전체 검색하면 비효율적이므로, 파일시스템은 빈 블록 정보를 모은 Free Block List를 유지한다파일 삭제 시, 파일 전체를 지우는 것이 아니라 헤더만 삭제하고 블록은 Free Block List에 추가해 재사용함 동적 프로그래밍 - 타뷸레이션(Tabulation)타뷸레이션은 상향식 계산 방식이다. 문제를 해결하는 데 필요한 값을 미리 계산하여 테이블에 저장하고, 이후 필요한 값은 테이블에서 꺼내 사용하는 방식이다.장점: 재귀 호출을 사용하지 않기 때문에 스택 오버플로우 위험 없음단점: 필요하지 않은 값까지 계산할 수 있음 (메모리 낭비 가능성)메모이제이션 vs 타뷸레이션메모이제이션(Memoization): 하향식(Top-down), 재귀 기반 → 코드가 직관적이고 문제 분할이 쉬움타뷸레이션(Tabulation): 상향식(Bottom-up), 반복문 기반 → 메모리 사용이 예측 가능하고 빠름문제가 분할 정복적으로 풀기 쉬우면 메모이제이션, 재귀가 복잡하거나 메모리 최적화가 중요하면 타뷸레이션이 더 적합하다. 자바 코드 예시 public static int fibonacci3(int n){ if(n 3주차 회고이번주 역시 매일 스케쥴에 맞춰 강의를 듣고 발자국 정리 하는건 빼먹지않았습니다.3주차 강의내용은 생각보다 정말 어려워 아직 이해했다 하기는 힘든상태라 발자국에 정리를 해두고 다시 3주차 처음부터 공부를 다시 해볼 계획입니다. 이번 인프런 워밍업 클럽 후기인프런 강의를 사두고 강의를 완강하는건 쉽지않아 완강할 수있는 계기가 필요해 이번 인프런 워밍업 클럽에 신청해 그중 cs지식이 필요해 감자님의 강의를 수강했습니다.국비과정을 수료해 코드만 칠줄알았었는데 cs 공부를 처음해보니 이해하기 정말 힘들었어서 이번 워밍업 클럽이 아니였으면 사실 손도 안댔을거같습니다.강의는 cs지식이 0에 가까운 저에게 강의제목처럼 그림으로 이해하기 쉽게 알려주셔서 cs지식이 필요한데 뭘 공부할지 모르시는 분들께 정말 추천드리고 강의를 듣다가 질문을 작성하면 답변을 새벽에 올려도 금방금방 답변해주셔서 정말 좋았습니다. 만약 4기 워밍업 클럽도 진행한다면 강력추천합니다.강의 영상도 좋고 질문답변해주시는 것도 빠르고 좋습니다.특히 난 강의를 구매하고 완강을 하기 힘드신분은 강력 추천드립니다.매일 어느파트의 강의를 들어야하는 시간표를 건내줘서 본인이 해당 시간표에 맞춰 행동하겠다 마음만 먹으면 충분히 하실수 있습니다.

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

재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?기저 조건이 없으면 무한으로 반복해 콜스택이 가득차 스택 오버플로우가 발생하여 프로그램이 비정상적으로 종료됩니다. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.자바 코드 예시 public static int sum(int n) { if (n == 1) return 1; // 탈출 조건 if(n % 2 == 1){ return n + sum(n - 1); } return sum(n - 1); } public static void main(String[] args) { System.out.println("홀수합 = " + sum(10)); // 120 출력 } 자바스크립트 예제function sumOdd(n){ if(n == 1) return 1; if(n % 2 == 1){ return n + sumOdd(n-1); } return sumOdd(n-1); } console.log(sumOdd(10)) // 25다음 코드는 매개변수로 주어진 파일 경로(.는 현재 디렉토리)에 있는 하위 모든 파일과 디렉토리를 출력하는 코드입니다. 다음 코드를 재귀 함수를 이용하는 코드로 변경해보세요.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("."); // 현재 경로의 모든 하위 경로의 파일, 디렉토리 출력 자바 코드 예시public static void directory(String directory) { if(directory == null){ return; } File dir = new File(directory); // 디렉토리값을 기반으로 파일 객체 생성 File[] files = dir.listFiles(); // 파일 및 하위 디렉토리 정보 저장 배열 if (files != null) { for (File file : files) { if (file.isDirectory()) { System.out.println("디렉토리 : " + file.getAbsolutePath()); // 경로를 출력 directory(file.getAbsolutePath()); // 재귀로 하위 디렉토리 탐색 } else { System.out.println("파일 : " + file.getAbsolutePath()); } } }else{ return; } } public static void main(String[] args) { directory("."); // 현재 경로의 모든 하위 경로의 파일, 디렉토리 출력 }

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

운영체제FIFO 스케줄링의 장단점이 뭔가요? 장점 : 선입선출 방식의 알고리즘이라 프로세스가 들어온 순서대로 처리할수 있어 단순하고 직관적임단점 : 먼저 온 프로세스가 실행 시간이 길면 실행 시간이 짧은 프로세스들은 그 뒤에서 작업이 끝날떄 까지 기다려야하는 호위효과가 발생하게됨 SJF를 사용하기 여러운 이유가 뭔가요?burst Time의 예측이 어렵고 burst Time이 짧은 작업이 계속 들어올경우 상대적으로 작업시간이 긴 프로세스는 계속 대기해야하는 기아현상이 발생합니다. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?CPU의 프로세스 간에 전환이 너무 자주 일어면 컨텍스트 스위칭이 자주 발생해 오버헤드가 커져 효율성이 떨어집니다. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요? CPU를 사용하는 프로세스가 실행하다가 스스로 CPU를 반납하면 I/O Bound Process이고CPU를 사용하는 프로세스가 타임 슬라이스를 오버해서 스케줄러에 의해 강제로 CPU를 뺏기는 상황이면 CPU Bound Process 입니다. 공유자원이란무엇인가요?프로세스 간 통신에서 공동으로 사용하는 변수나 파일이고 여러 프로세스가 동시에 접근하면 순서에 따라 결과가 달라질 수 있습니다. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?상호 배제, 비선점, 점유와 대기, 원형 대기가 모두 충족이 되어야 하고 이 중 하나라도 충족하지 못하면 교착상태에 빠지지 않습니다.

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

1일차프로세스 동기화와 통신,재귀 프로세스 간 통신프로세스는 독립적으로 실행될 수도 있지만 다른 프로세스와 데이터를 주고받으며 통신하기도 합니다.통신 방식은 한 컴퓨터 내의 프로세스 간 통신과 네트워크를 통해 다른 컴퓨터의 프로세스와 통신하는 방법으로 나눌 수 있습니다. 프로세스 간 통신 방법파일(File) 이용통신하려는 프로세스들이 공통된 파일을 이용하여 데이터를 읽고 씁니다.파이프(Pipe) 이용운영체제가 생성한 파이프를 통해 데이터를 읽고 쓰는 방식입니다. 한 프로세스가 파이프에 데이터를 쓰면, 다른 프로세스가 이를 읽습니다. 쓰레드를 이용한 통신한 프로세스 내에서 쓰레드 간 통신 방법입니다.쓰레드는 코드, 데이터, 힙 영역을 공유하고, 각 쓰레드는 독립적인 스택을 가집니다. 따라서 공유된 데이터나 힙 영역을 통해 쓰레드 간 데이터를 주고받을 수 있습니다.네트워크를 이용한 통신소켓(Socket): 운영체제가 제공하는 소켓을 사용하여 네트워크 상의 다른 컴퓨터와 통신합니다.RPC(Remote Procedure Call, 원격 프로시저 호출): 네트워크를 통해 다른 컴퓨터의 프로세스에 있는 함수를 호출하는 방식입니다. 공유 자원과 임계 구역공유 자원프로세스 간 통신에서 공동으로 사용하는 변수나 파일 등을 공유 자원(Shared Resource) 이라고 합니다.공유 자원은 여러 프로세스가 동시에 접근할 경우, 접근 순서에 따라 결과가 달라질 수 있습니다.경쟁 조건 (Race Condition)여러 프로세스가 동시에 공유 자원에 접근하려고 경쟁하는 상황을 경쟁 조건이라 합니다.컨텍스트 스위칭(Context Switching)으로 인해 어떤 프로세스가 먼저 실행될지 예측하기 어렵습니다.따라서 여러 프로세스가 동시에 사용하면 안되는 영역을 정의했는데 이를 **임계구역이라 함**임계 구역 (Critical Section)여러 프로세스가 동시에 접근하면 안 되는 코드 영역을 임계 구역이라 합니다. 임계 구역 문제 해결 - 상호 배제 매커니즘(Mutual Exclusion)임계 구역 문제를 해결하려면 상호 배제 매커니즘이 필요합니다.주요 상호 배제 메커니즘뮤텍스(Mutex):상호 배제를 위한 동기화 도구로, 한 번에 하나의 프로세스 또는 스레드만 접근할 수 있도록 합니다.세마포어(Semaphore):공유 자원에 여러 프로세스가 동시에 접근하는 것을 방지하기 위한 동기화 도구입니다.모니터(Monitor):공유 자원과 해당 자원에 대한 연산을 묶어서 관리하는 동기화 도구입니다.상호 배제를 만족하기 위한 요구사항:상호 배제: 어떤 시점에도 하나의 프로세스만 임계 구역에 접근해야 합니다.진행 조건: 여러 프로세스가 임계 구역에 들어가기를 원하면, 하나의 프로세스만 선택되어야 합니다.유한 대기: 임계 구역에 들어간 프로세스는 최대한 빨리 종료해야 하며, 다른 프로세스가 무한정 기다리는 것을 방지해야 합니다. 프로세스 동기화 기법세마포어 (Semaphore)공유 자원에 여러 프로세스가 동시에 접근하는 것을 방지하기 위한 동기화 도구입니다.wait() 함수와 signal() 함수를 사용하여 자원 접근을 조절합니다.문제점: wait()와 signal()을 잘못 사용하면 **교착 상태(Deadlock)나 **경쟁 상태가 발생할 수 있습니다.**교착 상태 : 여러 프로세스가 서로 필요한 자원을 기다리면서 무한정 대기하는 상태입니다. 세마포어의 wait() 함수를 잘못 사용하면 교착 상태가 발생할 수 있습니다.**경쟁 상태 : 세마포어의 signal() 함수를 잘못 사용하면 여러 프로세스가 동시에 임계 구역에 접근하여 데이터 불일치 등의 문제가 발생할 수 있습니다. 세마포어의 사용 코드 예제(JAVA) public static void main(String[] args) throws InterruptedException { Semaphore semaphore = new Semaphore(1); semaphore.acquire(); // acqurie()는 wait()과 같은 역할을 담당 System.out.println("wait 실행"); semaphore.release(); // release()는 signal()과 같은 역할을 담당 System.out.println("signal 실행"); } 모니터 (Monitor)세마포어의 문제점을 보완한 상호 배제 매커니즘입니다.운영체제가 아닌 프로그래밍 언어 차원에서 제공하며, Java의 synchronized 키워드가 대표적입니다.synchronized 키워드가 붙은 메서드는 한 번에 하나의 쓰레드만 접근할 수 있습니다. 그럼 세마포어의 문제점을 보완한게 모니터니까 모니터를 사용하는게 가장 좋은건가??세마포어와 모니터: 세마포어는 개발자가 직접 'wait'과 'signal'을 조작해야 하기 떄문에 세밀한 관리가 가능하지만 호출 순서 및 위치를 잘못 설정하면 교착상태,경쟁조건이 생길 수 있어 복잡하고 세밀한 동기화를 사용하기 좋음모니터는 공유 자원에 접근하는 코드를 '모니터'라는 방 안에 넣으면 알아서 한 번에 한 명씩만 들어가도록 관리를 해줘 개발자는 안전하게 코드가 작성이 가능해 안전한 동기화에 좋지만 세마포어보다 오버헤드가 클 수 가있음모니터의 사용 코드 예제(JAVA) public static void main(String[] args) { Object lock = new Object(); // 락으로 사용할 객체 synchronized (lock) { // 락이 있을경우 해당 메서드에 진입해 실행 System.out.println("Inside synchronized block."); //실행문 종료 후 별다른 명령어 없이 자동으로 lock 반납 } } 뮤텍스 (Mutex)세마포어와 유사하지만, 뮤텍스는 오직 하나의 프로세스/스레드만 공유 자원에 접근하도록 제한합니다.잠금(lock)과 해제(unlock) 연산을 통해 임계 영역을 보호합니다.주로 하나의 공유 자원에 대한 접근을 순차적으로 처리해야 할 때 사용됩니다.뮤텍스는 잠금을 소유한 스레드만이 잠금을 해제할 수 있다는 특징이 있습니다.뮤텍스의 사용 코드 예제(JAVA) public static void main(String[] args) { ReentrantLock lock = new ReentrantLock(); lock.lock(); // lock 활성화 System.out.println("Lock acquired."); lock.unlock(); // lock 반납 System.out.println("Lock released."); }재귀 (Recursion)재귀란?어떤 것을 정의할 때 자기 자신을 참조하는 방식입니다.함수가 자기 자신을 호출하는 재귀 함수가 대표적인 예입니다.재귀 함수의 종료 조건재귀 함수에는 반드시 탈출 조건이 필요합니다.탈출 조건이 없으면 무한 재귀가 발생하며, **콜 스택(Call Stack)이 가득 차 프로그램이 비정상 종료됩니다.함수를 호출하면 해당 함수는 콜스택 위에 올라가고 함수가 종료되면 콜스택에서 제거됨**콜 스택 (Call Stack)함수 호출 기록을 저장하는 메모리 영역입니다.FILO(First In Last Out) 구조를 가지며, 마지막에 호출된 함수가 가장 먼저 종료됩니다. 재귀, 반복문반복문(for, while)으로 해결 가능한 문제를 재귀 함수로 구현하면 비효율적일 수 있습니다.재귀 함수는 함수를 호출할 때마다 새로운 **스택 프레임을 생성합니다. 이 스택 프레임에는 함수의 매개 변수지역 변수,반환 주소 등의 정보가 저장되어 코드만 실행하면 되는 반복문에 비해 함수 호출 및 스택 관리에 더 많은시간과 메모리를 소비해야함** 스택 프레임??프로그램 실행 중에 함수가 호출될 때 생성되는 메모리 블록으로 함수에 호출된 정보를 저장그러나 팩토리얼 계산등 문제의 구조 자체가 재귀적인 경우 재귀 함수가 유리합니다.// 반복문 int sum = 0; for (int i = 1; i 팩토리얼 예제(JAVA)public class FactorialExample { public static int factorial(int n) { if (n == 1) return 1; // 탈출 조건 return n * factorial(n - 1); } public static void main(String[] args) { System.out.println("5! = " + factorial(5)); // 120 출력 } }2일차프로세스 동기화와 통신,재귀 교착상태 (Deadlock)교착상태란?교착상태(Deadlock)는 여러 프로세스가 서로 다른 프로세스가 보유한 자원을 기다리며 무한히 대기하는 상태를 의미합니다. 이 상태에 빠지면 어떤 프로세스도 작업을 진행하지 못하게 됩니다.공유 자원: 프로세스들이 서로 공유하는 자원(예: 프린터, 메모리 등)이 있을 때 발생할 수 있음.독립 자원: 반대로, 공유하지 않는 자원만 사용한다면 교착상태는 발생하지 않음. 교착상태의 필요조건교착상태가 발생하기 위한 4가지 필요조건이 있으며, 이 중 하나라도 충족되지 않으면 교착상태가 발생하지 않습니다.상호 배제 (Mutual Exclusion)어떤 자원이 한 프로세스에 의해 점유되었다면, 그 자원은 다른 프로세스와 공유되지 않아야 함.비선점 (No Preemption)다른 프로세스가 점유한 자원을 강제로 빼앗을 수 없어야 함.점유와 대기 (Hold and Wait)어떤 프로세스가 자원을 점유한 상태에서 추가 자원을 기다려야 함.즉, 이미 할당된 자원을 보유하면서 다른 자원을 요청하고 대기하는 상태여야 합니다.원형 대기 (Circular Wait)점유와 대기 상태의 프로세스들이 원형으로 연결되어 있어야 함.예를 들어, 프로세스 A는 프로세스 B가 가진 자원을 기다리고, 프로세스 B는 프로세스 C가 가진 자원을 기다리고, 프로세스 C는 프로세스 A가 가진 자원을 기다리는 식입니다. 교착상태 해결 방법교착 상태는 여러 프로세스가 서로 필요한 자원을 기다리며 무한히 대기하는 상황을 의미합니다. 이러한 교착 상태를 해결하기 위한 다양한 방법 중 하나가 바로 **교착 상태 회피입니다.**교착 상태 회피란?시스템이 자원을 할당하기 전에 교착상태 가능성을 검사하고, 교착상태가 발생하지 않도록 자원을 할당.대표 알고리즘: **은행가 알고리즘 (Banker's Algorithm)** 은행가 알고리즘의 특징시스템은 프로세스들의 최대 요구 자원을 미리 알고 있어야 함.자원 할당 전에 시스템의 상태를 안정 상태(Safe State)와 불안정 상태(Unsafe State)로 구분안정 상태(Safe State): 교착상태에 빠지지 않을 수 있는 상태.불안정 상태(Unsafe State): 교착상태에 빠질 가능성이 있는 상태. (불안정 상태가 반드시 교착상태를 의미하진 않음)안정 상태의 예시시스템의 총 자원 14개P1: 최대 9개, 현재 5개 점유 → 추가로 4개 필요P2: 최대 6개, 현재 4개 점유 → 추가로 2개 필요P3: 최대 4개, 현재 3개 점유 → 추가로 1개 필요사용 가능한 자원: 2개자원 할당 순서P1은 4개를 요청하므로 거절.P2는 2개 요청 가능 → 작업 완료 후 6개 반납.P1은 이제 4개 요청 가능 → 작업 완료 후 자원 반납.불안정 상태의 예시시스템의 총 자원 10개P1: 최대 7개, 현재 5개 점유 → 추가로 2개 필요P2: 최대 5개, 현재 3개 점유 → 추가로 2개 필요P3: 최대 4개, 현재 2개 점유 → 추가로 2개 필요사용 가능한 자원: 1개자원 할당 상태P1, P2, P3 모두 추가 자원을 받기 위해 대기.사용 가능한 자원이 1개뿐이라 어느 프로세스도 필요한 자원을 다 받지 못함.세 프로세스가 서로 자원을 기다리며 무한 대기 상태 → 교착상태 발생 교착상태가 발생한지 알아내는 방법가벼운 교착상태 검출:타이머를 설정해 특정 시간 동안 프로세스가 작업을 하지 않으면 교착상태라고 판단.해결 방법 : 체크포인트를 통해 주기적으로 상태를 저장하고, 교착상태 발생 시 마지막 체크포인트로 롤백.간단하지만, 오탐지 가능성이 있고 롤백에 따른 오버헤드가 발생할 수 있습니다무거운 교착상태 검출:**자원 할당 그래프(Resource Allocation Graph, RAG)를 사용.프로세스-자원 관계를 그래프로 표현하고 사이클이 발견되면 교착상태로 간주.정확도가 높지만, 자원 할당 그래프를 관리하고 순환을 탐지하는 데 오버헤드가 발생합니다.오버헤드가 발생하지만, 프로세스를 강제로 종료하지 않고 교착상태를 해결 가능. **자원 할당 그래프자원할당 그래프의 사이클이 존재하는 지 그림으로 확인해당 그림처럼 프로세스와 자원 간의 사이클이 존재한다면 교착상태이고 해당 그림처럼 프로세스와 자원간의 사이클이 없으면 교착상태가 아니다하지만 사이클이 있어도 교착상태에 안걸리는 경우도 존재하는데P2와 P4가 작업을 완료하고 자원을 반납하면R1과 R2의 자원을 반납P1과 P3가 필요한 자원을 얻을 수 있음.원형 대기 상태가 깨지므로 교착상태가 해소됨. 재귀적으로 생각하기 패턴 1: 단순 반복의 재귀적 구현 (비효율적)반복문으로 간단하게 해결할 수 있는 문제를 재귀 함수로 구현하는 것은 일반적으로 비효율적입니다. 재귀 호출은 콜 스택 공간 사용을 발생시키므로 단순 반복 작업은 for 문을 사용하는 것이 좋습니다.// 반복문 (효율적) public static int sum1(int n) { int total = 0; for (int i = 1; i 패턴 2: 하위 문제 기반 문제 해결 (하향식 vs. 상향식)재귀는 하위 문제의 결과를 기반으로 현재 문제를 해결하는 데 특히 유용합니다. 대표적인 예가 팩토리얼 계산입니다.재귀함수를 이용한 팩토리얼 자바코드 예시public static int factorial(int n) { if (n == 0) { return 1; } return n * factorial(n - 1); }for문을 이용한 팩토리얼 자바코드 예시public static int factorial(int n) { int result = 1; for (int i = 1; i 재귀와 반복문재귀 함수는 상향식 계산도 가능하지만, 반복문으로 구현하는 것보다 성능이 좋지 않습니다.재귀 함수는 하향식 계산에서 위력을 발휘합니다. 특히 문제의 구조 자체가 재귀적인 경우 재귀 함수를 사용하면 코드를 간결하고 이해하기 쉽게 만들 수 있습니다. 재귀와 for문을 이용해 배열의 합 구현// 재귀 함수 public static int arraySum(int[] arr, int n) { if (n == 0) { return 0; } return arr[n - 1] + arraySum(arr, n - 1); } // 반복문 public static int arraySum(int[] arr) { int total = 0; for (int num : arr) { total += num; } return total; } 문자열 길이 계산 public static int strLength(String arr) { if (arr == null || arr.isEmpty()) { return 0; } return strLength(arr.substring(1)) + 1; } 지수 함수 하향식 구현public static int power(int x, int y) { if (y == 0) { return 1; } return x * power(x, y - 1); } 3일차컴파일과 프로세스, 재귀 - 하노이 탑 컴파일과 프로세스프로그래밍 언어의 종류프로그래밍 언어는 컴파일 언어와 인터프리터 언어로 구분할 수 있습니다.컴파일 언어개발자가 코드를 작성하고 컴파일이라는 과정을 거쳐 기계어(0과 1) 로 된 실행 파일을 생성합니다.컴파일 과정에서 문법 오류가 있는지 검사하고, CPU에서 실행할 수 있는 기계어로 변환합니다.미리 실행 파일을 만들어 놓으므로 실행 속도가 빠릅니다.예시: C, C++, C# 등인터프리터 언어개발자가 작성한 코드를 미리 기계어로 변환하지 않고, 실행 시점에 한 줄씩 해석하며 실행합니다.실행 전에 오류 검사를 하지 않기 때문에 실행 중 오류가 발생할 수 있으며, 속도도 컴파일 언어보다 느립니다.예시: JavaScript, Python 등 컴파일 언어로 작성된 파일이 프로세스가 되기까지C 언어로 작성된 test.c 파일이 실행 파일이 되고, 최종적으로 프로세스가 되는 과정1. 컴파일 과정전처리컴파일러가 실행되면 가장 먼저 전처리기가 동작합니다.전처리기는 #include, #define 등 전처리 구문을 처리합니다.주석 제거를 수행한 후 전처리된 코드를 .i 파일로 저장합니다.컴파일전처리된 코드를 기계어에 가까운 어셈블리어로 변환합니다.이 과정에서 문법 오류 체크도 함께 이루어집니다.결과물은 어셈블리 코드가 담긴 .s 파일입니다.어셈블어셈블리어를 기계어 코드(오브젝트 코드)로 변환합니다.생성된 오브젝트 파일은 .o 확장자를 가집니다.이 오브젝트 파일에는 코드 영역과 데이터 영역이 나눠져 있습니다.링커오브젝트 파일은 실행 파일이 되기 위해 링커(Linker) 를 거칩니다.링커는 여러 오브젝트 파일을 하나로 합치고, 코드 영역과 데이터 영역을 하나로 묶습니다. 결과물은 실행 파일(.exe)입니다. 2. 프로세스 생성 과정실행 파일이 프로세스가 되려면 다음 과정을 거칩니다프로그램 실행사용자가 .exe 파일을 실행합니다.운영체제가 프로세스를 생성합니다.메모리 할당운영체제는 실행 파일에 있는 코드 영역과 데이터 영역을 가져와 프로세스의 코드 영역과 데이터 영역에 로드합니다.그리고 빈 스택(Stack)과 힙(Heap) 영역도 할당합니다.PCB 생성운영체제는 PCB를 생성하여 프로세스를 관리합니다.PCB에는 프로세스 상태, 프로그램 카운터(PC), CPU 레지스터, 메모리 정보 등이 저장됩니다.프로그램 카운터 설정프로그램 카운터(PC) 는 다음 실행할 명령어의 주소를 가리킵니다.처음에는 코드 영역의 첫 번째 명령어의 주소를 가리킵니다.CPU 스케줄링운영체제의 CPU 스케줄러가 프로세스를 준비 상태에 놓고, CPU를 할당받으면 실행 상태로 전환되어 명령어가 실행됩니다. 재귀-하노이탑자바 코드 사용 예시 public static void hanoi(int count, String from, String to, String temp) { if (count == 0) { return; } hanoi(count - 1, from, temp, to); System.out.println(count + "를 " + from + "에서 " + to + "로 이동"); hanoi(count - 1, temp, to, from); } public static void main(String[] args) { hanoi(3, "A", "C", "B"); // 3은 옮겨야할 갯수 A는 시작위치 C는 도착해야할 위치 B는 거쳐갈 위치 }결과창4일차메모리 관리,버블정렬과 선택정렬 메모리의 종류레지스터가장 빠른 기억 장소로 CPU 내부에 존재합니다.컴퓨터의 전원이 꺼지면 데이터가 사라지므로 휘발성 메모리입니다.CPU의 32비트, 64비트는 레지스터 크기를 의미합니다.CPU는 연산 시 메인 메모리(RAM)에 있는 데이터를 레지스터로 가져와 계산하고, 결과를 다시 메인 메모리에 저장합니다. 캐시(Cache)레지스터와 메인 메모리 사이에 위치하여, 데이터 접근 속도를 향상시키는 역할을 합니다.CPU는 필요한 데이터를 메인 메모리에서 가져오기 전에 L1 캐시 → L2 캐시 → L3 캐시 순으로 확인합니다.캐시에 가져올 데이터가 없으면 메인 메모리에서 데이터를 가져옵니다. 메인 메모리(RAM) 실제 운영체제와 프로세스가 로드되는 공간입니다.휘발성 메모리로, 전원이 꺼지면 데이터가 사라집니다.속도는 HDD/SSD보다 빠르지만, 가격이 비싸기 때문에 실행 중인 프로그램만 저장합니다. HDD/SSD비휘발성 메모리로, 전원이 꺼져도 데이터가 보존됩니다.속도는 메인 메모리보다 느리지만, 가격이 저렴하여 데이터 저장 용도로 사용됩니다. 메모리 할당 방식메모리 오버레이:프로그램을 분할하여 필요한 부분만 메모리에 로드하고, 나머지는 스왑 영역에 저장합니다.스왑(Swap): 스왑영역에 있는 데이터를 메모리로 가져오고 메모리에 있는 데이터를 스왑영역으로 옮기는것을 말합니다.가변 분할 방식(Variable Partitioning)프로세스 크기에 따라 메모리를 연속된 공간에 동적으로 할당합니다.장점: 연속된 공간으로 할당하기 때문에 내부 단편화가 발생하지 않습니다.단점: 외부 단편화가 발생합니다.예시: 프로세스 A(50MB), B(30MB), C(15MB), D(10MB)가 메모리에 차례로 로드이후 A와 D가 종료되어 빈 공간(50MB + 10MB)이 생기고 새로운 프로세스 E(60MB)를 로드하려고 할 때 이 공간들은 연속되어 있지 않아 할당할 수 없는데 이를 외부 단편화라고 하며, 조각 모음을 통해 빈 공간들을 하나로 합쳐야 합니다. 이 과정은 메모리에 있는 프로세스를 일시 중지하고 공간을 이동시키는 작업이므로 오버헤드가 발생합니다. 고정 분할 방식(Fixed Partitioning)메모리를 고정 크기 블록으로 나눠 프로세스를 할당합니다.장점: 구현이 간단하고 오버헤드가 적습니다.단점: 프로세스 크기와 상관없이 고정된 크기로 메모리를 할당하므로 내부 단편화가 발생합니다.예시: 메모리를 2MB로 나눈다 가정할 때 프로세스 A(1MB), B(2MB), C(5MB)를 할당할 경우,A는 2MB 블록에 할당되어 1MB의 내부 단편화가 발생합니다. B는 2MB 블록에 할당되고 B는 2MB이기 때문에 정확히 떨어짐. C는 총 5MB이기 때문에 2MB 블록을 3개의 구역에 나눠서 저장해 1MB의 내부 단편화가 발생. 버디 시스템(Buddy System)가변 분할 방식과 고정 분할 방식을 혼합하여 단점을 보완합니다.메모리를 2의 제곱수 크기로 나누고, 필요할 때마다 나눠 프로세스를 할당합니다.장점: 외부 단편화를 방지하고, 메모리 합병(병합)이 간단합니다.단점: 약간의 내부 단편화가 발생할 수 있습니다. 그럼 메모리 할당 방식은 둘의 단점을 최소화한 버디 시스템이 최고인가??버디 시스템의 내부 단편화와 작은 크기의 블럭을 지나치게 나누면 생기는 메모리 관리 오버헤드가 커질수있어 최신 운영체제는 페이징 기법을 활용하거나, 세그멘테이션과 조합해서 사용페이징 기법 (Paging)정의:메인 메모리를 고정된 크기의 블록인**페이지 프레임(Page Frame)으로 나누고, 프로세스의 가상 메모리 공간도 동일한 크기의 **페이지(Page)로 나눕니다.프로세스의 페이지들은 메모리의 페이지 프레임에 비연속적으로 할당됩니다.페이지 프레임과 페이지란???페이지는 프로세스를 나눈 조각페이지 프레임은 메모리를 나눈 조각장점:외부 단편화가 발생하지 않습니다.메모리 관리가 단순해집니다.단점:내부 단편화가 발생할 수 있습니다. (마지막 페이지가 완전히 채워지지 않는 경우)예시:프로세스 A가 5KB이고, 페이지 크기가 2KB라면, A는 3개의 페이지로 나뉩니다.마지막 페이지는 1KB만 사용되고 1KB는 낭비되므로 내부 단편화가 발생합니다.추가 설명: 페이지 테이블을 사용하여 가상 주소를 물리 주소로 변환합니다.고정 분할 방식과 페이징 기법은 비슷하지만 고정 분할 방식은 메모리를 나눈 후 프로세스를 맞춰 넣는 방식이고,페이징은 프로세스를 나눈 후 메모리에 퍼즐처럼 넣는 방식 세그멘테이션 (Segmentation)정의:프로세스를 논리적인 의미 단위인 세그먼트(Segment)로 나누어 메모리에 로드합니다.세그먼트의 크기는 가변적입니다.장점:논리적으로 관련된 코드나 데이터가 한 곳에 모이므로 효율적입니다.프로그램의 구조를 반영하여 메모리를 관리할 수 있습니다.단점:외부 단편화가 발생할 수 있습니다.예시:프로그램이 코드(10KB), 데이터(5KB), 스택(8KB)으로 나뉜 경우, 각 부분이 독립적인 세그먼트로 관리됩니다.추가 설명:세그먼테이션은 프로그램의 논리적인 구조를 반영하여 메모리를 관리하는 데 유용합니다.최근에는 페이징과 함께 사용되어 메모리 보호 및 공유 기능을 강화합니다.요약:페이징은 메모리를 고정 크기로 나누어 관리하고, 세그멘테이션은 논리적인 단위로 나누어 관리합니다.페이징은 외부 단편화를 해결하고, 세그멘테이션은 프로그램의 논리적인 구조를 반영합니다.. 페이징 + 세그먼테이션을 사용하면 내부/외부 단편화가 완전히 사라지는 것은 아니지만, 각각의 단점을 최소화할 수 있습니다. 버블 정렬과 선택 정렬정렬 알고리즘은 데이터를 특정 순서로 나열하는 방법을 정의버블 정렬과 선택 정렬은 가장 기본적인 정렬 알고리즘으로 이해와 구현이 쉽지만 성능은 다소 아쉬움1. 버블 정렬 (Bubble Sort)원리:인접한 두 원소를 비교하여 순서가 맞지 않으면 교환하는 과정을 반복합니다. 예시:[4, 2, 3, 1] 배열을 정렬하는 과정:[2, 4, 3, 1] (4와 2 교환)[2, 3, 4, 1] (4와 3 교환)[2, 3, 1, 4] (4와 1 교환)위 과정을 반복하여 [1, 2, 3, 4] 완성성능:시간 복잡도: O(n²) - 데이터가 많아질수록 비교 횟수가 제곱으로 증가합니다.장단점:장점: 이해와 구현이 매우 쉽습니다.단점: 성능이 좋지 않아 대규모 데이터 처리에는 부적합합니다. 자바코드로 예시 구현 public static void bubble(int[] arr) { int n = arr.length; for (int i = 0; i arr[j + 1]) { // arr[j]번쨰 값이 arr[j]다음의 값보다 크다면 int temp = arr[j]; // 현재 arr[j]번째의 값을 저장해두고 arr[j] = arr[j + 1]; // arr[j]의 값을 arr[j] 다음의값으로 변경 arr[j + 1] = temp;// arr[j] 다음의값을 이전에 temp에 저장해둔 arr[j]값으로 변경 } } } } public static void main(String[] args) { int[] arr = {4, 2, 3, 1}; bubble(arr); for (int num : arr) { System.out.print(num + " "); } } 2. 선택 정렬 (Selection Sort)원리:배열에서 가장 작은 원소를 찾아 첫 번째 위치로 이동시키고, 다음으로 작은 원소를 찾아 두 번째 위치로 이동시키는 과정을 반복합니다.정렬되지 않은 부분에서 최소값을 선택하여 정렬된 부분의 마지막 위치로 이동시킵니다.예시:[4, 2, 1, 3] 배열을 정렬하는 과정:[1, 2, 4, 3] (최소값 1을 첫 번째 위치로 이동 기존에 있던 4는 1이있던 자리로 이동)[1, 2, 4, 3] (다음 최소값 2는 이미 정렬된 위치)[1, 2, 3, 4] (다음 최소값 3을 세 번째 위치로 이동)성능:시간 복잡도: O(n²) - 버블 정렬과 마찬가지로 성능이 좋지 않습니다.장단점:장점: 버블 정렬과 마찬가지로 이해와 구현이 쉽습니다.단점: 성능이 좋지 않아 대규모 데이터 처리에는 부적합합니다. 자바코드로 예시 구현 public static void selection(int[] arr) { for (int i = 0; i 정리버블 정렬과 선택 정렬은 기본적이지만 비효율적인 정렬 알고리즘입니다. 2주차 회고 잘한 점저번주에 다짐했던 그날그날 강의를 듣고 정리하는건 잘지켰고 확실히 그날 배운 내용을 바로바로 정리하니 저번주보다 죽은지식이 덜했습니다.저번주는 몰아서 정리하다보니 아 이거 뭐였지 하며 다시 찾아보고 하는 경우가 많았는데 현저히 줄어든게 느껴졌습니다. 아쉬운 점운영체제는 역시 여전히 어려웠습니다.아무래도 강의가 기본으로 쉽게 이해하려는데 초점이 맞춰져있다보니 아주 쉽게 동작원리를 알려주다보니 하나의 내용을 던져주고 궁금해서 그걸 가지고 파다보면 끝도없는 용어와 또 다른 내용이 튀어나와 역시 쉽지않았습니다.자료구조와 알고리즘은 재귀 버블정렬 등 해당 알고리즘의 개념을 이해만 한다면 코드로 녹여내는건 생각보다 어렵지않았고 오히려 정말 재밌게 공부했었습니다.이무래도 코드를 작성하면 시각적으로 결과가 바로바로 보여지다보니 좀더 흥미를 느꼈던거같습니다. 개선할 점이제 다음주가 마지막 주차인데 이번주 보다 공부 시간을 좀 더 늘리겠습니다. 목표이번주 역시 로드맵에 맞게 해당 강의 영상을 듣고 바로바로 발자국으로 내용 정리하기2주차에 투자한 공부시간보다 더 늘리기질문 더 많이하기