https://leetcode.com/problems/target-sum/description/?envType=daily-question&envId=2024-12-26
You are given an integer array nums and an integer target.
You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.
- For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".
Return the number of different expressions that you can build, which evaluates to target.
Example 1:
Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
Example 2:
Input: nums = [1], target = 1
Output: 1
Constraints:
- 1 <= nums.length <= 20
- 0 <= nums[i] <= 1000
- 0 <= sum(nums[i]) <= 1000
- -1000 <= target <= 1000
싫어하지만, 피하기 힘든 DP category 문제이다.
한 번 부딛쳐보자.
DP문제 특징이, 이해는 쉬운데 이게 문제 해결 implementation이 어렵다 -_-
그래도 코테까지 내 인생 마지막 코딩문제(?) 공부란 생각으로 함 해보자..
아오!!
1. Python
실패했다. DP 카테고리를 봤음에도, 어떻게 Memoization을 써야하는 지 모르겠다.
아니 정확히 말하면 머릿속으로는 알겠는데 이걸 어떻게 구현하는 지 모르겠다 ㅠㅠ
위 Example 기준으로 머리를 굴려봐도 대충 특정 계산방법이 반복되는 구조라는 건 쉽게 알 수 있는데 이걸 코딩으로 구현하는게 넘 힘들다.
진짜 Dynamic Programming 손쉽게 푸는 사람들 Respect.. + 신기하다
일단 나는 개떡같이 시도하다가 코딩완성에 실패했는데,
내가 하려던 것은 Memoization이 없는 Recursive Solution이다. GPT도움을 받아 코드를 작성해봤다.
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
def recursive(index:int, curr_sum:int) -> int:
if index == len(nums):
if curr_sum == target : return 1
else : return 0
add_case = recursive(index+1, curr_sum + nums[index])
sub_case = recursive(index+1, curr_sum - nums[index])
return add_case + sub_case
return recursive(0,0)
GPT 도움을 받아서 코드를 썼음에도, 좀 긴 Test case에 대해선 time-limit이 걸린다..
C++로 코드를 짜면 성능 꼴등... 으로 PASS되긴 한다...
class Solution {
public:
int recur(int idx, int sum, vector<int>& nums, int target){
if(idx==nums.size()){
if(sum==target) return 1;
else return 0;
}
int add = recur(idx+1, sum + nums[idx], nums, target);
int sub = recur(idx+1, sum - nums[idx], nums, target);
return add+sub;
}
int findTargetSumWays(vector<int>& nums, int target) {
return recur(0,0,nums,target);
}
};
Python + Memoization을 쓴 case는 아래와 같다.
# Python with Memoization
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
# 메모이제이션을 위한 캐시
memo = {}
def dfs(index: int, current_target: int) -> int:
# 이미 계산한 상태라면 캐시에서 결과 반환
if (index, current_target) in memo:
return memo[(index, current_target)]
# 기저 조건: 모든 숫자를 사용한 경우
if index == len(nums):
return 1 if current_target == 0 else 0
# 현재 숫자를 + 또는 -로 사용한 결과를 재귀 호출
positive = dfs(index + 1, current_target - nums[index])
negative = dfs(index + 1, current_target + nums[index])
# 메모이제이션 저장
memo[(index, current_target)] = positive + negative
return memo[(index, current_target)] # 이 Return 부분이 햇갈릴 수 있는데 걍 return pos + neg 이다
# 탐색 시작
return dfs(0, target)
배열 기반 DP 코드는 아래와 같다.
사실 Time complexity 기준 성능은 DP나 Memoization이나 중복계산을 방지하는 건 똑같아서 비슷하다고 보면 된다.
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
total_sum = sum(nums)
if abs(target) > total_sum: # target이 만들 수 있는 범위를 벗어난 경우
return 0
# DP 테이블 초기화
dp = [0] * (2 * total_sum + 1)
offset = total_sum # 음수 인덱스를 처리하기 위해 offset 추가
dp[nums[0] + offset] += 1 # 첫 번째 숫자를 +로 사용하는 경우
dp[-nums[0] + offset] += 1 # 첫 번째 숫자를 -로 사용하는 경우
# 숫자 배열 순회
for i in range(1, len(nums)):
next_dp = [0] * (2 * total_sum + 1)
for current_sum in range(-total_sum, total_sum + 1):
if dp[current_sum + offset] > 0:
# 현재 숫자를 +로 사용하는 경우
next_dp[current_sum + nums[i] + offset] += dp[current_sum + offset]
# 현재 숫자를 -로 사용하는 경우
next_dp[current_sum - nums[i] + offset] += dp[current_sum + offset]
dp = next_dp # 업데이트된 dp 테이블로 이동
# 결과 반환
return dp[target + offset]
2. C
C로도 풀어봅시다
솔직히 Memoization 없는 건 가볍고 할만한데,
있는건 코드가 넘 빡세다
# C로도 똑같이 Recursive
int recursive(int idx, int curr_sum, int* lst, int lstsize, int target){
if(idx==lstsize){
return curr_sum == target ? 1 : 0;
}
int add = recursive(idx+1,curr_sum + lst[idx],lst,lstsize,target);
int sub = recursive(idx+1,curr_sum - lst[idx],lst,lstsize,target);
return add+sub;
}
int findTargetSumWays(int* nums, int numsSize, int target) {
return recursive(0,0,nums,numsSize,target);
}# C Memoization
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// DP 캐시 초기화 (-1로 초기화)
int memo[21][2001];
int dfs(int nums[], int n, int index, int current_sum, int target) {
// Base case: 모든 숫자를 사용한 경우
if (index == n) {
return current_sum == target ? 1 : 0;
}
// 메모이제이션 캐시 확인
if (memo[index][current_sum + 1000] != -1) {
return memo[index][current_sum + 1000];
}
// 재귀 호출: +와 - 두 가지 경우
int add = dfs(nums, n, index + 1, current_sum + nums[index], target);
int subtract = dfs(nums, n, index + 1, current_sum - nums[index], target);
// 결과 저장
memo[index][current_sum + 1000] = add + subtract;
return memo[index][current_sum + 1000];
}
int findTargetSumWays(int* nums, int numsSize, int target) {
// 메모이제이션 배열 초기화 (-1로 설정)
memset(memo, -1, sizeof(memo));
// DFS 호출
return dfs(nums, numsSize, 0, 0, target);
}
int main() {
int nums[] = {1, 1, 1, 1, 1};
int target = 3;
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("Number of ways: %d\n", findTargetSumWays(nums, numsSize, target));
return 0;
}
3. C++
Memoization 사용해보기
근데 Python처럼 마냥 쉬운게 아니다.. 뭐지 이거
# C++
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
// unordered_map의 key를 위한 hash function
struct pair_hash {
template <class T1, class T2>
size_t operator()(const pair<T1, T2>& p) const {
return hash<T1>()(p.first) ^ hash<T2>()(p.second);
}
};
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
unordered_map<pair<int, int>, int, pair_hash> memo; // pair를 key로 사용
// 재귀 함수 구현
function<int(int, int)> dfs = [&](int index, int current_target) -> int {
// 메모이제이션 확인
pair<int, int> key = {index, current_target};
if (memo.find(key) != memo.end()) {
return memo[key];
}
// 기저 조건: 모든 숫자를 사용한 경우
if (index == nums.size()) {
return current_target == 0 ? 1 : 0;
}
// 현재 숫자를 + 또는 -로 사용한 결과 계산
int positive = dfs(index + 1, current_target - nums[index]);
int negative = dfs(index + 1, current_target + nums[index]);
// 결과를 메모이제이션에 저장
memo[key] = positive + negative;
return memo[key];
};
// 탐색 시작
return dfs(0, target);
}
};
OFFSET을 이용해서는 아래와 같이 Memoization을 이용한다
class Solution {
public:
int solve(vector<int>& nums, int target, int ind, int sum, vector<vector<int>>& dp, int offset){
if(ind == nums.size())
return sum == target ? 1 : 0;
if(dp[ind][sum+offset] != -1) return dp[ind][sum+offset];
int inc = solve(nums,target,ind+1,sum+nums[ind],dp,offset);
int exc = solve(nums,target,ind+1,sum-nums[ind],dp,offset);
dp[ind][sum+offset] = inc+exc;
return inc+exc;
}
int findTargetSumWays(vector<int>& nums, int target) {
int n = nums.size();
int sum = accumulate(nums.begin(),nums.end(),0);
int offset = sum; // 젤 큰놈으로 offset 해놓기구나
vector<vector<int>> dp (n,vector<int>(2*sum+1,-1));
return solve(nums,target,0,0,dp,offset);
}
};
offset을 sum으로 정한 이유
|
이 개념을 잘 이해했는지 확인하려면 그냥 이걸 C로 코딩해보면 된다.
백지에서 C로 이 문제를 코딩해보자..
고단해도 걸어가야할 길이다!
최대한.. solution을 안 보려고 했는데, C에서 int ** dp 초기화 하는 과정에서 좀 참고했다
ㅠㅠ 따흑 졌다...
int helper(int idx, int sum, int* nums,int numsSize, int target, int** dp, int offset){
if(idx==numsSize){
return sum == target ? 1 : 0;
}
if(dp[idx][sum+offset] != -1) return dp[idx][sum+offset];
int plus = helper(idx+1,sum + nums[idx],nums,numsSize,target,dp,offset);
int minus = helper(idx+1,sum - nums[idx],nums,numsSize,target,dp,offset);
dp[idx][sum+offset] = plus+minus;
return plus+minus;
}
int findTargetSumWays(int* nums, int numsSize, int target) {
int offset = 0;
for(int i=0;i<numsSize;i++){
offset += nums[i];
}
int** dp = (int**)malloc(numsSize*sizeof(int*));
for(int j=0;j<numsSize;j++){
dp[j] = (int *)malloc((offset*2+1)*sizeof(int));
for(int k=0;k<offset*2+1;k++){
dp[j][k] = -1;
}
}
// return helper(0,0,nums,numsSize,target,dp,offset);
int ans =helper(0,0,nums,numsSize,target,dp,offset);
for(int i=0;i<numsSize;i++){
free(dp[i]);
}
free(dp);
return ans;
}