알고리즘 — 동적 프로그래밍

개요 — 왜 동적 프로그래밍을 알아야 하는가

동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 더 작은 하위 문제로 분해하여 풀고, 그 결과를 저장해 재사용함으로써 불필요한 중복 연산을 제거하는 알고리즘 설계 패러다임입니다.

게임 개발에서 DP는 이론적 도구를 넘어 실전 시스템에 직접 적용됩니다.

• AI 캐릭터가 최소 비용 행동 시퀀스를 계획하는 의사결정 시스템
• 플레이어가 포인트를 효율적으로 분배하는 스킬 트리 최적화
• 절차적으로 맵을 생성하는 레벨 생성 알고리즘
• 여러 애니메이션 클립을 최소 비용으로 합성하는 블렌딩 최적화

---

1. 핵심 개념

1.1 최적 부분 구조 (Optimal Substructure)

전체 문제의 최적해가 부분 문제의 최적해로부터 구성될 수 있는 성질입니다.

예를 들어, A → C의 최단 경로가 A → B → C라면, 그 안에 포함된 A → B도 반드시 최단 경로여야 합니다. 이 성질이 있어야 부분 문제를 독립적으로 풀고 결합해 전체 최적해를 구성할 수 있습니다.

전체 문제: Fib(5)를 구하라
  ├─ 부분 문제: Fib(4) + Fib(3)
       ├─ Fib(3) + Fib(2)
       ├─ Fib(2) + Fib(1)
       ...

1.2 중복 부분 문제 (Overlapping Subproblems)

같은 하위 문제가 여러 번 반복해서 등장하는 성질입니다.

단순 재귀로 Fib(5)를 계산하면 Fib(3)이 2번, Fib(2)가 3번 호출됩니다. 이를 저장하지 않으면 지수 시간(O(2^n))이 소요됩니다. DP는 최초 계산 결과를 저장(메모이제이션)하거나 테이블에 미리 채워두어(타뷸레이션) 동일 계산을 O(1)에 재사용합니다.

Fib(5)
├─ Fib(4)
│   ├─ Fib(3)  ← 중복
│   └─ Fib(2)  ← 중복
└─ Fib(3)      ← 중복 발생 지점
    ├─ Fib(2)  ← 중복
    └─ Fib(1)

---

2. 메모이제이션(Top-Down) vs 타뷸레이션(Bottom-Up)

DP를 구현하는 방식은 크게 두 가지입니다.

구분	메모이제이션 (Top-Down)	타뷸레이션 (Bottom-Up)
방향	큰 문제 → 작은 문제 (재귀)	작은 문제 → 큰 문제 (반복)
구현	재귀 + 캐시(map/배열)	반복문 + DP 테이블
계산	필요한 부분만 계산 (Lazy)	모든 부분 문제를 순서대로 계산
스택 오버플로 위험	있음 (깊은 재귀)	없음
직관성	점화식을 그대로 코드로 표현	채우는 순서를 명시적으로 설계해야 함
공간 최적화	어려움	롤링 배열 등으로 쉽게 적용 가능

선택 기준:

• 모든 하위 문제가 필요하지 않을 때 → 메모이제이션
• 모든 하위 문제가 필요하고 공간 최적화가 중요할 때 → 타뷸레이션

---

3. 대표 DP 문제 I — 피보나치 수열

피보나치는 DP의 두 방식을 비교하기 가장 직관적인 예제입니다.

3.1 단순 재귀 (비효율)

// 지수 시간: O(2^n) — 같은 계산을 반복함
int64_t FibNaive(int32_t N)
{
    if (N <= 1)
    {
        return N;
    }
    return FibNaive(N - 1) + FibNaive(N - 2);
}

3.2 메모이제이션 (Top-Down)

#include <unordered_map>

// 시간: O(n), 공간: O(n)
int64_t FibMemo(int32_t N, std::unordered_map<int32_t, int64_t>& Memo)
{
    if (N <= 1)
    {
        return N;
    }

    auto It = Memo.find(N);
    if (It != Memo.end())
    {
        return It->second; // 캐시 히트 — 즉시 반환
    }

    int64_t Result = FibMemo(N - 1, Memo) + FibMemo(N - 2, Memo);
    Memo[N] = Result;
    return Result;
}

// 호출 예시
std::unordered_map<int32_t, int64_t> Memo;
int64_t Result = FibMemo(50, Memo); // 12586269025

3.3 타뷸레이션 (Bottom-Up)

#include <vector>

// 시간: O(n), 공간: O(n) → 롤링 배열로 O(1) 가능
int64_t FibTabulation(int32_t N)
{
    if (N <= 1)
    {
        return N;
    }

    std::vector<int64_t> Dp(N + 1, 0);
    Dp[0] = 0;
    Dp[1] = 1;

    for (int32_t I = 2; I <= N; ++I)
    {
        Dp[I] = Dp[I - 1] + Dp[I - 2];
    }

    return Dp[N];
}

// 공간 최적화: O(1) — 이전 두 값만 유지
int64_t FibOptimal(int32_t N)
{
    if (N <= 1)
    {
        return N;
    }

    int64_t Prev2 = 0;
    int64_t Prev1 = 1;

    for (int32_t I = 2; I <= N; ++I)
    {
        int64_t Current = Prev1 + Prev2;
        Prev2 = Prev1;
        Prev1 = Current;
    }

    return Prev1;
}

---

4. 대표 DP 문제 II — 0/1 배낭 문제 (Knapsack)

배낭에 담을 수 있는 무게 한도 내에서 가치의 합을 최대화하는 문제입니다. 각 아이템은 한 번만 사용할 수 있습니다.

• 입력: 아이템 N개, 각 아이템의 무게 Weight[i]와 가치 Value[i], 최대 무게 W
• 목표: sum(Weight[i]) <= W를 만족하면서 sum(Value[i])를 최대화

점화식:

Dp[i][w] = 아이템 i까지 고려하고 무게 한도가 w일 때 최대 가치

Dp[i][w] = max(
    Dp[i-1][w],             // 아이템 i를 선택하지 않음
    Dp[i-1][w - Weight[i]] + Value[i]  // 아이템 i를 선택 (Weight[i] <= w인 경우)
)

4.1 2D 타뷸레이션 구현

#include <vector>
#include <algorithm>

struct FItem
{
    int32_t Weight;
    int32_t Value;
};

// 시간: O(N * W), 공간: O(N * W)
int32_t Knapsack01(const std::vector<FItem>& Items, int32_t MaxWeight)
{
    const int32_t N = static_cast<int32_t>(Items.size());

    // Dp[i][w]: 아이템 0..i-1까지 고려, 무게 한도 w일 때 최대 가치
    std::vector<std::vector<int32_t>> Dp(N + 1, std::vector<int32_t>(MaxWeight + 1, 0));

    for (int32_t I = 1; I <= N; ++I)
    {
        const FItem& Item = Items[I - 1];

        for (int32_t W = 0; W <= MaxWeight; ++W)
        {
            // 기본: 이 아이템을 선택하지 않는 경우
            Dp[I][W] = Dp[I - 1][W];

            // 이 아이템을 선택할 수 있는 경우 (무게 조건 충족 시)
            if (Item.Weight <= W)
            {
                int32_t ValueWithItem = Dp[I - 1][W - Item.Weight] + Item.Value;
                Dp[I][W] = std::max(Dp[I][W], ValueWithItem);
            }
        }
    }

    return Dp[N][MaxWeight];
}

int main()
{
    // 아이템: {무게, 가치}
    std::vector<FItem> Items = {
        {2, 3},  // 무게 2, 가치 3
        {3, 4},  // 무게 3, 가치 4
        {4, 5},  // 무게 4, 가치 5
        {5, 6}   // 무게 5, 가치 6
    };

    int32_t MaxWeight = 8;
    int32_t MaxValue = Knapsack01(Items, MaxWeight);
    // MaxValue = 10 (아이템 1+3 선택: 무게 2+4=6, 가치 3+5=8
    //             또는 아이템 2+3 선택: 무게 3+4=7, 가치 4+5=9
    //             또는 아이템 1+4 선택: 무게 2+5=7, 가치 3+6=9
    //             또는 아이템 2+4 선택: 무게 3+5=8, 가치 4+6=10 ← 최대)

    return 0;
}

4.2 공간 최적화 — 1D DP (O(W))

2D 배열에서 현재 행은 직전 행(I-1)만 참조합니다. 1D 배열로 압축하되, 역방향 순회로 덮어쓰기 문제를 방지합니다.

// 시간: O(N * W), 공간: O(W) — 1D 롤링 배열
int32_t Knapsack01Optimized(const std::vector<FItem>& Items, int32_t MaxWeight)
{
    std::vector<int32_t> Dp(MaxWeight + 1, 0);

    for (const FItem& Item : Items)
    {
        // 역방향 순회: 같은 아이템이 중복 선택되는 것을 방지
        // 순방향으로 하면 Dp[W - Item.Weight]가 이미 이번 아이템을 선택한 값일 수 있음
        for (int32_t W = MaxWeight; W >= Item.Weight; --W)
        {
            Dp[W] = std::max(Dp[W], Dp[W - Item.Weight] + Item.Value);
        }
    }

    return Dp[MaxWeight];
}

---

5. 대표 DP 문제 III — 최장 공통 부분 수열 (LCS)

두 문자열 X와 Y에서 공통으로 나타나는 가장 긴 부분 수열(연속일 필요 없음) 의 길이를 구합니다.

• 예: X = “ABCBDAB”, Y = “BDCABA” → LCS = “BCBA” (길이 4)

점화식:

Dp[i][j] = X의 첫 i글자와 Y의 첫 j글자 사이의 LCS 길이

if X[i] == Y[j]:
    Dp[i][j] = Dp[i-1][j-1] + 1
else:
    Dp[i][j] = max(Dp[i-1][j], Dp[i][j-1])

5.1 2D 타뷸레이션 구현

#include <vector>
#include <string>
#include <algorithm>

// 시간: O(M * N), 공간: O(M * N)
int32_t LCSLength(const std::string& X, const std::string& Y)
{
    const int32_t M = static_cast<int32_t>(X.size());
    const int32_t N = static_cast<int32_t>(Y.size());

    // Dp[i][j]: X[0..i-1]와 Y[0..j-1]의 LCS 길이
    std::vector<std::vector<int32_t>> Dp(M + 1, std::vector<int32_t>(N + 1, 0));

    for (int32_t I = 1; I <= M; ++I)
    {
        for (int32_t J = 1; J <= N; ++J)
        {
            if (X[I - 1] == Y[J - 1])
            {
                Dp[I][J] = Dp[I - 1][J - 1] + 1;
            }
            else
            {
                Dp[I][J] = std::max(Dp[I - 1][J], Dp[I][J - 1]);
            }
        }
    }

    return Dp[M][N];
}

// LCS 실제 문자열 복원 (역추적)
std::string ReconstructLCS(const std::string& X, const std::string& Y)
{
    const int32_t M = static_cast<int32_t>(X.size());
    const int32_t N = static_cast<int32_t>(Y.size());

    std::vector<std::vector<int32_t>> Dp(M + 1, std::vector<int32_t>(N + 1, 0));

    for (int32_t I = 1; I <= M; ++I)
    {
        for (int32_t J = 1; J <= N; ++J)
        {
            if (X[I - 1] == Y[J - 1])
            {
                Dp[I][J] = Dp[I - 1][J - 1] + 1;
            }
            else
            {
                Dp[I][J] = std::max(Dp[I - 1][J], Dp[I][J - 1]);
            }
        }
    }

    // 역추적으로 실제 LCS 문자열 복원
    std::string LCS;
    int32_t I = M, J = N;

    while (I > 0 && J > 0)
    {
        if (X[I - 1] == Y[J - 1])
        {
            LCS += X[I - 1];
            --I;
            --J;
        }
        else if (Dp[I - 1][J] > Dp[I][J - 1])
        {
            --I;
        }
        else
        {
            --J;
        }
    }

    std::reverse(LCS.begin(), LCS.end());
    return LCS;
}

int main()
{
    std::string X = "ABCBDAB";
    std::string Y = "BDCABA";

    int32_t Length = LCSLength(X, Y);      // 4
    std::string Lcs = ReconstructLCS(X, Y); // "BCBA" 또는 "BDAB" (복수 정답 가능)

    return 0;
}

5.2 공간 최적화 — 두 행만 유지

// 시간: O(M * N), 공간: O(N) — 현재/이전 행만 유지
int32_t LCSLengthOptimized(const std::string& X, const std::string& Y)
{
    const int32_t M = static_cast<int32_t>(X.size());
    const int32_t N = static_cast<int32_t>(Y.size());

    std::vector<int32_t> PrevRow(N + 1, 0);
    std::vector<int32_t> CurrRow(N + 1, 0);

    for (int32_t I = 1; I <= M; ++I)
    {
        for (int32_t J = 1; J <= N; ++J)
        {
            if (X[I - 1] == Y[J - 1])
            {
                CurrRow[J] = PrevRow[J - 1] + 1;
            }
            else
            {
                CurrRow[J] = std::max(PrevRow[J], CurrRow[J - 1]);
            }
        }

        std::swap(PrevRow, CurrRow);
        std::fill(CurrRow.begin(), CurrRow.end(), 0);
    }

    return PrevRow[N];
}

---

5.5 대표 DP 문제 IV — 동전 교환 (Coin Change)

주어진 동전 종류로 목표 금액을 만들 때 필요한 최소 동전 수를 구합니다. 각 동전은 무한정 사용할 수 있습니다(무한 배낭 문제 변형).

• 입력: 동전 종류 Coins[], 목표 금액 Amount
• 목표: Coins를 사용해 Amount를 만드는 최소 동전 수 (불가능하면 -1)

점화식:

Dp[0] = 0                       (금액 0을 만드는 데 동전 0개)
Dp[a] = min(Dp[a - coin] + 1)   (coin ∈ Coins, a >= coin인 경우)

#include <vector>
#include <algorithm>
#include <climits>

// 시간: O(Amount × |Coins|), 공간: O(Amount)
int CoinChange(const std::vector<int>& Coins, int Amount)
{
    // Dp[a]: 금액 a를 만드는 최소 동전 수
    // INT_MAX/2로 초기화 (오버플로우 방지)
    std::vector<int> Dp(Amount + 1, INT_MAX / 2);
    Dp[0] = 0;

    for (int A = 1; A <= Amount; ++A)
    {
        for (int Coin : Coins)
        {
            if (Coin <= A)
            {
                Dp[A] = std::min(Dp[A], Dp[A - Coin] + 1);
            }
        }
    }

    return Dp[Amount] == INT_MAX / 2 ? -1 : Dp[Amount];
}

int main()
{
    // 예시 1: Coins = {1, 5, 6, 9}, Amount = 11
    // 최적: 9+1+1 = 3개 또는 6+5 = 2개 → 정답: 2
    std::vector<int> Coins1 = {1, 5, 6, 9};
    int Result1 = CoinChange(Coins1, 11); // 2

    // 예시 2: Coins = {2}, Amount = 3
    // 짝수 동전으로 홀수 금액 불가능 → 정답: -1
    std::vector<int> Coins2 = {2};
    int Result2 = CoinChange(Coins2, 3);  // -1

    return 0;
}

DP 테이블 추적 (Coins={1,5,6,9}, Amount=11):

Dp[0]  = 0
Dp[1]  = min(Dp[0]+1) = 1            (1동전)
Dp[5]  = min(Dp[4]+1, Dp[0]+1) = 1   (5동전)
Dp[6]  = min(Dp[5]+1, Dp[0]+1) = 1   (6동전)
Dp[10] = min(Dp[9]+1, Dp[4]+1, Dp[1]+1) = 2  (5+5 또는 9+1)
Dp[11] = min(Dp[10]+1, Dp[5]+1, Dp[2]+1) = 2  (5+6)

게임 개발 활용: 상점에서 정확한 잔돈을 최소 아이템 조합으로 계산하거나, 특정 스탯 목표에 도달하기 위한 최소 아이템 강화 횟수를 구할 때 활용됩니다.

// 게임 예시: 특정 공격력(targetAtk)에 도달하는 최소 강화석 사용 수
// 강화석 종류: {+1, +5, +10, +20} 공격력
int MinEnhancementStones(int TargetAtk)
{
    std::vector<int> StoneValues = {1, 5, 10, 20};
    return CoinChange(StoneValues, TargetAtk);
}

---

6. DP 최적화 기법 — 공간 복잡도 줄이기

DP 문제에서 시간 복잡도는 점화식에 의해 결정되지만, 공간 복잡도는 접근 패턴을 분석해 크게 줄일 수 있습니다.

6.1 롤링 배열 (Rolling Array)

현재 상태가 이전 1~2개 상태만 참조하는 경우, 전체 테이블 대신 필요한 행만 유지합니다.

// 피보나치: O(n) 공간 → O(1) 공간
// Dp[i] = Dp[i-1] + Dp[i-2]
// 참조: 직전 2개만 필요 → 변수 2개로 압축 가능

int64_t FibRolling(int32_t N)
{
    if (N <= 1) return N;

    int64_t A = 0; // Dp[i-2]
    int64_t B = 1; // Dp[i-1]

    for (int32_t I = 2; I <= N; ++I)
    {
        int64_t Next = A + B;
        A = B;
        B = Next;
    }
    return B;
}

6.2 1D 압축 (0/1 배낭의 역방향 순회)

2D DP 테이블에서 현재 행이 직전 행만 참조할 때, 1D 배열로 압축합니다. 0/1 배낭에서는 같은 아이템이 중복 사용되지 않도록 무게를 큰 값부터 내려가며 갱신합니다.

// 0/1 배낭 1D 압축 핵심 패턴
for (const FItem& Item : Items)
{
    for (int32_t W = MaxWeight; W >= Item.Weight; --W) // 역방향!
    {
        Dp[W] = std::max(Dp[W], Dp[W - Item.Weight] + Item.Value);
    }
}

6.3 분할 정복 최적화 & 모노토닉 큐 (심화)

일부 DP는 점화식 내부에 min 또는 max 연산이 포함되고, 최적 분할점이 단조증가하는 성질(Knuth’s Optimization)을 이용해 O(n²)을 O(n log n) 또는 O(n)으로 줄일 수 있습니다. 슬라이딩 윈도우 최댓값 문제에는 모노토닉 데크(Deque) 를 활용합니다.

#include <deque>

// 슬라이딩 윈도우 최댓값 — O(n)
// Dp[i] = max(Dp[j]) for j in [i-K, i-1] 형태의 점화식 최적화
std::vector<int32_t> SlidingWindowMax(const std::vector<int32_t>& Values, int32_t K)
{
    const int32_t N = static_cast<int32_t>(Values.size());
    std::vector<int32_t> Result;
    std::deque<int32_t> MonoDeque; // 인덱스 저장, 값은 단조 감소

    for (int32_t I = 0; I < N; ++I)
    {
        // 윈도우 범위를 벗어난 인덱스 제거
        while (!MonoDeque.empty() && MonoDeque.front() < I - K + 1)
        {
            MonoDeque.pop_front();
        }

        // 현재 값보다 작은 후미 인덱스 제거 (단조 감소 유지)
        while (!MonoDeque.empty() && Values[MonoDeque.back()] < Values[I])
        {
            MonoDeque.pop_back();
        }

        MonoDeque.push_back(I);

        if (I >= K - 1)
        {
            Result.push_back(Values[MonoDeque.front()]);
        }
    }

    return Result;
}

---

7. Unreal Engine 게임 개발에서의 DP 활용

7.1 AI 의사결정 — 최소 비용 행동 시퀀스

AI가 여러 행동 중 목표 달성 비용을 최소화하는 행동 시퀀스를 선택하는 데 DP를 적용할 수 있습니다. Behavior Tree의 상위 계층에서 전략적 행동 계획을 최적화하는 용도입니다.

AIActionPlanner.h

UCLASS()
class UMyAIActionPlanner : public UObject
{
    GENERATED_BODY()

public:
    // 행동 타입 정의
    UENUM(BlueprintType)
    enum class EAIAction : uint8
    {
        Patrol,
        Scout,
        Attack,
        Retreat,
        Heal
    };

    struct FActionCost
    {
        EAIAction Action;
        float StaminaCost;
        float ExpectedReward;
    };

    // DP로 N 스텝의 최대 보상 행동 시퀀스 계산
    // 현재 스태미나 제약 하에서 최대 기대 보상을 얻는 행동 플랜 반환
    TArray<EAIAction> PlanOptimalActionSequence(
        const TArray<FActionCost>& AvailableActions,
        float TotalStamina,
        int32 MaxSteps) const;

private:
    // Dp[step][stamina_bucket]: step번째에 stamina_bucket만큼 스태미나를 가진 상태의 최대 보상
    TArray<TArray<float>> DpTable;
};

AIActionPlanner.cpp

TArray<UMyAIActionPlanner::EAIAction> UMyAIActionPlanner::PlanOptimalActionSequence(
    const TArray<FActionCost>& AvailableActions,
    float TotalStamina,
    int32 MaxSteps) const
{
    // 스태미나를 정수 버킷으로 이산화 (0.1 단위)
    const int32 StaminaBuckets = FMath::RoundToInt(TotalStamina * 10.0f);
    const int32 N = AvailableActions.Num();

    // Dp[step][bucket] = 최대 보상
    TArray<TArray<float>> Dp;
    Dp.SetNum(MaxSteps + 1);
    for (TArray<float>& Row : Dp)
    {
        Row.Init(0.0f, StaminaBuckets + 1);
    }

    // 선택한 행동을 역추적하기 위한 테이블
    TArray<TArray<int32>> Choice;
    Choice.SetNum(MaxSteps + 1);
    for (TArray<int32>& Row : Choice)
    {
        Row.Init(-1, StaminaBuckets + 1);
    }

    // Bottom-Up DP (0/1 배낭 구조와 동일)
    for (int32 Step = 1; Step <= MaxSteps; ++Step)
    {
        for (int32 ActionIdx = 0; ActionIdx < N; ++ActionIdx)
        {
            const FActionCost& ActionData = AvailableActions[ActionIdx];
            int32 CostBucket = FMath::RoundToInt(ActionData.StaminaCost * 10.0f);

            for (int32 S = StaminaBuckets; S >= CostBucket; --S)
            {
                float RewardWithAction = Dp[Step - 1][S - CostBucket] + ActionData.ExpectedReward;
                if (RewardWithAction > Dp[Step][S])
                {
                    Dp[Step][S] = RewardWithAction;
                    Choice[Step][S] = ActionIdx;
                }
            }
        }
    }

    // 역추적으로 최적 행동 시퀀스 복원
    TArray<EAIAction> OptimalSequence;
    int32 RemainingBucket = StaminaBuckets;

    for (int32 Step = MaxSteps; Step >= 1; --Step)
    {
        int32 ActionIdx = Choice[Step][RemainingBucket];
        if (ActionIdx < 0)
        {
            break;
        }

        OptimalSequence.Insert(AvailableActions[ActionIdx].Action, 0);
        int32 CostBucket = FMath::RoundToInt(AvailableActions[ActionIdx].StaminaCost * 10.0f);
        RemainingBucket -= CostBucket;
    }

    return OptimalSequence;
}

7.2 스킬 트리 최적화 — 포인트 배분

플레이어가 제한된 스킬 포인트를 여러 스킬 카테고리에 배분할 때, 전체 효율(DPS, 생존력 등)을 최대화하는 배분을 DP로 계산합니다.

SkillTreeOptimizer.h

UCLASS()
class USkillTreeOptimizer : public UObject
{
    GENERATED_BODY()

public:
    // 각 스킬 카테고리에 포인트를 K만큼 투자했을 때의 효율 반환 함수 테이블
    // EfficiencyTable[CategoryIdx][Points] = 해당 카테고리에 Points만큼 투자 시 효율
    using FEfficiencyTable = TArray<TArray<float>>;

    // 총 스킬 포인트 TotalPoints를 CategoryCount개 카테고리에 배분하여 최대 효율 달성
    // 반환값: OptimalAllocation[i] = 카테고리 i에 배분할 포인트
    TArray<int32> OptimizeSkillPointAllocation(
        const FEfficiencyTable& EfficiencyTable,
        int32 TotalPoints) const;
};

SkillTreeOptimizer.cpp

TArray<int32> USkillTreeOptimizer::OptimizeSkillPointAllocation(
    const FEfficiencyTable& EfficiencyTable,
    int32 TotalPoints) const
{
    const int32 CategoryCount = EfficiencyTable.Num();

    // Dp[i][p] = 카테고리 0..i-1에 p포인트를 배분했을 때 최대 효율
    TArray<TArray<float>> Dp;
    Dp.SetNum(CategoryCount + 1);
    for (TArray<float>& Row : Dp)
    {
        Row.Init(0.0f, TotalPoints + 1);
    }

    TArray<TArray<int32>> Allocation;
    Allocation.SetNum(CategoryCount + 1);
    for (TArray<int32>& Row : Allocation)
    {
        Row.Init(0, TotalPoints + 1);
    }

    for (int32 CatIdx = 1; CatIdx <= CategoryCount; ++CatIdx)
    {
        const TArray<float>& CatEfficiency = EfficiencyTable[CatIdx - 1];

        for (int32 P = 0; P <= TotalPoints; ++P)
        {
            // 이 카테고리에 K포인트 투자 (K = 0 ~ P)
            for (int32 K = 0; K <= P && K < CatEfficiency.Num(); ++K)
            {
                float TotalEfficiency = Dp[CatIdx - 1][P - K] + CatEfficiency[K];
                if (TotalEfficiency > Dp[CatIdx][P])
                {
                    Dp[CatIdx][P] = TotalEfficiency;
                    Allocation[CatIdx][P] = K;
                }
            }
        }
    }

    // 역추적으로 각 카테고리 배분 포인트 복원
    TArray<int32> OptimalAllocation;
    OptimalAllocation.SetNum(CategoryCount);

    int32 RemainingPoints = TotalPoints;
    for (int32 CatIdx = CategoryCount; CatIdx >= 1; --CatIdx)
    {
        int32 AllocatedPoints = Allocation[CatIdx][RemainingPoints];
        OptimalAllocation[CatIdx - 1] = AllocatedPoints;
        RemainingPoints -= AllocatedPoints;
    }

    return OptimalAllocation;
}

7.3 절차적 레벨 생성 — 구간 분할 최적화

레벨을 여러 구역(Zone)으로 나눌 때, 각 구역의 난이도 편차를 최소화하도록 최적 분할점을 DP로 결정합니다.

// 레벨을 K개 구역으로 나눌 때 구역 간 난이도 분산을 최소화
// Difficulty[i]: i번째 방의 난이도
// 목표: K개 구역으로 분할하여 구역 내 난이도 편차 합계 최소화

float ZoneCost(const TArray<float>& Difficulty, int32 StartIdx, int32 EndIdx)
{
    // 구역의 비용: 구역 내 최대-최소 난이도 차이 (편차)
    float MaxDiff = Difficulty[StartIdx];
    float MinDiff = Difficulty[StartIdx];

    for (int32 I = StartIdx + 1; I <= EndIdx; ++I)
    {
        MaxDiff = FMath::Max(MaxDiff, Difficulty[I]);
        MinDiff = FMath::Min(MinDiff, Difficulty[I]);
    }

    return MaxDiff - MinDiff;
}

// Dp[i][k] = 방 0..i를 k개 구역으로 분할했을 때 최소 비용
TArray<int32> OptimalLevelPartition(const TArray<float>& Difficulty, int32 ZoneCount)
{
    const int32 RoomCount = Difficulty.Num();
    constexpr float Inf = TNumericLimits<float>::Max();

    TArray<TArray<float>> Dp;
    Dp.SetNum(RoomCount);
    for (TArray<float>& Row : Dp)
    {
        Row.Init(Inf, ZoneCount + 1);
    }

    TArray<TArray<int32>> Split;
    Split.SetNum(RoomCount);
    for (TArray<int32>& Row : Split)
    {
        Row.Init(0, ZoneCount + 1);
    }

    // 기저 조건: 1개 구역으로 나누는 경우
    for (int32 I = 0; I < RoomCount; ++I)
    {
        Dp[I][1] = ZoneCost(Difficulty, 0, I);
    }

    // Bottom-Up DP
    for (int32 K = 2; K <= ZoneCount; ++K)
    {
        for (int32 I = K - 1; I < RoomCount; ++I)
        {
            for (int32 J = K - 2; J < I; ++J)
            {
                float Cost = Dp[J][K - 1] + ZoneCost(Difficulty, J + 1, I);
                if (Cost < Dp[I][K])
                {
                    Dp[I][K] = Cost;
                    Split[I][K] = J;
                }
            }
        }
    }

    // 분할점 역추적
    TArray<int32> Partition;
    int32 End = RoomCount - 1;
    int32 K = ZoneCount;

    while (K > 1)
    {
        int32 SplitPoint = Split[End][K];
        Partition.Insert(SplitPoint + 1, 0); // 구역 시작 인덱스
        End = SplitPoint;
        --K;
    }
    Partition.Insert(0, 0);

    return Partition; // 각 구역의 시작 방 인덱스 목록
}

7.4 애니메이션 블렌딩 최적화 — 최적 가중치 배분

여러 애니메이션 클립을 블렌딩할 때, 타겟 포즈와의 차이를 최소화하는 가중치 조합을 DP로 탐색합니다. 가중치를 이산화한 뒤 배낭 문제 구조로 풀 수 있습니다.

// 블렌딩 가중치 최적화 개념 예시
// AnimationClips: 각 클립의 특성 벡터 (속도, 방향, 에너지 레벨 등)
// TargetPose: 목표 포즈 특성 벡터
// 목표: 가중치 합 = 1.0 제약 하에 타겟과의 차이(비용)를 최소화

UCLASS()
class UAnimationBlendOptimizer : public UObject
{
    GENERATED_BODY()

public:
    struct FAnimClipFeature
    {
        FName ClipName;
        float Speed;
        float Direction; // -1.0 (왼쪽) ~ 1.0 (오른쪽)
        float EnergyLevel;
    };

    // 이산화된 가중치 스텝(WeightSteps개)으로 나누어 DP 최적화
    // 반환: 각 클립의 블렌딩 가중치 (합계 = 1.0)
    TArray<float> OptimizeBlendWeights(
        const TArray<FAnimClipFeature>& Clips,
        const FAnimClipFeature& TargetPose,
        int32 WeightSteps = 10) const;

private:
    // 두 포즈 사이의 비용 (유클리드 거리의 제곱)
    float ComputeBlendCost(
        const TArray<FAnimClipFeature>& Clips,
        const TArray<float>& Weights,
        const FAnimClipFeature& Target) const
    {
        float BlendedSpeed = 0.0f;
        float BlendedDir = 0.0f;
        float BlendedEnergy = 0.0f;

        for (int32 I = 0; I < Clips.Num(); ++I)
        {
            BlendedSpeed += Weights[I] * Clips[I].Speed;
            BlendedDir += Weights[I] * Clips[I].Direction;
            BlendedEnergy += Weights[I] * Clips[I].EnergyLevel;
        }

        float DSpeed = BlendedSpeed - Target.Speed;
        float DDir = BlendedDir - Target.Direction;
        float DEnergy = BlendedEnergy - Target.EnergyLevel;

        return DSpeed * DSpeed + DDir * DDir + DEnergy * DEnergy;
    }
};

실전 참고: Unreal Engine의 UBlendSpace와 AnimationBlueprintLibrary는 내부적으로 삼각 분할(triangulation) 기반의 블렌딩을 사용합니다. 커스텀 블렌드 로직이 필요한 경우, 위 DP 접근을 UAnimInstance::NativeUpdateAnimation에서 호출해 매 프레임 최적 가중치를 갱신할 수 있습니다.

MyAnimInstance.cpp

void UMyAnimInstance::NativeUpdateAnimation(float DeltaSeconds)
{
    Super::NativeUpdateAnimation(DeltaSeconds);

    // DP 기반 블렌드 가중치 최적화는 매 프레임 실행 시 비용이 큼
    // 상태 변화가 있을 때만 재계산 (이벤트 드리븐)
    if (bBlendWeightsDirty)
    {
        UAnimationBlendOptimizer* Optimizer = GetWorld()
            ->GetSubsystem<UAnimationBlendOptimizerSubsystem>()
            ->GetOptimizer();

        if (Optimizer)
        {
            OptimalBlendWeights = Optimizer->OptimizeBlendWeights(
                AvailableClips, CurrentTargetPose);
            bBlendWeightsDirty = false;
        }
    }
}

---

핵심 요약

항목	메모이제이션 (Top-Down)	타뷸레이션 (Bottom-Up)
구현 도구	재귀 + std::unordered_map / 배열	반복문 + std::vector / TArray
계산 범위	필요한 부분만 (Lazy)	전체 하위 문제
스택 위험	있음	없음
공간 최적화	어려움	롤링 배열 / 1D 압축 용이

문제 유형	시간 복잡도	공간 복잡도 (원본)	공간 복잡도 (최적화)
피보나치	O(n)	O(n)	O(1) — 변수 2개
0/1 배낭	O(N·W)	O(N·W)	O(W) — 역방향 1D
LCS	O(M·N)	O(M·N)	O(N) — 두 행 교체

Unreal Engine 실전 적용 패턴:

• AI 의사결정: 스태미나 제약 하에 최대 보상 행동 시퀀스 계획 (0/1 배낭 구조)
• 스킬 트리 최적화: 포인트 배분으로 전체 효율 최대화 (구간 배분 DP)
• 레벨 생성: 난이도 편차 최소화 구역 분할 (구간 분할 DP)
• 애니메이션 블렌딩: 타겟 포즈 오차 최소화 가중치 배분 (연속 배낭 구조)

동적 프로그래밍은 “무조건 다 시도해보는” 완전 탐색의 반대편에 있는 개념입니다. 문제에 최적 부분 구조와 중복 부분 문제 성질이 있음을 인식하는 순간, 지수 시간 알고리즘을 다항 시간으로 전환할 수 있습니다. Unreal Engine C++ 개발자라면 이 패턴을 AI, 스킬 시스템, 절차적 콘텐츠 생성에서 적극적으로 활용할 수 있어야 합니다.