인프런 워밍업 클럽 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]

1. 정렬된 영역: [4], 삽입할 값: 1 → [1, 4, 5, 3, 6, 2]

2. 다음 값 5는 4보다 크므로 그대로

3. 3은 5보다 작아, 5와 4를 오른쪽으로 밀고 → [1, 3, 4, 5, 6, 2]

4. 반복하여 최종 정렬 결과: [1, 2, 3, 4, 5, 6]

삽입 정렬의 성능

• 시간 복잡도 : O(n^2)

장/단점

• 장점: 구현이 간단, 데이터가 거의 정렬된 경우 최적의 성능을 보임

• 단점: 역순 배열이면 최악의 성능을 보임, 큰 배열에서는 성능이 떨어짐

2. 병합 정렬(Merge Sort)

재귀적으로 정렬하는 알고리즘

분할 정복 알고리즘에 속함

배열들의 데이터를 최소한을 쪼갠 후 각 단계 별로 병합을 하면서 정렬을 진행하는 방식

1. 데이터를 반으로 나누어 분할.

2. 각각을 정렬한 후 병합하며 정렬.

3. 두 개의 데이터가 하나로 합쳐질 때 비교 연산이 두 번 발생.

4. 네 개의 데이터가 두 개로 병합될 때 비교 연산이 네 번 발생.

5. 단계마다 영역의 수가 반으로 줄어들기 때문에 O(log n)의 성능을 가짐.

6. 병합할 때 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회독 완주한 점

• 멘토님과 적극적으로 소통하려고 노력한 점

😅아쉬웠던 점

• 전공 시간에 이미 한 번 배웠던 것들인데 아직 완전한 내 것이 아닌 점이 아쉽네요... 좀 더 분발!

🛠보완하고 싶은 점

• 워밍업 클럽이 끝나고 운영체제, 자료구조와 알고리즘 강의를 개인 노션에 정리한 내용을 보면서 다시 정주행 돌릴 예정인데 그 때는 정리에 급급하기 보다는 차분하게 시간을 들여 내 것으로 만들도록 노력해야겠습니다.

• 강의 재생 도중에 궁금한 점이 있으면 당장 찾아보는 것이 아니라 일단 다 듣고 찾아보기

• 공부 흐름 끊어먹지 않고 온전히 집중하기