[알고리즘] DP(동적 프로그래밍)란? (백준 11050, 1010)

📌 핵심 요약

• DP는 큰 문제를 작은 문제로 쪼개고, 이미 계산한 값을 저장해 재사용하는 알고리즘 기법입니다.
• 파스칼의 삼각형은 이항 계수를 DP로 표현한 대표적인 예시입니다.
• 문제풀이 과정에서 이항계수의 로직을 재귀 또는 DP를 활용하여 풀이했을 때, 차이점을 알아보려고 합니다. 
• DP를 활용해 백준 11050 · 1010번을 오버플로우 없이 효율적으로 풀 수 있습니다.

 

 

목차

1 DP(동적 프로그래밍)란?

DP(Dynamic Programming, 동적 프로그래밍)는 큰 문제를 작은 부분 문제로 쪼개어, 이미 계산한 값을 배열에 저장해두고 필요할 때 다시 꺼내 쓰는 알고리즘 설계 기법입니다.

💡

한 줄 정의

"이미 푼 문제는 다시 풀지 않는다" — 중복 계산을 없애 효율을 극적으로 높이는 기법

DP의 두 가지 핵심 조건

조건	설명	예시
① 중복 부분 문제 Overlapping Subproblems	같은 작은 문제가 반복해서 등장한다	C(5,2)를 구할 때 C(4,1)이 여러 번 필요
② 최적 부분 구조 Optimal Substructure	큰 문제의 답이 작은 문제의 답으로 구성된다	C(5,2) = C(4,1) + C(4,2)

재귀 vs DP

일상에서의 예시로 설명하면, 매번 1+1+1+1+1을 계산하는 대신 "5"라는 답을 메모지에 적어두고 꺼내 쓰는 것이 바로 DP입니다. 프로그래밍에서는 이 메모지 역할을 배열(dp[ ])이 합니다.

⚠️

재귀만 쓰면 느린 이유

피보나치를 일반 재귀로 구현하면 fib(40)을 구하기 위해 같은 값을 수억 번 다시 계산합니다. DP를 쓰면 단 40번의 연산으로 끝납니다.

2 파스칼의 삼각형이란?

백준 11050 · 1010번은 이항계수를 활용한 문제들로 이는 파스칼의 삼각형을 이용해 풀이할 수 있습니다.

파스칼의 삼각형은 이항 계수를 삼각형 모양으로 배열한 수표로 DP의 대표적인 예시입니다.

N번째 행의 K번째 값이 정확히 C(N, K)와 같습니다.

핵심 규칙 2가지

ℹ️

점화식

dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
바로 위 왼쪽 + 바로 위 오른쪽. 양쪽 끝은 항상 1.

규칙	수식	설명
양쪽 끝은 항상 1	C(N,0) = C(N,N) = 1	어떤 행이든 첫째·마지막 값은 1
나머지 = 위 두 값의 합	C(N,K) = C(N-1,K-1) + C(N-1,K)	바로 위 왼쪽 + 바로 위 오른쪽

이항 계수와의 관계

파스칼의 삼각형을 미리 계산해두면 C(N, K)를 dp[N][K] 한 번의 배열 조회로 O(1)에 바로 얻을 수 있습니다. 예를 들어 C(5,2) = 10은 5번째 행 3번째 값으로 바로 확인됩니다.

3 파스칼의 삼각형을 DP로 구현하기

점화식 dp[i][j] = dp[i-1][j-1] + dp[i-1][j]를 그대로 코드로 옮기면 됩니다.

30×30 배열에 미리 전처리해두면 이후 조회는 dp[n][k] 한 줄로 끝납니다.

 

Java — 파스칼의 삼각형 DP 전처리

static int[][] dp = new int[30][30];

static void precompute() {
    for (int i = 0; i < 30; i++) {
        dp[i][0] = dp[i][i] = 1;      // 양쪽 끝은 항상 1
        for (int j = 1; j < i; j++) {
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
            //       ↑ 위 왼쪽            ↑ 위 오른쪽
        }
    }
}

💡

왜 30×30 배열인가?

백준 1010번의 제약이 N, M < 30이기 때문입니다. 미리 전처리해두면 이후 조회는 dp[m][n] 한 줄로 O(1)에 끝납니다.

4 백준 11050 — 이항 계수 1

BOJ #11050

이항 계수 1

1 ≤ N ≤ 10 · 시간제한 1초

난이도: Bronze I

자연수 N과 정수 K가 주어졌을 때 이항 계수 C(N, K)를 구하시오.

풀이 과정

1. 파스칼의 삼각형을 11×11 배열에 전처리한다.
2. N과 K를 입력받는다.
3. dp[N][K]를 출력한다.

 

Java — BOJ 11050 정답 코드

import java.util.Scanner;

public class Main {
    static int[][] dp = new int[11][11];

    static void precompute() {
        for (int i = 0; i <= 10; i++) {
            dp[i][0] = dp[i][i] = 1;
            for (int j = 1; j < i; j++)
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        precompute();
        int n = sc.nextInt();
        int k = sc.nextInt();
        System.out.println(dp[n][k]);
    }
}

입출력 예시

입력	출력	계산
5 2	10	C(5,2) = 5!/(2!·3!) = 10
10 5	252	C(10,5) = 252

5 백준 1010 — 다리 놓기

BOJ #1010

다리 놓기

0 < N ≤ M < 30 · 시간제한 0.5초

난이도: Silver V

서쪽 N개 사이트를 동쪽 M개 사이트에 겹치지 않게 연결하는 경우의 수 = C(M, N)

풀이 과정

1. 파스칼의 삼각형을 30×30 배열에 전처리한다.
2. 테스트케이스 T를 입력받는다.
3. 각 케이스에서 N, M을 입력받아 dp[M][N]을 출력한다.

💡

왜 C(M, N)인가?

다리가 겹치지 않으려면 동쪽 M개 중 N개를 순서를 유지하며 선택해야 합니다. 선택 후 위에서부터 1:1 매핑하면 자동으로 교차하지 않으므로 답은 조합 C(M, N)이 됩니다.

 

Java — BOJ 1010 정답 코드

import java.util.Scanner;

public class Main {
    static int[][] dp = new int[30][30];

    static void precompute() {
        for (int i = 0; i < 30; i++) {
            dp[i][0] = dp[i][i] = 1;
            for (int j = 1; j < i; j++)
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        precompute();
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            System.out.println(dp[m][n]);  // C(M, N)
        }
    }
}

입출력 예시

입력	출력	계산
2 2	1	C(2,2) = 1
1 5	5	C(5,1) = 5
13 29	67863915	C(29,13)

 

6재귀 / DP 풀이 비교 정리

재귀 풀이 예시

 

 

Java — BOJ 11050 정답 코드

import java.util.Scanner;

public class Main {

    // n! 을 반환하는 팩토리얼 함수
    static int factorial(int n) {
        if (n <= 1) return 1;
        return n * factorial(n - 1);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();

        // C(N, K) = N! / (K! * (N-K)!)
        int result = factorial(N) / (factorial(K) * factorial(N - K));
        System.out.println(result);
    }
}

구분	팩토리얼 방식	파스칼 삼각형 (DP)
오버플로우	위험 (N≥13)	안전
조회 속도	O(N) — 매번 계산	O(1) — 배열 조회
전처리 비용	없음	O(N²) — 1회만
다중 쿼리	느려질 수 있음	매우 빠름
추천 상황	N ≤ 10, 단일 쿼리	N ≥ 13 또는 다중 쿼리

✅

결론

이항 계수 문제는 파스칼의 삼각형 DP로 구현하는 것이 안전하고 확장성이 좋습니다. 다중 테스트케이스 문제에서는 미리 전처리하는 방식이 필수입니다.

🚨

팩토리얼 방식 사용 시 주의

N이 13 이상이면 int는 물론 long으로도 중간 계산 값이 오버플로우됩니다. 반드시 파스칼 DP 또는 분할 계산 방식을 사용하세요.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.