[C/Python] 조합론

[알고리즘] 숫자의 마법, 조합론(Combinatorics) 완벽 가이드

프로그래밍에서 '경우의 수'를 구하는 조합론은 알고리즘의 기초이자 효율적인 문제 해결의 열쇠입니다. 기초 공식부터 대량 데이터를 처리하는 최적화 기법까지 정리해 봅니다.

---

1. 기초 체력: 팩토리얼(Factorial)

모든 조합론의 시작은 팩토리얼(n!)입니다. n개를 일렬로 세우는 모든 경우의 수를 의미합니다.

• 수식: n! = n * (n-1) * - - - - - * 1
• C언어 구현: 반복문(for)을 사용해 결과값에 계속 곱해주는 방식이 가장 안정적입니다.
• 주의점: 팩토리얼은 숫자가 폭발적으로 커집니다. C언어의 int는 12!, long long은 **20!**까지만 담을 수 있다는 점을 항상 기억해야 합니다.

---

2. 실전 응용: 이항계수(Binomial Coefficient)

서로 다른 n개 중에서 순서에 상관없이 r개를 뽑는 경우의 수입니다. 흔히 **nCr**로 표현합니다.

• 공식: {n}{r} = {n!} / {r!(n-r)!}
• 구현 포인트: 팩토리얼 함수를 만들어 두면 공식 그대로 구현할 수 있어 편리합니다.
• 성질: {n}{r} = {n}{n-r} (대칭성)을 이용하면 계산 횟수를 줄일 수 있습니다.

---

3. 한계 극복: 파스칼의 삼각형과 DP

n이 커지면(n > 20) 팩토리얼 값이 너무 커져서 직접 계산할 수 없습니다. 이때 사용하는 것이 **동적 계획법(Dynamic Programming)**입니다.

• 원리: {n}{r} = {n-1}{r-1} + {n-1}{r}
• 장점: 팩토리얼(곱셈) 대신 덧셈만 사용하므로 오버플로우 위험이 적고 매우 빠릅니다.
• 적용: '다리 놓기(백준 1010번)' 문제처럼 n이 30 정도인 경우, 미리 2차원 배열에 값을 채워두는 Lookup Table 방식을 사용합니다.

---

4. 성능의 완성: 초고속 입출력 기법

알고리즘 문제에서 데이터가 많을 때 '출력 초과'나 '시간 초과'를 피하는 비결입니다.

1. 매번 출력 (printf): 시스템 콜 부하가 커서 가장 느립니다.
2. 배열 저장 후 출력: 메모리 관리는 편하지만 여전히 printf 호출 횟수가 많습니다.
3. 문자열 버퍼 (sprintf + fwrite): [추천] 모든 결과를 하나의 커다란 문자열 버퍼에 담아 한 번에 출력합니다. 시스템 콜을 단 1번으로 줄여 압도적인 성능을 냅니다.

---

💡 정보처리기사 실기 대비 요약

2026년 시험을 준비하신다면 아래 세 단어는 꼭 챙겨가세요!

• FIFO/LIFO: 큐와 스택의 기본 원리 (이전 포스팅 내용 복습)
• 재귀(Recursion): 자기 자신을 호출하는 함수. 팩토리얼 구현의 대표적 방법.
• 메모이제이션(Memoization): DP에서 이미 계산한 값을 저장해두고 재사용하는 기법.

---

🛠️ IoT 엔지니어의 시선

실제 센서 노드나 임베디드 장치에서는 팩토리얼을 매번 계산하지 않습니다.

배터리를 아끼기 위해 **파스칼의 삼각형으로 미리 구한 값(Lookup Table)**을 메모리에 올려두고 즉시 참조하는 방식을 사용합니다. 이것이 바로 소프트웨어 최적화의 핵심입니다.