자료구조 · 알고리즘 기초집LESSON 22

동적 계획법 기초: 중복 계산을 줄이는 방법

난이도초급 → 중급 입문

예상 시간40분

선수지식이전 강의

22강. 동적 계획법 기초: 중복 계산을 줄이는 방법

1. 이번 강의에서 해결할 문제

한 칸 또는 두 칸씩 이동해 최대 점수를 구하는 재귀는 같은 스테이지의 최댓값을 여러 번 다시 계산합니다.

2. 학습 목표

3. 핵심 개념

동적 계획법은 겹치는 부분 문제와 최적 부분 구조가 있을 때 작은 답을 저장해 재사용합니다. 먼저 dp[i]가 무엇인지 한 문장으로 정의하고, 이전 상태에서 현재 상태로 오는 점화식과 초기값을 세웁니다. 모든 재귀가 DP는 아니며 상태가 충분한 정보를 담는지 검증해야 합니다.

4. 단계별 실습

1. 예제 파일 작성

실행 환경: 코드 편집기

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: 같은 이름의 파일이 있다면 덮어쓰기 전에 Git diff로 변경 범위를 확인합니다. 선택한 LTS JDK의 java -version과 javac -version이 모두 실행되어야 합니다.

대상 파일: src/StageScoreDp.java

src/StageScoreDp.java
import java.util.Arrays;

public class StageScoreDp {
    static int maxScore(int[] scores) {
        if (scores.length == 0) return 0;
        int[] dp = new int[scores.length + 1];
        dp[1] = scores[0];
        for (int i = 2; i <= scores.length; i++) {
            dp[i] = scores[i - 1] + Math.max(dp[i - 1], dp[i - 2]);
        }
        System.out.println("DP 표: " + Arrays.toString(dp));
        return dp[scores.length];
    }

    public static void main(String[] args) {
        System.out.println("최대 점수: " + maxScore(new int[]{100, 30, 250, 50}));
    }
}

2. PowerShell에서 컴파일·실행

실행 환경: Windows PowerShell

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: src/StageScoreDp.java가 저장되었고 out 폴더에는 삭제해도 되는 컴파일 결과만 있는지 확인합니다.

대상: src/StageScoreDp.java와 out 아래 생성되는 class 파일

Windows PowerShell
Set-Location C:\dev\game-ranking-algorithms
New-Item -ItemType Directory -Force .\out | Out-Null
javac -Xlint:all -d .\out .\src\StageScoreDp.java
java -cp .\out StageScoreDp

예상 결과: DP 표와 함께 1칸 또는 2칸 이동으로 얻는 최대 점수 400이 출력됩니다.

실행 시간은 PC의 CPU·메모리, JDK 버전, JVM 워밍업, 백그라운드 작업과 입력 분포에 따라 달라질 수 있습니다. 측정값은 같은 조건에서 여러 번 비교하고 Big-O 분석과 함께 해석합니다.

5. 코드와 알고리즘이 동작하는 이유

dp[i]는 i번째 스테이지에 도착했을 때의 최대 누적 점수입니다. 직전 또는 두 칸 전에서 오므로 두 상태 중 큰 값에 현재 점수를 더합니다. 각 상태를 한 번 계산해 O(n) 시간, 표 O(n) 공간이며 이전 두 값만 유지하면 O(1) 공간으로 줄일 수 있습니다.

6. 자주 하는 실수와 해결법

7. 직접 실습

8. 이해 점검 질문 3개

9. 핵심 요약

MINI QUIZ