경우의 수 (Counting Principle)
쉽게 풀면
편의점에서 삼각김밥 3종류 중 하나와 음료수 4종류 중 하나를 고른다고 해봅시다. 삼각김밥을 고르는 방법은 3가지, 그 각각에 대해 음료수를 고르는 방법이 4가지이므로, 전체 조합은 3×4=12가지가 됩니다. 이렇게 "동시에 일어나는 여러 단계"의 경우의 수를 곱해서 구하는 것을 곱의 법칙이라 하고, "둘 중 하나만 고르는" 상황처럼 동시에 일어나지 않는 사건의 경우의 수를 더해서 구하는 것을 합의 법칙이라고 합니다. 순열이나 조합처럼 복잡한 계산도 결국 이 두 가지 기본 원리에서 출발합니다.
왜 중요한가
경우의 수를 세는 원리는 확률론, 통계학, 컴퓨터과학의 알고리즘 복잡도 분석 등 다양한 정량적 분야의 출발점입니다. 어떤 사건이 일어날 가능성을 계산하려면 먼저 전체 경우의 수와 관심 있는 사건의 경우의 수를 정확히 셀 수 있어야 하기 때문에, 경우의 수 개념은 확률 계산이나 조합적 최적화 문제를 다루는 논문에서 암묵적인 전제로 깔려 있는 경우가 많습니다.
논문에서는 이렇게 쓰입니다
이 문장은 경우의 수를 세는 능력이 이후 확률 학습의 기초가 된다는 점에서, 학습 성취도를 예측하는 선행 변수로 다뤄지고 있음을 보여줍니다.
생물학·의학 실험설계 논문에서, 여러 조건을 조합해 실험군을 구성할 때 경우의 수의 곱의 법칙을 적용해 필요한 실험군 수를 산출했다는 뜻입니다.
컴퓨터과학 논문에서 경우의 수가 너무 많아질 때(조합적 폭발) 모든 경우를 다 따져보는 대신 효율적인 근사 방법을 써야 한다는 논리를 설명할 때 등장하는 예시입니다.
조금 더 깊게 보면
경우의 수를 세는 기본 원리(합의 법칙, 곱의 법칙)는 순서를 고려하는지에 따라 순열(permutation)과 조합(combination)이라는 좀 더 구체적인 계산 방법으로 발전하며, 조건이 복잡해질수록 포함배제의 원리처럼 중복을 제거하며 세는 고급 기법이 필요해지기도 합니다. 컴퓨터과학에서는 가능한 경우의 수가 변수 개수에 비례해 기하급수적으로 늘어나는 현상을 조합적 폭발(combinatorial explosion)이라 부르며, 이런 상황에서는 모든 경우를 다 세는 대신 확률적 샘플링이나 근사 알고리즘을 사용하는 경우가 많습니다. 논문에서 "경우의 수가 방대하다"는 표현이 등장하면, 이후 어떤 방식으로 그 문제를 우회했는지를 함께 살펴보는 것이 좋습니다.
주의할 점
경우의 수를 셀 때 같은 상황을 두 번 세거나(중복), 반대로 빠뜨리는(누락) 실수가 흔합니다. 특히 뽑은 것을 다시 배열하는 문제인지 아닌지에 따라 순열과 조합 중 어느 것을 써야 하는지가 달라지므로, 순서를 따지는 문제인지 먼저 구분하는 것이 중요합니다.