정수형 요소로 이루어진 배열이 주어졌을 때, 배열에서 만들 수 있는 모든 쌍(pair)을 구성하고 각 쌍의 합을 계산한 뒤, 그 합이 주어진 정수 k로 나누어떨어지는지 판별하는 문제입니다. 이 글에서는 직관적인 브루트 포스 방식과 나머지 연산을 활용한 효율적인 방식, 두 가지 접근 방법을 C++ 코드와 함께 살펴봅니다.
문제 예시
예제 1
입력 − int arr[] = {4, 1, 2, 0, 2}, int k = 2
출력 − 합이 k로 나누어떨어지는 쌍의 개수: 6
설명 − 배열에서 만들 수 있는 쌍과 그 합은 다음과 같습니다. (4, 1) = 5(나누어떨어지지 않음), (4, 2) = 6(나누어떨어짐), (4, 0) = 4(나누어떨어짐), (4, 2) = 6(나누어떨어짐), (1, 2) = 3(나누어떨어지지 않음), (1, 0) = 1(나누어떨어지지 않음), (1, 2) = 3(나누어떨어지지 않음), (2, 0) = 2(나누어떨어짐), (2, 2) = 4(나누어떨어짐), (0, 2) = 2(나누어떨어짐). 배열에 2가 두 개 있으므로 조건을 만족하는 쌍은 (4, 2), (4, 0), (4, 2), (2, 0), (2, 2), (0, 2)로 총 6개입니다.
예제 2
입력 − int arr[] = {2, 4, 8, 6, 10}, int k = 4
출력 − 합이 k로 나누어떨어지는 쌍의 개수: 4
설명 − 만들 수 있는 쌍은 (2, 4) = 6, (2, 8) = 10, (2, 6) = 8, (2, 10) = 12, (4, 8) = 12, (4, 6) = 10, (4, 10) = 14, (8, 6) = 14, (8, 10) = 18, (6, 10) = 16입니다. 이 가운데 4로 나누어떨어지는 쌍은 (2, 6), (2, 10), (4, 8), (6, 10)으로 총 4개입니다.
방법 1: 브루트 포스(완전 탐색)
가장 직관적인 방법은 가능한 모든 쌍을 하나씩 확인하는 것입니다.
- 정수 배열과 정수 변수 k를 입력받고, 배열의 크기를 계산해 함수에 전달합니다.
- 조건을 만족하는 쌍의 개수를 저장할 임시 변수 count를 선언합니다.
- i를 0부터 배열 크기까지 반복하는 FOR 루프를 시작합니다.
- 루프 내부에서 j를 i + 1부터 배열 크기까지 반복하는 FOR 루프를 시작합니다.
- sum = arr[i] + arr[j]를 계산하고, sum % k == 0이면 count를 1 증가시킵니다.
- 모든 쌍을 확인한 뒤 count를 반환하고 결과를 출력합니다.
이 방식의 시간 복잡도는 O(n²)로, 배열의 크기가 커질수록 비효율적입니다.
방법 2: 나머지 연산을 활용한 효율적 접근
두 수의 합이 k로 나누어떨어지려면, 두 수를 k로 나눈 나머지의 합이 0 또는 k가 되어야 한다는 성질을 이용합니다. 나머지별 등장 횟수만 미리 세어 두면 모든 쌍을 일일이 확인하지 않아도 됩니다.
- 정수 배열을 입력받아 크기를 계산하고 함수에 전달합니다.
- 쌍의 개수를 저장할 임시 변수 count를 선언합니다.
- k로 나눈 나머지는 0부터 k−1 사이이므로, 크기가 k인 빈도 배열 check를 생성합니다.
- 배열을 순회하면서 temp = arr[i] % k를 구하고, ++check[temp]로 나머지별 개수를 기록합니다.
- 나머지가 0인 원소들은 서로 조합해 쌍을 이루므로 count = check[0] × (check[0] − 1) / 2로 초기화합니다.
- i를 1부터 i ≤ k/2이면서 i ≠ k−i인 동안 반복하며, 나머지 i와 k−i가 서로 짝을 이루므로 count += check[i] × check[k − i]를 더합니다.
- k가 짝수라면 나머지가 k/2인 원소들끼리의 쌍도 고려해 count += check[k/2] × (check[k/2] − 1) / 2를 추가합니다.
- count를 반환하고 결과를 출력합니다.
이 방식의 시간 복잡도는 O(n + k)로, 배열의 크기가 클 때 특히 유리합니다.
예제 코드 (브루트 포스)
#include <iostream>
using namespace std;
int pair_k(int arr[], int size, int k){
int count = 0;
for(int i = 0 ;i <size ; i++){
for(int j = i+1; j<size; j++){
int sum = arr[i] + arr[j];
if(sum % k == 0){
count++;
}
}
}
return count;
}
int main(){
int arr[] = {4, 1, 2, 0, 2};
int size = sizeof(arr) / sizeof(arr[0]);
int k = 2;
cout<<"배열에서 합이 k로 나누어떨어지는 쌍의 개수: "<<pair_k(arr, size, k);
return 0;
}출력
배열에서 합이 k로 나누어떨어지는 쌍의 개수: 6
예제 코드 (효율적 접근)
#include <iostream>
using namespace std;
int pair_k(int arr[], int size, int k){
int temp = 0;
int count = 0;
int check[k] = {0};
for (int i = 0; i < size; i++){
temp = arr[i] % k;
++check[temp];
}
count = check[0] * (check[0] - 1) / 2;
for (int i = 1; i <= k / 2 && i != (k - i); i++){
count = count + check[i] * (check[k - i]);
}
if (k % 2 == 0){
count = count + (check[k / 2] * (check[k / 2] - 1) / 2);
}
return count;
}
int main(){
int arr[] = {4, 1, 2, 0, 2};
int size = sizeof(arr) / sizeof(arr[0]);
int k = 2;
cout<<"배열에서 합이 k로 나누어떨어지는 쌍의 개수: "<<pair_k(arr, size, k);
return 0;
}출력
배열에서 합이 k로 나누어떨어지는 쌍의 개수: 6
마무리
단순히 모든 쌍을 검사하는 브루트 포스 방식은 구현이 쉽지만 O(n²)의 시간이 걸립니다. 반면 나머지 빈도를 이용하면 O(n + k)로 최적화할 수 있어, 데이터 크기가 큰 실무 환경에서는 후자의 접근이 훨씬 효율적입니다.