양수와 음수 부호를 사용한 목표 합
목표 합 할당 문제를 부분집합 합의 차이를 구하는 배낭 문제로 변환해 O(n × sum) 시간에 해결합니다.
양수와 음수 부호를 사용한 목표 합은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
목표 합 문제
정수 배열 nums와 정수 target이 주어졌을 때, 각 숫자에 + 또는 - 부호를 할당하여 그 결과로 만들어지는 식의 값이 target이 되도록 합니다. 이렇게 하는 서로 다른 방법의 수를 반환합니다. 예를 들어 nums=[1,1,1,1,1]이고 target=3이면 5가지 방법이 있습니다(서로 다른 위치에서 원소 4개를 양수로, 1개를 음수로 선택합니다).
완전 탐색: DFS 열거
DFS 방식은 각 숫자에 + 또는 -를 할당하고 재귀적으로 탐색하여, target에 도달한 리프 노드의 개수를 반환합니다. 정확한 방법이지만 O(2^n) 시간 복잡도를 가지므로 지수 시간입니다. n=20이면 재귀 호출이 100만 번을 넘습니다. 먼저 DFS 방식을 언급한 다음, 빠르게 DP 최적화로 전환하는 것이 좋습니다.
def findTargetSumWays_dfs(nums, target):
count = [0]
def dfs(i, current_sum):
if i == len(nums):
if current_sum == target:
count[0] += 1
return
dfs(i+1, current_sum + nums[i])
dfs(i+1, current_sum - nums[i])
dfs(0, 0)
return count[0]
print(findTargetSumWays_dfs([1,1,1,1,1], 3)) # 5메모이제이션을 적용한 DFS
DFS에 메모이제이션을 추가합니다. 상태는 (index, current_sum)입니다. current_sum은 -total부터 +total까지의 값을 가질 수 있으므로 고유한 상태는 O(n × total)개입니다. 메모이제이션을 사용하면 DFS는 O(n × total) 시간과 공간에 실행됩니다. 면접에서도 사용할 수 있는 타당한 방법이지만, 변환 기반 DP가 더 우아하고 공간 효율적입니다.
from functools import lru_cache
def findTargetSumWays_memo(nums, target):
total = sum(nums)
@lru_cache(maxsize=None)
def dp(i, remaining):
if i == len(nums):
return 1 if remaining == 0 else 0
return dp(i+1, remaining - nums[i]) + dp(i+1, remaining + nums[i])
return dp(0, target)
print(findTargetSumWays_memo([1,1,1,1,1], 3)) # 5수학적 변환
P를 +가 할당된 숫자의 집합, N을 -가 할당된 숫자의 집합이라고 합시다. 그러면 sum(P) - sum(N) = target이고 sum(P) + sum(N) = total입니다. 두 식을 더하면 2 × sum(P) = target + total이므로 sum(P) = (target + total) / 2가 됩니다. 문제는 nums에서 합이 (target + total) / 2가 되는 부분집합의 개수를 세는 문제로 환원됩니다. 이는 정확히 0/1 배낭 문제에서 부분집합 개수를 세는 변형입니다.
# sum(P) - sum(N) = target
# sum(P) + sum(N) = total
# => 2*sum(P) = target + total
# => sum(P) = (target + total) / 2
# Count subsets with sum = new_target = (target + total) // 2
print('Reduction: count subsets summing to (target + total) // 2')DP 전 유효성 검사
DP를 실행하기 전에 다음을 확인합니다. (1) target + total은 짝수여야 합니다. 그렇지 않으면 sum(P)이 정수가 아니므로 불가능합니다. (2) abs(target) > total이면 모든 부호가 같은 방향으로 정해져도 목표값에 도달할 수 없습니다. 어느 하나라도 검사에 실패하면 즉시 0을 반환합니다. 이러한 검사는 DP 반복문 안에서 별도로 처리하지 않고도 경계 사례를 깔끔하게 다룹니다.
def findTargetSumWays(nums, target):
total = sum(nums)
if (target + total) % 2 != 0:
return 0 # sum(P) would be non-integer
if abs(target) > total:
return 0 # impossible to reach
new_target = (target + total) // 2
# Count subsets summing to new_target
dp = [0] * (new_target + 1)
dp[0] = 1
for num in nums:
for c in range(new_target, num - 1, -1):
dp[c] += dp[c - num]
return dp[new_target]
print(findTargetSumWays([1,1,1,1,1], 3)) # 5작은 예제를 따라가며 확인하기
nums=[1,1,1,1,1]이고 target=3인 경우, 총합은 5이고 새 목표값은 (3+5)//2=4입니다. [1,1,1,1,1]에서 합이 4가 되는 부분집합을 셉니다. 이는 C(5,4)=5입니다(1 다섯 개 중 4개를 양수로 선택하고 나머지 하나를 음수로 선택하면 1+1+1+1-1=3). DP는 정확히 5를 반환합니다. 이 변환은 부호 할당 문제를 표준적인 부분집합 개수 세기 문제로 우아하게 바꿉니다.
nums의 0 처리하기
nums에 0이 포함되어 있으면 0에 + 또는 -를 할당해도 합은 변하지 않습니다. 각 0은 유효한 할당 방법의 수를 두 배로 만듭니다. DP는 이를 자연스럽게 처리합니다. num=0을 처리할 때 내부 반복문 range(new_target, -1, -1)은 new_target에서 0까지 실행되고, dp[c] += dp[c - 0] = dp[c]에 따라 도달 가능한 모든 합이 두 배가 됩니다. range(new_target, num-1, -1)을 사용하면 특별한 처리가 필요 없습니다. 이때 num=0이면 new_target에서 0까지 역방향으로 시작합니다.
# With zeros: each zero doubles the count
print(findTargetSumWays([0, 0, 1], 1)) # 4
# Assignments: +0+0+1, +0-0+1, -0+0+1, -0-0+1 = all give sum 1복잡도 비교
완전 탐색 DFS는 O(2^n)입니다. 메모이제이션을 적용한 DFS는 시간과 공간 모두 O(n × total)입니다. 변환 기반 1차원 DP는 new_target ≤ total일 때 시간 O(n × new_target), 공간 O(new_target)을 사용합니다. 1차원 DP는 변환을 통해 인덱스 차원을 제거하므로 메모이제이션보다 훨씬 적은 공간을 사용합니다.
다른 배낭 문제와의 연결
목표 합 문제는 여러 배낭 문제 개념을 연결합니다. 처음에는 할당 문제로 시작하지만 부분집합 합 문제로 변환되고(부분집합 합 균등 분할과 유사), 부분집합 개수 세기를 적용한 동일한 0/1 배낭 역방향 순회 틀을 사용합니다(코인 교환 II와 유사). 이러한 연결을 익히면 면접에서 새로운 문제를 기존 패턴과의 구조적 유사성에 따라 빠르게 분류할 수 있습니다.
경계 사례와 면접 참고 사항
중요한 경우는 다음과 같습니다. (1) target = total: 모든 부호가 양수인 한 가지 방법만 있습니다. (2) target = -total: 모든 부호가 음수인 한 가지 방법만 있습니다. (3) target = 0이고 모두 0인 경우: 답은 2^n입니다. (4) 총합은 매우 크지만 n이 작은 경우 — 1차원 DP 배열의 크기는 total/2로 제한됩니다. 면접에서는 코딩하기 전에 변환 과정을 말로 먼저 설명해야 합니다. 이것이 뛰어난 지원자를 가르는 핵심적인 통찰입니다.
변환을 사용하지 않는 2차원 DP 대안
변환을 사용하지 않는다면, 처음 i개 숫자에 부호를 할당하여 합 s에 도달하는 방법의 수를 dp[i][s]로 정의합니다. 합은 음수가 될 수 있으므로 총합만큼 오프셋을 적용하여 dp[i][s + total]을 사용합니다. 이 방법에는 (n+1) × (2*total+1) 크기의 2차원 표가 필요합니다. 정확한 방법이지만, 변환 후의 1차원 배낭 DP보다 더 많은 공간을 사용하고 면접에서 빠르게 구현하기도 어렵습니다.
빠른 확인
이번 레슨에서 배운 자료 구조 및 알고리즘 — 코딩 면접 준비 개념을 제대로 이해했는지 확인해 보세요.
학습 내용 정리
이번 레슨에서는 다음을 배웠습니다. 목표 합은 부호 할당 문제를 (목표값 + 총합) / 2를 합으로 갖는 부분집합 개수 세기 문제로 변환합니다. 1차원 0/1 배낭의 역방향 순회는 O(n × new_target) 시간과 O(new_target) 공간에 부분집합의 개수를 셉니다. 또한 초기 유효성 검사(합이 홀수인지, 목표값의 절댓값이 총합보다 큰지)로 불필요한 DP 실행을 방지할 수 있습니다. 다음에는 다익스트라 알고리즘과 우선순위 큐를 사용해 최단 경로를 구하는 영역으로 들어갑니다.
자주 묻는 질문
“양수와 음수 부호를 사용한 목표 합” 강의는 무료인가요?
네 — “양수와 음수 부호를 사용한 목표 합” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“양수와 음수 부호를 사용한 목표 합”에서 뭘 배우나요?
목표 합 할당 문제를 부분집합 합의 차이를 구하는 배낭 문제로 변환해 O(n × sum) 시간에 해결합니다. 브라우저에서 직접 실행하는 실습 코드로 DSA Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.
“양수와 음수 부호를 사용한 목표 합” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 0/1 배낭과 공간 최적화
- 무한 배낭과 동전 교환 II
- 동일한 부분집합 합으로 분할
- 양수와 음수 부호를 사용한 목표 합