알고리즘으로 얼마나 최적화 할 수 있을까 (프로그래머스 제곱근 판별 문제)

최근 Swift 언어로 프로그래머스 문제를 조금씩 풀어보면서 다른 사람들은 어떻게 풀었을까 관심을 가지고 있었는데, 내가 몰랐던 방법을 우연히 보게되면서 굉장히 흥미로움을 느꼈다.

어떤 아이디어를 가지고 이렇게 접근했는지 궁금했기도 하고, 그러다보니 주변에 42Seoul 동료들과도 알고리즘으로 재밌는 대화를 나누기도 했다.

물론 많은 사람들이 이미 알고있는 방식일 수도 있다. 그래도 이런 과정들을 충분히 포스팅해도 재밌을거 같아 포스팅 해보려 한다.

내 풀이와 참고한 풀이

우선, 내가 풀었던 방식은 정말 정석같은 느낌이다.

func sqrt(_ n: Int64) -> Int64 {
    var x: Int64 = 0
    while (x * x) < n {
        x += 1
    }
    if x * x == n {
        return x
    }
    return -1
}

func solution(_ n:Int64) -> Int64 {
    let x: Int64 = sqrt(n)
    if x != -1 {
        return Int64((x + 1) * (x + 1))
    }
    return -1
}

0 부터 입력 값으로 들어온 n 까지 1 씩 증가하면서 순차적으로 탐색하는 방식으로 풀어냈다. 이렇게 풀어냈을 때, 만약 sqrt(121) 이라면 정수 제곱근인 11 까지 0 부터 시작해서 12 번 탐색 과정을 거친다.

그런데 다른 사람들 풀이를 보면서 어떻게 풀었을지 보는 와중에 아래와 같은 재밌는 코드를 보게되었다.

프로그래머스에서 문제를 푸신 익명의 'TheVoid' 선생님 코드를 인용했습니다.

문제를 접하고 나서

내가 이 방식을 보고 재밌었던건 두 가지다.

• 첫 번째로, Swift-ish 한 코드라는 점이다. extension 을 활용했고 또 그 안에서 String 자료형 객체에서 이진수로 바꿔주는 초기화 메소드를 활용한 점이다.
• 두 번째로, 비트 수를 절반으로 나눠 이것을 제곱근의 비트카운트 기준으로 두고 n-1 과 n 승 사이의 min to max 값으로 루프 조건을 매우 줄인 부분이다.

생각해보면 내 풀이는 항상 최악의 조건으로 탐색해서 입력 값에 따라 시간복잡도가 늘어난다. 반면에, 위 풀이를 같은 예시인 sqrt(121) 와 비교해 보았을 때 조회량이 굉장히 많이 줄어들 수 있다.

왜냐면 예를 들어,121 이라는 수가 들어왔을 때, 비트 값은 1111001 이 되고, 비트의 개수는 7, 비트 개수의 절반을 나누고 비트시프트 연산을 거치면 min 값은 8, max 값은 16 으로 루프 조건에 제한을 둠 으로서 8 9 10 11 로 4번 만에 정답에 도달했다.

이렇게 한 번 예시를 적용시켜보니 괜찮은 방식이라는 생각이 들었고, 몇 가지 생각이 들었다.

1. 내 알고리즘과 비교해서 얼마나 시간 차이가 있을까
2. 수학적으로 증명이 되는 방식인가
3. 더 나은 알고리즘이 있을까

(1) 내 알고리즘과 비교해서 얼마나 시간 차이가 있을까

나는 맨 처음에 비트시프트 연산과, 그 값으로 루프 조건을 줄였기 때문에 무조건 참고한 풀이가 더 빠를 것이라 생각했다. 그런데 막상 돌리고 나니 의외의 결과가 있었다.

첫 번째 이미지는 내 풀이의 결과고, 두 번째는 참고한 풀이의 결과이다. 만약 이 비트시프트 풀이를 C 언어 로 했다면 충분히 만족할 결과를 얻었을텐데 아마 익스텐션에서 문자열 객체를 리턴하는 과정에서 시간복잡도가 많이 생기지 않았을까 판단된다.

(2) 수학적으로 증명이 되는 방식인가

수학은 잘하지 못하지만 그래도 이 방식이 실제로 예외가 없는 방식인지 궁금했다. 왜냐면 위와 같이 비트로 풀어낸 문제를 보았을 때 입력 값의 비트 수가 n 이라면 무조건 제곱근 값이 2$(n-1)\over 2$

수학적인 증명은 내가 할 수 없지만, 그래도 대략 한 번 유추 해보자.
31 이라는 값이 입력값으로 들어왔다. 그러면 11111 이라는 값이 만들어지고 여기서 비트의 개수는 5 개 이다....
(여기 부분은 다시 다듬어서 정리!)

(3) 더 나은 알고리즘이 있을까

위의 풀이가 나에겐 재미있었지만 그래도 Swift 로는 성능이 생각보다 나오지 않아 이 풀이를 가지고 42Seoul 사람들과 대화를 좀 하게 되었는데, 그 과정에서 알고리즘에 대한 아이디어를 얻기도 했고 실제로 한 분이 비트시프트에 대한 아이디어를 참고해서 C 언어 로 이진탐색 알고리즘을 직접 그 자리에서 구현하셨다. 빠른 것은 물론이고 Swift 로 포팅해서 직접 체크해봐도 최악의 경우일수록 눈에 띄는 성능을 보인다.

먼저 42Seoul에서 카뎃 동료 @sehan 님이 C 언어 로 짜신 걸 보면

#include <stdio.h>

long long ft_sqrt(long long n, long long sqrt_n)
{
    long long result = sqrt_n * sqrt_n;
    if (result > n)
        return (1);
    else if (result < n)
        return (-1);
    else
        return (0);
}
​
long long solution(long long n) {
    long long answer = n;
    long long min;
    long long now;
    long long max;
    long long result;
    min = 0;
    now = 3037000499;
    max = 3037000499;
    while (1)
    {
        result = ft_sqrt(answer, now);
        if (max - min == 1)
            return (-1);
        if (result < 0)
        {
            min = now;
            now = min + ((max - min) >> 1);
        }
        else if (result > 0)
        {
            max = now;
            now = min + ((max - min) >> 1);
        }
        else
        {
            return (now + 1) * (now + 1);
        }
    }
    return answer;
}

1. Int64 의 최대값의 제곱근을 now와 max에 저장하고, min을 0으로 둔다.
2. 현재 바라보는 값이 입력값의 제곱근 값과 대소비교를 했을 때 조건을 저장한다.
3. now 의 제곱이 입력값 보다 크면 max를 낮추고, 입력값 보다 작다면 min을 높인다.
4. 이 때, 비트시프트 연산을 활용해서 절반씩 조건 범위를 줄이면서 이분 탐색을 한다.

이 로직을 Swift 로 포팅해서 테스트를 해보니 놀라운 결과가 나왔다.

func ft_sqrt(n: Int64, sqrtN: Int64) -> Int {
    let result: Int64 = sqrtN * sqrtN
    if result > n {
        return 1
    } else if result < n {
        return -1
    } else {
        return 0
    }
}

func solution(_ n:Int64) -> Int64 {
    var min: Int64 = 0
    var max: Int64 = 3037000499
    var now: Int64 = 3037000499

    while true {
        let isSqrt = ft_sqrt(n:n, sqrtN: now)
        if max - min == 1 {
            return -1
        }
        if isSqrt < 0 {
            min = now
            now = min + ((max - min) >> 1)
        } else if isSqrt > 0 {
            max = now
            now = min + ((max - min) >> 1)
        } else {
            return (now + 1) * (now + 1)
        }
    }
    return -1
}

결과의 속도만 보더라도 확연히 차이가 난다. 특히 더 놀란 점은, 결과를 내는 속도가 거의 균일 하다는 점이다. 내가 처음에 짠 로직은 순차적으로 탐색하기 때문에 입력값에 영향을 많이 받는다. 중간에 큰 수가 들어올 때는 20.0ms 까지도 나온다.

결론

사실 프로그래머스 문제들을 활용해서 Swift 언어 방식으로 생각하는 습관을 좀 들이고 싶어서 차근차근 문제들을 풀고 있는데 이렇게 제곱근 풀이 문제에서 많은 생각을 하게될 줄은 몰랐다.
알고리즘을 잘 알고 있는 상태에서 이런 작은 단위서부터 적용해서 어플리케이션을 구축하면 나중에 얼마나 좋은 서비스가 될 지도 생각이 들면서, 알고리즘의 중요성을 깨달았다.
또 한편으로는, 내가 봤을 때 괜찮은 로직인데 생각보다 시간복잡도가 크게 나오는 것을 보면서 멋진 로직을 짜는게 전부가 아니라 언어마다 그 내부 구현이 다르기 때문에 하나에 너무 맹신하지 않고 테스트 해봐야 한다는 결론을 얻었다.

익명의 'TheVoid' 선생님 코드 인용한 부분은 혹여나 문제가 된다면 내리겠습니다!