[김대수의 수학 어드벤처] 경우의 수 따질 땐 트리 구조 활용하면 일목요연

중앙선데이

입력

많은 사람이 수학적으로 문제를 풀 경우 방정식이나 어떤 특정한 틀에 따라 문제 해결을 시도하는 경우가 많다. 그러나 문제에 따라서는 전혀 다른 방법으로 접근해야 효율적인 경우도 많다. 컴퓨터 공학에서는 문제 해결 방법 가운데 트리(tree·수형도, 나뭇가지 그림)라는 구조를 흔히 사용한다. 트리는 장기·바둑·체스 등의 게임에서 진행과 전략을 구사할 수 있는 게임 트리 등으로도 폭넓게 활용되고 있다. 특히 경우의 수가 많을 경우에는 트리 구조를 활용하는 결정 트리(decision tree) 방법을 통해 주어진 문제를 일목요연하게 해결할 수 있다.

이제 결정 트리를 활용하는 예를 들어보자. 크기와 색깔이 똑같은 8개의 동전 중 하나가 다른 동전들보다 무거운 불량품이라고 하자. 또한 무게가 같거나 크고 작음만을 판단할 수 있는 하나의 천칭 저울을 사용한다. 그러면 몇 번의 저울질로 불량 동전을 찾아낼 수 있을까? 이 경우엔 단 두 번의 저울질만으로 무거운 불량 동전을 찾아낼 수 있다. 이 문제를 해결해 줄 수 있는 결정 트리는 <그림 1>과 같다. 여기서 편의상 각 동전에 1부터 8까지의 숫자를 부여하는데 >, =, < 은 각각 크고, 같고, 작음을 나타낸다.

먼저 1, 2, 3과 4, 5, 6을 각 묶음으로 천칭 저울로 계량해 보자. 만약 ‘=’이면 1부터 6까지는 정상인 셈이므로 나머지 7과 8을 저울질해 7이 크면 불량이고, 그 반대면 8이 불량으로 판정한다.

만약 1, 2, 3의 합이 4, 5, 6의 합보다 무거울 경우에는 1과 2를 비교한다. 이때 1과 2의 값이 같다면 3이 불량이고, 1이 2보다 무겁다면 1이 불량이고, 2가 1보다 무겁다면 2가 불량이다.

만약 1, 2, 3의 합이 4, 5, 6의 합보다 가벼울 경우에는 4와 5를 비교한다. 이때 4와 5의 값이 같다면 6이 불량이고, 4가 5보다 무겁다면 4가 불량이며, 4가 5보다 가볍다면 5가 불량이다.

결정 트리에서는 어떤 단계에서 나타날 수 있는 모든 경우를 체계적인 몇 가지로 나누어 판단할 수 있도록 해준다.

[문제 1]에서는 공 2개를 천칭 저울 양쪽에 하나씩 올림으로써 판단할 수 있다. 만약 천칭 저울이 균형을 이루면 나머지 공이 가벼운 것이 된다. 만약 왼쪽이 무거우면 오른쪽 공이 가벼운 공이 되고, 오른쪽이 무거우면 왼쪽 공이 가벼운 공이 된다. [문제 2]는 간단하면서도 잠시 동안이나마 생각하게 만들며, 발상의 중요성이 강조되는 문제다. [문제 3]에서는 6개의 공 가운데 4개를 골라 2개씩 양쪽 저울에 올린다. 이것의 결정 트리는 해답과 같다. 따라서 두 번이면 된다.