예상 대진표 문제 (3) - 비트연산과 이진트리

 

 

이어지는 글 

해당 글에서 이어집니다.

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

 

---

비트 연산을 활용해서 풀기

참가자 1번부터 8번까지의 사람이 토너먼트를 한다고 했을 때 각 도전자의 위치를 이진수로 표현하면 다음과 같습니다. ( 0부터 시작하기 위해 -1을 하고, 0을 생략했습니다. )

예를 들어 7번 참가의 경우에는 다음과 같습니다.

 

(7 - 1) = 2² + 2 ¹

 

하지만 사실 다음과 같이 표현할 수도 있습니다.

 

(7 - 1) = (2² * 1) + (2 ¹ * 1) + (2⁰ * 0)

 

사실 생략이 있었지만 위와 같은 표현이 맞습니다. 그리고 이를 이진수로 바꾸게 되면 다음과 같습니다.

 

(7 - 1) = (2² * 1) + (2 ¹ * 1) + (2⁰ * 0) = 110

 

각 자리는 결국 2의 지수를 의미합니다. 지금까지 직접 지수를 구하고, 비교하고 하는 연산은 필요가 없게 될 것입니다. 간단히 최대 지수는 2라고도 알 수 있는 것입니다. (이렇게 되면 필요한 대전 횟수는 2+1 = 3회가 필요하게 됩니다.)

이러한 비트를 통해 연산을 하게 된다면 반복의 횟수도 줄일 수 있을뿐더러 메모리의 낭비도 줄일 수 있습니다. 심지어 위와 같이 비트를 사용한다면 비트의 길이만으로도 대전횟수를 구할 수 있지요 ( 비트의 길이 수 == 대전횟수가 됩니다. )

한번 이러한 특성을 활용해서 문제를 다시 풀어보도록 하겠습니다.

참가자 1부터 8까지 있는 토너먼트가 있다고 가정할 때. 참가자 7과 8이 주어진 경우입니다. 이러한 경우에 각 참가자 7과 8의 대해서는 다음과 같이 이진수로 표현할 수 있습니다.

 

(7-1) = (2² * 1) + (2 ¹ * 1) + (2⁰ * 0) = 110

(8-1) = (2² * 1) + (2 ¹ * 1) + (2⁰ * 1) = 111

 

트리로는 상황이 다음과 같습니다.

여기서 비트로써 맨 처음 자릿수가 같기 때문에 이를 제거할 수 있습니다. 그럼 다음과 같은 상태 됩니다.

 

(7-1) -> (2⁰ * 0) = 0

(8-1) -> (2⁰ * 1) = 1

이를 통하면 결국 서로 만나는데 1번의 대결만이 필요하다는 것을 알 수 있습니다.

 

---

 

이번에는 다른 경우를 보겠습니다. 참가자 2과 8이 주어진 경우입니다. 이러한 경우에 각 참가자 2과 8의 대해서는 다음과 같이 표현할 수 있습니다.

(2-1) = (2² * 0) + (2 ¹ * 0) + (2⁰ * 1) = 1

(8-1) = (2² * 1) + (2 ¹ * 1) + (2⁰ * 1) = 111

 

이진수로는 앞자리를 생략할 수 있지만, 구현상으로는 아래처럼 하는 것이 비교하는데 편할 것입니다.

 

(2-1) = (2² * 0) + (2 ¹ * 0) + (2⁰ * 1) = 001

(8-1) = (2² * 1) + (2¹ * 1) + (2⁰ * 1) = 111

이러한 경우에는 비트의 첫째 자리가 다르기 때문에 더 이상 비트 자릿수를 줄일 수 없습니다. 실제로도 그렇기 때문에 참가자 2번과 8번이 만나는데 필요한 대결 횟수는3번입니다.

이런 식으로 비트로 생각해서 계산한다면 구현과 계산에 있어서 더 쉽게 계산할 수 있을 것입니다.

 

---

 

구현해 보기

실제로 한번 구현해 보도록 하겠습니다. 여러 가지 방법이 있습니다. 우선 가장 쉬운 방법으로 구현해 보았습니다. 언어는 kotlin을 사용했습니다.

 

• 1. 진수 변환하기

비트 연산자를 활용하면 좀 더 빠르게 할 수 있을지 모르겠습니다. 하지만, 이번 시간에는 이진수를 직접 확인해보자는 취지에서 toString() 함수를 활용해 보겠습니다.

toString()은 단순히 String으로 바꾸어주는 함수입니다만, 파라미터 값으로 숫자를 넣으면 해당 진법으로 변환됩니다. 우리는 이진법을 활용할 것이기 때문에 다음과 같이 하겠습니다.

이때 주의할 것은 참가자의 수에 -1을 해야 한다는 것입니다. 위에서 여러 번 언급했었죠.

 

 

• 2. 문자열 길이 확인하기 (비트 길이가 같을 경우)

구현 방법에는 다양한 방법이 있습니다만, 우선 저는 먼저 문자열의 길이를 확인하도록 하겠습니다. toString()으로 변환하게 되면 우선 문자열의 길이가 다릅니다. 이렇게 되면 인덱스 별로 확인해야 하지만, index out of bound exception가 발생할 위험이 있습니다. 따라서 먼저 문자열의 길이를 확인해서 같은 경우에만 따로 보려고 합니다.

이 경우 문자열에서 제거하면 그것 나름대로 또 비용이 드니 그냥 얼마나 줄었는지 만 보는 것이 더 좋을 것입니다. 이러한 결과는 바로 해가 될 수 있습니다.

 

 

• 3. 비트 길이 비교하기( 비트 길이가 다를 경우 )

위의 조건에 걸리지 않은 경우입니다. 이러한 경우 두 수의 비트 수 중, 가장 큰 비트수가 해가 됩니다. 이를 반별 하기 위해서 kotlin.math의 max를 사용했습니다.

 

 

전체 코드는 다음과 같습니다.

 

import kotlin.math.*

class Solution {
    fun solution(n: Int, a: Int, b: Int): Int {

       var aBit = (a-1).toString(2)
        var bBit = (b-1).toString(2)

        if(aBit.length == bBit.length){
            var counter = 0
            for(i in 0 .. aBit.length - 1){
                if(aBit[i] == bBit[i]){
                    counter++
                }else{
                    break
                }
            }

            return aBit.length - counter

        }else{
            return max(aBit.length, bBit.length)
        }
    }
}

 

• 4. 더 쉽게 푸는 방법 ( 비트 연산자 이용하기 )

한 번 더 쉽게 풀어봅시다. 비트 연산을 사용하면 좀 더 쉽게 할 수 있을 것입니다. 아래 예시는 xor 비트 연산자를 사용해서 코드를 1줄로 줄이는 방법입니다. 이렇게 되면 반복도 필요가 없습니다.

class Solution {
    fun solution(n: Int, a: Int, b: Int): Int {

       return ((a-1) xor (b-1)).toString(2).length

    }
}

추가적으로 설명을 하자면, xor은 비트가 같으면 0이 됩니다. 그리고 앞에 부분이 0이 된다면, 생략되어 길이가 줄어들지요. 이러한 성질을 이용해서 풀 수 있습니다. 

 

---

 

이번 파트를 마치면서

사실 이번 글은 많이 힘들었습니다. 참고할만한 가이드라인이 없었고, 처음부터 끝까지 구조를 잡고, 예시부터 읽기 쉽도록 글의 흐름과 스토리텔링도 많이 고려해야 했습니다. 결과적으로는 남들이 읽었을 때 쉽게 이해되도록 하는 것이 제일 중요하니까요.

다만 아쉬운 점은 제가 다시 읽어도 많이 부족한 글이었습니다. 알고리즘 푸는 것보다 글 쓰는 것이 몇 배는 더 힘들었던 것 같습니다.

이것이 포스트가 늦은 변명이 되지는 않습니다만, 그래도 앞으로 더 열심히, 그리고 꾸준히 글을 더 써보도록 하겠습니다. 우선 여기까지 글을 봐주셔서 감사합니다. 다음부터는 위에서 언급했던 분할 정복법부터 DP알고리즘까지 이어지는 글을 작성하려고 합니다.

 

지금까지 이 글을 읽어주셔서 감사합니다. 다음에 뵙겠습니다.