Target Sum (DFS)

LeetCode의 Queue, Stack 튜토리얼에서 Stack, DFS의 세 번째 문제인 Target Sum이다.

Explore - LeetCode

Stack과 DFS에 포함된 문제긴 하지만 Stack을 활용한 풀이는 거의 찾아볼 수 없고 나도 Stack으로 풀어보려다가 포기했다. DFS를 활용할 수 있지만 DP, Dynamic Programming을 활용할 수 있으며 이를 이용한 풀이가 상위권에 위치하고 있다. 일단 이번 포스트에서는 DFS 풀이 위주로 작성하겠다.

 

문제는 다음과 같다.

• 자연수의 리스트가 매개변수로 주어진다. 자연수의 개수는 20개를 넘지 않는다.

• 이 리스트에 있는 요소를 모두 합해서 만들어야 하는 목표 자연수가 매개변수로 주어진다. 이때 모든 요소의 합은 1000을 초과하지 않는다.

• 리스트 내의 자연수를 각각 더하거나 빼서 목표 자연수를 만들 수 있는 조합의 수를 반환하라.

예를 들어 [1, 1, 1, 1, 1]이 주어졌을 때 이 자연수들을 활용하여 3을 만드는 경우의 수는 다음과 같이 5가지다.

• - 1 + 1 + 1 + 1 + 1

• + 1 - 1 + 1 + 1 + 1

• + 1 + 1 - 1 + 1 + 1

• + 1 + 1 + 1 - 1 + 1

• + 1 + 1 + 1 + 1 - 1

즉 자연수를 음수로 만들던 양수로 만들던 상관없이 이런저런 조합으로 합해보면서 목표로 하는 자연수를 만들 수 있는 경우의 수를 반환하는 것이다. 문제에서는 모든 자연수를 합해서 조합하는 것을 원하고 있기 때문에 이를 그래프 구조로 생각해보면 다음처럼 나타낼 수 있다. 편의를 위해 주어진 자연수는 [1, 1] 밖에 없다고 생각하고 축약하였다.

위의 그래프처럼 기반(0)에서 시작해서 자연수 리스트에서 하나씩 꺼내서 각각 음수, 양수로 변환시켜 현재까지의 합계에 더하면서 진행하면 자연수 리스트로 만들 수 있는 조합을 구할 수 있다. 이때 마지막 자연수까지 다 더했다면(위의 그래프에서는 제일 아래의 노드) 현재 합계가 목표 자연수와 일치하는지 확인하여 일치한다면 카운터를 증가시키는 방식을 생각해볼 수 있다.

 

이를 활용한 자바 코드는 다음과 같다.

class Solution {
    private int count = 0;
    public int findTargetSumWays(int[] nums, int S) {
        findWays(nums, 0, S, 0);
        return count;
    }
    
    private void findWays(int[] nums, int index, int target, int currentSum){
        if(index >= nums.length){
            if(currentSum == target) count++;
            return;
        }
        
        findWays(nums, index+1, target, currentSum + nums[index]);
        findWays(nums, index+1, target, currentSum - nums[index]);
    }
}

하지만 이 코드를 제출하면 실행시간이 꽤나 오래 걸리는 것을 볼 수 있다.

약 500ms로 이는 하위 25%에 속하는 수준이다. 왜 이렇게 오래 걸리는 것일까? 일단 그래프의 모든 노드를 탐색하기 때문에, 그리고 각 노드는 2개의 자식 노드를 갖고 있기 때문에 시간 복잡도가 약 O(2^n)에 해당한다. 위의 그래프의 그림만 봐도 주어진 자연수는 2개([1, 1])밖에 없는데 노드는 7개가 생성됐다. 만약 3개가 있다면 그래프가 한층 더 늘어나서 1 + 2 + 4 + 8 = 15개가 될 것이며 리스트가 커질수록 더 많은 노드들을 탐색해야 하기 때문에 시간 복잡도가 매우 나쁘다고 할 수 있다. 그럼 이를 어떻게 최적화할 수 있을까? 제일 우선순위는 중복되는 노드를 탐색하지 않는 것이다.

[1, 2, 3,...]이 리스트로 주어졌을 때 이를 기반으로 트리를 구축하면 위처럼 3번째 자연수를 합하는 과정에서 중복된 노드가 생성된다. 그래프를 구축할 때는 순서대로 자연수를 합해왔기 때문에 중복된 노드들은 이후 4번째 자연수부터 합할 때도 완전히 동일한 결과(노드)로 뿌리내리게 된다. 그래서 중복된 노드들 중 하나만 진행하고 나머지는 진행하지 않을 필요가 있다. 여기서 진행한다는 것은 나머지 자연수를 합하는 과정을 의미한다. 즉 이미 계산된 것은 다시 계산하지 않는 Memoization 기법을 사용하는 것이다.

 

처음에 시도했던 방법은 Set이나 Map을 이용하여 기억하는 것이었는데 단순히 합산된 값으로만 생각할 경우 이전 합(현재 3번째 자연수까지 더했다면 2번째 자연수까지 더한 합이라던지)과 현재 합을 구분할 수 없는 문제가 발생할 수 있다.

예를 들어 [1, 1, 1,...]의 자연수 리스트가 주어졌을 때 3번째 자연수까지 더했을 때 중복된 '-1' 값을 첫 번째 자연수만 더했을 때 나왔던 '-1' 값과 구분할 수 없는 것이다. 이를 구분하려면 현재 나온 중복 값이 몇 번째 자연수까지 더했을 때 나온 중복 값인지 파악할 수 있어야 하는데 이 로직을 구현하다가 시간이 너무 많이 소모되었다. 그래서 풀이을 참조한 결과 다음처럼 배열을 활용하여 Memoization을 구현할 수 있었다.

class Solution {
    private int[][] memo;
    
    public int findTargetSumWays(int[] nums, int S) {
        memo = new int[nums.length][2001];
        return findWays(nums, 0, S, 0);
    }
    
    private int findWays(int[] nums, int index, int target, int currentSum){
        if(index >= nums.length){
            if(currentSum == target) return 1;
            else return 0;
        }
        
        if(memo[index][currentSum+1000] > 0){
            return memo[index][currentSum+1000];
        }
        
        int add = findWays(nums, index+1, target, currentSum + nums[index]);
        int sub = findWays(nums, index+1, target, currentSum - nums[index]);
        memo[index][currentSum+1000] = add + sub;
        return memo[index][currentSum+1000];
    }
}

이번에는 풀이의 구조가 좀 바뀌었는데 외부의 count 변수를 증가시키던 것과 달리 findWays 함수 자체에서 return 하는 것을 볼 수 있다. 이는 그래프에서 더 이상 합산할 자연수가 없는 말단 노드(leaf node)까지 탐색했을 경우 합산된 값이 목푯값이라면 1을, 그렇지 않다면 0을 반환해서 조합이 몇 개나 있는지 세는 방식이다. 대부분의 풀이에서 값을 합산해서 반환하는 방식으로 푼 것을 볼 수 있는데 이는 그래프의 말단 노드에서 최상위 노드까지 값을 반환하는 과정이기 때문에 상위 노드에서는 하위 노드에서 반환한 값을 모두 합산하여 다시 자신의 상위 노드로 반환할 필요가 있다.

 

그리고 Memoization을 구현하기 위해 2차원 정수 배열을 구현한 것을 볼 수 있다. 그런데 이 배열을 1차원 크기는 자연수 리스트의 길이로, 2차원 크기는 2001이라는 상수값을 이용하여 초기화하는 것을 볼 수 있는데 왜 이런 값을 사용하는 것일까?

 

먼저 1차원 크기의 경우 자연수 리스트에서 n번째 자연수까지 더했을 때 합산된 값을 따로따로 저장하기 위해서 자연수 리스트의 크기만큼 할당한 것이다. 만약 5개의 자연수가 주어졌다면 memo [2]는 3번째 자연수까지 더했을 때 합산된 값을 다룬다는 것을 의미한다. 합산된 값은 실제로 함수에서 자연수의 합을 구할 때 대응되는 배열의 2차원 위치에 저장된다.

 

2차원 크기의 경우 문제에서 자연수들의 합이 1000을 초과하지 않는다는 조건을 반영한 것이다. 만약 자연수들을 모조리 음수로 바꿔서 합산한다면 자연수들의 합은 -1000까지 내려갈 수 있으며 반대로 양수로 합산한다면 1000까지 올라갈 수 있다. 이를 저장하려면 -1000 ~ 1000까지 총 2001개의 합을 저장할 공간이 필요하기 때문에 2차원의 크기를 이렇게 지정한 것이다. 그리고 실제로 n번째 자연수까지 합산된 값이 음수일 경우 배열을 참조하는데 문제가 생기기 때문에 1000을 더해서 일종의 패딩을 적용해 참조하게 된다.

 

즉 1차원 값은 "n번째 자연수까지 더했을 때"라는 것을 의미하며 2차원 값은 "n번째 자연수까지 더했을 때 합산된 자연수들의 값"을 의미하는 것이다. 언급했듯이 자연수는 n개가 있기 때문에 배열의 크기만큼, 합산된 자연수는 -1000부터 1000까지 총 2001개가 존재할 수 있기 때문에 2001개만큼 배열로 미리 생성하여 Memoization을 구현한 것이다.

 

어쨌든 함수에서는 n번째 자연수를 양수로 더한 값, 음수로 더한 값을 각각 재귀 호출하고 있다. 이때 함수가 목푯값을 만드는 조합을 발견했다면 1을 반환하도록 했기 때문에 각 재귀 호출의 반환 값을 합산해야 현재 노드 이후의 노드에서 몇 개의 조합을 발견했는지 알 수 있다. 그리고 합산된 값은 다른 중복된 노드에서 자신이 중복된 것을 판단할 수 있도록 memo 배열에 저장한다. 중복된 노드는 memo에서 자신의 인덱스(현재까지 더한 자연수의 개수)와 자신의 값(현재까지 합산된 값)을 기반으로 참조하여 만약 0이 아니라면 이미 자신과 중복된 다른 노드에서 조합을 발견했다는 것으로 간주하고 메모된 값을 반환, 더 이상 탐색하지 않는다. 이렇게 반환되는 값들은 결국 첫 번째 노드(위의 그래프에서는 맨 위의 노드 0)로 반환되어 합산되기 때문에 이를 반환해주면 되는 것이다.

하지만 생각보다 그렇게 빨라지지 않았는데 어째서일까? 코드를 다시 살펴보니 다음과 같은 부분에서 구현 실수가 있었다는 것을 알 수 있었다.

...
	if(memo[index][currentSum+1000] > 0){
	return memo[index][currentSum+1000];
	}
...

바로 메모에 저장된 값이 0을 초과하는 경우에만 이 노드가 이미 탐색되었다고 판단하도록 구현했던 것인데 만약 중복된 노드 A부터 탐색할 때 목푯값을 만드는 조합을 발견하지 못했다면 어떻게 될까? 맨 마지막 노드에서 현재까지 합산된 값(currentSum)과 목푯값(target)을 비교하여 다르다면 0을 반환하도록 했기 때문에 결과적으로 메모에는 0이 저장된다. 그런데 중복된 다른 노드에서는 메모를 참조할 때 노드 A가 저장한 0을 얻어오기 때문에 위의 "메모에 저장된 값이 0보다 큰가"라는 조건에 부합하지 않아 이 노드가 탐색되지 않았다고 생각해버리게 된다. 즉 Memoization이 중복 연산을 완전히 제거하지 못했던 것이다.

class Solution {
    private int[][] memo;
    
    public int findTargetSumWays(int[] nums, int S) {
        memo = new int[nums.length][2001];
        for(int[] _memo: memo){
            Arrays.fill(_memo, Integer.MIN_VALUE);
        };
        
        return findWays(nums, 0, S, 0);
    }
    
    private int findWays(int[] nums, int index, int target, int currentSum){
        if(index >= nums.length){
            if(currentSum == target) return 1;
            else return 0;
        }
        
        if(memo[index][currentSum+1000] > Integer.MIN_VALUE){
            return memo[index][currentSum+1000];
        }
        
        int add = findWays(nums, index+1, target, currentSum + nums[index]);
        int sub = findWays(nums, index+1, target, currentSum - nums[index]);
        memo[index][currentSum+1000] = add + sub;
        return memo[index][currentSum+1000];
    }
}

그래서 이를 개선하여 배열을 0보다 작은 값(Integer.MIN_VALUE)으로 초기화한 결과 다음처럼 개선된 결과를 얻을 수 있었다.

풀이 결과에서 통계를 보니 이보다 우수한 결과는 대부분 DP를 활용한 풀이로 얻은 결과였다. 아직은 Dynamic Programming에 대한 이해가 부족하기 때문에 나중에 작성하도록 하겠다.