모든 부분집합 생성하기
각 원소를 선택하거나 건너뜁니다
모든 부분집합 생성하기은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
부분집합을 생성하는 이유
많은 경시대회 문제에서는 작은 집합의 모든 부분집합을 시도하라고 합니다. 재귀를 사용하면 모든 부분집합을 깔끔하고 안정적으로 나열할 수 있습니다. 🧩
각 요소를 선택하거나 건너뛰기
핵심 아이디어는 각 요소마다 하나의 이진 선택을 하는 것입니다. 요소를 포함하거나 제외하면 됩니다. 가능한 선택을 모두 끝내면 부분집합 하나가 만들어집니다.
부분집합은 몇 개일까요
요소가 n개인 집합에는 정확히 2의 n제곱개의 부분집합이 있습니다. 각 요소가 개수를 두 배로 늘리기 때문입니다. 따라서 n은 20 이하 정도로 작아야 합니다.
재귀 계획 세우기
배열을 따라 인덱스를 이동합니다. 각 인덱스에서 두 갈래로 나누어 한 번은 요소를 선택하고, 한 번은 건너뜁니다.
기저 사례
인덱스가 마지막 요소를 지나면 현재 경로는 하나의 완전한 부분집합입니다. 이때가 부분집합을 기록할 기저 사례입니다.
코드로 구현하는 부분집합 재귀
이 재귀 순회는 끝에 도달하면 부분집합을 기록한 다음, 각 인덱스에서 건너뛰는 경우와 선택하는 경우를 탐색합니다.
def gen(i, cur):
if i == len(a):
out.append(cur[:])
return
gen(i + 1, cur)
gen(i + 1, cur + [a[i]])되돌려서 백트래킹하기
요소를 append한 뒤에는 재귀 호출이 끝나면 그 요소를 제거하여 다음 분기가 깨끗한 상태에서 시작하게 합니다. 이 되돌리기 단계가 백트래킹의 핵심입니다.
cur.append(a[i])
gen(i + 1, cur)
cur.pop()비트마스크를 사용하는 방법
0부터 2의 n제곱 - 1까지의 각 정수를 하나의 부분집합에 대응시킬 수도 있습니다. 각 비트가 어떤 요소를 포함할지 나타냅니다.
for mask in range(1 << n):
sub = [a[i] for i in range(n) if mask >> i & 1]저장하기 전에 복사하기
현재 목록 자체가 아니라 항상 현재 목록의 복사본을 저장해야 합니다. 그렇지 않으면 나중의 변경 사항이 저장해 둔 모든 부분집합을 덮어씁니다. ⚠️
조합 생성하기
크기가 k로 정해진 부분집합을 얻으려면 선택한 개수가 k에 도달했을 때 해당 분기를 멈춥니다. 그러면 부분집합 생성이 조합 생성으로 바뀝니다.
부분집합이 활용되는 곳
부분집합 열거는 작은 배낭 문제, 팀 선택 문제, 그리고 가능한 모든 선택을 검사해야 하는 실행 가능성 확인 문제를 해결하는 데 사용됩니다.
빠른 확인
요소가 n개인 집합에는 부분집합이 몇 개 있을까요?
복습: 모든 요소에서 분기하기
각 요소를 선택하거나 건너뛰고, 각 분기 후에 되돌려 모든 부분집합을 나열하는 방법을 배웠습니다. 개수가 2의 n제곱이므로 n은 작게 유지해야 합니다. 🎯
자주 묻는 질문
“모든 부분집합 생성하기” 강의는 무료인가요?
네 — “모든 부분집합 생성하기” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“모든 부분집합 생성하기”에서 뭘 배우나요?
각 원소를 선택하거나 건너뜁니다 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.
“모든 부분집합 생성하기” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.