개인정보 수집 유효기간

🎁문제 풀이

접근 순서

1. 날짜 계산을 편하게 하기 위해 today와 privacies의 날짜 형식을 일 단위로 계산한다.
2. 약관 알파벳에 접근해서 기간을 구해야 하므로 공백으로 자르고, map을 활용한다.

🎁전체 풀이 코드

#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <sstream>

using namespace std;

int year, month, day, total;
map<char, int> t_map;
vector<int> priv;

vector<int> solution(string today, vector<string> terms, vector<string> privacies) {
    vector<int> answer;

    // 날짜 계산
    year = stoi(today.substr(0, 4)); month = stoi(today.substr(5, 2)); day = stoi(today.substr(8, 2));
    total = year * 12 * 28 + (month - 1) * 28 + day;

    // 약관 자르기
    for(int i = 0; i < terms.size(); i++){
        stringstream ss(terms[i]);
        char alpha; int month;
        ss >> alpha >> month;
        t_map[alpha] = month;
    }

    // cout << t_map['A'];

    // 프라이버시 날짜 계산
    for(int i = 0; i < privacies.size(); i++){
        int y = stoi(privacies[i].substr(0, 4)); 
        int m = stoi(privacies[i].substr(5, 2)); 
        int d = stoi(privacies[i].substr(8, 2));
        char a = privacies[i].back();
        // cout << y << "," << m << "," << d << "," << a << endl;
        int tmp = y * 12 * 28 + (m - 1) * 28 + d + (t_map[a] * 28 - 1);

        priv.push_back(tmp);
    }

    // 비교
    for(int i = 0; i < priv.size(); i++){
        if(priv[i] < total){
            answer.push_back(i + 1);
        }
    }


    return answer;
}

이진탐색트리는 정렬된 트리이다.

어느 노드를 선택하든 해당 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로만 이루어져 있고, 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로만 이루어져 있는 이진 트리 , 저장과 동시에 정렬한다.

검색, 저장, 삭제의 시간복잡도는 모두 O(logn)이고, worst case는 한쪽으로 치우친 트리가 됐을 때 O(n)이다.

worst case는 한쪽으로 치우친 트리인데, Linked List와 다를게 없다.

자가 균형 BST는 알고리즘으로 이진 트리의 균형이 잘 맞도록 유지하여 높이를 가능한 낮게 유지한다. 대표적으로 AVL트리와 Red-black tree가 있다.

Hash table

효율적인 탐색(빠른 탐색)을 위한 자료구조로써 key - value쌍 구조를 가진다.

hash function h 에 key값을 입력으로 넣어 얻은 해시값 h(k)를 위치로 지정하여 저장

저장, 삭제, 검색의 시간 복잡도는 모두 O(1)이다.

🥇Collision 발생

서로 다른 key의 해시값이 똑같을 때 발생

즉, 중복되는 key는 없지만 해시값은 중복 될 수 있는데 이때 Collision이 발생한다.

최대한 hash function을 잘 설계해야하고, 어쩔 수 없이 collision이 발생하는 경우 separate chaining 이나 open addressing등의 방법을 사용하여 해결한다.

[해결 방법]

1. Open addressing

   미리 정한 규칙에 따라 hash table의 비어있는 slot을 찾는다. 빈 슬롯을 찾는 방법에 따라 Linear Probing, Quadratic Probing, Double Hashing으로 나뉜다.

   메모리를 적게 사용한다.

   • Linear Probing & Quadratic Probing

     충돌이 발생한 해시값으로 부터 일정한 값만큼 건너뛰어 비어있는 slot에 저장

     -> 탐사이동폭이 같기 때문에 특정 영역에 데이터가 집중적으로 몰리는 클러스터링 문제가 발생할 수 있다.

     

   • Double Hashing

     클러스터링 문제가 발생하지 않도록 2개의 해시함수를 사용하는 방식

     하나는 최초의 해시값을 얻을 때 사용, 다른 하나는 해시 충돌이 발생할 때 탐사 이동폭을 얻기 위해 사용

     이동폭이 다르게 발생

2. Separete chaining

   Linked list를 활용하여 노트(slot)을 추가하여 데이터를 저장

   

​ [Worst Case]

​ n개의 모든 key가 동일한 해시값을 갖게 되면 길이 n의 linked list가 생성되게 된다.

​ 이때, 특정 key를 찾기 위해서는 길이 n의 linked list를 검색하는 O(n)의 사간복잡도를 갖게 된다.

queue는 선립선출(FIFO) 자료구조

시간복잡도는 데이터 추가 enqueue O(1), 데이터 추출 dequeue O(1) 이다.

활용 예시로는 Cache구현, 프로세스 관리, 너비우선탐색(BFS)가 있다.

구현 방식

• Array-Based queue

  enqueue와 dequeue과정에서 남는 메모리가 생긴다. 메모리 낭비를 줄이기 위해 주로 Circular queue 형식으로 구현한다.

• List-Based queue

  재할당이나 메모리 낭비의 걱정을 할 필요가 없다.

Stack

stack은 후입선출(LIFO) 자료구조

시간복잡도는 push O(1), pop O(1)이다.

활용예시는 후위 표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문기록, DFS등이 있다.

Stack 2개로 Queue 구현

enqueue에 사용할 stack instack 과 dequeue에 사용할 outstack을 구현한다.

1. enqueue() : instack에 push()하여 데이터를 저장한다.

2. dequeue() :

   a. 만약 outstack이 비어 있다면 instack.pop()을 하고 outstack.push()를 하여 instack에서

   ​ outstack으로 데이터를 옮긴다. 이 결과로 가장 먼저 왔던 데이터는 outstack의 top에 위치하게 된다.

   b. outstack.pop()을 하면 가장 먼저 왔던 데이터가 가장 먼저 추출된다.(FIFO)

Queue 2개로 Stack 구현

push()에 사용할 queue를 q1, pop()에 사용할 queue를 q2라고 한다.

1. push() : q1으로 enqueue()히여 데이터를 저장한다.

2. pop():

   a. q1에 저장된 데이터의 갯수가 1이하로 남을 때까지 dequeue()를 한 후, 추출된 데이터 를 q2에 enqueue()한다. 결과적으로 가장 최근에 들어온 데이터를 제외한 모든 데이 터는 q2로 옮겨진다.

   b. q1에 남아 있는 하나의 데이터를 dequeue()해서 가장 최근에 저장된 데이터를 반환

   c. 다음에 진행될 pop()을 위와 같은 알고리즘으로 진행하기 위해 q1, q2이름을 swap

Priority Queue(Heap)

• 우선 순위가 높은것이 먼저 나온다.

• push, pop 모두 O(logn)의 시간복잡도

• Heap -> Tree로 구현 -> Tree의 대부분 linked list로 구현 -> but, heap은 Array로 구현

  -> 새로운 인자가 언제나 마지막에 위치

Array는 연관된 data를 메모리상에 연속적이며 순차적으로 미리 할당된 크기 만큼 저장하는 자료구조

Array의 특징

• 고정된 저장 공간
• 순차적인 데이터 저장

Array의 장점은 lookup과 append가 빠르다. 조회를 자주 해야되는 작업에서는 Array자료구조를 많이 사용

Array의 단점은 fixed-size 특성상 선언시에 Array의 크기를 미리 정해야 된다. 이는 메모리 낭비나 추가적인 overhead가 발생할 수 있다.

Q. 미리 예상한 것보다 더 많은 수의 data를 저장하느라 Array의 size를 넘어서게 되면 어떻게 할것인가?

A. 기존의 size보다 더 큰 Array를 선언하여 데이터를 옮겨 할당한다. 모든 데이터를 옮겼다면 기존 Array는 메모리에서 삭제하면 된다. 이런식으로 동적으로 배열의 크기를 조절하는 자료구조를 Dynamic array라고 한다.

다른 방법으로 size가 예측하기 쉽지 않다면, Array대신 Linked List를 사용함으로써 데이터가 추가될 때마다 메모리 공간을 할당받는 방식을 사용하면 된다.

Dynamic Array

Array의 fixed-size의 한계를 극복하기 위한 자료구조

저장공간이 가득 차게 되면 resize를 하여 유동적으로 size를 조절하여 데이터를 저장

• Doubling

​ resize의 대표적인 방법

​ 데이터를 추가(append O(1))하다가 메모리를 초과하게 되면 기존 배열의 size보다 2배 큰 배열을 선언하고 데이터를 일일이 옮기는(O(n)) 방법

append의 시간복잡도

대부분 인덱스에 추가하는 (O(1))이고 resize 할때 O(n)이 발생하므로 전체적으로 --> O(1)

Linked List

Node라는 구조체로 이루어져있다. Node는 데이터 값과 다음 Node의 address를 저장

Linked List는 물리적인 메모리상에서는 비연속적으로 저장이 되지만 Linked list를 구성하는 각각의 Node가 다음 Node의 address를 가리킴으로써 논리적인 연속성을 가진 자료구조

데이터 삽입/ 삭제

물리적 옮길 필요없이 next address의 주소값 변경만 하면 되기 때문에 O(1)의 시간복잡도를 가진다.

RDBMS에서는 B+tree구조로된 index를 사용해서 검색속도를 향상시킨다.

Full Table Scan을 안해도 된다.

구조 : B+tree, Hash, Bitmap...

특정 Column을 search-key 값으로 설정하여 index를 생성하면, 해당 search-key 값을 기준으로 정렬하여(search-key, pointer)를 별로 파일에 저장한다. -> table크기의10 % 저장공간

사용이유 : talbe은 순서없이 누적된다. 하지만, index는 정렬되어 저장

특정 column에 대한 index를 생성해 놓은 경우 해당 속성에 대하여 search-key가 정렬되어 저장되어 있기 때문에 조건 검색(SELECT ~ WHERE) 속도가 굉장히 빠르다.

• Clustering index : pk 기준으로 table이 정렬(영어사전)

• Secondary index : 따로 index table(부록 색인)

index의 장단점

장점

검색 속도 향상

단점

1. 추가 저장공간 필요
2. 느린 데이터 변경 작업

🥇Index를 어느 Column에 사용하는 것이 좋을까?

1. where에서 자주 조회
2. 수정 빈도가 낮고
3. 카디널리티 높고 (중복되지 않은 정도)
4. 선택도가 낮은 (특정 값을 잘 골라낼 수 있는 정도, 1일수록 unique)

Q. 성별 column에 index를 걸어주는게 좋을까?

성별처럼 남녀 두 종류로만 나눠지는 경우는 카디널리티가 매우 낮고, 선택도는 매우 높게 된다. 이 경우 index가 주는 이점은 매우 적고, 오히려 저장공간 차지와 데이터 수정시 성능저하등을 고려하여 index를 생성하지 않는 것이 좋다.

Q. true 또는 false 값을 갖는 column에서, true 1%, false 99 %의 비율로 구성된 상황에서 index를 거는게 좋을까?

아무리 비율의 차이가 있어도 true, false 두 종류로만 나눠지는 경우에는 카디널리티가 매우 낮고, 선택도는 매우 높게 된다. 따라서 index를 생성하지 않는것이 좋다.

index를 B+tree로 구현하는 이유

Hash table을 사용하면 하나의 데이터를 탐색하는 시간은 O(1)로 b-tree보다 빠르지만, 값이 정렬되어 있지 않기 때문에 부등호를 사용하는 query에 대해서는 매우 비효율적이게 되어 데이터를 정렬 해서 저장하는 b+tree를 이용한다.

DB의 무결성을 유지하며 DB의 상태를 변화시키는 기능을 수행한다.

transaction은 하나 이상의 query를 포함해야 하고, ACID(원자성, 일관성, 고립성, 지속성)의 4가지 규칙을 만족해야 한다.

• Atomicity(원자성) : transaction에 포함된 작업은 전부 수행되거나, 전부 수행되지 말아야 한다. (All or Nothing)
• Consistency(일관성) : tansaction실행을 성공적으로 완료하면 언제나 일관성 있는 DB상태로 유지한다.
• Isolation(고립성) : 각 transaction은 독립적으로 작업을 수행한다.(동시성 제어)
• Durability(지속성) : 성공적으로 수행된 transaction은 DB에 영원히 반영되어야 한다.

동시성 제어

transaction이 한개의 data를 동시에 update할때 충돌로 인한 갱신 손실 발생

-> 방지를 위해 Lock을 건다.

Commit 과 Rollback

DB는 Commit과 Rollback 명령어를 통해 데이터 무결성을 보장

• Commit : transaction 작업을 완료했다고 확정하는 명령어. DB에 저장하고, DB가 변경됨
• Rollback : 작업 중 문제가 발생했을 때, 변경 사항을 취소, 이전 Commit 상태로 되돌림

DeadLock

DB에서 deadlock이란 여러 transaction들이 각각 자신의 데이터에 대하여 lock을 획득한 상태에서 상대방 데이터에 대하여 접근하조가 대기를 할때 교차 대기를 하게 되면서 영원히기다리는 상태를 말한다.

해결방법

1. 예방 기법 : 모든 데이터를 미리 locking
2. 회피 기법 : time stamp를 사용
3. 탐지/ 회복 기법

상호배제(Mutual Exclusive)

Monitor.Enter()와 Monitor.Exit() 사이에 있는 코드사이에는 들어올 수 가 없다.

문제점 : 코드가 길어진다면 관리가 힘들어질 수 있다.

for (int i = 0; i < 100000; i++)
{
    Monitor.Enter(_obj); // 문을 잠구는 행위
    {
        number++;
        return;
    }
    Monitor.Exit(_obj); // 잠금을 풀어준다.
}

이런 경우 잠금을 풀어줄 수가 없다.

즉, 데드락(DeadLock) 상태에 빠지게 된다.

try
{
    Monitor.Enter(_obj);
    {
        number++;
        return;
    }
}
finally
{
    Monitor.Exit(_obj);
}

이런식으로 해결이 가능하다.

하지만 대체로 잘 사용되지 않는 방법이고 lock 키워드를 사용한다.

lock(_obj)
{
    number++;
}

candidate key(후보키)중 선택한 main key로써, 각 row를 구분하는 유일한 열(column)을 말한다. 그래서 기본키는 Null 값을 가질 수 없고, 중복된 값을 가질 수 없다. 기본키는 table당 1개만 지정해야한다.

Relation

table중 DB에서 사용할 조건을 갖춘것

1. table의 cell은 단일 값을 갖는다.
2. 어떤 두 개의 row도 동일하지 않다.

table이랑 구분하지 않고 사용하기도 한다.

Super Key(슈퍼키) - 유일성

Candidate Key(후보키) - 유일성 + 최소성

Alternate Key(대체키) - primary key를 제외한 나머지 후보키들을 말한다.

테이블간의 관계

N:M 관계

관계형 데이터베이스(RDB)에서 양쪽 entity모두가 서로에게 1:N관계를 갖는 구조

1 : N + N : 1 = N : M

ex)수강신청 - 학생 <-> 수업

• 1 : N 관계

  고객은 여러 상품을 주문할 수 있고, 주문된 상품은 1명의 고객만을 갖는다.

  

​ Foreign Key(외래키)

​ 다른 table의 Primary key column과 연결되는 table의 column을 의미한다.

​ 두 table을 연결할 때 한 table의 외래키가 다른 하나의 table의 기본키가 된다.

left outer join / inner join

Join이란 두 개 이상의 테이블을 서로 연결하여 하나의 결과를 만들어 보여주는 것

inner join은 두 테이블에 모두 있는 내용만 join되는 방식(교집합)

left outer join은 왼쪽 table의 모든 행에 대해서 join을 진행

🥇RDB-NoSQL

NoSql은 언제 사용하면 좋을까?

NoSQL은 정확한 데이터 구조가 정해지지 않은 경우, 데이터 update가 적고 조회가 많은경우,Scale out(수평적 확장)이 가능하므로 데이터 양이 매우 많은 경우에 사용하는게 좋다.

RDB는 언제 사용하면 좋을까?

RDB는 데이터 구조가 명확하여 변경될 여지가 없는 경우, 또 데이터 중복이 없으므로 데이터 update가 잦은 시스템에서 사용하면 좋다.

이 경우 0 이 나와야 하지만, 0이 나오지 않는다.

// number++; 
int temp = number;
temp += 1;
number = temp;

number++ 은 실제로 실행될 때 다음과 같은 3가지 과정을 거친다.

더이상 쪼갤 수 없는 작업인 원자성 이라고 한다.

저 안의 과정이 한번에 이루어져야 하므로 Interlocked를 사용해야 한다.

static void Thread_1()
{
    for (int i = 0; i < 100000; i++)
    {
        Interlocked.Increment(ref number);
    }
}

static void Thread_2()
{
    for (int i = 0; i < 100000; i++)
    {
        Interlocked.Decrement(ref number);
    }
}

동시 다발적이여도 순서가 생긴다.(Race Condition 문제)

static void Thread_1()
{
    for (int i = 0; i < 100000; i++)
    {
        int prev = number;
        Interlocked.Increment(ref number);
        int next = number;
    }
}

싱글스레드가 아니므로 꺼내오는 순간에 어딘가에서 건드릴 수가 있다. 즉, 유효한지 검증을 할 수 없다.

int afterValue = Interlocked.Increment(ref number);

이런식으로 값을 가져와야 유효한 값을 얻을 수 있다.

HTTP특징 Connectionless, Stateless 때문에 클라이언트가 이전 상태를 유지하지 않음

쿠키(Cookie)

1. 서버가 클라이언트로부터 요청을 받았을 때, 클라이언트 정보를 토대로 쿠키를 구성
2. 서버는 클라이언트에게 보내는 응답의 header에 쿠키를 담아 보냄
3. 클라이언트가 응답을 받으면, 브라우저는 쿠키를 쿠키 디렉터리에 저장

클라이언트(브라우저)가 Key-Value쌍으로 로콜에 저장되는 데이터 파일

유효시간 내에서 블라우저가 종료되어도 계속 유지

사용자가 따로 작업을 하지 않아도 브라우저가 쿠키를 request header에 담아 서버에 전송

세션

기본적으로 쿠키를 이용하여 구현

클라이언트를 구분하기 위해 각 클라이언트에게 session ID를 부여하고 클라이언트 쿠키에 session ID를 저장한다.

세션은 서버측에 저장하여 관리 되기 때문에 보안은 좋지만 서버에 과부하를 줄 수 있다.

쿠키와 세션을 통한 인증과 인가

1. 클라이언트가 로그인을 하면 서버는 회원정보를 대조하여 인증을 한다.(인증)

2. 회원 정보를 세션저장소에 생성하고 session ID를 발급

3. http response header 쿠키에 발급한 session ID를 담아서 보낸다.

4. 클라이언트에서 session ID를 쿠키 저장소에 저장하고, 이후 http request를 보낼 때마다 쿠키에 session ID를 담아서 보낸다.

5. 서버에서 쿠키에 담겨져온 session ID에 해당하는 회원 정보를 세션 저장소에서 가져옴

   (인가)

6. 응답 메시지에 회원 정보를 바탕으로 처리된 데이터를 담아서 클라이언트에 보냄

단점

1. Load Balancing

   서버가 처리해야할 요청(Load)을 여러대의 서버로 나누어(Balancing) 처리하는 기법

2. 서버 효율성 관리 및 확장이 어려움

서버-클라이언트 모델을 따르면서 request, response 구조로 웹 상에서 정보를 주고받을 수 있는 프로토콜

TCP/IP를 기반으로 작동

특징

1. Connectionless

   서버에 연결 후 요청에 응답을 받으면 연결을 끊어버림

   -> 실제 동시 접속을 최소화, 더 많은 유저의 요청을 처리 가능

2. Stateless

   연결이 끊겼기 때문에, 클라이언트의 이전 상태(로그인 유무)를 알 수 없다.

   -> cookie, session, jwt등이 도입 됨

HTTP는 Text형식으로 주고받기 때문에 데이터 유출의 문제점이 있을 수 있다.

-> 암호화를 추가한 프로토콜이 HTTPS

🥇Request Method

GET 메소드

클라이언트가 서버에게 리소스를 요청할 때 사용

필요한 정보를 특정하기 위해 Query String을 추가하여 정보 조회

브라우저 히스토리에 남고 캐시가 가능하다.

POST 메소드

서버에게 데이터처리(주로 생성)을 요청할 때 사용하는 메소드

전달할 데이터를 body부분에 포함하여 통신

캐시 불가능

PUT

전체 리소스 수정(리소스를 대체), 없으면 생성

PATCH

일부 리소스 수정

Status code

클라이언트가 보낸 HTTP요청에 대한 서버의 응답 코드

상태 코드를 통해 요청의 성공/실패 여부를 판단할 수 있다.

100번대부터 총 500번대까지 총 5개의 클래스로 구분되어 HTTP요청에 대한 상태를 알려줌

• 1xx(정보) : 요청을 받았으며 작업을 계속한다.
• 2xx(성공) : 클라이언트가 요청한 동작을 성공적으로 수신하였고, 성공적 처리하였다.
• 3xx(리다이렉션) : 요청을 완료하기 위해 추가 작업 조치가 필요하다.
• 4xx(클라이언트오류) : 클라이언트 요청에 문제가 있다.
• 5xx(서버오류) : 서버가 유효한 요청의 수행을 실패했다.

웹 동작 과정

1. 사용자가 브라우저에 URL 입력
2. 브라우저는 DNS를 통해 서버의 IP주소를 찾는다.
3. 클라이언트에서 HTTP request 메시지 => TCP/IP 패킷 생성 => 서버로 전송
4. 서버에서 HTTP response메시지 => TCP/IP 패킷 생성 => 클라이언트로 전송
5. 도착한 HTTP response 메시지는 웹 브라우저에 의해 출력(랜더링)

1. Client -> SYN패킷 -> Server
2. Client <- SYN + ACK 패킷 <- Server
3. Client -> ACK패킷-> Server

4-way handshake

TCP 연결 종료

1. Client -> FIN -> Server

2. Client <- ACK <- Server

3. Client <- FIN <- Server

4. Client -> ACK -> Server

TCP 통신과정

1. Connetction Setup(TCP연결 초기화) - 3way handshaking
2. Data Transfer(데이터 전송)
3. Connection Termination(TCP연결 종료) - 4way handshaking

연결형, 신뢰성 전송 프로토콜

연결지향적 서비스를 제공하기 위해 데이터 전송전에 3way handshaking을 하여 논리적 연결을 성립

신뢰성 있는 서비스를 제공하기 위해 오류, 흐름, 혼잡 제어 등을 실행, header가 더 크고 속도가 비교적 느리다는 단점

통신 단계

1. Connection Setup
2. Data Transfer
3. Connection Termination

패킷명 : Segment

HTTP, File 전송에 사용

UDP

비연결형 프로토콜

단순성 덕분에 적은 양의 오버헤드를 갖고 수신 여부를 확인하지 않아 속도가 빠르다

패킷명 : datagram

실시간성이 중요한 통신(동영상 스트리밍)에 사용

[TCP/UDP비교]

TCP/IP 전송 계층

-> 단순화한 TCP/IP 4계층이 사용

상단에 위치할 수록 사용자가 직접 만날 수 있는 계층(응용계층)

각 계층은 하위계층을 이용하고, 상위계층에 기능을 제공

ex) HTTP프로토콜은 TCP프로토콜과 IP프로토콜을 이용해서 작동

캡슐화 & 역캡슐화

캡슐화:통신 프로토콜의 특성을 포함한 정보를 Header에 포함시켜 하위계층에 전달하는 것

역캡슐화:Header를 역순으로 제거하면서 원래의 Data를 얻는 과정

사용자 입장에서는 data가 그냥 전송되는 것처럼 보이지만, 다음과 같은 과정을 거친다.

하위로 내려오면서 Header에 data가 쌓이고 거꾸로 상위로 올라가면서 정보가 풀어진다.

사용자 프로그램이 물리적 메모리보다 커져도 실행이 가능하다는 장점

program 논리적 영역에서 필요한 부분만 물리적 메모리에 적재, 필요하지 않은 메모리 공간은 디스크(Swap 영역)에 저장

요구 페이징

당장 사용될 주소공간을 page 단위로 메모리에 적재하는 방법

유효/무효 비트를 두어 각 page가 메모리에 존재하는 지 표시

장점

1. 메모리 사용 감소
2. 적재 입출력 오버헤드 감소

Page fault

CPU가 무효비트로 표시된 page에 엑세스 하는 상황

MMU 가 page fault trap 을 발생

페이지 교체 알고리즘

page fault가 발생하면, 요청된 page를 디스크에서 메모리로 가지고 온다.

이때, 물리적 메모리 공간이 부족하게 되면 메모리에 올라와 있는 page를 디스크로 옮겨서 메모리 공간을 확보해야 한다.

1. FIFO

   가장 오래된 page 교체

2. 최적 페이지 교체

   앞으로 가장 오랫동안 사용되지 않을 page를 예측해서 교체

3. LRU(Least Recently Used)

   가장 오랫동안 사용되지 않은 page 교체

4. LFU(Least Frequently Used)

   참조 횟수가 가장 적은 page 교체

일반적으로 Code, Data, Heap, Stack 등의 기능 단위로 segment를 정의

주소 변환을 위해 segment table이 필요하다.

--> 외부 단편화 문제 발생 가능

Paged Segmentation

segmentation을 기본으로 하되 이를 다시 동일 크기의 page로 나누어 물리 메모리에 할당하는 메모리 관리 기법 즉, 프로그램을 의미 단위인 segment로 나누고 개별 segment의 크기를 page의 배수가 되도록 하는 방법