자릿수 동적 계획법 (Digit Dynamic Programming)

최근 Leetcode Daily Problem에서 Dynamic Progrmming을 사용해야 되는 문제가 나왔습니다.

 

Total Waviness of Numbers in Range II라는 문제로, 정해진 범위 내에 조건에 맞는 숫자가 몇 개가 있는지 찾아보는 문제였습니다. Brute Force로 쉽게 풀 수 있지만 범위가 너무 커지면 TLE (Time Limit Exceeded) 오류를 받게 되죠.

 

그래서 오늘은 이러한 범위 내에 특정 숫자들을 찾을 수 있는 알고리즘인 Digit Dynamic Programming을 소개합니다.

Digit Dynamic Programming

---

Digit Dynamic Programming은 숫자의 가장 큰 자릿수(왼쪽)부터 작은 자릿수(오른쪽)로 순회하면서, 특정 조건을 만족하는 숫자의 개수나 합을 구하는데요.

 

Brute Force랑 다르게 자릿수(Digit)를 상태(State)로 만들어 한 칸씩 채워나갑니다. 이렇게 되면, 1부터 N까지 순회하는 알고리즘과 다르게 숫자의 자릿수만 순회하면 되기 때문에, 시간상 훨씬 더 효율적이게 되죠.

 

예를 들어서, a부터 b까지의 자릿수를 모두 더하는 문제를 푼다고 가정해 봅시다.

 

Brute Force의 방법으로 푼다면 아마 코드는 아래와 같이 풀 수 있을 것 같습니다.

for (int i = a; i <= b; i++) {
	int temp = i;
	while (temp > 0) {
    	sum += temp % 10;
        temp /= 10;
    }
}

 

이러한 방식은 공간 복잡도를 O(1)로 만들지만 시간 복잡도는 O( (b-a) * K)가 될 겁니다. 여기서 K는 전체 자릿수(Digit)입니다.

 

범위가 아주 작다면 문제가 없겠지만 숫자가 커진다면 어떻게 될까요? 1 ≤ a < b ≤ 10^18 사이의 숫자를 넣는다고 가정해 봅시다. a의 숫자가 1이고 b가 10^18일 때, Brute Force는 10^18 이상 도는 엄청난 연산량을 필요로 하게 됩니다.

 

여기서 Digit Dynamic Programming을 사용한다면, 시간 복잡도는 숫자 크기가 아닌, 자릿수(Digit)의 상태를 기반으로 계산이 됩니다. 10^18의 자릿수는 18이니, 대략 O(자릿수 * 상태 수) 정도의 복잡도를 가지게 됩니다. 결과적으로 Memoization을 위한 공간 복잡도는 올라갔지만 시간 복잡도는 훨씬 낮아진 모습을 볼 수 있게 됐습니다.

 

그러면 이 알고리즘을 어떻게 구현할까요?

 

Digit Dynamic Programming 구현 방식

---

꼭 기억해야 할 두 가지:

1. 자릿수 위치 (Position): 가장 큰 자릿수(맨 왼쪽)부터 시작해서 오른쪽으로 한 칸씩 이동하며 숫자를 결정하는 기준점
2. 상한선 (Upper Bound):  다음 자릿수에 얼마큼의 숫자가 들어올 수 있는지?

이제 어떻게 알고리즘을 구현하는지 하나씩 알려드리겠습니다. 예시 문제는 위에서 언급한, a부터 b까지의 자릿수를 모두 더하는 문제로  진행하겠습니다.

Memoization Table

우선 모든 DP는 substructure를 참고해야 되기 DP Memoization Table을 만들어봅시다.

 

Digit Dynamic Programming은 자릿수(Digit)에 따라서 상태를 저장해합니다. 그러면 최대 18만큼의 자릿수를 저장할 수 있어야겠죠?

숫자	3	2	4	5
자릿수	4	3	2	1

 

다음 상태는 상한선 (Upper Bound)입니다. 저희가 3245라는 숫자를 순회하고 있다고 가정해 봅시다. 천의 자리에서는 3을 백의 자리에서는 2를 골랐다고 가정해봅시다. 그러면 다음 자리에 들어올 수는 4를 초과하는 숫자는 나올 수 없습니다. 그 이상이 나오면 325_가 되어 원래 순회해야 할 3245를 훌쩍 넘어버리게 됩니다. 

 

그래서 이 상한선은 현재 자릿수에서 고를 수 있는 숫자가 주어진 숫자인 3245 의 해당 자릿수 값으로 제한되는지, 아니면 0에서 9까지 아무 숫자나 넣을 수 있는지를 말해줍니다.

 

마지막 상태는 합(sum)입니다. 이 문제는 숫자의 개수가 아닌 자릿수의 합을 구하는 문제이므로, 현재 자릿수 직전까지 골라온 숫자들의 누적 합이 얼마인지 알고 있어야 다음 자리에 올바른 합을 넘겨줄 수 있습니다.

 

그러면 이거를 코드로 표현한다면 아래와 같이 되겠죠?

long dp[][][] = new long[19][172][2] //Position, Summation, Upper Bound;

 

그럼 마지막으로 으로 Meomization 하는 코드를 아래와 같이 작성해보겠습니다.

//출처: GeeksforGeeks
public class GFG {
    static long dp[][][] = new long[19][172][2];

    // 1에서 자릿수 벡터까지의 합을 return 합니다.
    static long digitSum(int idx, int sum, int upperBound,
                         ArrayList<Integer> digit)
    {
        if (idx == -1)
            return sum;

        // DP에 이미 있는 값이라면 return
        if (dp[idx][sum][upperBound] != -1 && upperBound != 1)
            return dp[idx][sum][upperBound];

        long ret = 0;

        // Upper Bound에 걸리면 현재 index에 있는 자릿수까지
        // 아니면 9까지.
        int k = (upperBound != 0) ? digit.get(idx) : 9;

        for (int i = 0; i <= k; i++) {
            // 새로운 Upper Bound 업데이트
            int newUpperBound
                = (digit.get(idx) == i) ? upperBound : 0;

            ret += digitSum(idx - 1, sum + i, newUpperBound,
                            digit);
        }

        return dp[idx][sum][upperBound] = ret;
    }
}

 

이렇게 상태를 정의하면, 동일 상태를 만났을 때 재연산 없이 배열의 값을 재활용하므로 O(인덱스*합* 상한선)라는 시간 복잡도를 가지게 됩니다. 기존 Brute Force의 시간 복잡도인 O( (b-a) * K)와 비교하면 훨씬 빠르죠. 하지만 속도가 빨라지면 메모리적인 부분의 trade-off가 항상 있듯이, Space Complexity 면에서는 constraints에 따라서 배열을 저장해야되기 때문에, 약간의 메모리를 더 사용해야합니다. 

 

Reference

---

https://www.geeksforgeeks.org/dsa/digit-dp-introduction/

Digit DP | Introduction - GeeksforGeeks

https://www.youtube.com/watch?v=sCwokuCoQB8&t=639s