중간에서 만나기
탐색을 나눠 지수를 절반으로 줄입니다
중간에서 만나기은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
완전 탐색이 너무 느릴 때
어떤 문제는 N이 40 정도라서 2^N개의 모든 부분집합을 시도하는 것이 불가능합니다. 중간에서 만나기 기법이 이런 중간 규모의 경우를 해결해 줍니다. 🤝
핵심 아이디어
입력을 두 절반으로 나눕니다. 각 절반을 완전 탐색으로 해결한 다음, 두 부분 결과를 영리하게 결합합니다.
지수 절반으로 줄이기
크기가 N/2인 두 절반은 전체 2^N 대신 각각 2^(N/2)의 비용이 듭니다. 이 제곱근 수준의 감소 덕분에 2^40이 다루기 쉬운 2^20으로 줄어듭니다.
대표적인 목표: 부분집합 합
어떤 부분집합의 합이 목표값 T가 되는지 물어봅니다. N이 40에 가까운 부분집합 합은 중간에서 만나기 기법의 대표적인 문제입니다.
첫 번째 절반 열거하기
왼쪽 절반의 모든 부분집합 합을 나열하여 저장합니다. 원소가 N/2개라면 합의 개수는 2^(N/2)뿐입니다.
from itertools import combinations
left = arr[:len(arr)//2]
sums_l = []두 번째 절반 열거하기
오른쪽 절반에도 같은 작업을 하여 모든 부분집합 합의 목록을 만듭니다. 이제 다루기 쉬운 목록 두 개가 생겼습니다.
조회로 결합하기
각 오른쪽 합 r에 대해 T에서 r을 뺀 값과 같은 왼쪽 합이 필요합니다. 집합이나 정렬된 목록을 사용하면 이 확인을 빠르게 할 수 있습니다.
need = T - r
found = need in left_set매칭하는 두 가지 방법
정확한 목표값을 찾을 때는 해시 집합을 사용하세요. 개수를 세거나 가장 가까운 합을 찾을 때는 한쪽 절반을 정렬하고 그 안에서 이진 탐색을 수행하세요.
시간 비용
전체 작업량은 검색이나 정렬에 필요한 로그 인자를 곱한 2^(N/2) 정도입니다. 이 복잡도 덕분에 N이 40에 가까운 문제도 풀 수 있습니다.
메모리라는 절충
한쪽 절반 전체를 저장하므로 메모리 사용량은 2^(N/2)까지 증가합니다. 제한을 지키려면 꼭 필요한 것만 저장하세요.
다른 활용 분야
부분집합 합 외에도 상한 이하의 최댓값 부분집합, 쌍의 개수 세기, 이산 로그와 유사한 문제에 사용할 수 있습니다. 깔끔한 분할이 필요한 문제에 잘 맞습니다.
빠른 확인
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개 중 3번째 강의입니다.
“중간에서 만나기” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.