예상 대진표 문제 (1) - 개요

 

 

들어가는 글

안녕하세요 오랜만입니다. 한 동안 코틀린의 대해서 유용한 기능이나 팁 등을 알아보는 시간을 가졌습니다. 이러한 글을 쓰는 것은 저도 정리가 되는 부분이 있어 유용합니다. 가끔씩 생각나지 않은 부분이 있다면, 한 번씩 둘러보게 되더라고요. 이 뿐만 아니라, 남들에게 도움도 될 수 있다면 더 좋겠죠.

이러한 나날이 계속되던 중에 우연히 프로그래머스에 있는 문제를 풀어보았는데 이에 대해서 글을 써 보는 것도 좋겠다는 생각이 들었습니다. 이번 시간에는 우리가 지금까지 다뤄왔던 자료구조인 이진트리를 비트 연산을 통해 쉽게 다루 어보는 시간을 가지려고 합니다. 자세한 수학적인 설명과, 문제 풀이를 통해서 이번 글을 써 보려고 합니다.

 

---

 

문제

해당 문제의 출처는 다음과 같습니다.

https://programmers.co.kr/learn/courses/30/lessons/12985

 

문제가 길지만, 간단하게 축약해 보자면 다음과 같습니다.

N명이 참가하는 토너먼트에서 참가자 A와 B가 몇 번의 대결을 거처야 만날 수 있는가? ※ N은 2의 지수 승이다. ※ A == B 인 경우는 없다. ※ 부전승이나, 무승부 등의 변친 적인 부분은 없으며, A와 B는 만나기 전까지는 항상 대결에서 이기는 것을 전제로 한다.

 

위의 문제를 보면 N이 2의 지수 승이라는 점, 그리고 각 구성요소 2명이 만나는 토너먼트의 구조를 생각해보면 이진트리를 생각해 볼 수 있을 것입니다.

 

이러한 2진 트리의 구조를 생각했을 때, 풀 수 있는 방법은 크게 2가지입니다.

첫 번째 방법 : 실제로 트리를 재귀적으로 실행하면서, 횟수를 구하는 방법 두 번째 방법 : 비트연산을 활용해서 바로 횟수를 구하는 방법

 

첫 번째 방법은 완전 탐색의 관한 글을 읽어보신다면 어렵지 않게 푸실 수 있을 것 같습니다.

따라서 이번 시간에는 두 번째 방법인 비트 연산을 이용하도록 하겠습니다. (사실 여기에는 일종의 분할 정복법[Divide and Conquer]의 내용도 포함하지만, 이는 아직 다루지 않았기 때문에 나중에 간단히만 짚겠습니다.)

 

---

 

문제 분석

우선 문제를 분석해 봅시다. 이러한 문제를 어떻게 풀 수 있을까요? 우선 2가지 문제를 해결해야 합니다.

 

• 1. 대결 횟수 구하기

첫 번째는 트리에서 몇 번의 대결이 필요한 지를 구하는 방법입니다. 이는 쉽게 알 수 있습니다. 바로 트리의 높이입니다. 한번 높이가 2인 트리만 확인해 봅시다. (높이가 1인 경우는 토너먼트라고 볼 수 없으므로, 2부터 시작해야 함)

높이가 2인 트리만 보자면 사실상 결승전입니다. 대결은 1번이면 충분합니다.

높이가 3일 때, 4일 때는 약간 다르지만, 흐름은 크게 다르지 않습니다. 각각 대결은 많아도 2번, 3번이면 충분하죠. 이처럼 대결 횟수는 트리의 높이에 비례할 수 있습니다. 이점을 고려해서 우리는 트리의 높이를 구하는 알고리즘 하나가 필요합니다.

 

• 2. 대결 범위 좁히기

위에서 문제가 발생합니다. 결승전, 즉 높이가 2인 트리의 경우에는 명백하게 1번의 대전 횟수만을 필요로 합니다. 하지만 높이가 3인 경우부터는 상황이 달라집니다. 높이가 3부터는 대전 횟수가 1번 필요할 수 있고, 2번이 필요할 수 있습니다. 즉 높이가 N일 때는 1~N-1까지의 대결 횟수가 필요합니다. 아래의 그림을 보시면 쉽게 이해가 되실 겁니다.

때문에 단순히 높이에 비례해서 대결 횟수를 구하는 데에는 무리가 있습니다. 하지만 다음과 같이 하면 높이에 비례해서 대결 횟수를 수할 수 있을 것입니다. 다음 그림을 봐주세요

위의 상황에서는 참가자 5번과 8번에 필요한 대결 횟수를 구하는 방법입니다. 만약 다음과 같은 상황이라고 가정한다면, 우리는 굳이 모든 노드를 순회할 필요 없습니다. 왜냐하면 마지막 부분만 간추려서 확인하면 되기 때문입니다. 아래와 같이 말입니다.

이렇게 간추리게 되면 높이에 비례해서 대전 횟수를 구하는 것이 가능합니다. 위와 같은 경우는 결국 높이가 3인 경우가 됩니다. 따라서 대전 횟수도 2회가 필요하고, 실제로도 그렇습니다. 우리는 이를 전제조건으로 활용할 수 있을 것입니다. (이러한 전제조건을 증명하는 것은 또 다른 문제이지만 우선 그렇다고 넘어가 봅시다.)

 

결국 정리하자면 다음과 같을 것입니다.

전체 이진트리에서 A와 B사이를 간추린 트리 T의 높이를 구하는 것으로 참가자 A 와 B 사이의 대전횟수를 구할 수 있다.

 

 

 

 

다음 글에서 이어집니다...