부분집합 합과 분할
선택한 부분집합으로 목표에 도달합니다
부분집합 합과 분할은(는) CoddyKit의 무료 Competitive Programming Academy 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Competitive Programming Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
부분집합 합 문제
수들과 목표값이 주어졌을 때, 어떤 부분집합의 합이 정확히 그 목표값이 될 수 있을까요? 값과 무게가 같은 배낭 문제라고 볼 수 있습니다.
값이 아닌 불리언 DP
여기서는 최댓값이 아니라 도달 가능 여부를 추적합니다. dp[s]를 어떤 부분집합의 합이 정확히 s일 때 True가 되는 값이라고 합시다.
dp = [False] * (target + 1)
dp[0] = True0은 항상 도달 가능합니다
공집합의 합은 0이므로 dp[0]은 True로 시작합니다. 다른 모든 합은 어떤 수가 도달 가능하다는 것을 증명할 때까지 False로 시작합니다.
전이
각 수에 대해 s - num이 이미 도달 가능했다면 s도 도달 가능하다고 표시합니다. 하나의 수로 여러 합을 True로 바꿀 수 있습니다.
for num in nums:
for s in range(target, num - 1, -1):
dp[s] = dp[s] or dp[s - num]다시 역순으로
각 수는 최대 한 번만 사용하므로 안쪽 반복문은 역순으로 실행합니다. 0/1 배낭 문제와 같습니다. 정방향으로 진행하면 하나의 수를 재사용하게 됩니다.
판정 읽기
모든 수를 처리한 뒤 dp[target]이 답을 알려 줍니다. True는 유효한 부분집합이 존재한다는 뜻이고, False는 불가능하다는 뜻입니다.
분할 문제 시작하기
분할 문제는 배열을 합이 같은 두 부분으로 나눌 수 있는지 묻습니다. 이 문제는 곧바로 부분집합 합 문제로 바꿀 수 있습니다.
전체 합을 절반으로 나누기
전체 합이 홀수라면 같은 두 부분으로 나눌 수 없으므로 즉시 아니오로 답합니다. 그렇지 않다면 목표값은 간단히 total // 2입니다.
total = sum(nums)
if total % 2:
return False
target = total // 2부분집합 합 재사용
이제 어떤 부분집합의 합이 total // 2에 도달하는지만 확인하면 됩니다. 한쪽이 목표값에 도달하면 나머지가 자동으로 일치하는 두 번째 부분이 됩니다.
복잡도
비용은 n 곱하기 target 수준인 유사 다항식 시간입니다. target이 작으면 빠르고, 합이 매우 크면 느립니다.
문제의 한 계열
부분합, 분할, 0/1 배낭 문제는 하나의 엔진을 공유합니다. 선택하거나 버리는 형태를 발견하면 같은 반복문을 재사용할 수 있습니다.
빠른 확인
분할 환원을 확인해 보세요.
복습
논리값 DP와 역방향 반복문으로 부분합을 해결한 다음, 전체 합을 total // 2에 도달하는 문제로 분할 환원했습니다. 같은 엔진으로 새로운 문제도 해결했습니다. ✅
자주 묻는 질문
“부분집합 합과 분할” 강의는 무료인가요?
네 — “부분집합 합과 분할” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Competitive Programming Academy 강의 전체를 잠금 해제할 수 있습니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“부분집합 합과 분할”에서 뭘 배우나요?
선택한 부분집합으로 목표에 도달합니다 브라우저에서 직접 실행하는 실습 코드로 Competitive Programming Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Competitive Programming Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Competitive Programming Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.
“부분집합 합과 분할” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Competitive Programming Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Competitive Programming Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.