C++로 GCD가 1인 부분 수열 개수 구하기

정수로 이루어진 배열이 주어졌을 때, 그중 GCD(최대공약수)가 1인 부분 수열(sub-sequence)의 개수를 찾는 것이 이 글의 목표입니다. GCD(Greatest Common Divisor)란 두 개 이상의 정수를 모두 나누어 떨어지게 하는 수 중에서 가장 큰 값을 의미합니다.

문제 예시

입력 − int arr[] = {3, 4, 8, 16}

출력 − GCD가 1인 부분 수열의 개수 − 7

설명 −

주어진 배열에서 만들 수 있는 GCD가 1인 부분 수열은 (3, 4), (3, 8), (3, 16), (4, 3), (8, 3), (16, 3), (3, 4, 8) 입니다.

입력 − int arr[] = {5, 7, 10}

출력 − GCD가 1인 부분 수열의 개수 − 3

설명 −

주어진 배열에서 만들 수 있는 GCD가 1인 부분 수열은 (5, 7), (7, 10), (5, 7, 10) 입니다.

풀이 접근 방식

• 임의의 크기를 가진 정수 배열을 입력받습니다.

• 배열의 크기를 계산한 뒤, 이후 처리를 위해 해당 데이터를 함수에 전달합니다.

• GCD가 1인 부분 수열의 개수를 저장할 임시 변수 count를 선언합니다.

• i를 0부터 배열의 크기까지 반복하는 FOR 루프를 시작합니다.

• 바깥 루프 안에서 j를 0부터 배열의 크기까지 반복하는 내부 FOR 루프를 시작합니다.

• 내부 루프에서 IF 조건으로 gcd(arr[i], arr[j]) == 1 인지 확인하고, 참이라면 count를 1 증가시킵니다.

• count를 반환합니다.

• 결과를 출력합니다.

코드 예제

# include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b){
    if (a == 0)
        return b;
    return gcd(b % a, a);
}
int GCD_1(int arr[],int size){
    int count = 0;
    for(int i=0;i<size;i++){
        for(int j=0;j<=size;j++){
            if(gcd(arr[i],arr[j])==1){
                count++;
            }
        }
    }
    return count;
}
int main(){
    int arr[] = {3, 4, 8, 16};
    int size = sizeof(arr)/sizeof(arr[0]);
    cout<<"Count of number of sub-sequences with GCD 1 are: "<<GCD_1(arr, size);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −

Count of number of sub-sequences with GCD 1 are: 7