문승현 튜터님 강의 - ‘동적 계획법(DP) + 가상 메모리’

7 분 소요

Dynamic Programming (동적 계획법, DP)

1.1 개념:

우리는 살면서 같은 실수를 반복하지 않기 위해 메모를 하곤 합니다.
동적 계획법(DP)은 알고리즘계의 ‘메모 습관’과 같습니다.

복잡하고 큰 문제를 한 번에 해결하기 어려울 때,
이를 작은 문제들로 나누고 그 결과를 저장해 두었다가 더 큰 문제를 풀 때 재사용하는 전략입니다.

왜 ‘Dynamic’ 인가요?

사실 이 이름은 별 뜻이 없습니다.
창시자인 리처드 벨만이 당시 연구비 지원을 받기 위해 “멋있어 보여서” 붙인 이름일 뿐입니다.
여러분은 단순히 “기억하며 풀기”라고 이해하시면 충분합니다.

DP가 성립하기 위한 2가지 조건:

중복되는 부분 문제 (Overlapping Subproblems): 큰 문제를 풀다 보니 똑같은 작은 문제들이 계속 반복해서 나타날 때 사용합니다.
최적 부분 구조 (Optimal Substructure): 작은 문제들의 최적의 답을 모으면, 결국 전체 문제의 최적의 답이 되는 구조여야 합니다.

핵심 도구:

메모이제이션 (Memoization): “한 번 계산한 건 배열(DP 테이블)에 적어두자!” (위에서 아래로 내려가는 Top-down 방식)
타뷸레이션 (Tabulation): “바닥(제일 작은 문제)부터 표를 차근차근 채워 나가자!” (밑에서 위로 올라가는 Bottom-up 방식)

1.2 점화식(Recurrence Relation) 이해하기

DP의 꽃은 점화식입니다.
점화식이란 “현재의 상태를 이전 상태들의 조합으로 표현한 수학적 식”입니다.
점화식만 잘 세우면 코딩은 식을 옮기는 과정에 불과합니다.

점화식 세우기 3단계:

상태 정의: dp[n]이 무엇을 의미하는지 문장으로 정의합니다. (예: dp[n]은 n원 거스름 돈을 줄 때 필요한 최소 동전 개수)
관계 찾기: dp[n]을 만들기 위해 바로 직전($n-1$, $n-2$ 등)에 어떤 일이 있었어야 하는지 논리적으로 연결합니다.
기초값(Base Case) 설정: 가장 작은 문제(예: dp[0], dp[1])처럼 더 이상 쪼개지지 않는 값을 미리 정해줍니다.

대표 예제 1 [난이도 하] : 계단 오르기 (Climbing Stairs)

계단을 오르고 있습니다.
한 번에 1계단 또는 2계단씩 올라갈 수 있습니다.
n번째 계단에 도달하는 방법의 가짓수는 모두 몇 가지일까요?

입력: n = 4 (4번째 계단까지 가야 함)

출력: 5

해결 논리:

생각의 흐름: 4번째 계단에 발을 내딛기 직전의 위치는 어디였을까요?
- 3번째 계단에서 1칸 올라왔거나 (dp[3])
- 2번째 계단에서 2칸 올라왔을 것 (dp[2])입니다.
점화식: dp[n] = dp[n-1] + dp[n-2]
기초값: dp[1] = 1, dp[2] = 2

정답 코드 예시

#include <iostream>
#include <vector>

using namespace std;

// dp[i] : i번째 계단에 도달하는 방법의 수
int dp[101];

int main() {
    int n = 4;

    // 1. 기초값 설정 (Base Case)
    // 1번 계단은 1가지 방법뿐, 2번 계단은 (1+1)과 (2) 총 2가지 방법
    dp[1] = 1;
    dp[2] = 2;

    // 2. 점화식을 이용한 바닥부터 채우기 (Bottom-up)
    // 3번째 계단부터 n번째 계단까지 차례대로 계산해서 올라갑니다.
    for (int i = 3; i <= n; i++) {
        // "i번째 도달법 = (i-1에서 한 칸 오기) + (i-2에서 두 칸 오기)"
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    cout << n << "번째 계단까지 가는 법: " << dp[n] << endl;
    // 결과: 5 (1111, 112, 121, 211, 22)
    
    return 0;
}

대표 예제 2 [난이도 중] : RGB 거리 (RGB Distance)

거리에 집이 N개 있습니다. 집을 빨강, 초록, 파랑 중 하나로 칠해야 합니다.
각 집을 칠하는 비용이 주어질 때, 모든 집을 칠하는 최소 비용을 구하세요.
단, 인접한 집(앞뒤 집)은 서로 색이 달라야 합니다.

입력: 3 / 집1: [26, 40, 83], 집2: [49, 60, 57], 집3: [13, 89, 99]

출력: 96

해결 논리:

상태 정의: dp[i][0]은 i번째 집을 빨강으로 칠했을 때, 그 집까지의 누적 최소 비용.
점화식 핵심: “내가 오늘 빨강을 칠하려면, 어제는 무조건 초록이나 파랑 중 하나였어야 해!”
- dp[i][빨강] = cost[i][빨강] + min(dp[i-1][초록], dp[i-1][파랑])
최종 정답: 마지막 집까지 칠한 후 min(dp[N][빨강], dp[N][초록], dp[N][파랑])

정답 코드 예시

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int n = 3;
    int cost[3][3] = { {26, 40, 83}, {49, 60, 57}, {13, 89, 99} };
    int dp[3][3];

    // 1. 첫 번째 집 초기화 (선택지가 없으므로 그냥 자기 비용)
    dp[0][0] = cost[0][0]; dp[0][1] = cost[0][1]; dp[0][2] = cost[0][2];

    // 2. 두 번째 집부터 점화식 적용
    for (int i = 1; i < n; i++) {
        // 이번에 빨강(0) 선택 = 오늘 빨강값 + 어제(초록, 파랑) 중 최솟값
        dp[i][0] = cost[i][0] + min(dp[i - 1][1], dp[i - 1][2]);
        // 이번에 초록(1) 선택 = 오늘 초록값 + 어제(빨강, 파랑) 중 최솟값
        dp[i][1] = cost[i][1] + min(dp[i - 1][0], dp[i - 1][2]);
        // 이번에 파랑(2) 선택 = 오늘 파랑값 + 어제(빨강, 초록) 중 최솟값
        dp[i][2] = cost[i][2] + min(dp[i - 1][0], dp[i - 1][1]);
    }

    // 마지막 집에서 나온 3가지 결과 중 가장 저렴한 비용 선택
    int result = min({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]});
    cout << "최소 비용: " << result << endl; // 결과: 96
    
    return 0;
}

대표 예제 3 [난이도 상] : 평범한 배낭 (0/1 Knapsack)

배낭에 담을 수 있는 최대 무게 K가 정해져 있습니다.
여러 물건들의 무게 W와 가치 V가 주어질 때, 배낭에 담을 수 있는 가치의 최댓값을 구하세요.
(물건은 쪼갤 수 없습니다.)

입력: N=4, K=7 (물건 4개, 가방 한도 7) / 물건1(6,13), 물건2(4,8), 물건3(3,6), 물건4(5,12)

출력: 14 (물건2와 3을 넣었을 때)

해결 논리:

상태 정의: dp[i][w] = i번째 물건까지 고려했을 때, 무게 한도가 w인 배낭의 최대 가치.
점화식 핵심: “i번째 물건을 버릴까? 아니면 공간을 만들어서 넣을까?“
- 안 넣는 경우: 그냥 이전 물건까지의 가치와 동일 -> dp[i-1][w]
- 넣는 경우: 현재 가치 + dp[i-1][w - 현재 무게] (현재 물건 무게만큼 비웠을 때의 최댓값)

결론: dp[i][w] = max(안 넣기, 넣기)

정답 코드 예시

#include <iostream>
#include <algorithm>

using namespace std;

int dp[101][100001]; // 물건 번호, 무게 한도
int weight[101], val[101];

int main() {
    int N = 4, K = 7;
    weight[1]=6; val[1]=13; weight[2]=4; val[2]=8;
    weight[3]=3; val[3]=6;  weight[4]=5; val[4]=12;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= K; j++) {
            if (j >= weight[i]) {
                // 넣을 수 있다면? [안 넣었을 때]와 [내 자리를 비우고 나를 넣었을 때] 중 최대값
                dp[i][j] = max(dp[i - 1][j], val[i] + dp[i - 1][j - weight[i]]);
            } else {
                // 내 몸무게가 한도 초과라면? 이전 최댓값 그대로 유지
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    cout << "배낭의 최대 가치: " << dp[N][K] << endl; // 결과: 14
    return 0;
}

DP는 ‘일반화’가 가능한가에 집중해볼것!
- 0~N까지 나누어 체계화 할 수 있을지?
- 그러한 결과에서 규칙성을 찾을 수 있는지
  (이전 결과로 현재 결과를 구할 수 있는지)

가상 메모리 (Virtual Memory)

1.1 개념

이전 시간에 프로세스가 사용하는 4가지 메모리 영역(Code, Static, Stack, Heap)에 대해 배웠습니다.
그런데 의문이 생깁니다. 내 RAM은 16GB인데, 어떻게 수십 개의 프로그램이 각자 거대한 영토를 차지하면서도 서로 충돌하지 않을까요?

가상 메모리는 운영체제가 프로세스에게 “이 컴퓨터의 메모리는 전부 네 것이야”라고 속이는 거대한 마법입니다.
프로세스는 ‘실제 RAM 주소’를 직접 보지 못하고, OS가 제공한 가상 주소(Virtual Address)라는 가짜 주소 공간에서만 활동합니다.

🎯 핵심 특징

격리성 (Isolation)
- 프로세스 A의 0x1000 번지와 프로세스 B의 0x1000 번지는 이름만 같을 뿐,
  실제 물리 RAM에서는 전혀 다른 곳에 위치합니다.
유연성
- 실제 RAM 용량보다 훨씬 큰 프로그램을 실행할 수 있습니다.
  당장 실행에 필요한 부분만 RAM에 올리면 되기 때문입니다.

1.2 페이지 테이블 (Page Table)

프로세스가 가짜 주소(0x1000)를 불렀을 때,
OS는 이를 실제 RAM의 물리 주소(0xABCD)로 순식간에 바꿔줘야 합니다.
이 번역 업무를 담당하는 것이 바로 페이지 테이블입니다.

비유: 도서관의 도서 검색 대장

여러분은 책의 “제목(가상 주소)”만 알고 있습니다.
하지만 실제 책은 “3층 B구역 5번 서가(물리 주소)”에 있죠.
사서(MMU)는 검색 대장(페이지 테이블)을 보고 여러분을 안내합니다.

🎯 작동 원리

1. MMU (Memory Management Unit)

CPU 옆에 붙어 있는 하드웨어 번역기입니다. CPU가 가상 주소를 던지면 MMU가 페이지 테이블을 뒤져 ‘실제 주소’를 찾아냅니다.

2. 페이지 테이블 엔트리 (PTE)

테이블의 한 줄 한 줄을 의미하며, 여기에는 물리 주소뿐만 아니라 중요한 정보가 담깁니다.
- Present Bit (존재 비트): 지금 이 데이터가 RAM에 있는가? (1이면 RAM, 0이면 하드디스크)
- RWX 비트: 읽기/쓰기/실행 권한 정보

왜 번역 과정이 필요한가요? 만약 번역기가 없다면, 프로그래머는 프로그램을 만들 때마다 “이 데이터는 반드시 RAM 1234번지에 저장해!”라고 지정해야 합니다. 그런데 이미 다른 프로그램이 그 자리를 쓰고 있다면? 프로그램은 실행조차 되지 않겠죠. 번역기 덕분에 우리는 언제나 “0번지부터 시작하는 편안한 내 영토”에서 코딩할 수 있습니다.

1.3 페이징 (Paging): 메모리를 나누는 똑똑한 단위

메모리를 관리할 때 “1바이트씩” 관리하면 관리 장부(페이지 테이블)가 너무 커집니다.
그래서 OS는 메모리를 일정한 크기로 뭉텅이 내어 관리하는데, 이를 페이징이라고 합니다.

페이지 (Page): 가상 메모리를 자른 단위 (보통 4KB)
프레임 (Frame): 물리 RAM을 자른 단위 (페이지와 크기가 같습니다.)

현대 OS는 페이지와 프레임이라는 규격화된 박스를 사용하기 때문에,
메모리 여기저기에 흩어져 있는 빈 공간들을 알뜰하게 재사용할 수 있습니다.
이를 통해 외부 단편화 문제를 완벽하게 해결합니다.

외부 단편화?
큰 메모리 데이터들 사이에 작은 데이터들이 끼어있는 상황

1.4 스왑 영역 (Swap Area): RAM의 든든한 지원군

가상 메모리의 가장 큰 마법은 “RAM보다 큰 프로그램을 돌리는 것”입니다.
이것이 가능한 이유는 바로 하드디스크(HDD/SSD)의 일부를 RAM처럼 사용하는 스왑 영역 덕분입니다.

비유: 요리사의 조리대(RAM)와 창고(스왑 영역)
요리사는 지금 당장 볶아야 할 재료는 조리대(RAM)에 두지만,
나중에 쓸 재료는 창고(하드디스크)에 넣어둡니다. 조리대가 꽉 차면, 가장 안 쓰는 재료를 다시 창고로 보내고 필요한 재료를 가져오죠.

🎯 상세 동작: 페이지 폴트 (Page Fault)

1.요청:

CPU가 특정 페이지를 요청했는데, 페이지 테이블의 Present Bit가 0(RAM에 없음)입니다.

2.중단:

CPU는 하던 일을 멈추고 OS에게 “데이터가 없으니 가져와 달라”고 요청합니다. (이것이 Page Fault입니다.)

3.교체 (Swapping):

만약 RAM이 꽉 찼다면, OS는 RAM에서 가장 오랫동안 안 쓴 페이지를 골라 스왑 영역(디스크)으로 보냅니다. (Swap-out)
그 빈자리에 지금 필요한 데이터를 디스크에서 가져와 채웁니다. (Swap-in)

4.재개:

페이지 테이블을 ‘Present’로 업데이트하고, CPU는 중단했던 지점부터 다시 실행합니다.

⚠️ 주의: 쓰래싱 (Thrashing) RAM이 너무 부족해서 OS가 하루 종일 데이터를 디스크와 RAM 사이로 나르기만(Swapping) 하는 현상입니다. 하드디스크는 RAM보다 수천 배 느리기 때문에, 컴퓨터가 사실상 멈춘 것처럼 버벅거리게 됩니다. 게이머들이 “램 다익선(RAM은 많을수록 좋다)”을 외치는 이유가 바로 이 쓰래싱을 막기 위해서입니다.

1.5 가상 메모리와 보안: 페이지 보호

가상 메모리는 단순히 주소 번역만 하는 게 아니라,
프로그램이 미쳐 날뛰지 못하게 막는 보안 요원 역할도 합니다.

🎯 권한 제어 (Protection Bits)

각 페이지 테이블 엔트리에는 이 페이지를 어떻게 쓸 수 있는지 적혀 있습니다.

Code 영역 페이지: Read-Execute (읽고 실행만 해! 수정은 안 돼!)
Stack/Heap 영역 페이지: Read-Write (데이터를 쓰고 읽어! 하지만 코드로 실행하진 마!)

보안 사고 예시: 버퍼 오버플로우

해커가 Stack 영역에 악성 코드를 심고 실행시키려 해도,
OS가 “이 페이지는 실행 권한(X)이 없는데?”라며
프로세스를 즉시 종료(Segmentation Fault)시켜 버립니다.

이것이 현대 운영체제가 시스템을 보호하는
핵심 원리 중 하나인 ‘DEP’ (Data Execution Prevention)입니다.

Twitter Facebook LinkedIn

Hyun JaeHoon

문승현 튜터님 강의 - ‘동적 계획법(DP) + 가상 메모리’

Dynamic Programming (동적 계획법, DP)

1.1 개념:

DP가 성립하기 위한 2가지 조건:

핵심 도구:

1.2 점화식(Recurrence Relation) 이해하기

대표 예제 1 [난이도 하] : 계단 오르기 (Climbing Stairs)

대표 예제 2 [난이도 중] : RGB 거리 (RGB Distance)

대표 예제 3 [난이도 상] : 평범한 배낭 (0/1 Knapsack)

가상 메모리 (Virtual Memory)

1.1 개념

1.2 페이지 테이블 (Page Table)

1.3 페이징 (Paging): 메모리를 나누는 똑똑한 단위

1.4 스왑 영역 (Swap Area): RAM의 든든한 지원군

1.5 가상 메모리와 보안: 페이지 보호

공유하기

댓글남기기

참고

백준 Gold 4 키 순서

프로세스 메모리 구조

State Tree TIL (251222)

백준 Gold 4 해킹