Dec 26, 2024

494. Target Sum

내 코드

Backtracking

817ms, 11.57MB

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        // 다 찾기.
        backtrack(nums, target, 0, 0);
        return answer;
    }

private:
    int answer{};
    void backtrack(vector<int>& nums, int target, int index, int sum) {
        if(index == nums.size()) {
            if(sum == target) ++answer;
            return;
        }
        backtrack(nums, target, index + 1, sum + nums[index]);
        backtrack(nums, target, index + 1, sum - nums[index]);
    }
};

Solution

Approach 1: Brute Force

809ms, 11.52MB
Complexity
- Let $n$ be the size of the input array nums.
- Time Complexity: $O(2^n)$
- Space Complexity: $O(n)$

class Solution {
public:
    int totalWays = 0;  // Tracks the total number of ways to reach the target

    int findTargetSumWays(std::vector<int>& nums, int target) {
        calculateWays(nums, 0, 0, target);
        return totalWays;
    }

private:
    void calculateWays(std::vector<int>& nums, int currentIndex, int currentSum,
                       int target) {
        if (currentIndex == nums.size()) {
            // Check if the current sum matches the target
            if (currentSum == target) {
                totalWays++;
            }
        } else {
            // Include the current number with a positive sign
            calculateWays(nums, currentIndex + 1,
                          currentSum + nums[currentIndex], target);
            // Include the current number with a negative sign
            calculateWays(nums, currentIndex + 1,
                          currentSum - nums[currentIndex], target);
        }
    }
};

GPT

이 코드는 배열 nums의 숫자들을 조합하여 목표 값(target) 을 만드는 방법의 수를 계산합니다. 각 숫자를 양수(+) 또는 음수(-) 로 사용하여 합계를 구성합니다. 문제는 유명한 “Target Sum Problem”에 해당하며, 완전 탐색(재귀적 방법)으로 해결하고 있습니다.

코드 분석

1. 클래스 변수 초기화

int totalWays = 0;  // Tracks the total number of ways to reach the target

totalWays는 목표 값을 만드는 총 경우의 수를 저장하는 변수입니다.
각 재귀 호출에서 target과 동일한 합계를 만들면 이 값을 증가시킵니다.

2. `findTargetSumWays` 함수

int findTargetSumWays(std::vector<int>& nums, int target) {
    calculateWays(nums, 0, 0, target);
    return totalWays;
}

findTargetSumWays 함수는 문제의 진입점입니다.
calculateWays라는 재귀 함수를 호출하여 문제를 해결합니다.
- nums: 입력 배열.
- 0: 현재 인덱스(초기값 0).
- 0: 현재까지의 합(초기값 0).
- target: 목표 값.

3. `calculateWays` 재귀 함수

void calculateWays(std::vector<int>& nums, int currentIndex, int currentSum, int target) {
    if (currentIndex == nums.size()) {
        // Check if the current sum matches the target
        if (currentSum == target) {
            totalWays++;
        }
    } else {
        // Include the current number with a positive sign
        calculateWays(nums, currentIndex + 1,
                      currentSum + nums[currentIndex], target);
        // Include the current number with a negative sign
        calculateWays(nums, currentIndex + 1,
                      currentSum - nums[currentIndex], target);
    }
}

a. 기저 조건 (종료 조건)

if (currentIndex == nums.size()) {
    if (currentSum == target) {
        totalWays++;
    }
}

모든 숫자를 처리한 경우(currentIndex == nums.size()):
- 현재 합계(currentSum)가 목표 값(target)과 동일하면 totalWays를 1 증가시킵니다.

b. 재귀 호출

calculateWays(nums, currentIndex + 1, currentSum + nums[currentIndex], target);
calculateWays(nums, currentIndex + 1, currentSum - nums[currentIndex], target);

현재 숫자를 양수(+)로 포함하거나 음수(-)로 포함한 두 가지 경우를 재귀적으로 탐색합니다.
currentIndex + 1로 다음 숫자를 처리합니다.
재귀적으로 모든 가능한 조합을 탐색하여 목표 값을 찾습니다.

동작 과정 예시

입력:

nums = [1, 1, 1, 1, 1]
target = 3

탐색 트리:

                            (0, 0)
                  +1 /                 \ -1
              (1, 1)                 (1, -1)
         +1 /        \ -1        +1 /       \ -1
      (2, 2)       (2, 0)     (2, 0)     (2, -2)
     +1/\-1       +1/\-1     +1/\-1      +1/\-1
  (3, 3)(3, 1) (3, 1)(3, -1)(3, 1)(3, -1)(3,-1)(3,-3)

각 노드는 (currentIndex, currentSum)을 나타냅니다.
트리의 맨 아래에서 currentSum == target인 경우의 수를 찾습니다.

계산:

(3, 3)에서 총 5가지 경우가 target = 3과 일치합니다:
- +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

시간 및 공간 복잡도

시간 복잡도

이 알고리즘은 모든 가능한 조합을 탐색하므로, 시간 복잡도는 $O(2^n)$ $O (2^{n})$ , 여기서 $n$ $n$ 은 배열 nums의 크기입니다.
- 각 숫자에 대해 양수와 음수 두 가지 선택이 있기 때문입니다.
최악의 경우 $n$ 이 커질수록 시간이 기하급수적으로 증가합니다.

공간 복잡도

함수 호출 스택은 최대 $n$ 개의 깊이를 가집니다.
따라서 공간 복잡도는 $O(n)$ 입니다.

최적화 가능성

위 코드는 비효율적일 수 있습니다. 동일한 계산을 여러 번 반복하기 때문입니다. 최적화를 위해 메모이제이션(Memoization) 기법을 사용할 수 있습니다.

메모이제이션 추가 코드

class Solution {
public:
    int findTargetSumWays(std::vector<int>& nums, int target) {
        unordered_map<string, int> memo;
        return calculateWays(nums, 0, 0, target, memo);
    }

private:
    int calculateWays(std::vector<int>& nums, int currentIndex, int currentSum, int target,
                      unordered_map<string, int>& memo) {
        if (currentIndex == nums.size()) {
            return currentSum == target ? 1 : 0;
        }

        string key = to_string(currentIndex) + "," + to_string(currentSum);
        if (memo.find(key) != memo.end()) {
            return memo[key];
        }

        int positive = calculateWays(nums, currentIndex + 1, currentSum + nums[currentIndex], target, memo);
        int negative = calculateWays(nums, currentIndex + 1, currentSum - nums[currentIndex], target, memo);

        memo[key] = positive + negative;
        return memo[key];
    }
};

메모이제이션 효과

중복 계산을 방지하여 시간 복잡도를 $O(n \times \text{sumRange})$ $O (n \times sumRange)$ 로 줄입니다.
- $n$ : 배열 크기.
- $\text{sumRange}$ : 가능한 합계의 범위.

Approach 2: Recursion with Memoization

12ms, 25.67MB
Complexity
- Let $n$ be the size of the input array nums.
- Time Complexity: $O(n \cdot \text{totalSum})$
- Space Complexity: $O(n \cdot \text{totalSum})$

class Solution {
public:
    int totalSum;

    int findTargetSumWays(vector<int>& nums, int target) {
        totalSum = accumulate(nums.begin(), nums.end(), 0);

        vector<vector<int>> memo(
            nums.size(),
            vector<int>(2 * totalSum + 1, numeric_limits<int>::min()));
        return calculateWays(nums, 0, 0, target, memo);
    }

    int calculateWays(vector<int>& nums, int currentIndex, int currentSum,
                      int target, vector<vector<int>>& memo) {
        if (currentIndex == nums.size()) {
            // Check if the current sum matches the target
            if (currentSum == target) {
                return 1;
            } else {
                return 0;
            }
        } else {
            // Check if the result is already computed
            if (memo[currentIndex][currentSum + totalSum] !=
                numeric_limits<int>::min()) {
                return memo[currentIndex][currentSum + totalSum];
            }
            // Calculate ways by adding the current number
            int add =
                calculateWays(nums, currentIndex + 1,
                              currentSum + nums[currentIndex], target, memo);

            // Calculate ways by subtracting the current number
            int subtract =
                calculateWays(nums, currentIndex + 1,
                              currentSum - nums[currentIndex], target, memo);

            // Store the result in memoization table
            memo[currentIndex][currentSum + totalSum] = add + subtract;

            return memo[currentIndex][currentSum + totalSum];
        }
    }
};

GPT

이 코드는 “Target Sum Problem”을 메모이제이션(Memoization) 을 활용하여 최적화한 풀이입니다. 메모이제이션은 중복 계산을 방지하여 완전 탐색의 시간 복잡도를 크게 줄이는 기법입니다. 아래에서 코드의 주요 부분을 단계적으로 설명하겠습니다.

코드 설명

1. 클래스 멤버 변수 초기화

int totalSum;

totalSum: 배열 nums의 모든 요소의 합계를 저장합니다.
이 값을 사용하여 가능한 currentSum 값을 양수와 음수 범위로 변환하고 메모이제이션 테이블을 초기화합니다.

2. `findTargetSumWays` 함수

int findTargetSumWays(vector<int>& nums, int target) {
    totalSum = accumulate(nums.begin(), nums.end(), 0);

    vector<vector<int>> memo(
        nums.size(),
        vector<int>(2 * totalSum + 1, numeric_limits<int>::min()));

    return calculateWays(nums, 0, 0, target, memo);
}

a. `totalSum` 계산

totalSum = accumulate(nums.begin(), nums.end(), 0);

nums 배열의 총합을 계산합니다.
가능한 currentSum 값은 $[- \text{totalSum}, +\text{totalSum}]$ 범위 내에 있습니다.

b. 메모이제이션 테이블 초기화

vector<vector<int>> memo(
    nums.size(),
    vector<int>(2 * totalSum + 1, numeric_limits<int>::min()));

메모이제이션 테이블 memo는 2차원 벡터로 구성됩니다:
- 행: 현재 인덱스(currentIndex)를 나타냄.
- 열: 현재 합(currentSum)을 변환한 값(currentSum + totalSum)을 나타냄.
numeric_limits<int>::min()은 아직 계산되지 않은 상태를 나타냅니다.

c. 재귀 함수 호출

return calculateWays(nums, 0, 0, target, memo);

초기 상태로 currentIndex = 0, currentSum = 0에서 탐색을 시작합니다.

3. `calculateWays` 함수

int calculateWays(vector<int>& nums, int currentIndex, int currentSum,
                  int target, vector<vector<int>>& memo) {

이 함수는 현재 노드(currentIndex, currentSum)에서 목표 값을 달성할 수 있는 경우의 수를 반환합니다.

a. 기저 조건 (종료 조건)

if (currentIndex == nums.size()) {
    if (currentSum == target) {
        return 1;
    } else {
        return 0;
    }
}

모든 숫자를 처리한 경우:
- currentSum이 target과 같으면 경우의 수는 1.
- 그렇지 않으면 경우의 수는 0.

b. 메모이제이션 확인

if (memo[currentIndex][currentSum + totalSum] != numeric_limits<int>::min()) {
    return memo[currentIndex][currentSum + totalSum];
}

memo[currentIndex][currentSum + totalSum]에 저장된 값이 있다면, 이미 해당 상태를 계산한 적이 있으므로 저장된 값을 반환합니다.
currentSum + totalSum을 사용하는 이유는 currentSum이 음수일 수 있기 때문입니다. 이를 보정하여 테이블의 인덱스로 사용합니다.

c. 재귀 호출

int add = calculateWays(nums, currentIndex + 1,
                        currentSum + nums[currentIndex], target, memo);
int subtract = calculateWays(nums, currentIndex + 1,
                             currentSum - nums[currentIndex], target, memo);

현재 숫자를 양수로 사용하는 경우와 음수로 사용하는 경우를 재귀적으로 탐색합니다.
두 가지 경우의 수를 각각 계산하여 합산합니다.

d. 결과 저장 및 반환

memo[currentIndex][currentSum + totalSum] = add + subtract;
return memo[currentIndex][currentSum + totalSum];

add + subtract 값을 메모이제이션 테이블에 저장하여 중복 계산을 방지합니다.
저장된 값을 반환합니다.

동작 과정 예시

입력:

nums = [1, 1, 1, 1, 1]
target = 3

탐색 트리:

이전 완전 탐색과 동일한 방식으로 탐색되지만, 메모이제이션을 통해 중복 계산이 방지됩니다.

시간 및 공간 복잡도

시간 복잡도

메모이제이션 테이블의 크기는 $O(n \times (2 \times \text{totalSum} + 1))$ $O (n \times (2 \times totalSum + 1))$ , 여기서:
- $n$ : 배열 nums의 크기.
- $\text{totalSum}$ : 배열의 총합.
각 상태를 한 번만 계산하므로, 시간 복잡도는 $O(n \times \text{totalSum})$ 입니다.

공간 복잡도

메모이제이션 테이블의 크기는 $O(n \times (2 \times \text{totalSum} + 1))$ .
재귀 호출 스택의 깊이는 최대 $n$ 이므로 추가 공간 복잡도는 $O(n)$ 입니다.

최적화의 효과

메모이제이션을 사용하지 않는 완전 탐색의 시간 복잡도는 $O(2^n)$ 입니다. 하지만 메모이제이션을 사용하면 복잡도가 $O(n \times \text{totalSum})$ 로 감소하여, $n$ 과 $\text{totalSum}$ 이 작을 때 매우 효율적입니다.

Approach 3: 2D Dynamic Programming

11ms, 25.77MB
Complexity
- Let $n$ be the size of the input array nums.
- Time Complexity: $O(n \cdot \text{totalSum})$
- Space Complexity: $O(n \cdot \text{totalSum})$

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int totalSum = accumulate(nums.begin(), nums.end(), 0);
        vector<vector<int>> dp(nums.size(), vector<int>(2 * totalSum + 1, 0));

        // Initialize the first row of the DP table
        dp[0][nums[0] + totalSum] = 1;
        dp[0][-nums[0] + totalSum] += 1;

        // Fill the DP table
        for (int index = 1; index < nums.size(); index++) {
            for (int sum = -totalSum; sum <= totalSum; sum++) {
                if (dp[index - 1][sum + totalSum] > 0) {
                    dp[index][sum + nums[index] + totalSum] +=
                        dp[index - 1][sum + totalSum];
                    dp[index][sum - nums[index] + totalSum] +=
                        dp[index - 1][sum + totalSum];
                }
            }
        }

        // Return the result if the target is within the valid range
        return abs(target) > totalSum ? 0
                                      : dp[nums.size() - 1][target + totalSum];
    }
};

GPT

이 코드는 “Target Sum Problem”을 동적 프로그래밍(Dynamic Programming, DP)을 사용하여 해결한 방식입니다. DP 테이블을 이용하여 가능한 모든 합계를 계산하고, 각 합계를 만드는 방법의 수를 기록합니다. 이 방식은 메모이제이션 기반 재귀 풀이보다 효율적이며, 반복문을 사용해 더 간결하게 구현됩니다.

코드 분석

1. `findTargetSumWays` 함수

int findTargetSumWays(vector<int>& nums, int target) {
    int totalSum = accumulate(nums.begin(), nums.end(), 0);
    vector<vector<int>> dp(nums.size(), vector<int>(2 * totalSum + 1, 0));

totalSum 계산:
- 배열 nums의 모든 원소의 합계를 계산합니다.
- 가능한 합의 범위는 $[- \text{totalSum}, \text{totalSum}]$ 입니다.
DP 테이블 초기화:
- dp[index][sum + totalSum]은 nums[0:index]를 사용하여 합계가 sum이 되는 방법의 수를 저장합니다.
- 열 인덱스에서 + totalSum을 추가하는 이유는 음수 합계를 허용하기 위해 양의 범위로 보정하기 위함입니다.

2. DP 테이블 초기화

dp[0][nums[0] + totalSum] = 1;
dp[0][-nums[0] + totalSum] += 1;

첫 번째 숫자 처리:
- nums[0]을 양수로 사용하는 경우(nums[0] + totalSum)를 1로 초기화.
- nums[0]을 음수로 사용하는 경우(-nums[0] + totalSum)를 1로 초기화.
- += 1을 사용하는 이유는 nums[0] == 0일 때, 같은 위치에 값을 두 번 더해야 하기 때문입니다.

3. DP 테이블 채우기

for (int index = 1; index < nums.size(); index++) {
    for (int sum = -totalSum; sum <= totalSum; sum++) {
        if (dp[index - 1][sum + totalSum] > 0) {
            dp[index][sum + nums[index] + totalSum] +=
                dp[index - 1][sum + totalSum];
            dp[index][sum - nums[index] + totalSum] +=
                dp[index - 1][sum + totalSum];
        }
    }
}

a. 각 숫자 처리

index는 현재까지 처리할 숫자를 나타냅니다.
sum은 이전 숫자까지의 합계를 나타냅니다.

b. 가능한 합계 업데이트

이전 숫자까지의 합계가 sum이고, 이를 만드는 방법의 수가 0보다 크다면:
- nums[index]를 양수로 사용한 경우: 합계는 sum + nums[index].
- nums[index]를 음수로 사용한 경우: 합계는 sum - nums[index].
두 경우를 DP 테이블에 기록합니다.

4. 결과 반환

return abs(target) > totalSum ? 0
                              : dp[nums.size() - 1][target + totalSum];

목표 값 target이 [-totalSum, totalSum] 범위를 벗어나면, 목표 값을 만들 방법이 없으므로 0을 반환합니다.
그렇지 않으면, DP 테이블의 마지막 행에서 target + totalSum 위치의 값을 반환합니다.

동작 과정 예시

입력:

nums = [1, 1, 1, 1, 1]
target = 3

DP 테이블 구축:

totalSum = 5
DP 테이블은 $5 \times 11$ 크기 ( $-5$ 에서 $+5$ 를 포함).

초기화:

dp[0][5+1] = 1 (nums[0] = +1)
dp[0][5-1] = 1 (nums[0] = -1)

테이블 채우기:

index = 1, nums[1] = 1:
  dp[1][6] += dp[0][5]  // sum +1
  dp[1][4] += dp[0][5]  // sum -1
  ...

마지막 행 결과:
- dp[4][8] (target = 3) 위치의 값은 5 (방법의 수).

시간 및 공간 복잡도

시간 복잡도

DP 테이블을 채우는 데 필요한 시간은 $O(n \times \text{totalSum})$ $O (n \times totalSum)$ .
- $n$ : 숫자의 개수.
- $\text{totalSum}$ : 숫자의 합계.

공간 복잡도

DP 테이블의 크기는 $O(n \times (2 \times \text{totalSum} + 1))$ $O (n \times (2 \times totalSum + 1))$ .
- $O(2 \times \text{totalSum} + 1)$ 은 가능한 합계의 범위를 포함하기 때문입니다.

최적화 가능성

이 코드는 시간과 공간 모두 효율적이지만, 공간 복잡도를 더 최적화할 수 있습니다.

공간 최적화 (1D DP 사용)

현재 행만 사용하여 계산하면, 이전 행을 유지할 필요가 없습니다.
공간 복잡도를 $O(2 \times \text{totalSum} + 1)$ 로 줄일 수 있습니다.

vector<int> dp(2 * totalSum + 1, 0);
dp[nums[0] + totalSum] = 1;
dp[-nums[0] + totalSum] += 1;

for (int index = 1; index < nums.size(); index++) {
    vector<int> next(2 * totalSum + 1, 0);
    for (int sum = -totalSum; sum <= totalSum; sum++) {
        if (dp[sum + totalSum] > 0) {
            next[sum + nums[index] + totalSum] += dp[sum + totalSum];
            next[sum - nums[index] + totalSum] += dp[sum + totalSum];
        }
    }
    dp = next;
}
return dp[target + totalSum];

Approach 4: Space Optimized

3ms, 24.86MB
Complexity
- Let $n$ be the size of the input array nums.
- Time Complexity: $O(n \cdot \text{totalSum})$
- Space Complexity: $O(2 \cdot \text{totalSum})$

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int totalSum = accumulate(nums.begin(), nums.end(), 0);
        vector<int> dp(2 * totalSum + 1, 0);

        // Initialize the first row of the DP table
        dp[nums[0] + totalSum] = 1;    // Adding nums[0]
        dp[-nums[0] + totalSum] += 1;  // Subtracting nums[0]

        // Fill the DP table
        for (int index = 1; index < nums.size(); index++) {
            vector<int> next(2 * totalSum + 1, 0);
            for (int sum = -totalSum; sum <= totalSum; sum++) {
                if (dp[sum + totalSum] > 0) {
                    next[sum + nums[index] + totalSum] += dp[sum + totalSum];
                    next[sum - nums[index] + totalSum] += dp[sum + totalSum];
                }
            }
            dp = next;
        }

        // Return the result if the target is within the valid range
        return abs(target) > totalSum ? 0 : dp[target + totalSum];
    }
};

GPT

이 코드는 “Target Sum Problem”을 동적 프로그래밍(DP)으로 해결하며, 이전 구현에서 1차원 DP 배열을 사용해 공간 복잡도를 최적화한 방식입니다. 이 최적화는 이전 행만 유지하면 된다는 점을 이용하여 공간을 $O(2 \times \text{totalSum} + 1)$ 로 줄입니다. 아래에서 단계별로 코드를 설명합니다.

코드 설명

1. `findTargetSumWays` 함수

int findTargetSumWays(vector<int>& nums, int target) {
    int totalSum = accumulate(nums.begin(), nums.end(), 0);
    vector<int> dp(2 * totalSum + 1, 0);

a. `totalSum` 계산

nums 배열의 총합을 계산합니다.
가능한 합의 범위는 $[- \text{totalSum}, \text{totalSum}]$ 입니다.

b. 1차원 DP 배열 초기화

dp[sum + totalSum]은 특정 합계를 만드는 방법의 수를 저장합니다.
배열 크기는 $2 \times \text{totalSum} + 1$ , 이는 음수와 양수 합계를 모두 표현하기 위해 필요합니다.

2. 초기 상태 설정

dp[nums[0] + totalSum] = 1;    // Adding nums[0]
dp[-nums[0] + totalSum] += 1;  // Subtracting nums[0]

첫 번째 숫자를 양수로 사용하면 합계는 nums[0].
첫 번째 숫자를 음수로 사용하면 합계는 -nums[0].
두 경우를 DP 배열에 기록합니다.
+= 1을 사용하는 이유는 nums[0] == 0인 경우, 같은 위치에 값을 두 번 추가해야 하기 때문입니다.

3. DP 배열 업데이트

for (int index = 1; index < nums.size(); index++) {
    vector<int> next(2 * totalSum + 1, 0);
    for (int sum = -totalSum; sum <= totalSum; sum++) {
        if (dp[sum + totalSum] > 0) {
            next[sum + nums[index] + totalSum] += dp[sum + totalSum];
            next[sum - nums[index] + totalSum] += dp[sum + totalSum];
        }
    }
    dp = next;
}

a. 반복문을 통해 숫자 처리

index: 현재 처리 중인 숫자의 인덱스.
sum: 이전 숫자까지의 합계.

b. 가능한 합계 업데이트

이전 합계가 sum이고, 이를 만드는 방법의 수가 $> 0$ $> 0$ 이면:
- 양수로 사용: 새로운 합계는 sum + nums[index].
- 음수로 사용: 새로운 합계는 sum - nums[index].
새로운 방법의 수를 next 배열에 저장합니다.

c. 현재 상태를 다음 상태로 교체

dp를 next로 교체하여 1차원 배열을 유지합니다.

4. 결과 반환

return abs(target) > totalSum ? 0 : dp[target + totalSum];

목표 값 target이 [-totalSum, totalSum] 범위를 벗어나면 만들 수 없으므로 0을 반환합니다.
그렇지 않으면, DP 배열에서 target + totalSum 위치의 값을 반환합니다.

동작 과정 예시

입력:

nums = [1, 1, 1, 1, 1]
target = 3

과정:

초기화:
- totalSum = 5
- dp[5 + 1] = 1, dp[5 - 1] = 1.
1단계 (index = 1):
- next[6] += dp[5] // $1+1$
- next[4] += dp[5] // $1-1$
2단계 (index = 2):
- 업데이트된 값이 next에 저장됩니다.
- 가능한 합계를 점차 확장.
최종 결과:
- dp[8] = 5 (target = 3).

시간 및 공간 복잡도

시간 복잡도

DP 배열을 채우는 데 필요한 시간은 $O(n \times \text{totalSum})$ $O (n \times totalSum)$ .
- $n$ : 숫자의 개수.
- $\text{totalSum}$ : 숫자 합계.

공간 복잡도

DP 배열 크기는 $O(2 \times \text{totalSum} + 1)$ .
이전의 2차원 배열 구현에 비해 공간 복잡도가 감소했습니다.

최적화 효과

이전 구현 (2D DP 배열):
- 공간 복잡도: $O(n \times (2 \times \text{totalSum} + 1))$ .
현재 구현 (1D DP 배열):
- 공간 복잡도: $O(2 \times \text{totalSum} + 1)$ .

1차원 DP를 사용하여 불필요한 메모리 사용을 줄였지만, 시간 복잡도는 동일합니다.

494. Target Sum

내 코드

Solution

Approach 1: Brute Force

GPT

코드 분석

1. 클래스 변수 초기화

2. findTargetSumWays 함수

3. calculateWays 재귀 함수

a. 기저 조건 (종료 조건)

b. 재귀 호출

동작 과정 예시

입력:

탐색 트리:

계산:

시간 및 공간 복잡도

시간 복잡도

공간 복잡도

최적화 가능성

메모이제이션 추가 코드

메모이제이션 효과

Approach 2: Recursion with Memoization

GPT

코드 설명

1. 클래스 멤버 변수 초기화

2. findTargetSumWays 함수

a. totalSum 계산

b. 메모이제이션 테이블 초기화

c. 재귀 함수 호출

3. calculateWays 함수

a. 기저 조건 (종료 조건)

b. 메모이제이션 확인

c. 재귀 호출

d. 결과 저장 및 반환

동작 과정 예시

입력:

탐색 트리:

시간 및 공간 복잡도

시간 복잡도

공간 복잡도

최적화의 효과

Approach 3: 2D Dynamic Programming

GPT

코드 분석

1. findTargetSumWays 함수

2. DP 테이블 초기화

3. DP 테이블 채우기

a. 각 숫자 처리

b. 가능한 합계 업데이트

4. 결과 반환

동작 과정 예시

입력:

DP 테이블 구축:

시간 및 공간 복잡도

시간 복잡도

공간 복잡도

최적화 가능성

공간 최적화 (1D DP 사용)

Approach 4: Space Optimized

GPT

코드 설명

1. findTargetSumWays 함수

a. totalSum 계산

b. 1차원 DP 배열 초기화

2. 초기 상태 설정

3. DP 배열 업데이트

a. 반복문을 통해 숫자 처리

b. 가능한 합계 업데이트

c. 현재 상태를 다음 상태로 교체

4. 결과 반환

동작 과정 예시

입력:

과정:

시간 및 공간 복잡도

시간 복잡도

공간 복잡도

최적화 효과

2. `findTargetSumWays` 함수

3. `calculateWays` 재귀 함수

2. `findTargetSumWays` 함수

a. `totalSum` 계산

3. `calculateWays` 함수

1. `findTargetSumWays` 함수

1. `findTargetSumWays` 함수

a. `totalSum` 계산