인프런 워밍업 클럽 CS 3기 3주차 발자국
강의 내용 요약운영체제가상 메모리1. 가상 메모리가상 메모리는 물리적 메모리(RAM)의 크기가 부족한 경우에 대한 해결책가상 메모리의 크기는 물리 메모리의 크기와 CPU의 비트수에 따라 결정32bit CPU → 2^32(약 4GB)64bit CPU → 2^64 2. 가상 메모리를 이용한 여러 프로세스 실행물리 메모리 내용의 일부를 하드 디스크 내의 스왑 영역에 보관처리가 필요할 때 메인 메모리에 가져와서 실행 동적 주소 변환메모리 관리자는 물리 메모리(RAM)와 스왑 영역을 합쳐서 프로세스가 사용하는 가상주소를 물리주소로 변환이를 동적주소변환(Dynamic Address Translation)이라 부름동적 주소 변환을 거치면 사용자 데이터를 물리 메모리에 배치 가능메모리 관리자의 임무물리 메모리를 어떻게 나눌지프로세스를 메모리의 어디에 배치할지부족한 물리 메모리는 어떻게 처리할지가상 메모리 시스템에서 메모리를 관리하는 방식운영체제 영역을 제외한 나머지 영역을 일정한 크기로 나누어서 프로세스에게 할당메모리 분할 방식과 마찬가지로 가변 분할 방식(세그멘테이션)과 고정 분할 방식(페이징)을 사용각각 외부 단편화와 내부 단편화 문제가 있으므로 둘을 혼합한 방식인 세그멘테이션-페이징 혼용기법을 사용 가상주소와 물리주소의 매핑메모리 관리자는 가상주소와 물리주소를 일대일 매핑 테이블로 관리 3. 세그멘테이션 기법가변 분할 방식을 이용하는 기법프로그램(사용자) 관점의 메모리: 각 세그먼트는 인접할 필요가 없음프로세스 관점의 메모리: 각 세그먼트 영역이 서로 인접한 것처럼 바라봄 논리주소와 물리주소, 메모리 관리자논리주소 : 사용자, 프로세스, CPU 입장에서의 주소물리주소 : 실제 메모리 내의 주소논리주소와 물리주소의 변환은 메모리 관리자(MMU)가 처리 메모리 관리자는 세그멘테이션 테이블에 대한 정보를 가지고 있음세그멘테이션 테이블 자체는 메인 메모리에 저장세그멘테이션 테이블에는 Base Address와 Bound Address가 저장되고 이를 이용하여 물리 메모리 주소를 계산 세그멘테이션을 이용한 주소 변환 과정CPU에서 논리주소 전달 → 메모리 관리자는 해당 논리주소의 세그먼트 번호를 알아냄 → 메모리 관리자 내의 Segment Table Base Register(STBR)를 이용하여 물리 메모리 내에 있는 세그멘테이션 테이블을 찾음 → 세그먼트 번호를 인덱스로 Base Address와 Bound Address를 찾음 Bound Address는 세그먼트의 크기를 나타냄메모리 관리자는 CPU에서 받은 논리주소와 Bound Address를 비교하여 논리주소 < Bound Adrress라면 논리주소 + Base Adress하여 물리주소를 구하고 논리주소 > Bound Adrress라면 메모리 침범으로 인식하여 해당 프로세스 종료 세그멘테이션의 장/단점장점메모리를 가변적으로 분할 가능코드, 데이터, 스택, 힙 영역을 모듈로 처리할 수 있어 공유 및 메모리 접근 보호가 편리단점가변 분할 방식의 단점인 “외부 단편화”가 발생 4. 페이징 기법고정 분할 방식을 이용하는 기법 논리주소공간사용자와 프로세스가 바라보는 주소공간페이지 → 논리주소공간을 일정한 크기로 나눈 것물리주소공간실제 메모리에서 사용되는 주소공간프레임 → 물리주소공간을 페이지의 크기와 동일하게 나눈 것 페이징을 이용한 주소변환 과정CPU에서 논리주소 전달 → 메모리 관리자는 이 논리주소의 페이지 번호, 오프셋을 알아냄 → 메모리 관리자 내의 Page Table Base Register(PTBR)를 이용하여 물리 메모리 내에 있는 페이지 테이블을 찾아냄 → 페이지 번호를 인덱스로 프레임 번호를 알아냄 → 오프셋을 이용해 물리주소로 변환(프레임이 invalid라면 스왑영역에 있음) 5. 세그멘테이션 vs 페이징세그멘테이션은 프로세스마다 크기가 달라 Bound Address를 가짐페이징은 모든 페이지의 크기가 동일하여 크기를 표현하는 Bound Address가 필요하지 않음세그멘테이션은 세그먼트마다 크기를 다르게 나눌 수 있기 때문에 논리적인 영역별로 세그먼트를 나눌 수 있는 반면, 페이징은 페이지의 크기가 고정되어 있어 논리적인 영역을 나눌 수 없음 페이지 테이블에서 가장 신경써야 하는 것은 페이지 테이블 크기프로세스가 많아질 수록 페이지 테이블의 개수도 많아짐메모리 관리자가 참조하는 페이지 테이블도 물리 메모리의 운영체제 영역에 저장되어 있음따라서 페이지 테이블의 크기가 너무 크면 사용자 영역이 부족해짐 6. 페이지드 세그멘테이션세그멘테이션과 페이징을 혼합하여 장점을 취한 방식 메모리 접근 권한메모리의 특정 번지에 부여된 권한읽기(Read),쓰기(Write),실행(Execute) 3가지 존재프로세스의 각 영역마다 접근 권한이 존재메모리 접근 권한에 대한 검사는 가상주소에서 물리주소로 변환될 때마다 발생 페이지드 세그멘테이션기존 세그먼테이션 테이블에서 변화한 점권한비트 추가Base address → 페이지 넘버Bound address → 페이지 개수페이지 넘버와 페이지 개수는 이름만 달라졌을 뿐 수행 역할은 거의 동일 페이지드 세그멘테이션 과정가상주소가 들어오면 가상주소를 이용해 세그먼트 번호를 알아냄 → 해당 세그먼트가 메모리 접근 권한을 위반하는 검사 (접근 권한 위반 시 프로세스를 종료시킴) → 페이지 넘버와 페이지 개수를 가져옴 (페이지 개수를 통해 메모리 침범 검사) → 페이지 넘버를 통해 페이지 테이블에 접근하여 프레임 번호를 가져옴 → 물리 메모리내의 해당 프레임에 접근하여 그 위치에서 페이지 개수를 더해 물리주소를 구함 (물리 메모리에 해당 프레임이 없다면 스왑 영역에서 물리 메모리로 가져옴) 페이지드 세그멘테이션의 단점물리 메모리 접근을 위해 메모리에 2번 접근해야 함세그멘테이션 테이블 참조 (1번) + 페이지 테이블 참조(1번) = 2번이러한 단점이 있어 현대 운영체제는 페이징과 페이지드 세그멘테이션 기법을 적절히 섞어서 사용함 7. 디멘드 페이징지역성 이론과 디멘드 페이징지역성 이론: 조만간 쓰일 데이터만 메모리에 올리고 당분간 필요하지 않을 것 같은 데이터는 스왑 영역으로 보내 성능을 향상시킴공간의 지역성: 현재 위치와 가까운 데이터에 접근할 확률이 높음시간의 지역성: 최근 접근했던 데이터가 오래 전에 접근했던 데이터보다 접근할 확률이 높음 디멘드 페이징 ← 지역성 이론을 구현한 정책디멘드 페이징의 목적은 스왑 영역으로 데이터를 이동시키는 것을 최소화시키는 것스왑인 : 스왑영역에서 물리 메모리로 데이터를 가져오는 것스왑아웃: 물리 메모리에서 스왑영역으로 데이터를 보내는 것 페이지 테이블 엔트리페이지 테이블은 데이터가 물리 메모리, 스왑영역 중 어디에 위치해있는지 알아내기 위해 인덱스, 프레임 외에도 여러 비트가 존재페이지 테이블 엔트리(PTE) → 페이지 테이블을 이루는 하나의 행 접근 비트페이지가 메모리에 올라온 후 데이터에 접근이 있었는지 알려주는 비트메모리에 읽기나 실행 작업을 했다면 1로 바뀜 변경비트페이지가 메모리에 올라온 후 데이터의 변경이 있었는지 알려주는 비트메모리에 쓰기 작업을 했다면 1로 바뀜 유효비트페이지가 물리 메모리에 있는지 알려주는 비트유효비트가 1 → 페이지가 스왑영역에 있음유효비트가 0 → 페이지가 물리메모리에 있음 읽기/쓰기/실행 비트권한비트해당 메모리에 접근권한이 있는지 검사하는 비트 디멘드 페이징 과정전체적인 과정프로세스가 가상 메모리에 접근요청→ 메모리 관리자는 페이지 테이블을 보고 물리 메모리의 프레임을 찾아냄→ 만약, 물리 메모리에 없다면 Page Fault라는 인터럽트를 발생 시킴→ Page Fault가 발생 시 보조저장장치의 스왑영역에 접근, 해당 프로세스는 대기상태가 됨→ 스왑 영역의 데이터가 메모리로 올라감→ 메모리로 올라가면 대기상태의 프로세스가 다시 실행 8. 페이지 교체 정책Page Fault가 발생했을 때 메모리에 빈 공간이 없다면 메모리에 있는 페이지 중 어떤 페이지를 스왑영역으로 옮길 지 결정하는 방법 Random무작위로 선택해서 교체하는 방법지역성을 고려하지 않으므로 자주 사용되는 페이지가 선택될 수도 있어 성능이 좋지 않음 FIFO(First In First Out)가장 먼저 메모리에 들어온 페이지를 선택하는 방법자주 쓰이는 페이지가 먼저 들어왔다는 이유로 교체될 수도 있음구현이 간단하고 성능도 준수하기에 FIFO 정책을 변형하여 많이 사용 Optimum앞으로 가장 오랫동안 쓰이지 않을 페이지를 선택하는 방법사실상 구현이 불가능한 이론적 방법알고리즘 성능 비교 시 참조용으로 사용 LRU(Least Recently Used)최근 가장 사용이 적은 페이지를 선택하는 방법시간 지역성(최근 접근했던 데이터가 접근할 확률이 높음)에 근거한 방식Optimum 알고리즘에 근접한 성능을 보임프로그램이 지역성을 가지지 않을 때는 성능이 떨어짐페이지 테이블 엔트리에 시간 정보를 저장하기 위해서는 많은 비트가 필요실제 LRU를 구현할 때는 접근 비트를 이용하여 LRU에 근접하게 구현 빌레이디의 역설Page Fault를 줄이려고 프레임 수를 늘렸는데 오히려 Page Fault가 더 많이 발생하는 현상FIFO에서만 발생하고 LRU에서는 발생하지 않음 클락 알고리즘(Clock Algorithm)LRU와 유사하게 구현하는 방법클락 알고리즘은 접근비트 하나만 이용일정 시간 간격마다 모든 페이지의 접근비트를 0으로 초기화접근비트의 초기값은 0으로 설정되며 페이지 참조 시 1로 수정페이지를 원형으로 연결하고 스왑영역으로 옮길 페이지를 포인터로 가리키는데 이를 클락 핸드라고 부름클락 핸드는 시계 방향으로 돌며 Page Fault가 발생하여 스왑영역으로 보내야하는 상황이 나오면 클락 핸드는 현재 참조하고 있는 페이지의 접근비트를 봄접근비트가 1이면 0으로 바꾸고 다음 페이지를 가리킴접근비트가 0이면 해당 페이지를 스왑영역으로 보냄 향상된 클락 알고리즘(Enhanced Clock Algorithm)접근 비트와 변경 비트 모두 이용 스왑 영역으로 보내지는 순위접근 비트 0, 변경 비트 0 > 접근 비트 0, 변경 비트 1 > 접근 비트 1, 변경 비트 0 > 접근 비트 1, 변경 비트 1 2차 기회 페이지 교체 알고리즘FIFO 방식을 개선한 방식자주 사용되는 페이지에게 또 한번의 기회를 주는 방식Page Fault 없이 페이지 접근에 성공했다면 해당 페이지를 큐의 맨 뒤로 이동시켜 수명을 연장시키는 방법FIFO 보다는 성능이 좋지만 LRU보다는 성능이 좋지 않음 스레싱(Thrashing)CPU 사용률을 올리기 위해 멀티프로그래밍의 정도를 올렸지만 CPU가 작업하는 시간보다 스왑작업의 시간이 더 길어져 CPU 사용률이 0%에 가까워 지는 것 스레싱의 해결책하드웨어적인 방법 → 물리 메모리의 크기를 늘리는 것소프트웨어적인 방법 → 워킹셋과 적절한 페이지 수 할당 적절한 페이지 수 할당프로세스가 실행되면 일정량의 페이지 할당Page Fault 발생 시 더 많은 페이지 할당해당 프로세스에서 Page Fault가 매우 적게 발생하면 메모리 낭비라 판단하여 페이지 회수이 절차를 반복하면 해당 프로세스에 맞는 적절한 페이지 수가 결정됨 워킹셋지역성 이론에 따라 현재 메모리에 올라온 페이지들을 하나의 셋트로 묶어서 실행하는 방법프로세스가 준비상태에서 실행상태가 되는 컨텍스트 스위칭을 할 때 사용됨 주변 장치1. 주변 장치 개요주변장치 내부 구조주변 장치들은 메인보드에 있는 버스로 연결됨하나의 버스는 Address 버스, Data 버스, Control 버스로 이루어져 있음 주변 장치들은 메인보드에 있는 버스로 연결됨하나의 버스는 Address 버스, Data 버스, Control 버스로 이루어져 있음 주변 장치의 구성 요소외부 인터페이스버스 인터페이스레지스터장치의 상태와 데이터를 보관입출력 작업 시 데이터를 저장하는 역할레지스터의 값들은 CPU가 사용하기 위해 메모리로 이동되기도 함컨트롤러로직주변 장치의 종류캐릭터 디바이스데이터 전송 단위가 캐릭터(글자)로 상대적으로 크기가 작음마우스, 키보드, 사운드카드, 직렬/병렬 포트 등이 포함블록 디바이스데이터 전송 단위가 블록(범위)로 상대적으로 크기가 큼SSD, HDD, 그래픽 카드 등이 포함 CPU와 주변 장치 간의 전체적 구조CPU는 I/O 명령을 만나면 입출력 제어기에게 입출력 작업을 맡기고 다른 작업을 수행입출력 제어기는 시스템 버스와 입출력 버스로 구분함시스템 버스 → 고속으로 작동하는 CPU와 메모리가 사용입출력 버스 → 주변장치가 사용느린 장치와 빠른 장치를 구분하여 속도 병목 현상을 해결하기 위해 고속 입출력 버스와 저속 입출력 버스로 나뉨그래픽 카드가 다루는 데이터는 매우 대용량이라 시스템 버스를 이용입출력 제어기가 메모리에 접근하기 위해서는 CPU가 필요한 문제가 있었음. 이를 해결하기 위해 DMA(Direct Memory Access) 제어기를 추가하였고 DMA 제어기를 통해 데이터를 직접 메모리에 저장 및 가져올 수 있음Memory Mapped I/O → CPU와 DMA가 사용하는 메모리가 겹치지 않도록 구분하게 하는 것 2. 마우스/키보드마우스DSP(Digital Signal Processor)가 마우스 움직임 혹은 클릭 같은 데이터 감지→ 디바이스 컨트롤러가 CPU에게 인터럽트를 보냄→ 마우스 드라이버가 동작하여 데이터를 읽어감→ 마우스 드라이버가 운영체제에게 이벤트 신호를 줌→ 운영체제는 이벤트를 Foreground 애플리케이션으로 전달→ 애플리케이션에서 받은 마우스 이벤트 처리 키보드키보드의 디바이스 컨트롤러가 어떤 키를 입력 받았는지 알아냄→ CPU에게 인터럽트→ 키보드 드라이버가 운영체제에게 이벤트를 보냄→ 운영체제는 Foreground 애플리케이션으로 이벤트 전달→ 애플리케이션에서 그에 맞는 키보드 이벤트 처리 3. 하드디스크와 플래쉬 메모리하드디스크스핀들: 하드디스크의 달린 막대플래터: 자기화된 원판으로 이루어짐디스크암: 읽기/쓰기 헤드로 플래터의 표면을 읽음플래터는 여러 개의 트랙으로 구성되어 있음플래터 표면에는 자성이 있기 때문에 N극을 띠면 0, S극을 띠면 1로 인식헤드는 디스크암에 고정되어 있으므로 모든 헤드는 항상 같이 움직임실린더: 여러 개의 플래터에 있는 같은 트랙의 집합섹터: 하드디스크의 가장 작은 단위, 여러 섹터가 모여 트랙을 이룸 하드 디스크에서 데이터를 읽어오는 예시실린더 C로 가서 트랙 B에 있는 섹터 D를 읽어라Seek: 헤드를 특정 실린더로 이동시키는 것Seek time: 헤드를 특정 실린더로 이동시키는 데 걸리는 시간 (ms 단위)실린더 C까지 이동했으면 트랙 B의 섹터 D가 헤드에 닿을 때까지 스핀들을 회전시킴헤드에 섹터 D가 읽히면 작업이 끝남 플래쉬 메모리장점크기가 HDD에 비해 작음Flash Memory는 전기적으로 읽기 때문에 굉장히 빠르고 조용자기성을 띄는 HDD에 비해 안전함충격에 강함단점데이터 덮어쓰기 불가능데이터를 지우기 가능한 횟수가 정해짐 파일시스템1. 파일시스템파일시스템 → 운영체제가 파일을 관리하기 위해 만든 관리자가상 메모리의 메모리 관리자와 하는 일이 비슷함파일시스템은 파일 테이블을 이용하여 파일을 관리 파일시스템의 기능파일과 디렉토리 생성파일과 디렉토리 수정/삭제파일 권한 관리무결성 보장백업과 복구암호화 저장장치의 전송단위는 블록이지만 사용자는 바이트 단위로 접근이 필요함. 이를 파일 관리자가 중간에서 관리해줌 파일의 구조파일은 헤더와 데이터로 구성헤더 → 파일의 속성(파일 이름, 식별자, 유형 등)들이 담겨져있음 파일 디스크립터File Descriptor (File Control Block)파일을 관리하기 위해 정보를 보관하는 곳파일 디스크립터는 파일마다 독립적으로 존재저장장치에 존재하다가 파일이 오픈되면 메모리로 이동파일시스템(운영체제)이 관리, 사용자가 직접 참조 불가능 파일의 종류순차파일구조파일의 내용이 연속적으로 이어진 형태모든 데이터가 순서대로 기록되기 때문에 공간의 낭비가 없고 구조가 단순특정 지점으로 바로 이동이 어려움(삽입/삭제 시 탐색 시간이 걸림) 직접파일구조저장하려는 데이터의 저장 위치를 해시 함수를 통해 결정하는 파일구조자료구조의 Hash Table 구조와 같음해시 함수를 이용하기 때문에 데이터 접근이 굉장히 빠름해시 함수의 선정이 굉장히 중요저장공간이 낭비될 수 있음 인덱스 파일구조순차접근과 직접접근 방식의 장점을 취한 방식으로 2가지 방식 모두 가능기본적인 접근은 순차적으로 접근특정 위치를 선택하면 인덱스 테이블의 인덱스에 접근해 블록 번호를 알아내고 순차 데이터의 해당 블록 번호로 이동하여 접근 가능 2. 디렉토리관련 있는 파일들을 하나로 모아둘 수 있는 구조디렉토리는 1개 이상의 파일을 가질 수 있고 자식 디렉토리도 가질 수 있음루트 디렉토리 → 가장 최상위에 있는 디렉토리 디렉토리와 파일은 다른 구조가 아님일반 파일에는 데이터가 저장되어 있음디렉토리에는 해당 디렉토리 내의 파일 정보가 저장되어 있음 디렉토리 구조초기 파일 시스템의 경우 루트 디렉토리에서만 하위 디렉토리를 생성할 수 있었고 그 외의 디렉토리에서는 생성할 수 없는 단순한 구조였음파일이 많아지며 관리의 불편함이 생겨 다단계 디렉토리 구조가 등장다단계 디렉토리어떠한 디렉토리에서도 하위 디렉토리를 만들 수 있는 트리구조현대의 운영체제는 트리구조에서 순환이 생김ex)윈도우/맥 의 바로가기 아이콘 3. 파일과 디스크파일 시스템은 메모리와 비슷함페이징과 같이 전체 디스크 공간을 일정한 크기로 나누고 그 공간에 주소를 할당하여 관리일정한 크기로 나눈 공간을 파일시스템에서는 블록이라 부름한 블록의 크기는 1~8KB정도 파일시스템은 파일정보를 파일테이블로 관리파일테이블에는 파일이 시작하는 블록의 위치정보가 담겨있음 하나의 파일은 여러 개의 블록으로 구성되어 있으며 연결하는 방식에 따라 연속할당, 불연속할당으로 나눌 수 있음 연속 할당파일을 구성하는 블록들을 디스크에 연속적으로 저장하는 방식파일의 시작 블록만 알면 파일 전체를 찾을 수 있음외부 단편화가 발생하기 때문에 실제로는 사용되지 않음 불연속 할당디스크의 비어있는 공간에 데이터를 분산해 저장하는 방식분산된 블록은 파일 시스템이 관리불연속 할당의 방식은 연결 할당, 인덱스 할당이 존재 연결 할당파일에 속한 데이터를 연결리스트로 관리파일테이블에는 시작 블록에 대한 정보만 저장하고 나머지는 연결리스트를 이용해 다른 블록에 접근하는 방식 인덱스 할당테이블의 블록 포인터가 데이터 블록에 직접 연결하는 것이 아닌 데이터들의 인덱스를 가지고 있는 인덱스 블록을 연결인덱스 블록에 있는 참조하면 모든 데이터를 찾을 수 있음데이터가 많아 테이블이 꽉 찬 경우, 인덱스 블록을 더 만들어 연결하는 방식이기 때문에 테이블 공간을 확보할 수 있음 파일의 크기가 작음 → 블록 포인터를 이용파일의 크기가 큼 → 간접 포인터를 이용이 방식은 리눅스 및 유닉스에서 i-node라는 이름으로 사용되고 있음 파일 시스템에서 빈 공간을 관리하는 전략디스크에 파일을 저장할 때마다 빈 공간을 찾기 위해 모든 공간을 뒤지는 방식은 매우 비효율적파일시스템은 효율적인 관리를 위해 빈 공간을 모아둔 free block list를 가지고 있음특정 파일 삭제 시, 파일시스템은 모든 정보를 지우는 것이 아니라 파일의 헤더만을 삭제하고 free block list에 추가사용자는 파일이 삭제된 것처럼 느끼지만, 사용했던 블록의 데이터는 그대로 남아있기 때문에 포렌식을 통해 데이터 복구가 가능 자료구조1. 삽입 정렬(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^2) 장/단점장점: 구현이 간단, 데이터가 거의 정렬된 경우 최적의 성능을 보임단점: 역순 배열이면 최악의 성능을 보임, 큰 배열에서는 성능이 떨어짐 2. 병합 정렬(Merge Sort)재귀적으로 정렬하는 알고리즘분할 정복 알고리즘에 속함배열들의 데이터를 최소한을 쪼갠 후 각 단계 별로 병합을 하면서 정렬을 진행하는 방식 데이터를 반으로 나누어 분할.각각을 정렬한 후 병합하며 정렬.두 개의 데이터가 하나로 합쳐질 때 비교 연산이 두 번 발생.네 개의 데이터가 두 개로 병합될 때 비교 연산이 네 번 발생.단계마다 영역의 수가 반으로 줄어들기 때문에 O(log n)의 성능을 가짐.병합할 때 n개의 데이터를 비교하므로 전체 시간 복잡도는 O(n log n). 병합 정렬의 성능시간 복잡도 : O(n log n) 장/단점장점: 성능이 좋음단점: 이해와 구현이 어려움. 메모리 공간이 추가적으로 필요 3. 퀵 정렬(Quick Sort)분할 정복(Divide and Conquer) 알고리즘정렬 전에 배열에서 하나의 원소를 피벗(Pivot)으로 선택.피벗을 기준으로 작은 값과 큰 값으로 나누어 재귀적으로 정렬 수행. 퀵 정렬의 성능평균 : O(n log n)최악: O(n^2) -> 피벗이 한 쪽으로 지나치게 치우친 경우퀵 정렬은 최악의 피벗을 선택할 확률이 매우 낮아 병합 정렬에 비해 안정적인 성능을 보장병합 정렬에 비해 더 적은 비교와 더 적은 메모리 공간을 사용하기에 효율적 4. 동적 프로그래밍 - 메모이제이션(Memoization)재귀 사용 시 콜 스택 영역 차지 이외에도 같은 계산을 반복해서 수행하는 단점 존재이에 대한 해결책으로 동적 프로그래밍의 메모이제이션(Memoization)을 사용메모이제이션이미 계산된 값을 메모(캐싱)하여 재사용하는 방법.주로 재귀 함수에서 중복되는 연산을 방지하기 위해 많이 사용재귀를 이용하는 하향식(Top-down) 방식 메모이제이션을 통한 피보나치 수열 최적화시간 복잡도: 중복 계산을 방지하여 O(n^2) -> O(n)으로 줄일 수 있음장점재귀 함수 이용 시 성능 향상중복 계산 방지단점메모리 사용량 증가(계산한 값을 메모(캐싱)해야 하기 때문) 5. 동적 프로그래밍 - 타뷸레이션(Tabulation)하위 문제부터 해결하는 상향식 접근 방법. 반복문을 사용메모이제이션과 원리는 같음 (중복될 것 같은 값을 저장했다가 필요하면 계산이 아니라 값을 가져다 쓰기)장점재귀 호출을 이용하지 않아 과도한 콜 스택 호출로 인한 메모리 걱정이 없음단점가장 최하단의 하위 문제들에 대한 계산이 필요. 불필요한 계산이 발생할 수도 있음 메모이제이션과 타뷸레이션 중 어떤 것을 사용해야 할까?문제에 따라 다르지만눈에 보이는 재귀 or 분할 정복으로 풀기 쉬움 -> 메모이제이션(Memoization)복잡한 재귀 or 메모리 사용량이 중요함 -> 타뷸레이션(Tabulation) 일주일 간의 회고🍷칭찬하고 싶은 점강의를 1회독 완주한 점멘토님과 적극적으로 소통하려고 노력한 점😅아쉬웠던 점전공 시간에 이미 한 번 배웠던 것들인데 아직 완전한 내 것이 아닌 점이 아쉽네요... 좀 더 분발!🛠보완하고 싶은 점워밍업 클럽이 끝나고 운영체제, 자료구조와 알고리즘 강의를 개인 노션에 정리한 내용을 보면서 다시 정주행 돌릴 예정인데 그 때는 정리에 급급하기 보다는 차분하게 시간을 들여 내 것으로 만들도록 노력해야겠습니다.강의 재생 도중에 궁금한 점이 있으면 당장 찾아보는 것이 아니라 일단 다 듣고 찾아보기공부 흐름 끊어먹지 않고 온전히 집중하기
_K-Devcon 9월 치맥_배너.png?w=560)
