04. 네 번째 수업: “대표 2명 뽑기” 가 조합이 되는 이유 (Why Combinations Work)

코딩 테스트 확률 문제를 풀 때 초보자들의 뇌가 가장 먼저 에러를 뿜는 분기점이 있습니다. “이 문제 텍스트에 순열(P) 곱하기 배치를 때려야 하나? 아니면 조합(C) 나누기 압축을 때려야 하나?”

정답은 문제의 퀘스트 조건이 “위계/서열/순서 데이터” 를 요구하느냐 아니냐에 100% 달려 있습니다. 가장 악질적이고 많이 출제되는 클래식 기믹, [직책] 과 [대표] 의 차이점을 확실히 렌더링해 봅시다.

1. 위계 질서($\mathbf{P}$): [회장 1명, 부회장 1명 뽑기]

반 학생 $10$명 중에서 학교폭력 예방 모임의 간부를 뽑습니다. 직책 테이블: [회장 슬롯] / [따까리 부회장 슬롯]

$A$가 회장, $B$가 부회장인 평행우주 엔딩은 해피엔딩입니다. 하지만 거꾸로 $B$가 일진짱 회장이고, $A$가 빵셔틀 부회장으로 순위가 리버싱 된 엔딩 우주는? 전혀 다른 배드엔딩 개별 게임 오버 시나리오입니다! 배기통에 순서태그 값이 붙어서 떨어지는 순열 조건이기 때문에, 그냥 무식하게 상자 $2$개를 열고 냅다 포격하면 끝납니다.

$\mathbf{_{10}P_2 = 10 \times 9 = 90}$ 가지 엔딩 씬 생성 완료!

2. 블록 압축($\mathbf{C}$): [그냥 공동 대표 2명 뽑기]

반 학생 $10$명 중에서 학교폭력 피해자 상담을 위한 “비밀 평등 요원 $2$명 패키지 세트” 를 뽑습니다. 직책 테이블: [요원 슬롯] / [요원 슬롯] (계급 없음, 서열 없음)

$A$ 와 $B$ 가 한 바구니에 요원 번들 팩으로 묶였습니다. 이 바구니를 뒤집어서 $B, A$ 순서로 포장지를 열어도 어차피 안에는 $A,B$ 듀오 콤보 세트 하나뿐입니다. 순서 데이터 태그를 프로그래머가 읽을 필요가 없으니 불필요한 메모리를 삭제(나누기 압축) 해버려야 합니다!

$\mathbf{{10}C_2 = \frac{{10}P_2}{2!}}$ $= \mathbf{\frac{10 \times 9}{2 \times 1} = 45}$ 가지의 듀오 콤보 바구니 생성 완료!

3. 대칭 버그: C 의 숨겨진 거울(Mirror) 마법

조합(C) 코딩을 짜다 보면 연산 효율을 수백 배로 올려주는 미친 버그성 스킬 하나를 발견하게 됩니다.

“야, 100명의 노예 중에서 내가 마음에 쏙 드는 98명의 노예를 구출할 건데 가지 수 좀 세 봐.”

하수: $\mathbf{{100}C{98}}$ 을 계산하기 위해 수식을 적습니다. $= \frac{100 \times 99 \times 98 \times 97 \times \dots 3}{98!}$ (계산하다 분필이 동나고 뇌출혈로 쓰러짐)

해커: “생각을 거꾸로 뒤집어(Mirror)!” 100명 중에서 98명을 “살릴 놈으로 고집스럽게 뽑아 바구니에 담는 행위” 나, 100명 중에서 단 2명만 “죽일 놈 블랙리스트로 골라서 버려버리는 행위” 나, 어차피 똑같이 반대편 세상(여집합) 의 결과를 찍어내는 완벽한 데칼코마니 복제 이벤트가 아닙니까!

조합의 미러링 락다운 정리: $\mathbf{{100}C{98} \ = \ _{100}C_2}$ “100개 중 98개를 고르는 고통은, 100개 중 2개를 고르는 꿀빨기와 결괏값이 무조건 $100\%$ 똑같다!”

이 거울 대칭 마법 덕분에 $\mathbf{_{100}C_2 = \frac{100 \times 99}{2} = 4,950}$ 이라는 답이 3초 만에 툭 떨어집니다. 현대 컴퓨터의 조합 연산 렌더링 내부 함수(라이브러리) 들도 이 미러링($N-R$) 체크 알고리즘이 내장되어 있어서, 큰 R 값이 들어오면 자동으로 작은 짝꿍 숫자로 변환 튜닝을 터뜨려 메모리 과부하를 싹 정리해 줍니다.

다음 강의에선 카드를 연달아 뽑을 때 앞 사건이 뒷사건의 멸망을 불러일으키는 ‘비복원 추출’ 과 확률의 콤보 연속 폭파에 대해 다룹니다!