정수 요소로 이루어진 임의의 크기를 가진 배열이 주어졌을 때, 배열에서 한 요소가 다른 요소를 나누어 떨어지게 하는 쌍(pair)의 개수를 계산하는 것이 우리의 과제입니다.
배열은 동일한 타입의 요소들을 고정된 크기로 순차적으로 저장할 수 있는 자료구조입니다. 배열은 데이터 모음을 저장하는 용도로 사용되지만, 같은 타입의 변수들이 모인 집합으로 이해하면 더욱 유용하게 활용할 수 있습니다.
예시
입력 − int arr[] = {1, 2, 3, 6}
출력 − count is 4설명 − (1,2), (1,3), (1,6), (3,6)은 한 요소가 다른 요소를 나누어 떨어지게 하는 쌍입니다. 1은 어떤 수든 나눌 수 있고, 3은 6을 나눌 수 있기 때문입니다. 따라서 개수는 4입니다.
입력 − int arr[] = {2, 5, 10}
출력 − count is 2설명 − (2,10)과 (5,10)은 한 요소가 다른 요소를 나누어 떨어지게 하는 쌍입니다. 2는 10을 나눌 수 있고, 5 역시 10을 나눌 수 있기 때문입니다. 따라서 개수는 2입니다.
프로그램에 적용한 접근 방법
arr[]라는 이름의 배열을 생성합니다.
sizeof 연산자 등을 활용해 배열의 길이를 계산합니다. 길이는 배열에 포함된 요소의 개수에 해당하는 정수 값으로 반환됩니다.
배열 내 요소들로 만들 수 있는 나누어 떨어지는 쌍의 개수를 저장할 임시 변수를 선언합니다.
i를 0부터 시작하여 배열의 크기보다 작을 때까지 반복하는 바깥쪽 for 루프를 시작합니다.
바깥쪽 루프 안에서 j를 i+1부터 시작하여 배열의 크기보다 작을 때까지 반복하는 안쪽 루프를 시작합니다.
루프 안에서 arr[i] % arr[j] == 0 또는 arr[j] % arr[i] == 0 인지 검사하고, 조건을 만족하면 카운트를 1 증가시킵니다.
모든 쌍을 검사한 후 최종 카운트를 반환합니다.
결과를 화면에 출력합니다.
이 방식은 두 개의 중첩 루프를 사용해 가능한 모든 쌍을 하나씩 검사하므로, 시간 복잡도는 O(n²)입니다.
코드 예시
#include <iostream>
using namespace std;
int divisibles(int a[], int size){
int result = 0;
// 모든 쌍을 순회합니다
for (int i=0; i<size; i++){
for (int j=i+1; j<size; j++){
if (a[i] % a[j] == 0 || a[j] % a[i] == 0){
result++;
}
}
}
return result;
}
int main(){
int a[] = {1, 4, 7, 8, 9};
int size = sizeof(a) / sizeof(a[0]);
cout <<"count is " <<divisibles(a, size);
return 0;
}
출력 결과
위 코드를 실행하면 다음과 같은 출력을 얻을 수 있습니다 −
count is 5
배열 {1, 4, 7, 8, 9}에서 나누어 떨어지는 쌍은 (1,4), (1,7), (1,8), (1,9), (4,8)로 총 5개입니다. 1은 모든 수를 나눌 수 있고, 4는 8을 나눌 수 있기 때문입니다.