C++을 사용해 본 경험이 있다면 부분 배열(subarray)이 무엇이며 얼마나 유용한지 잘 알고 있을 것입니다. C++은 다양한 수학적 문제를 손쉽게 해결할 수 있는 강력한 프로그래밍 언어입니다. 이 글에서는 C++의 부분 배열을 활용하여 정확히 m개의 홀수를 포함하는 부분 배열의 개수를 구하는 방법을 단계별로 자세히 설명합니다.
이 문제는 주어진 배열과 정수 m이 있을 때, 각 부분 배열이 정확히 m개의 홀수를 포함하도록 만들 수 있는 모든 경우의 수를 세는 것입니다. 다음 예시를 통해 살펴보겠습니다.
입력 : array = { 6,3,5,8,9 }, m = 2
출력 : 5
설명 : 정확히 2개의 홀수를 포함하는 부분 배열은
{ 3,5 }, { 6,3,5 }, { 3,5,8 }, { 5,8,9 }, { 6,3,5,8 }
입력 : array = { 1,6,3,2,5,4 }, m = 2
출력 : 6
설명 : 정확히 2개의 홀수를 포함하는 부분 배열은
{ 1,6,3 }, { 3,2,5 }, { 1,6,3,2 }, { 6,3,2,5 }, { 3,2,5,4 }, { 6,3,2,5,4 }
첫 번째 접근 방식: 브루트 포스
이 방식은 주어진 배열에서 만들 수 있는 모든 부분 배열을 생성한 뒤, 각 부분 배열에 홀수가 정확히 m개 들어 있는지 하나씩 검사합니다. 단순하게 "생성하고 찾는" 방식이며, 시간 복잡도는 O(n2)입니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int main (){
int a[] = { 1, 6, 3, 2, 5, 4 };
int n = 6, m = 2, count = 0; // n은 배열의 크기, m은 부분 배열에서 찾을 홀수의 개수,
// count는 홀수가 m개인 부분 배열의 개수
for (int i = 0; i < n; i++){ // 각 요소를 시작점으로 처리하는 외부 루프
int odd = 0;
for (int j = i; j < n; j++) { // 홀수 m개를 포함하는 부분 배열을 찾는 내부 루프
if (a[j] % 2)
odd++;
if (odd == m) // 홀수 개수가 m과 같아지면
count++;
}
}
cout << "홀수가 " << m << "개인 부분 배열의 개수: " << count;
return 0;
}
실행 결과
홀수가 2개인 부분 배열의 개수: 6
코드 설명
이 코드는 중첩 루프를 사용하여 홀수가 m개인 부분 배열을 찾습니다. 외부 루프는 시작 인덱스 i를 증가시키며 배열의 각 요소를 부분 배열의 시작점으로 삼습니다.
내부 루프는 i부터 배열의 끝까지 요소를 순회하면서 홀수 카운터(odd)를 누적하고, 홀수 개수가 m에 도달할 때마다 결과 카운터(count)를 1씩 증가시킵니다. 마지막으로 count 변수에 저장된 값을 출력합니다.
두 번째 접근 방식: 접두사 배열 활용 (효율적)
더 효율적인 방법은 "홀수가 i개인 접두사(prefix)의 개수"를 저장하는 배열을 만들어 활용하는 것입니다. 배열의 모든 요소를 한 번씩 순회하면서 홀수를 발견할 때마다 홀수 카운터를 증가시킵니다.
각 인덱스를 처리하기 전에 현재까지의 홀수 개수 상태를 prefix_array[odd]에 1씩 더해 기록합니다. 그리고 홀수 개수(odd)가 m보다 크거나 같아지면, 현재 인덱스를 끝으로 하는 부분 배열 중 정확히 m개의 홀수를 가지는 경우의 수는 prefix_array[odd - m]과 같습니다. 이 값을 count에 계속 더해 나가면 최종 결과를 얻을 수 있습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int main (){
int array[] = { 1, 6, 3, 2, 5, 4 };
int n = 6, m = 2, count = 0, odd = 0, i;
int prefix_array[n + 1] = { 0 };
// 배열의 모든 요소를 처리하는 외부 루프
for (i = 0; i < n; i++){
prefix_array[odd] = prefix_array[odd] + 1; // 현재 홀수 개수 상태를 prefix_array에 기록
// 배열 요소가 홀수이면 odd 변수 증가
if (array[i] % 2 != 0)
odd++;
// 홀수 개수가 m 이상이 되면
// 해당 인덱스까지 만들 수 있는 부분 배열의 개수를 더함
if (odd >= m)
count += prefix_array[odd - m];
}
cout << "홀수가 " << m << "개인 부분 배열의 개수: " << count;
return 0;
}
실행 결과
홀수가 2개인 부분 배열의 개수: 6
코드 설명
먼저 배열과 변수들을 초기화합니다.
int array[6] = { 1, 6, 3, 2, 5, 4 };
int n = 6, m = 2, count = 0, odd = 0, i;
int prefix_array[n + 1] = { 0 };
여기서 n은 배열의 크기, m은 찾으려는 홀수의 개수, count는 가능한 부분 배열의 개수를 저장하는 변수, odd는 지금까지 발견한 홀수의 개수, prefix_array는 크기 n+1의 접두사 기록 배열로 모두 0으로 초기화됩니다.
루프 동작 이해하기
for (i = 0; i < n; i++){
prefix_array[odd] = prefix_array[odd] + 1;
if (array[i] % 2 != 0)
odd++;
if (odd >= m)
count += prefix_array[odd - m];
}
이 루프에서는 먼저 현재까지의 홀수 개수 상태를 prefix_array에 기록하고, 현재 요소가 홀수라면 odd 변수를 증가시킵니다. 그리고 odd가 m 이상이 되면, 현재 인덱스까지 형성할 수 있는 유효한 부분 배열의 개수를 count에 더합니다.
모든 요소를 처리한 후에는 홀수가 m개인 부분 배열의 개수가 저장된 count 변수를 출력하여 최종 결과를 얻습니다.
결론
이 글에서는 정확히 m개의 홀수를 포함하는 부분 배열의 개수를 구하는 두 가지 방법을 살펴보았습니다.
브루트 포스: 모든 부분 배열을 생성하고 각 배열에 홀수가 m개 있는지 확인한 뒤, 조건을 만족할 때마다 개수를 증가시킵니다. 시간 복잡도는 O(n2)입니다.
접두사 배열 활용: 배열의 각 요소를 한 번씩 순회하면서 접두사 배열을 만들고, 이를 이용해 결과를 계산합니다. 시간 복잡도는 O(n)으로 훨씬 효율적입니다.
이 글이 문제와 해결 방법을 이해하는 데 도움이 되기를 바랍니다.