백준 Class3 핵심 알고리즘 개념 정리

📌 들어가며

백준 Class3부터는 본격적인 알고리즘 문제들이 등장해요. DP, DFS, 힙 등 핵심 알고리즘을 확실히 이해해야 문제를 풀 수 있답니다!

---

📚 1. 다이나믹 프로그래밍 (Dynamic Programming, DP)

🤔 DP가 뭐야?

큰 문제를 작은 문제로 나누어 푸는 기법이에요. 한 번 계산한 결과를 저장해두고 재사용하는 게 핵심!

💡 비유: 피보나치 수열을 계산한다고 생각해보세요.
F(5)를 구하려면 F(4)와 F(3)이 필요하고,
F(4)를 구하려면 또 F(3)과 F(2)가 필요해요.
F(3)을 두 번 계산하지 말고 한 번만 계산해서 저장해두면 빠르겠죠?

✅ DP를 쓸 수 있는 조건 (2가지)

1️⃣ Overlapping Subproblems (중복되는 부분 문제)

• 같은 작은 문제가 여러 번 반복해서 나타남
• 예시: 피보나치에서 F(3)이 여러 번 필요

2️⃣ Optimal Substructure (최적 부분 구조)

• 큰 문제의 최적해 = 작은 문제들의 최적해 조합
• 예시: 최단경로 (서울→부산) = (서울→대전) + (대전→부산)

---

🎨 DP 접근 방식 2가지

📍 Top-down (Memoization) - 위에서 아래로

재귀 + 메모이제이션을 사용해요!

// 피보나치 예제 - Top-down 방식
function fib(n, memo = {}) {
    // 이미 계산한 값이면 바로 반환
    if (n in memo) return memo[n];

    // 기본값
    if (n <= 2) return 1;

    // 계산하고 저장
    memo[n] = fib(n-1, memo) + fib(n-2, memo);
    return memo[n];
}

console.log(fib(50));  // 빠르게 계산 완료!

🌟 장점: 필요한 것만 계산, 직관적
⚠️ 단점: 재귀 깊이 제한, 함수 호출 오버헤드

📍 Bottom-up (Tabulation) - 아래에서 위로

반복문으로 작은 문제부터 차례대로 풀어요!

// 피보나치 예제 - Bottom-up 방식
function fib(n) {
    const dp = [0, 1, 1];  // 초기값 설정

    // 작은 문제부터 차례로 계산
    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }

    return dp[n];
}

console.log(fib(50));  // 안정적으로 계산!

🌟 장점: 스택 오버플로우 없음, 캐시 효율적
⚠️ 단점: 불필요한 계산 가능, 공간 더 사용

---

📊 DP 문제 유형별 접근법

🔢 Type 1. 계수 문제 (Counting)

"경우의 수를 구하시오" 유형

💼 대표 문제: 계단 오르기
• 1계단 또는 2계단씩 오를 수 있을 때
• n계단까지 가는 경우의 수는?

// 계단 오르기 - dp[i] = i번째 계단까지 가는 경우의 수
function climbStairs(n) {
    const dp = [0, 1, 2];  // 0계단:0, 1계단:1, 2계단:2

    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];  // 점화식
    }

    return dp[n];
}

🎯 Type 2. 최적화 문제 (Optimization)

"최댓값/최솟값을 구하시오" 유형

💼 대표 문제: 최대 부분 배열 합

// 카데인 알고리즘 - 연속된 부분 배열의 최대 합
function maxSubArray(nums) {
    let maxSoFar = nums[0];
    let maxEndingHere = nums[0];

    for (let i = 1; i < nums.length; i++) {
        // 현재 원소를 포함한 최대값 vs 현재 원소만
        maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }

    return maxSoFar;
}

console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6

✔️ Type 3. 결정 문제 (Decision)

"가능한가? 불가능한가?" 유형

💼 대표 문제: 부분집합 합

// 주어진 숫자들로 target을 만들 수 있는가?
function canPartition(nums, target) {
    const dp = new Array(target + 1).fill(false);
    dp[0] = true;  // 0은 항상 가능 (아무것도 안 선택)

    for (let num of nums) {
        // 뒤에서부터 계산 (중복 방지)
        for (let j = target; j >= num; j--) {
            dp[j] = dp[j] || dp[j - num];
        }
    }

    return dp[target];
}

---

🎯 백준 Class3 DP 대표 문제

📝 1463번 - 1로 만들기

const n = 10;
const dp = new Array(n + 1).fill(0);

for (let i = 2; i <= n; i++) {
    // 1을 빼는 경우
    dp[i] = dp[i - 1] + 1;

    // 2로 나누어 떨어지는 경우
    if (i % 2 === 0) {
        dp[i] = Math.min(dp[i], dp[i / 2] + 1);
    }

    // 3으로 나누어 떨어지는 경우
    if (i % 3 === 0) {
        dp[i] = Math.min(dp[i], dp[i / 3] + 1);
    }
}

console.log(dp[n]);  // 최소 연산 횟수

🔑 핵심: 세 가지 연산 중 최솟값 선택!

📝 11726번 - 2×n 타일링

const n = 9;
const dp = [0, 1, 2];  // 초기값

for (let i = 3; i <= n; i++) {
    dp[i] = (dp[i-1] + dp[i-2]) % 10007;  // 나머지 연산 주의!
}

console.log(dp[n]);

🔑 핵심: 마지막에 세로 타일(1×2) 또는 가로 타일(2×1) 2개 놓는 경우로 분류

 

---

🌲 2. 깊이 우선 탐색 (Depth-First Search, DFS)

🤔 DFS가 뭐야?

그래프나 트리를 탐색하는 방법 중 하나예요. 한 길로 쭉 가다가 막히면 돌아와서 다른 길로 가는 방식!

💡 비유: 미로 찾기
오른손 법칙으로 미로를 탈출한다고 생각해보세요.
벽을 따라 쭉 가다가 막다른 길이면 돌아와서 다른 길로 가는 거예요!

📊 DFS 동작 원리 (그림으로 이해하기)

    1 (시작)
   / \
  2   3
 / \   \
4   5   6

탐색 순서: 1 → 2 → 4 → 5 → 3 → 6

🎯 핵심: 깊이를 우선으로 탐색해요!

---

💻 DFS 구현 방법 2가지

📍 방법 1: 재귀로 구현 (추천!)

// 인접 리스트로 그래프 표현
const graph = {
    1: [2, 3],
    2: [1, 4, 5],
    3: [1, 6],
    4: [2],
    5: [2],
    6: [3]
};

// DFS 재귀 구현
function dfs(graph, node, visited = new Set()) {
    // 방문 처리
    visited.add(node);
    console.log(node);  // 방문 순서 출력

    // 인접 노드 탐색
    for (let neighbor of graph[node]) {
        if (!visited.has(neighbor)) {
            dfs(graph, neighbor, visited);
        }
    }
}

dfs(graph, 1);  // 1부터 시작

📍 방법 2: 스택으로 구현

function dfsStack(graph, start) {
    const stack = [start];
    const visited = new Set();
    const result = [];

    while (stack.length > 0) {
        const node = stack.pop();

        if (!visited.has(node)) {
            visited.add(node);
            result.push(node);

            // 인접 노드를 스택에 추가
            for (let neighbor of graph[node]) {
                if (!visited.has(neighbor)) {
                    stack.push(neighbor);
                }
            }
        }
    }

    return result;
}

---

🎮 격자(2D 배열)에서 DFS

🎯 4방향 탐색 (상하좌우)

const grid = [
    [1, 1, 0, 0],
    [1, 1, 0, 0],
    [0, 0, 1, 1],
    [0, 0, 1, 1]
];

// 방향 벡터 (상, 하, 좌, 우)
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];

function dfsGrid(grid, x, y, visited) {
    const n = grid.length;
    const m = grid[0].length;

    // 범위 체크
    if (x < 0 || x >= n || y < 0 || y >= m) return;
    if (grid[x][y] === 0 || visited[x][y]) return;

    // 방문 처리
    visited[x][y] = true;

    // 4방향 탐색
    for (let i = 0; i < 4; i++) {
        const nx = x + dx[i];
        const ny = y + dy[i];
        dfsGrid(grid, nx, ny, visited);
    }
}

// 섬의 개수 세기
function countIslands(grid) {
    const n = grid.length;
    const m = grid[0].length;
    const visited = Array.from({length: n}, () => Array(m).fill(false));
    let count = 0;

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (grid[i][j] === 1 && !visited[i][j]) {
                dfsGrid(grid, i, j, visited);
                count++;  // 새로운 섬 발견!
            }
        }
    }

    return count;
}

console.log(countIslands(grid));  // 2개의 섬

---

🔍 DFS vs BFS 언제 뭘 쓸까?

✅ DFS를 쓰면 좋은 경우

• 🎯 모든 경로를 찾아야 할 때
• 🎲 백트래킹 문제 (N-Queen, 스도쿠)
• 💾 메모리가 제한적일 때
• 🌳 트리의 전위/중위/후위 순회

✅ BFS를 쓰면 좋은 경우

• 📏 최단 경로를 찾을 때 (가중치 없는 그래프)
• 🎯 목표가 가까이 있을 것 같을 때
• 📊 레벨별 탐색이 필요할 때

---

🎯 백준 Class3 DFS 대표 문제

📝 2606번 - 바이러스

// 1번 컴퓨터와 연결된 모든 컴퓨터 찾기
const n = 7;  // 컴퓨터 수
const connections = [[1,2], [2,3], [1,5], [5,2], [5,6], [4,7]];

// 인접 리스트 만들기
const graph = Array.from({length: n+1}, () => []);
for (let [a, b] of connections) {
    graph[a].push(b);
    graph[b].push(a);  // 양방향
}

// DFS로 감염된 컴퓨터 세기
function countVirus(graph, start) {
    const visited = new Set();

    function dfs(node) {
        visited.add(node);
        for (let next of graph[node]) {
            if (!visited.has(next)) {
                dfs(next);
            }
        }
    }

    dfs(start);
    return visited.size - 1;  // 시작 컴퓨터 제외
}

console.log(countVirus(graph, 1));

📝 1012번 - 유기농 배추

// 배추밭에서 지렁이가 필요한 최소 개수
function countWorms(field) {
    const n = field.length;
    const m = field[0].length;
    const dx = [-1, 1, 0, 0];
    const dy = [0, 0, -1, 1];
    let count = 0;

    function dfs(x, y) {
        if (x < 0 || x >= n || y < 0 || y >= m) return;
        if (field[x][y] === 0) return;

        field[x][y] = 0;  // 방문 처리

        for (let i = 0; i < 4; i++) {
            dfs(x + dx[i], y + dy[i]);
        }
    }

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (field[i][j] === 1) {
                dfs(i, j);
                count++;  // 새로운 배추 그룹
            }
        }
    }

    return count;
}

 

---

🏔️ 3. 힙 (Heap)

🤔 힙이 뭐야?

완전 이진 트리 형태로 최댓값이나 최솟값을 빠르게 찾을 수 있는 자료구조예요!

💡 비유: 토너먼트 대진표
1등을 빠르게 찾을 수 있도록 구성된 대진표라고 생각하면 돼요.
루트(맨 위)에는 항상 최강자(최댓값/최솟값)가 있어요!

📊 힙의 구조 (그림으로 이해하기)

최소 힙 (Min Heap)

       1 (최솟값)
      / \
     3   2
    / \ / \
   7  4 5  6

배열로 표현: [1, 3, 2, 7, 4, 5, 6]

🎯 규칙: 부모는 항상 자식보다 작아야 해요!

최대 힙 (Max Heap)

       9 (최댓값)
      / \
     7   8
    / \ / \
   3  2 6  5

배열로 표현: [9, 7, 8, 3, 2, 6, 5]

🎯 규칙: 부모는 항상 자식보다 커야 해요!

---

🔢 배열 인덱스로 힙 관계 표현

📍 0부터 시작하는 인덱스

// 노드 i의 관계
const parent = Math.floor((i - 1) / 2);
const leftChild = 2 * i + 1;
const rightChild = 2 * i + 2;

📍 1부터 시작하는 인덱스

// 노드 i의 관계
const parent = Math.floor(i / 2);
const leftChild = 2 * i;
const rightChild = 2 * i + 1;

---

💻 JavaScript로 최소 힙 구현하기

class MinHeap {
    constructor() {
        this.heap = [];
    }

    // 부모, 자식 인덱스 계산
    getParent(i) { return Math.floor((i - 1) / 2); }
    getLeft(i) { return 2 * i + 1; }
    getRight(i) { return 2 * i + 2; }

    // 두 노드 위치 바꾸기
    swap(i, j) {
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
    }

    // 삽입 - O(log n)
    push(value) {
        this.heap.push(value);  // 맨 끝에 추가
        this.heapifyUp(this.heap.length - 1);  // 위로 올리기
    }

    // 위로 올리기 (삽입 시)
    heapifyUp(index) {
        const parent = this.getParent(index);

        if (parent >= 0 && this.heap[parent] > this.heap[index]) {
            this.swap(index, parent);
            this.heapifyUp(parent);  // 재귀적으로 반복
        }
    }

    // 최솟값 제거 - O(log n)
    pop() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();

        const min = this.heap[0];
        this.heap[0] = this.heap.pop();  // 마지막 원소를 루트로
        this.heapifyDown(0);  // 아래로 내리기

        return min;
    }

    // 아래로 내리기 (삭제 시)
    heapifyDown(index) {
        const left = this.getLeft(index);
        const right = this.getRight(index);
        let smallest = index;

        // 왼쪽 자식과 비교
        if (left < this.heap.length && 
            this.heap[left] < this.heap[smallest]) {
            smallest = left;
        }

        // 오른쪽 자식과 비교
        if (right < this.heap.length && 
            this.heap[right] < this.heap[smallest]) {
            smallest = right;
        }

        // 자식이 더 작으면 교체
        if (smallest !== index) {
            this.swap(index, smallest);
            this.heapifyDown(smallest);
        }
    }

    // 최솟값 확인 (제거X) - O(1)
    peek() {
        return this.heap[0] || null;
    }

    // 크기 확인
    size() {
        return this.heap.length;
    }
}

// 사용 예제
const minHeap = new MinHeap();
minHeap.push(5);
minHeap.push(3);
minHeap.push(7);
minHeap.push(1);

console.log(minHeap.pop());  // 1
console.log(minHeap.pop());  // 3
console.log(minHeap.peek()); // 5 (제거X)

---

 

🎯 힙의 활용 (우선순위 큐)

📝 예제: K번째 최솟값 찾기

// 스트림에서 K번째로 작은 값 유지하기
class KthSmallest {
    constructor(k) {
        this.k = k;
        this.maxHeap = new MaxHeap();  // 최대 힙 사용
    }

    add(value) {
        this.maxHeap.push(value);

        // K개 초과하면 가장 큰 값 제거
        if (this.maxHeap.size() > this.k) {
            this.maxHeap.pop();
        }
    }

    getKthSmallest() {
        return this.maxHeap.peek();  // 루트가 K번째 최솟값
    }
}

📝 예제: 중앙값 찾기

// 두 개의 힙으로 중앙값 관리
class MedianFinder {
    constructor() {
        this.maxHeap = new MaxHeap();  // 작은 절반
        this.minHeap = new MinHeap();  // 큰 절반
    }

    addNum(num) {
        // 1. maxHeap에 추가
        this.maxHeap.push(num);

        // 2. 균형 맞추기
        this.minHeap.push(this.maxHeap.pop());

        // 3. 크기 조정
        if (this.minHeap.size() > this.maxHeap.size()) {
            this.maxHeap.push(this.minHeap.pop());
        }
    }

    findMedian() {
        if (this.maxHeap.size() > this.minHeap.size()) {
            return this.maxHeap.peek();
        }
        return (this.maxHeap.peek() + this.minHeap.peek()) / 2;
    }
}

---

🎯 백준 Class3 힙 대표 문제

📝 1927번 - 최소 힙

// 백준 제출용 코드
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

class MinHeap {
    // 위의 MinHeap 클래스 코드 동일
}

const n = Number(input[0]);
const heap = new MinHeap();
const result = [];

for (let i = 1; i <= n; i++) {
    const x = Number(input[i]);

    if (x === 0) {
        // 최솟값 출력 후 제거
        result.push(heap.pop() || 0);
    } else {
        // 값 추가
        heap.push(x);
    }
}

console.log(result.join('\n'));

---

 

📊 힙 시간복잡도 정리

연산	시간복잡도	설명
삽입 (push)	O(log n)	맨 끝에 추가 후 위로 이동
삭제 (pop)	O(log n)	루트 제거 후 재정렬
최댓값/최솟값 확인	O(1)	루트 확인
힙 생성	O(n)	Bottom-up 방식
힙 정렬	O(n log n)	모든 원소 pop

---

🎓 마무리하며

백준 Class3의 핵심 알고리즘 3가지를 정리했어요!

✅ DP: 큰 문제를 작은 문제로 나누어 해결
✅ DFS: 깊이 우선으로 그래프/트리 탐색
✅ Heap: 최댓값/최솟값을 빠르게 찾기

 

🔗 추가 학습 자료
• 백준 단계별로 풀어보기
• 프로그래머스 고득점 Kit
• LeetCode Top Interview Questions