이 글에서는 주어진 숫자 num이 있을 때, 1부터 num까지의 범위 안에서 2, 3, 4, 5, 6, 7, 8, 9, 10의 모든 수로 나누어 떨어지는 숫자가 몇 개인지 계산하는 방법을 다룹니다.
문제 이해하기
예시를 통해 문제를 살펴보겠습니다.
입력 − int num = 10000
출력 − 2부터 10까지의 모든 숫자로 나누어 떨어지는 수의 개수: 3
설명 − 1부터 10000 사이에는 2부터 10까지 모든 숫자로 나누어 떨어지는 수가 정확히 3개 존재하며, 그 값은 2520, 5040, 7560입니다.
입력 − int num = 20000
출력 − 2부터 10까지의 모든 숫자로 나누어 떨어지는 수의 개수: 7
설명 − 1부터 20000 사이에서는 조건을 만족하는 수가 7개이며, 각각 2520, 5040, 7560, 10080, 12600, 15120, 17640입니다.
접근 방법 1: 완전 탐색 (Naive Approach)
가장 직관적인 방법은 범위 내의 모든 숫자를 하나씩 검사하는 것입니다.
- 숫자 num을 입력받습니다.
- 2부터 10까지의 값을 크기가 9인 정수 배열에 저장합니다.
- 조건을 만족하는 숫자의 개수를 저장할 count 변수와, 나누어 떨어지는지 여부를 확인할 flag 변수를 준비합니다.
- i를 1부터 num까지 반복하는 For 루프를 시작합니다.
- 루프 내부에서 검사 대상을 i로 설정하고 인덱스를 0으로 초기화합니다.
- 인덱스가 배열 크기(9)보다 작은 동안 While 루프를 실행합니다.
- num % arr[index++] == 0 이면 flag를 1로 설정하고, 아니면 flag를 0으로 설정한 뒤 루프를 종료합니다.
- flag가 1이면 count를 1 증가시킵니다.
- 최종적으로 count를 반환하고 결과를 출력합니다.
접근 방법 2: 최소공배수(LCM) 활용 (Efficient Approach)
잘 관찰해 보면, 2부터 10까지의 모든 숫자로 나누어 떨어지는 수들 사이에는 일정한 패턴이 있습니다.
2부터 10까지 모든 수로 나누어 떨어지는 가장 작은 수는 2520입니다.
2520 = 5 × 7 × 8 × 9 (n = 1) 5040 = 5 × 7 × 8 × 9 × 2 (n = 2) 7560 = 5 × 7 × 8 × 9 × 3 (n = 3) ...
즉, 2520은 2, 3, 4, 5, 6, 7, 8, 9, 10 모두로 나누어 떨어지는 수들의 공통 인수, 곧 최소공배수입니다. 따라서 주어진 숫자를 2520으로 나눈 몫이 곧 우리가 찾는 답이 됩니다.
코드 1: 완전 탐색 방식
예제
#include <bits/stdc++.h>
using namespace std;
int count(int num){
int count = 0;
int flag=0;
int index=0;
int arr[9] = {2, 3, 4, 5, 6, 7, 8, 9, 10 };
for (int i = 1; i <= num; i++){
int num = i;
index=0;
while(index<9){
if(num % arr[index++] == 0){
flag=1;
}
else{
flag=0;
break;
}
}
if (flag == 1){
count++;
}
}
return count;
}
int main(){
int num = 10000;
cout<<"Count numbers which are divisible by all the numbers from 2 to 10 are: "<<count(num);
return 0;
}출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Count numbers which are divisible by all the numbers from 2 to 10 are: 3
코드 2: 효율적인 방식
예제
#include <bits/stdc++.h>
using namespace std;
int main(){
int num = 10000;
int count = num / 2520;
cout<<"Count numbers which are divisible by all the numbers from 2 to 10 are: "<<count;
return 0;
}출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Count numbers which are divisible by all the numbers from 2 to 10 are: 3
마무리
완전 탐색 방식은 O(num × 9)의 시간 복잡도를 가지므로 num이 커질수록 비효율적입니다. 반면 최소공배수 2520을 활용한 방식은 단 한 번의 나눗셈으로 답을 구할 수 있어 O(1)의 시간 복잡도를 자랑합니다. 실무에서는 이처럼 수학적 성질을 파악하여 알고리즘을 최적화하는 접근이 매우 중요합니다.