자료구조와 수능 수학: 트리(Tree)로 경우 나누기

Leesoft·2022년 10월 18일

요즘 수학 과외를 하면서 수능 기출 문제들을 다시 풀어보고 있는데, 자료구조를 공부하고 나서 수능 문제를 보니 적용해 보면 좋은 방법이 있어서 나중에 과외를 할 때 알려주거나 누가 보고 도움이 된다면 좋을 것 같아서 여기에 적어 두려고 한다! 물론 사람마다 스타일이 다르니까 평소에 자주 쓰고 편한 방법이 있으면 그 방법대로 하는 게 좋겠지만... 혹시 고난도 문제에 조금 더 편하게 다가가고 싶다면 한 번쯤 연습해 보는 것도 좋을 것 같다!

오늘은 크게 3개의 고난도 문제를 다룰 예정인데, 하나는 현행 고등학교 수학 I의 수열, 하나는 수학 II의 다항함수, 마지막 하나는 확률과 통계의 조건부 확률로 수능 범위에서 골고루 가져왔다! (미적분, 기하는 미안...하지만 충분히 적용할 수 있을 듯!)

이번에 풀어 볼 문제

일단 문제부터 보자! 풀어 보고 싶은 사람은 먼저 풀어 봐도 좋을 것 같다!

예제 1. 2021학년도 9월 나형 21 (2020 실시)

예제 2. 2019학년도 6월 나형 30 (2018 실시)

예제 3. 2023학년도 수능완성 확률과통계 실전 모의고사 1회 28 (2022)

해설지 스포 주의!

그리고 해설지를 보면 대부분 이렇게 되어 있다...! 물론 해설을 꼼꼼하게 읽어보라는 의미는 아니고 지금은 실전에서 이렇게 길쭉하게 풀기는 어렵다는 정도만 생각하면 된다.

예제 1번 해설

예제 2번 해설

예제 3번 해설

이런 문제들의 특징은 바로 아래와 같이, 문제를 해결하기 위해서 많은 세부적인 경우로 나누어야 하고 각각의 경우 안에서 더 세부적인 경우들이 생기는 경우, 즉 아래의 오른쪽 그림과 같은 모양이 만들어지게 된다!

물론 해설을 쓰신 분들이 능력이 없어서 이렇게 어렵게 쓰신 게 아니라 모든 풀이를 단지 글로만 전달해야 하다 보니 어쩔 수 없이 이러한 해설이 나올 수밖에 없는 것 같긴 하지만, 100분 내에 30문제를 풀어야 하는 시험에서 이러한 풀이를 시도한다면 실수가 생기거나 흐름을 놓치거나 끝이 보이지 않는 풀이에 막막함을 느끼게 될 것 같다...!

또 출제 의도가 다양한 경우를 고려하고 종합적인 사고로 답을 찾도록 하는 것인 문제를 풀기 위해서 경우를 나누는 것은 당연한 것이고, 혹시 경우 나누기를 하지 않아도 되는 획기적인 풀이가 있다고 하더라도 시험장에서 빠른 시간 내에 그것을 떠올리고 시도하기도 힘들다.

그래서 이번에는, 많은 경우 나누기와 노동을 해야 한다는 것을 받아들이되, 불필요한 노동과 실수를 줄이고 효과적으로 문제를 해결하는 데 도움을 주는 자료구조인 트리(Tree)에 대해서 소개하려 한다.

트리(Tree)란?

여러 개의 데이터를 저장할 때 사용되는 자료구조 중 하나인데, 데이터 간의 관계를 그림으로 나타내었을 때 나무 모양으로 보인다고 해서 트리이다! 템트리 할 때 그 트리다! 자세한 정의나 설명도 있지만 자료구조 알려주는 글이 아니므로 패스!

사실 경우의 수 단원에서 수형도(Tree diagram)라는 내용으로 배우는데, 이것도 맞다!

그런데 이 글에서는 수형도를 경우의 수 구하는 데에만 쓰는 게 아니라, 조금 넓게 확장해서 경우를 (아주) 많이 나누어야 하는 문제에 전반적으로 사용해 볼 생각이다!

기본적인 적용 방법

방법은 간단한데, 문제를 풀다가 경우를 나누어야 하는 상황이 오면 아래쪽으로 가지를 치면서 가지에 조건이나 확률 값 등을 적는 것이 전부이다!

그 이후로 문제를 풀다가 어떤 경우 안에서 또 경우를 나누어야 한다면 똑같이 그 밑에 가지를 치면 된다! 간단한 예시는 아래와 같다.

이러한 간단한 변화로 인해서 생기는 장점은 크게 세 가지가 있다.

첫째로 어디서 어떻게 경우가 나누어지는지, 또 현재 어떤 경우를 고려하고 있는지를 쉽게 확인할 수 있다는 점이다. 만약 위의 예시에서 각각의 경우마다 풀이가 길어진다면 (i), (ii), (iii)이 먼 위치에 있어 들여쓰기를 지키거나 표기법을 통일하고 꼼꼼히 확인하지 않으면 경우가 어떻게 나누어졌고 지금은 어떤 경우에 대해 구하고 있는지 찾기 어려울 수 있지만, 트리에서는 나뭇가지만 따라가면 고려하고 있는 상황과 조건을 모두 쉽게 확인할 수 있어 좋다!

둘째로는 가지만 잘 표시한다면 여러 가지 가능성 중, 가장 고려하기 쉬운 경우부터 원하는 대로 찾아 문제를 풀어갈 수 있다는 점이다! 위의 예시에서도 마찬가지로 (i), (ii), (iii)으로 경우가 나누어지고 세부적인 경우가 생긴다면, 보통 (i)부터 고려하고 세부 항목이 나오면 (i)-a. 부터 차례로 해결해 나가게 되고, 다른 예시를 먼저 고려하려고 하면 중간의 풀이를 건너뛰게 되어 역시 어떤 경우를 놓쳤는지를 파악하기 어렵게 된다. 하지만 트리에서는 모든 경우가 수평선상에 놓여 있기 때문에, 여러 나뭇가지 중 가장 쉬워 보이는 경우부터 문제를 해결하다 보면 자연스럽게 문제가 이해되고 다른 경우도 더 수월하게 풀어낼 수 있을 뿐만 아니라 모든 경우를 고려하지 않아도 되는 문제들의 경우에는 훨씬 효율적으로 문제를 해결할 수 있게 된다.

셋째는 만약 여러 가지 경우를 고려하면서 같은 논리를 사용하거나 중복되는 계산이 발생할 때 이를 쉽게 확인하고 적용할 수 있다는 점이다! 역시 글로 적는 풀이에서는 윗부분을 찾아보고 같은 논리를 적용해야 하지만, 트리의 경우에는 같은 모양의 트리가 반복되기 때문에 같은 논리를 적용한다는 점을 직관적으로 확인할 수 있게 된다.

트리를 이용한 예제 문제 해결 그림

예제 1번 무식하게 풀기

맨 앞에 소개한 예제 1번 문제를 통해, 트리의 세 가지 장점 중 첫 번째에 대해 알아보자! 위의 예제 1번의 해설지에서는 $a_1 \le a_2$ 와 $a_1 \ge 0$ 을 기준으로 경우를 나누어야 한다는 것을 바로 파악하고 (i)에 각각 ①, ②번, (ii)에 각각 ①, ②의 4가지로 나누었다. 하지만 이를 바로 파악하지 못한 채 만약 $a_1 = a$ , $a_2 = b$ 로 정하고 $a_1$ , $a_2$ , $a_3$ , $a_4$ , $a_5$ 의 대소 관계를 몰라서 경우를 나누어야 한다고 생각했다면 총 $2^5=32$ 개의 경우를 고려하는 상황이 벌어지게 되는데, 이걸 글로 다 적는다는 것 역시 쉽지 않다.

하지만 정말 32개의 경우를 고려한다는 생각으로 무식하게 트리를 그리고 조건을 적고 모순되는 조건에 가지를 친다면... 많은 경우의 수를 고려했음에도 불구하고 5개의 후보가 남았다는 것을 쉽게 확인하고 차근차근 문제를 풀 수 있다!

물론 해설지처럼 $a_3 = 2$ 를 미리 대입해서 풀었다면 이 정도로 나누지 않아도 되었겠지만, 이렇게 풀더라도 트리가 효과가 있다는 이야기를 하고 싶었고 정말 $a_3 = 2$ 를 미리 대입해서 트리를 그리는 것도 좋은 방법이 될 것이다!

예제 2번 유식하게 풀기

다음은 2번 예제를 통해 트리의 세 가지 장점 중 두 번째에 대해 알아보자!

일단 두 조건으로부터 이걸 얻었을 것이고, 맨 위의 $f(1)=f(1)f(2)$ 부터 마지막 조건까지 해결하려고 보니 경우가 계속 나누어지는 구조이다.

역시 이렇게 경우가 나누어질 텐데, 이렇게 트리로 경우를 나누고 나면 다음에 해결할 조건인 $f(1)+f(2)=f(2)f(3)$ 을 보면서 어떤 것부터 구하면 좋을지를 생각해 보고, 더 금방 풀 수 있을 것 같은 조건을 선택하면서 풀이할 수 있다. 다음에 고려할 조건에는 $f(2)$ 가 2번 포함되어 있으므로, $f(1)=0$ 보다는 $f(2)=1$ 을 대입해서 계속 진행하면 금방 확인할 수 있을 것 같은 느낌이 들어서 이쪽으로 진행했다! 물론 해 보고 안 되면 반대쪽 조건도 구하면 되니까...!

비슷한 방식으로 답을 금방 확인할 수 있을 것 같은 조건으로 계속 진행해서 트리를 그린 결과 아래와 같이 $f(1)$ 부터 $f(5)$ 까지의 값 후보를 찾아냈고, 그 값으로 그림을 그려서 이렇게 찾은 함수가 조건을 만족하는 것을 확인하였다!

이 문제는 조건을 만족하는 경우를 모두 찾는 것이 아니라 하나만 찾으면 되기 때문에, 쉬워 보이는 조건이나 빨리 풀 수 있는 조건을 골라서 풀다 보면 이렇게 적은 경우만 고려하고도 문제를 풀 수'도' 있다!

물론 "이 문제는 운이 좋아서 잘 들어맞고 금방 풀린 거 아니야?"라고 질문한다면... 맞다! 하지만 안 들어맞으면 돌아가서 다시 풀면 되고, 내가 강조하고 싶은 말은 많은 경우들을 실수할 우려 없이 내 마음대로 골라서 풀 수 있다는 것이 엄청난 시간과 노력을 절약해 줄 수도 있다는 것이다!

예제 3번 쉽게 풀기

마지막으로 예제 3번을 통해 트리의 세 가지 장점 중 세 번째를 알아보자!

해설지에서는 총 9가지의 경우를 고려하고, 해당되는 경우를 찾아 조합으로 계산한다. 그런데 정말 9가지 경우를 따로 고려해야 할까? 트리를 그려보자!

흰 공이 $w$ 개 있고 검은 공이 $b$ 개 있는 상황을 트리에 $(w, b)$ 로 표시하고, 공 2개를 뽑을 때 나오는 경우와 그 확률을 계산해서 가지에 적어주면 이렇다.

여기에 개수가 적은 색의 공을 2개 더 넣는 과정을 추가하면 아래와 같다.

이제 1회 시행이 끝났고, 아래쪽에서 $(4,3)$ 이 또 등장했다! 그렇다면 같은 시행을 한 번 더 하게 되면 트리의 모양도 똑같지 않을까?

그리고, 남아 있는 $(3,4)$ 역시, $(4,3)$ 에서 공의 색만 바뀐 것이므로, 각각의 확률 값은 같지만 공의 색만 달라질 것이다. 그래서 여기도 계산 없이 구할 수 있다.

개수가 적은 색의 공을 다시 넣어주면 트리는 아래와 같은데, 놀라운 사실은 트리의 중복된 모양을 발견한 덕분에 실제로 계산한 확률 값은 맨 위의 3개밖에 없다는 점이다(심지어 나머지 하나는 여사건으로 구했다)!

마지막으로 문제에서 주어진 사건을 표시하고 조건부 확률을 구하면 되는데, 나올 수 있는 최종 결과의 확률은 모두 $\frac{□}{7}×\frac{□}{7}$ 꼴이므로, 분모를 무시하고 계산해 주면 답을 쉽게 구할 수 있다!

마무리

이렇게 수능 고난도 문제들에서 경우를 많이 나누어야 할 때 트리를 사용하면 좋은 이유와 예시를 살펴보았고, 대부분의 해설지가 따르고 있는 (i), (ii), ...를 세로로 나열하는 방법과 비교했을 때 경우를 나누어 문제를 해결한다는 점은 같지만 경우를 표시하는 방법이 다른 것이라서 조금만 연습하면 적용하기 어렵지 않을 것이라고 생각한다! 마지막으로 오늘 포스팅을 간단히 요약해서 적고 마무리해야지!