C++로 홀수 합을 가지는 부분 배열의 개수 구하기

부분 배열(Subarray)이란 배열에서 연속된 요소들로 이루어진 부분을 의미합니다. 예를 들어 배열 [5, 6, 7, 8]이 있다면, (5), (6), (7), (8), (5, 6), (6, 7), (7, 8), (5, 6, 7), (6, 7, 8), (5, 6, 7, 8)과 같이 총 10개의 비어 있지 않은 부분 배열이 존재합니다.

이 글에서는 C++를 사용하여 합이 홀수인 부분 배열의 개수를 구하는 다양한 방법을 자세히 설명합니다. 먼저 간단한 예제를 통해 문제를 살펴보겠습니다.

입력 : array = {9, 8, 7, 6, 5}
출력 : 9

설명 :
부분 배열의 합 -
{9} = 9
{7} = 7
{5} = 5
{9, 8} = 17
{8, 7} = 15
{7, 6} = 13
{6, 5} = 11
{8, 7, 6} = 21
{9, 8, 7, 6, 5} = 35

브루트 포스(Brute Force) 접근법

가장 직관적인 방법은 모든 부분 배열의 합을 일일이 계산하여 홀수인지 확인하는 것입니다. 합이 짝수라면 해당 부분 배열을 제외하고, 홀수라면 카운트를 증가시킵니다. 이 방법은 구현이 간단하지만 중첩 반복문을 사용하기 때문에 시간 복잡도가 O(n²)으로 효율성이 떨어집니다.

코드 예제

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n = 5, temp = 0;
    int a[n-1] = { 9, 8, 7, 6, 5 }; // 배열 선언
    int cnt = 0; // 카운터 변수
    for(int i = 0; i < n; i++){
        temp = 0; // 임시 합 초기화
        for(int j = i; j < n; j++){ // i부터 n-1까지의 부분 배열 생성
            temp = temp + a[j];
            if( temp % 2 == 1 )
                cnt++;
        }
    }
    cout << "홀수 합을 가지는 부분 배열의 개수 : " << cnt << "\n";
    return 0;
}

실행 결과

홀수 합을 가지는 부분 배열의 개수 : 9

코드 설명

위 코드는 중첩 반복문을 사용합니다. 외부 반복문은 배열의 시작 위치를 가리키는 인덱스 i를 하나씩 증가시키고, 내부 반복문은 위치 i에서 시작하는 모든 부분 배열의 합을 계산하여 그 합이 홀수인 경우 카운트를 증가시킵니다.

효율적인 접근법 (O(n))

더 효율적인 방법은 배열의 각 요소를 순차적으로 처리하면서 짝수/홀수 카운터를 활용하는 것입니다. 현재 요소가 짝수라면 짝수 카운터를 증가시킵니다. 만약 홀수를 만나면, 부분 배열의 합의 홀짝성(parity)이 뒤바뀌므로 짝수 카운터와 홀수 카운터의 값을 서로 교환합니다. 마지막으로 매 반복마다 홀수 카운터의 값을 결과에 더해줍니다. 이 방법은 각 요소를 한 번씩만 처리하므로 시간 복잡도는 O(n)입니다.

코드 예제

#include <bits/stdc++.h>
using namespace std;
int main(){
    int odd = 0, even = 0, result = 0, n = 5, i, temp;
    int arr[n-1] = { 9, 8, 7, 6, 5 }; // 배열 초기화
    // 배열의 모든 요소를 처리하는 반복문
    for ( i = 0 ; i < n ; i ++ ) {
        if ( arr[ i ] % 2 == 0 ) {
            even++; // 짝수인 경우 짝수 카운터 증가
        } else {
            // 홀수인 경우 짝수/홀수 카운터 값 교환
            temp = even;
            even = odd;
            odd = temp + 1;
        }
        result += odd;
    }
    cout << "홀수 합을 가지는 부분 배열의 개수 : " << result;
}

실행 결과

홀수 합을 가지는 부분 배열의 개수 : 9

코드 설명

이 코드는 배열의 각 요소가 짝수인지 홀수인지 판별합니다. 짝수라면 짝수 카운터를 증가시키고, 홀수를 만나면 부분 배열의 홀짝성이 변경되기 때문에 짝수 카운터와 홀수 카운터의 값을 서로 교환합니다. 그리고 매 반복(iteration)이 끝날 때마다 홀수 카운터의 값을 결과 변수(result)에 누적합니다.

결론

이 글에서는 합이 홀수인 부분 배열의 개수를 구하는 두 가지 방법을 살펴보았습니다. 첫 번째는 모든 부분 배열을 생성하고 합이 홀수인 경우 카운트를 증가시키는 브루트 포스 방식으로, 시간 복잡도는 O(n²)입니다. 두 번째는 배열의 각 요소를 순회하며 짝수/홀수 카운터를 관리하고, 홀수를 만날 때마다 카운터 값을 교환하는 효율적인 방식으로, 시간 복잡도는 O(n)입니다. 상황에 맞는 적절한 알고리즘을 선택하여 문제를 해결하시길 바랍니다.