예상 대진표 문제 (2) - 이진법 풀이

 

 

이어지는 글 

해당 글에서 이어집니다.

https://kuck-su-labor.tistory.com/73

 

---

 

구현 문제

우선 첫 번째로 트리의 높이를 구하는 것은 쉽습니다. 여러 가지 방법이 있지요, 제일 쉬운 것은 2로 계속해서 나눈 횟수를 이용하거나 해서, 결국 지수를 구하기만 하면 됩니다.

문제는 두 번째, A와 B사이를 간추릴 방법입니다. 단순히 차이로 계산하기에는 재귀적인 구조여서 구현하기 힘들어집니다..

우리는 이 문제가 이진 트리과 관련이 있다는 것을 생각한다면 이진법으로 풀 수 있다는 것을 알 수 있습니다. 우선 참가자가 8명인 토너먼트가 존재한다고 할 때, 토너먼트 구조는 다음과 같고, 해당 참가자는 다음과 같이 이진 적으로 표현할 수 있을 것입니다.

 

 

이를 활용하기 위해서는 2가지 경우를 알아야만 합니다.

 

1. 두 값이 0과 N일 때

이때 만약 A와 B중 한 요소가 0이라면, 대전 횟수는 A와 B중 큰 숫자의 지수의 의해 결정됩니다.

 

예를 들면 다음과 같습니다. 0부터 7까지 있는 트리가 있다고 가정할 때. 0과 3이 주어진 경우를 트리로 나타내면 다음과 같습니다.

0이 항상 고정적이기 때문에 우리는 결과적으로 나머지 참가자 즉 N만 보면 됩니다. 즉 위에서 말했듯이 대전 횟수는A와 B중 0이 아닌 나머지 참가자 N의 의해서 결정된다고 볼 수 있습니다.

위의 경우 두 참가자가 만나기 위해서는 총 2번의 대결이 필요합니다. 이러한 경우를 이진법으로 나타낸다면, 0은 0이고, 3은 2 ¹ + 2⁰ + 0으로 나타낼 수 있습니다. 3이 가질 수 있는 최대의 지수는 1이고 높이는 대전 횟수에 비례하기 때문에, (최대높이) + 1로 나타낼 수 있을 것입니다.

 

 0과 3이 대전하는데 필요한 경기 수  =  (3의 가장 큰 지수 = 1) + 1 = 2

 

2. 두 값이 N과 M일 때

위의 경우는 문제가 없습니다. 하지만 그 나머지의 경우는 위의 방법을 사용할 수 없습니다. 아래의 경우를 보죠, 이번에는 0부터 7까지 있는 트리가 있다고 가정할 때. 4과 6이 주어진 경우입니다.

이러한 경우에는 0번부터 3번째 참가자는 신경 쓰지 않게 됩니다. 즉 이런 부분은 간추려야 하는 것입니다. 그렇지 않으면 정상적인 해가 도출되지 않습니다. 정확한 해를 구하기 위해서는 지수를 확인하는 것으로 해결할 수 있습니다. 한 번 0부터 7까지 이진적으로 적어보았습니다. 그 결과는 다음과 같습니다.

 

0 = 0   1 = 2⁰   2 = 2 ¹   3 = 2 ¹ + 2⁰   4 = 2²   5 = 2² + 2⁰   6 = 2² + 2 ¹   7 = 2² + 2 ¹ + 2⁰

 

이러한 경우에는 우리는 규칙을 발견할 수 있습니다. 4부터 7까지의 참가자를 이진적으로 나타내면 다음과 같습니다.

이 수 모두 2²을 포함하고 있다는 것을 알 수 있습니다. 그렇다면 한번 2² 를 한번 지워보도록 하겠습니다. 그렇다면 다음과 같습니다.

마지막 결과는 어디서 많이 본 것 같습니다. 맞습니다. 바로 위에서 했었던 0부터 3까지의 참가자의 이진 구조와 같습니다. 이렇게 된다면 위의 경우 즉 두 값이 0과 N일 때의 경우가 되므로 이를 통해 대전 횟수를 구하는 것이 가능합니다.

 

4와 7이 대전하는데 필요한 경기 수  =   0과 3이 대전하는데 필요한 경기 수 =  (3의 가장 큰 지수 = 1) + 1 = 2

 

---

 

지금까지 다룬 것들을 종합해서 간단하게 표현하면 위와 같습니다. 이는 모든 수는 각자의 수의 부분 집합이기 때문에 가능한 것입니다. 파보나치 수열과 비슷하지요, 사실 이러한 부분은 분할 정복법[Divide and Conquer]으로 풀이하는 것이지만 이의 대해서는 아직 다루지 않았기 때문에 여기서 더는 언급하지 않겠습니다.

 

결과적으로 이러한 점과 토너먼트가 포화 이진트리와 비슷한 점이라는 것을 고려한다면 이진법을 활용해서 위와 같은 풀이가 가능할 것입니다.

 

---

 

알고리즘 정리

우선 한번 알고리즘을 총 정리해 보도록 하겠습니다. 정리하면 다음과 같습니다.

1. 두 수 A와 B를 받는다. 2. 두 수를 이진법 구조로 바꾼다. (방법은 여러 가지) 3. 무한 반복      if(A의 최대지수 == B의 최대지수)      -> A와 B에서 지수가 최대인 것을 뺀다. (2로 나누면 됩니다.)      else      -> 루프문을 탈출한다. 4. A와 B중 가장 큰 지수 C에 1을 더한값을 해로 반환한다.

 

 

---

해당 알고리즘의 문제점

 

• 1. 0부터 시작

우선 위에서 언급했던 것과 실제 문제의 차이점이 있다면 0번째 참가자는 없다는 것입니다. 1번째부터 시작합니다. 이는 오류이지만 쉽게 각 요소를 1칸씩 쉬프트 하는 것으로 해결할 수 있습니다. 아래와 같이 해도 잘 동작합니다.

 

만약 위에서 한다면 1번과 2번 사이에 A와 B에 각각 -1씩 하는 것으로 구현할 수 있습니다.

 

• 2. 비용 발생

무한 반복을 구현하게 됩니다. 문제까지는 아니지만 이렇게 될 경우에는 위에서 했던 첫 번째 방법과 크게 다른 것이 없습니다. 좀 더 쉽게 구현할 수 있는 방법이 있을 것입니다.

이는 비트 연산을 통해서 더 쉽게 구현할 수 있을 것입니다. 비트는 결국 이진수이기 때문에 더 쉽고 빠르게 구현이 가능합니다.

 

---

 

 

 

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