경우의 수

경우의 수 number of cases

경우의 수는 왜 구하는가?

 우리는 경우의 수를 구하는 다양한 방법을 배운다. 그렇다면 왜 우리는 경우의 수를 배우는 것일까? 그 이유는 산업시대 이전의 농경시대 때에도 여러가지 경우의 수를 구하는 과정을 상정해 볼 수 있다. 이를 테면, 다음과 같은 가상의 원시 농경 사회의 풍경을 살펴보자.

 일반인 A씨는 나무에서 열매를 따서 보관을 하였다. 하나하나 세면서 n개의 열매를 구했다는 것을 알게 되었다.^[각주:1] 일반인 A씨는 자신의 마을에 사는 m명의 사람이 자신과 똑같이 n개의 열매를 구해서 마을 전체적으로 nm개의 열매를 구했다는 것도 알게 되었다.^[각주:2] 일반인 A씨가 사는 마을의 족장은 이번에 구한 열매를 보관할 사람을 p명의 일반인 중에서 k명을 뽑아야 겠다고 생각하였다.^[각주:3] 그런데 생각을 해보니, 유사시에 빠른 의사 결정을 하기 위해서는 열매를 보관하는 k명에 서로 다른 지위를 부여해야겠다는 생각도 들었다.^[각주:4] 한편, k명을 뽑는 것은 좋지만 마을 사람들의 의견을 반영하기 위해서 p명의 일반인이 공객적으로 k명 중 자신의 믿음이 가는 사람을 지지해서 뽑기로 하였다.^[각주:5] 그런데 k명을 뽑는 것도 좋지만 공개적인 지지를 꺼리는 사람을 위해서 무기명으로 k명 중 자신이 믿음이 가는 사람을 뽑는 선거를 실시하기로 했다.^[각주:6]

 위 사례에서 알 수 있듯이, 우리는 일상생활에서 많은 의사 결정을 내리기 위해 은연중에 경우의 수를 다양한 방법(합의 법칙, 곱의 법칙, 조합, 순열 등)을 실생활에 적용하고 있음을 알 수 있다. (각 경우의 수를 구하는 방법은 각주를 통해 밝혀 두었다.)

 이러한 사례는 비단 옛 농경사회 뿐만 아니라, 현대 사회에도 마찬가지로 적용할 수 있다. 이를 테면, 우리는 일상 생활에 일어나는 다양한 사건을 상태공간트리(State Space Tree)를 이용해서 정리를 하고, 예상되는 경우의 수를 구해본다. 여기서 상태공간트리란 초기 상태의 사건에서 시작하여, 어떤 상태 A에서 다른 어떤 상태 B로 갈 수 있다면, 상태 A를 나타내는 노드와 상태 B를 나타내는 노드가 이어져 있는 트리를 말한다. 예컨대, 동전을 2번 던지는 경우에 대한 상태공간트리의 예는 다음과 같다.

상태공간트리의 예

 위 그림에서 알 수 있듯이, 초기상태로부터 나타날 수 있는 경우를 위와 같은 나무 형태로 정리하여 트리로 정리할 수 있다. 동전을 2번 던지는 경우에는 규칙성이 있기 때문에 위와 같은 트리로 정리하지 않더라도 전체 경우의 수를 구할 수 있지만, 규칙성을 알 수 없는 경우에는 위와 같은 트리 형태로 정리하는 것도 한 가지 방법이 될 수 있다.

 경우의 수는 확률을 구하는 데에도 이용할 수 있다. 확률은 대개 전체 경우의 수에서 그 문제 상황에서 주시하고 있는 상황에 대한 경우의 수의 비로 구할 수 있다. 가령, 복권이 당첨되는 확률은 복권에서 나타날 수 있는 전체 경우의 수에서 구입한 복권의 수가 당첨될 수 있는 확률이 된다는 것이 이에 대한 대표적인 사례가 될 수 있다. 경우의 수를 통해 확률을 구하는 것을 통해, 실생활에서 접하는 다양한 의사 결정 상황에서 적절한 선택을 하는 데에 도움을 받을 수 있다.

 정보과학(전산학)에서는 경우의 수를 활용해서, 알고리즘의 시간 복잡도나 공간 복잡도를 계산하는 데에 경우의 수의 개념을 많이 사용한다. 어떤 알고리즘의 시간 복잡도나 공간 복잡도란 간단하게 말하면 그 알고리즘을 구현한 프로그램이 자료의 크기 n이 주어졌을 때, 어느 정도의 연산 횟수가 필요하며(시간 복잡도), 그 연산을 하는 데에 어느 정도의 공간 저장이 필요한지(공간 복잡도)를 알아본 지표이다. 시간 복잡도나 공간 복잡도를 통해서, 구현하고자 하는 알고리즘이 현실적으로 구현이 가능하며, 그것을 통해서 의미 있는 결과를 얻을 수 있는지 뿐만 아니라, 여러 알고리즘의 특성을 알아 볼 수도 있다. 이런 이유로 현대 컴퓨터 공학에서 알고리즘을 구현하는 데에 있어서 이러한 경우의 수를 구하는 것이 중요하다.

 이와 같이, 경우의 수는 시간을 넘어서서 우리 일상 생활에서 여러 결정을 내리는 데에 큰 도움을 준다는 것을 알 수 있다. 경우의 수 그 자체뿐만 아니라, 그것을 통해서 구할 수 있는 확률 역시 우리에게 적절한 의사 결정을 하는 데에 도움을 준다는 것도 알 수 있었다. 경우의 수를 구하는 일련의 과정은 알고리즘을 구현하는 과정에서 알고리즘의 구현 가능성을 알아보고, 정성적인 평가를 하는 데에 이용될 수 있다는 것도 알 수 있었다. 이를 통해, 경우의 수를 구하는 것과 보다 효율적으로 구하는 여러 가지 방법을 아는 것이 대단히 중요하다는 것을 알 수 있다.

1. [합의 법칙] 열매를 따는 사건은 각각이 배반이고, 이들 n개의 사건에서 구한 열매의 수는 n개이다. [본문으로]
2. [곱의 법칙] '열매를 n개 구한다'는 사건이 똑같이 m번 나타났다. [본문으로]
3. [조합] p명 중에서 k명을 뽑는다. [본문으로]
4. [순열] p명 중에서 k명을 뽑고, 각각의 순위를 정한다. [본문으로]
5. [중복조합] k명에 대해서, p명이 공개적으로 지지한다. [본문으로]
6. [중복조합] k명에 대해서, p명이 비공개적으로 지지한다. [본문으로]