이 코드는 왜 느릴까? 알고리즘 효율성 분석

프로그래머스

 

문제 제출을 하고 정확성 테스트 다 통과하는 것을 보고 만족하고 있었는데

 

그래그래 드디어 왔구나 효율성 테스트.

어떻게 해결했는지 알아봅시다.

🛑 기존 코드

function solution(n) {
    let start = 1;
    let answer = 0;
    let sum = 0;
    while (start <= n) {
        for (let i = start; i <= n; i++) {
            sum += i;
            if (sum === n) {
                answer++;
                start++;
                sum = 0;
                break;
            }
            if (sum > n) {
                start++;
                sum = 0;
                break;
            }
        }
    }
    return answer;
}

기존 코드는 sum을 매번 누적하면서 계산을 합니다.

 

자 여기서 그래도 중학생 때 수학을 포기하지 않아서 다행이라고 생각한게 저희는 중학교 수학 과정에서 연속된 자연수의 합 공식을 배웠습니다. 매번 sum을 누적하지 않고 한 번의 계산으로 총합을 구할 수 있습니다. 

위키하우

✅ 1부터 n까지의 합 이용

function solution(n) {
    let answer = 0;
    const sum = (a, b) => (b * (b + 1) / 2) - ((a - 1) * a / 2);
    
    for (let i = 1; i <= n; i++) {
        for (let j = i; j <= n; j++) {
            if (sum(i, j) === n) {
                answer++;
                break;
            }
            if (sum(i, j) > n) {
                break;
            }
        }
    }
    return answer;
}

이전 코드와 다르게 i와 j까지의 합을 한 번의 연산으로 구합니다.

직전과 같이 O(N^2)의 중첩 반복문이 유지되지만, 내부 연산이 크게 줄어들어 실행 속도가 향상된 것을 알 수 있습니다.

✅  등차수열의 합 이용

연속된 자연수의 합이 n이 되려면, 어떤 정수 x에서 시작해서 k개의 연속된 숫자의 합이 n이 되는 경우를 찾아야 합니다.

등차수열의 합 공식: S = k  * (2x + k − 1) / 2

즉, x + (x + 1) + (x + 2) + ... + (x + k − 1) = n 를 만족하는 x와 k를 찾아야 합니다.

저희는 합인 n을 알고 있으므로 n에 대해서 식을 전개해보면, k(2x + k − 1) = 2n입니다.

k와 (2x + k -1)은 2n의 약수인 것을 알 수 있습니다.

이 식에서 k는 연속된 숫자의 개수이고 x는 어떤 숫자이니까 k는 양의 정수, x는 정수입니다.

 

이를 바탕으로 코드를 구현하면

function solution(n) {
    let answer = 0;
    for (let k = 1; k <= 2 * n; k++) {
    	// k가 2n의 약수인지 판별
        if (2 * n % k === 0) {
        	// k는 이미 양의 정수이므로 x가 양의 정수인지 판별하기 위해 x를 판별
            let x = (2 * n - k * (k - 1)) / (2 * k);
            if (x > 0 && Number.isInteger(x)) {
                answer++;  
            }
        }
    }
    return answer;
}

 

이 코드의 시간 복잡도는 O(n)입니다. 이는 최적화된 방식으로, 기존의 누적합을 사용하는 방식의 O(n^2)에 비해 효율적입니다.

 

같은 문제를 풀더라도 비효율적인 방식과 최적화된 방식의 성능 차이가 큽니다. 단순한 반복문으로 해결할 수도 있지만, 수학적 공식을 활용하면 더 효율적인 코드가 될 수 있습니다.

이처럼 반복문을 사용할 때 불필요한 연산이 많지는 않은지, 수학적으로 최적화할 방법이 있는지 고민하는 습관이 중요한 것 같습니다.

다음에 비슷한 문제가 나오면, 단순 구현보다는 더 나은 해결 방법이 있는지 한 번 더 생각해보는 것이 좋겠습니다!