아지트 듀오 휴게실 계산기의 Dynamic Programming 구조와 최적화 전략

2025년 9월 24일8분 읽기
알고리즘Dynamic Programming최적화

휴게실 계산기에 적용된 DP 구조와 다양한 최적화 기법을 상세히 분석합니다. Greedy 알고리즘의 한계부터 비트 연산 최적화까지 실제 구현 경험을 바탕으로 설명합니다.

광고 로딩 중...
Advertisement

아지트 듀오 휴게실 계산기의 이중 Dynamic Programming 구조와 최적화 전략

개요

휴게실 계산기는 메이플스토리의 특수 이벤트인 "아지트 듀오 휴게실"에서 9주간 최적의 스킬 투자 전략을 계산하는 도구입니다. 두 가지 서로 다른 레벨의 Dynamic Programming을 포함해 몇 가지 최적화를 위한 전략이 도입되어 있어, 약간 말을 해 보고자 합니다.

문제의 복잡성과 DP가 필요한 이유

1. 문제 정의

  • 목표: 9주간 주어진 포인트로 3개 스킬(장기 휴식, 역동적 휴식, 간식 충전)을 업그레이드하여 총 경험치를 최대화
  • 제약 조건:
    • 주간 포인트 한계 (주당 최대 20포인트)
    • 스킬 레벨 제한 (0~8레벨)

2. 왜 Dynamic Programming으로 접근하는가?

단순 Greedy Algorithm으로는 해결할 수 없는 이유: 부스트 효과로 인한 비선형성

휴게실 콤보 루틴 (스킬 2개 5레벨 이상): 1.68배
휴식 삼종 세트 (스킬 3개 3레벨 이상): 1.59배
휴식 스페셜리스트 (스킬 1개 7레벨 이상): 1.58배
휴게실 입문자 (스킬 1개 5레벨 이상, 다른 스킬 1개 3레벨 이상): 1.56배

스킬 레벨의 조합에 따른 부스트 효과가 계단식으로 변하기 때문에, 매 순간 가장 좋아 보이는 선택이 전체적으로 최적이 아닐 수 있습니다.

단순순 Greedy Algorithm으로는 해결할 수 없는 이유: 장기 휴식의 타이밍 의존성

모든 스킬은 "스킬을 올리는 순간" 배율이 적용되고, 그 이전에 시간을 썼다면 소급 적용되지 않습니다.

당연히 역동적 휴식과 간식 충전의 경우 경험치 배율이 증가하므로, 시간을 쓰기 전에 올리는 것이 무조건적으로 좋습니다. 여기에는 이견이 있을 수 없습니다.

다만 장기 휴식의 경우 레벨을 올리면 오히려 경험치 배율은 감소하고, 이에 따라 스킬을 올리기 전 시간을 모두 소모하고 이후에 올리게 되면, 기존 시간은 높은 배율로 얻고, 낮은 배율이겠지만 추가로 시간을 얻어 전체 획득량을 최적화할 수 있습니다.

문제는, 추가적인 변수가 있습니다. 부스트 효과가 적용되는 경우, 장기 휴식을 올리고도 배율이 증가할 수 있습니다. 예컨대 장기 휴식 6레벨의 경우 경험치 배율은 17%지만(부스트 효과 없음), 7레벨이 되면 경험치 배율 11%에 휴식 스페셜리스트 부스트를 받으면 1.58배가 곱해져 17.38%로 오히려 기존 대비 0.38%p 증가합니다. 이런 경우 레벨을 먼저 올리면 부스트 효과를 감안하여 전체 경험치 배율이 증가하게 됩니다.

정리하자면,

  • 선업글: 업그레이드 → 전체 시간에 새로운 배율 적용
  • 선소진: 시간 소진 → 업그레이드 → 추가된 시간에만 새로운 배율 적용

로 스킬을 올릴 때 두 가지 전략을 나눌 수 있습니다.

완전탐색으로는 해결하기 힘든 이유: 완전탐색의 복잡성

9주간 총 180포인트를 얻을 수 있고, 이로 인해 상태 공간은 제한되긴 합니다.

그럼에도 불구하고 완전탐색으로 하는 경우 0~8레벨의 스킬 3종 조합이 매 주차별로 별도로 계산되고, 각각에 대해 스킬 업그레이드 타이밍까지 고려해야 합니다. 대강 스킬은 총 10번 업그레이드가 가능할 것이고, 각각에 대해 8레벨까지만 업그레이드가 되므로, 스킬 업그레이드 조합은 3개 값의 배치 조합을 10개 두는 것이고, 하나가 9레벨 혹은 10레벨이 되는 경우를 제외하는 것이므로

310−(31)×[(109)×(3−1)10−9+(1010)×(3−1)10−10]3^{10} - \binom{3}{1} \times \left[ \binom{10}{9} \times (3-1)^{10-9} + \binom{10}{10} \times (3-1)^{10-10} \right]

= 58986 가지 경우가 생기게 됩니다.

여기서 장기 휴식의 경우 선업글/선소진을 나누어서 생각해야 하므로 스킬 업그레이드 선택지는 3종이 아닌 4종이 되고, 이 경우에 대강 103만 가지 경우로 증가합니다.

이상적인 경우에 부스트가 생기지 않는 경우 무조건 선소진이 유리할 것이고 이에 따라 3/5/7레벨 구간을 제외하면 선업글 분기를 하지 않는다던지 하는 추가적인 최적화의 여지가 있습니다. 반대로 완전 탐색이나 이런 비스무리한걸 하는 데는 비 직관적인 결과가 나올 수 있는지 검증을 하기 위함도 있기에 의도적인 비효율화도 고려하여야 합니다. 예컨대 실제로 이번 이벤트에서 이런 경우가 있을지는 모르겠지만, 특정 주차에 포인트를 사용하지 않고 이월시킨 다음 이후에 포인트를 몰아서 쓰는 게 더 최적인지 검증을 해 봐야겠죠(예컨대 장기 휴식을 선소진하게 되면 장기 휴식을 올리는 앞선 주차가 경험치가 더 나오는 경우도 있으니까요). 이런 부분들을 고려하면 주차별로 어떤 상태로 나누어서 진행할 것인지도 확인해야 할 것이고, 이런저런 부분을 고려하기 시작하면 완전 탐색은 상당히 난감해집니다.

Dynamic Programming의 적용: 독립적인 문제로 나누기

많은 경우의 수를 고려해야 하지만 최적화가 필요한 경우 자주 사용되는 기법은 분할 정복이고, 그 중에 다이나믹 프로그래밍(Dynamic Programming, DP, 기억하며 풀기, 나무위키 DP)이 있습니다.

이 문제의 경우, 꽤 단순화할 수 있는 편에 속합니다. 문제를 줄여볼까요? 총 9주차가 아니라, 특정 주차에 얻는 경험치를 최대화하는 문제로 바꿔 봅시다. 예컨대 내가 30포인트가 있고, 현재 스킬 레벨이 1/0/1레벨이면, 어떻게 이번 주에 경험치를 최대한으로 얻을 수 있을까? 라는 문제가 되는 것이죠.

이런 특정 주차의 문제로 바꾸게 되면 중요한 것은 남은 포인트와 현재 스킬 레벨만 남으며, 현재 스킬 레벨에 도달하기까지 어떤 과정을 거쳐왔는가 는 전혀 고려 대상이 아닙니다. 그러니까 1주차에 아무것도 안하다가 2주차에 1/0/1을 찍고 왔건, 1주차에 1/0/0을 찍고 2주차에 1/0/1을 찍고 왔건, 지금 이 문제를 푸는 데는 어떠한 영향도 없습니다.

그러면 여기서 한 발 더 나아가서, 내가 30포인트가 있고, 지금 3주차고, 현재 스킬 레벨이 1/0/1레벨이면, 어떻게 해서 누적 경험치를 최대화하는가의 문제는 어떻게 될까요? 단순합니다. 지금 이 상태에 도달할 때까지 얻은 최대 누적 경험치 + 지금 현재 상태에서 얻을 수 있는 이번 주 최대 경험치 가 됩니다. 그러면 여기서 생각해야 할 것은 지금 이 상태에 도달할 때까지 얻은 최대 누적 경험치 가 어떻게 되는지 입니다. 이것도 단순합니다. 지금 이 상태를 한 단계 전으로 돌려서 똑같은 문제를 풀게 하면 됩니다.

즉, 1주차부터 나아가면서, 남은 포인트 와 현재 스킬 레벨 의 조합에 대해 각각 누적 경험치의 최댓값을 갱신시키면서 다음주로 나아가는겁니다.

for 1~9주차:
  for 이번 주에 남은 포인트, 현재 스킬 레벨 조합 in 이번 주에 도달 가능했던 조합들:
    for 가능한 스킬레벨업 조합(이번 주에 남은 포인트, 현재 스킬 조합):
      이번 경험치 = 스킬 레벨 업을 통해 얻을 수 있는 경험치
      누적 경험치 = 이전 누적 경험치 + 이번 경험치
      if 누적 경험치 > 최대 경험치[다음 주][스킬레벨업 후 남은 포인트, 이후 스킬 레벨]:
        최대 경험치[다음 주][스킬레벨업 후 남은 포인트, 이후 스킬 레벨] = 누적 경험치
진짜 최종 경험치 = max( 최대 경험치[다음주][모든 조합] )

를 하면 되는 것이죠.

여기에 더해서 사실 이번 문제의 경우 어떤 경로로 가야 하는지를 알기 위한 목적이 더 큽니다. 이 경우에는 DP에 역추적 경로를 기록해 둠으로써 비교적 간단히 해결할 수 있습니다. 위에서 if... 최대 경험치[...] = ... 부분을 갱신할 때, 어디에서 어떤 경로로 가서 최대 경험치를 도달했는지를 기록해둡니다. 이후 진짜 최종 경험치가 어디에 있는지를 바탕으로, 매 칸 어디에서 어떤 경로로 가서를 바탕으로 어떤 경로로 왔는지를 역추적해서 경로를 재구성하는 방식입니다.

조금 더 나아가서

DP에서 고려할 점은 아직 한 개 더 있습니다. 이건 나중 섹션에서 자연스럽게 나올 테니 넘어가고요.

아무튼 DP로 문제를 단순화해버렸으니, 변수를 조금 더 늘리는 데는 지장이 없습니다. 어차피 문제 하나 푸는거고, 주차 최대 9개, 스킬 최대 3종/8레벨에 또 많이 올려봤자 11레벨 정도일거요. 그리고 위에서 굳이 이번 주에 남은 포인트, 현재 스킬 조합 이라고 거창하게 적어 뒀지만, 현재 스킬 조합만 있으면 어차피 매주 얻는 포인트 20p고, 주차가 저기 있으니까 그냥 20∗week20*week에 현재 스킬 조합에 필요한 포인트 빼면 나오니 포인트는 없어도 됩니다. 뭐 총 레벨 제한 없어도 9∗8∗8∗89*8*8*8개의 배열로 충분하고, 연산도 일단 최대 경험치 계산을 잘 한다 치면 몇 번 안 되겠죠. 최적화를 대충 해도 현재 상태에서 1초 안에 결과를 얻는데는 지장이 없을 겁니다.

이러면 문제의 변수를 좀 더 늘려도 됩니다. 예컨대, 이번 주에 시간이 얼마 안 남았다던지, 주차별 포인트가 20p가 아니라던지요. 시간이 얼마 안 남았어도 이건 첫 주차에만 고려될 대상일거고, 원래 하던 시간 연산 조금 더 하면 됩니다. 주차별 포인트가 20p가 아니면, 20∗주20*주로 총 포인트 계산하는거 해당 주까지 포인트 누적으로 바꾸면 됩니다. 또 변수를 더 늘릴 여지야 있겠지만, 딱히 떠오르는 건 없으니 이정도에서 마무리합니다. 사실 이 두 개 변수는 계산 과정에서의 변수는 아니고 초기 상태의 변수라서, 또 시간 복잡도가 늘어나진 않긴 한데, 또 어떻게 보면 최적화를 통해 연산 시간을 줄였기 때문에 이런저런 초기값에 대해서 빠르게 확인할 수 있도록 한 거라서 살짝 끼워넣어 봤습니다.

이중 DP 구조의 설계

Level 1: 주차별 전체 전략 최적화 (Forward DP)

구성

앞서 설명드린 Dynamic Programming의 적용 그 자체입니다. 사실 코드도 위에서 설명드린 부분이랑 다르지 않기 때문에, 여기는 자세한 설명을 생략하겠습니다.

코드

const findOptimalPathWithParents = (
  startWeek: number,
  startLevels: SkillLevels,
  remainingTimeThisWeek?: number,
  currentRemainingPoints?: number,
  weeklyPoints?: number[]
): WeeklyStates

상태 정의: weeklyStates[week][skillStateKey] = StateInfo

  • week: 현재 주차 (1~9)
  • skillStateKey: 스킬 레벨 조합을 인코딩한 키 (l1 << 8) | (l2 << 4) | l3
  • StateInfo: 누적 경험치, 이전 상태 참조, 액션 시퀀스

상태 전이:

for 주차 in [startWeek..9]:
  for 현재상태 in 주차별상태들:
    for 가능한업그레이드조합 in generateSkillCombinations():
      # 최적 타이밍 전략 계산
      strategy, exp = findOptimalTimingStrategy(현재레벨, 새레벨)
      누적경험치 = 이전누적경험치 + exp

      if 누적경험치 > 기존최적값:
        다음주차상태[새레벨조합] = 갱신

Level 2: 장기 휴식 타이밍 최적화 (2차원 DP)

구성

Dynamic Programming의 적용 파트에서 이번 경험치 = 스킬 레벨 업을 통해 얻을 수 있는 경험치 라고 뭉개고 넘어간 부분입니다. 아무튼 Level 1 부분에서는 모든 스킬 레벨 업 상황에 대해 고려했고, 모든 주차에 모든 상태에 대해서 최적 상황을 고려하고 있습니다만, 그 모든 스킬 레벨 업 상황에 대해 조금 더 고민해 볼 시점입니다.

빈틈을 메우려면 사실 이게 Level 2가 아니라 Level 1이어야 하긴 합니다만, 설명의 흐름상 이렇게 되었네요. 다만 Level 1과 골자는 동일합니다. 이번 주의 스킬 레벨 업은 다음 주나 이전 주 상태랑은 완전히 별개의 상태입니다. 어떻게 왔건, 어디로 가건은 특정 주에서 어떻게 스킬을 올리느냐 랑은 전혀 관계가 없는 내용입니다. 즉, 어떻게 스킬을 올리느냐는 별도의 부분 문제로 분리가 가능하다는 거죠.

그래서 어떻게 올리느냐 에서 1차적으로 어떤 스킬을 얼마나 올리느냐 는 generateSkillCombinations 함수를 통해 모든 조합을 그냥 만들었습니다. 그러면 그 어떤 스킬을 얼마나 외에 어떤 순서로 어떻게 를 추가적으로 고민해 봐야겠죠. 앞서 말했듯 주차별 상황에 대해서는 서로 격리된 상황이고 다음 주에 영향을 미치거나 하지 않으니, 이 문제 역시 독립적인 문제로 간주하면 됩니다.

여기서 초반에 말했던 휴리스틱(부스트가 올라가는 시점에서만 장기 휴식을 먼저 올린다, 그런 경우에라도 2레벨 이상 올릴 만큼의 부스트 효율은 안 나온다)을 적용해도 아마 무리는 없겠지만, 역시나 이런 부분을 검증하기 위한 부분이니 모든 경우를 고려해 봅니다. 우선 장기 휴식을 제외하고는 무조건 먼저 올리는게 맞습니다. 안 올리면 안 올리고 다음주로 미뤘지, 이번 주에 올릴거면 쓰기 전에 올려야지, 그렇지 않고서는 참작의 여지가 없습니다(앞서 말했듯 문제 분리가 되므로, 이번 주에 제시된 스킬 레벨 업 환경에서는 최대 경험치를 뽑아야 합니다). 그러면 장기 휴식, 이 경우에는 시간을 쓰고 올리거나, 안 쓰고 올리거나가 가능합니다. 그리고 올릴 때 시간을 다 쓰고 올리거나, 아예 안 쓰고 올리거나 두 선택지 중 하나인거지 막 애매하게 1시간만 쓰고 올린다 같은 경우는 없습니다. 다 쓰고 올리는 경우는 이후에 있을 이번 주 시나리오의 모든 경우보다 지금이 경험치 배율이 높은 경우일거고, 안 쓰고 올리는 경우에는 이후에 있을 어느 시점에는 지금보다 경험치 배율이 높은 경우가 있는 상황이겠죠. 그러면 그 시점이 왔을 때 최대한 쓸 수 있는 시간을 다 쓰는 게 맞습니다. 이러면 문제가 어디서 본 문제가 되지 않나요?

장기 휴식을 N번 할 수 있다. 현재 X시간 남아있고, 장기 휴식을 올리면 배율은 N% 증감(부스트+장기휴식)하고 시간은 N시간 늘어난다. ~~Level 1 문제(특정 주차에서 최대 경험치를 얻는 문제)와 유사한, 특정 장기 휴식 레벨에서 최대 경험치를 얻는 문제가 되는 것입니다. 추가 설정값으로 도입한 첫 주차 경험치 설정으로 들어가면 약간 더 복잡해질 수는 있습니다만 큰 선에서는 벗어나지 않습니다.

글을 쓰고 나서 추가로 확인하니 굳이 DP로 돌아갈 것 없이, 최적의 소진 타이밍을 찾는 그리디 문제로 접근할 수 있습니다. 역방향으로 확인하며 최댓값이 되는 시점에 시간을 모두 소진하는 식으로 진행하면 되죠.

코드(DP)

const findOptimalLongRestTiming = (
  oldL1: number,      // 기존 장기 휴식 레벨
  newL1: number,      // 목표 장기 휴식 레벨
  nl2: number,        // 역동적 휴식 레벨
  nl3: number,        // 간식 충전 레벨
  initialTime: number // 초기 시간
): { maxExp: number; strategy: TimingStrategy }

상태 정의: dp[step][integerHours][hasInitialTime]

  • step: 현재 업그레이드 단계 (0 ~ newL1-oldL1)
  • integerHours: 누적된 정수 시간 (업그레이드로 추가된 시간)
  • hasInitialTime: 초기 시간이 아직 소진되지 않았는지 여부

전이 방정식:

선소진: dp[step+1][timeAdded][false] = max(dp[step+1][timeAdded][false],
                                          dp[step][ih][hit] + currentTime × currentMultiplier)

선업글: dp[step+1][ih+timeAdded][hit] = max(dp[step+1][ih+timeAdded][hit],
                                          dp[step][ih][hit])

의사코드 (Greedy Algorithm)

현재최대배율 = -1
소진시점 = []
for 장기휴식레벨 in 최종레벨..처음레벨:
  if 현재최대배율 < 지금경험치배율(장기휴식레벨, 이외설정값):
    소진시점 += [장기휴식레벨] (해당 레벨 달성 후 소진)

이 때 레벨업 전/후에 대한 고려가 모두 필요해 처음 레벨과 최종 레벨 모두 포함해서 돌리거나 마지막에 시간 소진을 따로 두는 로직이 필요하므로 이 부분만 유의하면 될 것 같습니다

기타 최적화 기법들

서론

사실 구조상 연산 횟수가 그렇게 크지 않아서 충분할 것이라 봤는데, 별도의 로직 적용 없이는 0.5초정도의 시간이 소요되었습니다. 그렇게까지 느리진 않지만, 뭔가 구상한답시고 최적화해서 줄인 계산 횟수를 생각하면 뭔가 아쉬운 부분이더라고요. 그래서 코드를 확인하고 추가적으로 최적화한 부분들이 있습니다.

1. 캐싱 시스템 (LRU with Environment Adaptation)

일부 sub-dp 문제나 부스트 효과 계산하는 경우나 곱셈들에 캐싱을 적용했습니다. 사실 이 부분도, 배열 경우의 수가 크지 않아서 고정으로 모든 경우를 캐싱해 두도록 만들어도 문제는 없을 것 같았습니다. 다만 Claude 구현 그대로 사용했을 때 적당히 돌아가는 것 같아서, 캐시 키 개수 계산이나 이런 부분 생략하고 그냥 그대로 적용했습니다.

// 디바이스 환경에 따른 동적 캐시 크기 조정
const getCacheSize = (baseSize: number, factor: number = 1) => {
  if (isMobile && memoryGB <= 4) {
    return Math.floor(baseSize * 0.2 * factor) // 모바일 저사양: 20%
  } else if (isMobile) {
    return Math.floor(baseSize * 0.5 * factor) // 모바일 고사양: 50%
  } else if (memoryGB >= 16) {
    return Math.floor(baseSize * 3 * factor) // 데스크탑 고사양: 300%
  } else {
    return Math.floor(baseSize * 1.5 * factor) // 데스크탑 일반: 150%
  }
}

캐시 적용 파트:

  • boostMultiplierCache: 부스트 효과 계산 결과
  • totalMultiplierCache: 전체 배율 계산 결과
  • expWithTimingStrategyCache: 타이밍 전략별 경험치 계산 결과
  • skillCombinationsCache: 스킬 조합 생성 결과

2. 비트 연산을 활용한 상태 압축

키 생성 시에 문자열로 사용하고 있길래, 정수 키 하나 구성해서 하도록 했습니다. 크게 영향을 끼쳤을지는 모르겠습니다.

// 기존: 문자열 키 (메모리 비효율)
const oldKey = `${week}_${l1}_${l2}_${l3}`

// 최적화: 비트 연산 키 (메모리 효율)
const encodeState = (week: number, l1: number, l2: number, l3: number): number => {
  return (week << 12) | (l1 << 8) | (l2 << 4) | l3
}

장점:

  • 메모리 사용량 1/4 감소
  • 해시 계산 속도 향상
  • 캐시 적중률 개선

3. 정수 연산 최적화

부동 소수점 오차를 제거하고 아마도 속도를 조금 올리기 위해 정수 연산으로 변경했습니다. 1% 단위로 존재하는 장기 휴식, 간식 충전, 부스트의 경우 100배수를 적용했고 0.5% 단위로 존재하는 역동적 휴식(최소~최대 평균을 내다 보니)은 200배수를 적용한 뒤에, 마지막에 한 번만 나누어서 실수로 넘겼습니다.

// 부동소수점 오차 제거를 위한 스케일링
const SCALE_FACTORS = {
  long: 100,    // 장기 휴식 (1% 단위)
  dynamic: 200, // 역동적 휴식 (0.5% 단위)
  snack: 100,   // 간식 충전 (1% 단위)
  boost: 100,   // 부스트 효과 (1% 단위)
}

const TOTAL_SCALE_FACTOR = 100 × 200 × 100 × 100 = 200,000,000

// 최종 결과를 원래 스케일로 복원
export const scaleToOriginal = (scaledValue: number): number => {
  return scaledValue / TOTAL_SCALE_FACTOR
}

왜 Claude가 TOTAL_SCALE_FACTOR에 하드코딩을 해뒀을까요...?

4. 조기 종료 최적화

최종적으로 최적값 계산 시 9주차 결과에서 스킬 레벨별로 최댓값을 찾아줘야 합니다. 이 과정에서 장기 휴식은 잠수 시간을 줄이고자 하는 니즈가 분명할 것 같아서 장기 휴식 최대 레벨 제한 옵션을 넣었고, 이 부분 역시 사실 Level 1 DP를 한 번 실행시키고 나면, 최종 장기 휴식 레벨이 특정 값 이하인 부분에서만 최댓값을 찾으면 되는 부분입니다. 스킬 레벨이 단조 증가하는 구성이라서, 9주차에 장기 휴식이 5레벨이었는데 중간에 6레벨을 넘겼을 수는 없죠. 아무튼 이런 이유로 DP 테이블을 구성해 두고 장기 휴식의 최대 레벨 유형에 따라 최댓값을 미리 계산해 두면 이후에 최댓값을 찾기 위해 9주차의 모든 테이블(아까도 말했지만 기껏해야 66종이긴 합니다...)을 찾을 필요 없이 최댓값을 찾고 역추적만 하면 되는 환경을 만들어줄 수 있습니다. 어차피 제한 없거나 사용자가 지정한 제한 환경에서의 최댓값을 찾아야 하므로, 한 번 돌아야 하는 상황이니까요.

이 때 장기 휴식 레벨 제한이 있는 경우는 추가되는 제약이므로, 제약이 덜 한 상황이랑 비교했을 때 그 최댓값이 같을 수는 있어도 더 높을 순 없겠죠. 따라서 장기 휴식 레벨이 제한되고 있는 상황에서 이미 최댓값이 아니면, 그 제약이 느슨해졌을 때 그 값은 느슨한 제약에서의 최댓값이 될 수 없음이 자명합니다. 그래서 미리 종료해주면 조금이나마(또 언급하지만 기껏해야 66종이고, 기껏해야 최댓값 0~8로 9번 돌긴 합니다만) 최적화할 수 있을거라 봤습니다.

// 제한 레벨별 최적값 계산에서 조기 종료
for (let x = longRestLevel; x <= 8; x++) {
  if (info.totalExp > current.totalExp) {
    bestExp.set(x, { stateKey, totalExp: info.totalExp })
  } else {
    break // 더 큰 제한에서도 갱신 불가하므로 중단
  }
}

정리: 왜 DP가 Optimal Solution을 보장하는가?

1. 분할 가능한 문제

  • 주차별 독립성: k주차에서의 최적 전략은 k+1주차 이후의 혹은 k-1주차 이전의 최적 전략과 독립적
  • 장기 휴식 타이밍: 장기 휴식의 각 업그레이드 단계에서의 타이밍 선택 역시 다른 주차/스킬업 조합과 독립적

2. 중복 부분 문제

  • 동일한 상태 도달: 서로 다른 경로로 같은 (주차, 스킬레벨) 조합 및 (장기휴식 레벨, 남은 시간)에 도달 가능하겠지만 결국 최댓값이 중요
  • 재사용 가능성: 한 번 계산된 장기 휴식 타이밍 문제의 최적값은 다른 계산에서 재사용하더라도 문제 없음

3. 완전 탐색 보장

// 모든 가능한 스킬 조합을 체계적으로 탐색
for (let nl1 = l1; nl1 <= 8; nl1++) {
  for (let nl2 = l2; nl2 <= 8; nl2++) {
    for (let nl3 = l3; nl3 <= 8; nl3++) {
      // 해당 조합이 포인트 제약을 만족하는지 확인
      if (totalCost <= availablePoints) {
        // Level 1 DP로 해당 조합의 최적 전략 계산
      }
    }
  }
}
  • 모든 경우 커버: 올리는 스킬, 장기 휴식 타이밍 등 모두 고려

4. 뭉갤 수 있는 것들

  • 간식 충전, 역동적 휴식: 시간 소진 이전에 먼저 올리는 게 무조건 맞음
  • 장기 휴식 타이밍: 다 쓰고 올리거나, 아예 안 쓰고 올리거나

정리: 성능 분석과 복잡도, 마치며

캐싱까지 감안하면 최종 시간/공간 복잡도가 어떻게 되는지는 꽤 난감하네요. DP 자체의 경우에는 적당히 나온 것 같은데, 중간 중간 체크하고 계산하는 로직에서 비효율이 있어서 생각보다 시간이 오래 걸렸었지 않나 싶습니다. 최종 복잡도를 다 계산하기에는 캐싱의 경우에는 환경별로 다른 크기에서 LRU를 해 버렸고 캐시 넣을때 즈음 빨리 마무리하고 싶어서 대강 넘긴 상황이라 잘 모르겠습니다...

아무튼, 대충 초기 환경에서 500ms 정도 시간 소모에서 50ms 이내로 상당히 줄어들었습니다. 여전히 최적화할 여지가 남아있고, Level 2 DP는 아무래도 휴리스틱으로 대체해버려도 될 것 같은데, 이 부분은 일단 성능이 충분한 거라 판단한 상태고 기간 한정 이벤트다 보니 더 이상 고려하진 않았습니다. 만약 비슷한 이벤트나 비슷한 상황이 온다면 확장하기에도 DP로 두는 편이 낫지 않을까 싶기도 하고요. 글을 쓰면서 두 번째는 DP 없이 단순 그리디로 해결할 수 있는 걸로 확인해서 변경했고, 추가적으로 20~40ms정도까지는 줄어들었네요.

뭉갤 수 있는 부분을 뭉갬으로써(장기 휴식만 선소진 고려, 장기 휴식 최대 레벨 제한에 따른 최댓값 탐색 시 조기 skip) 알고리즘을 정리해서 이래저래 단순해진걸 여러모로 체감해봤던 시도였다고 봅니다. 제가 궁금했던 내용인 포인트 특수 상황이나 장기 휴식 레벨 제한 등에 대해서 이래저래 넣어놨으니, 유용하게 쓰였으면 좋겠습니다.

TL;DR

  1. 매 주 최대 경험치를 얻는 DP 문제로 판단
  2. 장기 휴식 이전에 시간 소진할지 여부는 특정 주차 안에 있는 작은 DP 문제로 판단
  3. DP 2중 적용 + 캐싱 + 기타 최적화 + 정수 연산 메인으로 최적화해서 50ms 이내로 웹계산기 구현

계산기 사용해보기

이 글에서 분석한 Dynamic Programming 알고리즘이 실제로 구현된 계산기를 직접 사용해볼 수 있습니다:

➡️ 휴게실 경험치 최적화 계산기

  • 9주간 최적 스킬 투자 전략 자동 계산
  • 장기 휴식 레벨 제한 옵션 지원
  • 실시간 결과 분석 및 상세 액션 가이드 제공
  • 설정 저장/공유 기능 포함

계산기에서 다양한 시나리오를 테스트해보면서 이 글에서 설명한 최적화 알고리즘의 성능을 직접 체험해보세요!

광고 로딩 중...
Advertisement