자바스크립트 코딩테스트 강좌, 연속된 자연수의 합 구하기

문제 설명

연속된 자연수의 합을 구하는 문제는 알고리즘 문제의 대표적인 유형 중 하나입니다. 주어진 숫자를 N이라고 할 때, 우리가 구하고자 하는 것은 N이라는 숫자를 만들 수 있는 연속된 자연수의 조합이 존재하는 경우 그 조합의 개수입니다. 즉, N은 여러 개의 연속된 자연수의 합으로 표현될 수 있는지를 알아보는 문제입니다.

문제 정의

다음과 같은 형식으로 문제를 정리할 수 있습니다:

        입력:
        - 정수 N (1 ≤ N ≤ 10^6)

        출력:
        - 연속된 자연수의 합으로 N을 표현할 수 있는 경우의 수
    

예제

예제 1

        입력: 15
        출력: 4
        설명: 15는 다음과 같은 방식으로 표현됩니다:
        - 7 + 8
        - 4 + 5 + 6
        - 1 + 2 + 3 + 4 + 5
        - 15 (정수 자체만으로 전부)
    

예제 2

        입력: 10
        출력: 2
        설명: 10은 다음과 같은 방식으로 표현됩니다:
        - 1 + 2 + 3 + 4
        - 4 + 6
    

문제 풀이

연속된 자연수의 합을 구하기 위해서는 특정한 방법론이 필요합니다. 기본적으로 연속된 두 자연수의 합은 다음과 같은 수학적 공식을 따릅니다:

여러 수 a, a+1, a+2, …, a+k의 합은 다음과 같이 표현됩니다:

        S = a + (a + 1) + (a + 2) + ... + (a + k)
          = (k + 1) * a + (0 + 1 + 2 + ... + k)
          = (k + 1) * a + (k * (k + 1) / 2)
    

이때, S가 N이 되어야 하죠. 이를 기반으로 알고리즘을 설계할 수 있습니다.

알고리즘 설계

이번 문제는 두 개의 포인터를 사용하는 슬라이딩 윈도우 알고리즘을 통해 효율적으로 접근할 수 있습니다. 제안하는 방법은 다음과 같습니다:

1. 시작 포인터와 끝 포인터를 설정하고 모두 1로 초기화합니다.
2. 현재 합계를 초기화합니다.
3. 끝 포인터를 오른쪽으로 이동하며 합계에 끝 포인터의 값을 더합니다.
4. 현재 합계가 N보다 작으면 끝 포인터를 계속 이동합니다.
5. 현재 합계가 N과 같으면 경우의 수를 증가시키고 시작 포인터를 오른쪽으로 이동하여 합계를 줄입니다.
6. 현재 합계가 N보다 크면 시작 포인터를 오른쪽으로 이동하여 합계를 줄입니다.
7. 끝 포인터가 N보다 작거나 같은 경우까지 반복합니다.

파이썬 코드 구현

이제 위에서 설명한 알고리즘을 바탕으로 파이썬 코드로 구현해보겠습니다. JavaScript의 문법과는 다르지만, 논리를 이해하는 데 도움이 될 것입니다.

        
def count_consecutive_sum(N):
    count = 0
    start = 1
    end = 1
    current_sum = 0

    while end <= N:
        current_sum += end

        while current_sum > N:
            current_sum -= start
            start += 1

        if current_sum == N:
            count += 1

        end += 1

    return count
        
    

자바스크립트 코드 구현

이제 위와 동일한 알고리즘을 JavaScript로 구현해크겠습니다.

        
function countConsecutiveSum(N) {
    let count = 0;
    let start = 1;
    let end = 1;
    let currentSum = 0;

    while (end <= N) {
        currentSum += end;

        while (currentSum > N) {
            currentSum -= start;
            start++;
        }

        if (currentSum === N) {
            count++;
        }

        end++;
    }

    return count;
}
        
    

결론

연속된 자연수의 합을 구하는 문제는 기본적인 알고리즘 문제 중 하나이며, 수학적 접근과 함께 슬라이딩 윈도우 기법을 사용하여 효과적으로 해결할 수 있습니다. 이 기법은 실제 코딩 면접에서도 자주 등장하는 주제이므로 숙지해 두면 유용합니다.

참고 자료

추가적으로 알고리즘을 공부할 수 있는 자료들은 다음과 같습니다:

• Geeks for Geeks
• LeetCode
• HackerRank