알고리즘/문제풀이
[algorithm 풀이] 1. 모두의 약수 구하기
PSYda
2021. 3. 15. 23:44
반응형
0. 문제
자연수 N이 입력되면 1부터 N까지의 각 숫자들의 약수의 개수를 출력하는 프로그램을 작성하세요. 만약 N이 8이 입력된다면 1(1개), 2(2개), 3(2개), 4(3개), 5(2개), 6(4개), 7(2개), 8(4개) 와 같이 각 숫자의 약수의 개수가 구해집니다.
출력은 다음과 같이 1부터 차례대로 약수의 개수만 출력하면 됩니다.
1 2 2 3 2 4 2 4 와 같이 출력한다.
- 입력설명
- 첫 번째 줄에 자연수 N(5<=N<=50,000)가 주어진다.
- 출력 설명
- 첫 번째 줄에 1부터 N까지 약수의 개수를 순서대로 출력한다.
- 입력 예제1
- 8
- 출력 예제1
- 1 2 2 3 2 4 2 4
- 문제 풀이 핵심
- 순서 대로 약수를 구하면 속도가 너무 느리다.
- i는 1~num 을 순회하며, i의 배수의 자리 개수를 더해주자.!
1. 풀이1 : 순서대로 약수 구하는 방법
- 두 개의 for문을 돌며, 순서대로 약수를 구하는 방법
- 이해가 쉽고, 동작되나 속도가 매우 느림(O(N제곱))
int getCount(int num){
int cnt = 2;
for ( int i = 2; <= num / 2; i++ ){
if (num % i == 0){
cnt++;
}
}
return cnt;
}
int main(){
int num;
std::cin >> num;
cout << "1 2 2 3"; // 4까지는 그냥 출력
for ( int i = 5 ; i<= num; i++){
cout<< " " << getCount(i);
}
}
2. 풀이2 : 배수를 이용하는 방법
- 사용자에게 num을 입력 받음
- num개의 숫자에 대한 약수 개수를 가지고 있는 공간 할당
- num 개수 만큼 공간 확보 및 1로 초기화
- i는 2 에서 num 까지 순회
- j는 i 에서 num 까지 i의 배수로 순회
- j의 위치 공간에 count를 +1함
- 최종 출력
#include<iostream>
#include<vector>
int main() {
int num;
// 1. 사용자에게 num을 입력 받음
std::cin >> num;
// 2. num 개수 만큼 공간 확보 및 1로 초기화
std::vector<int> cnt(num, 1);
// 3. i 는 2부터 num까지 순회
for (int i = 2; i <= num; i++) {
// 4. j는 i부터 num까지 순회하며, i의 배수 위치 공간에 count + 1
for (int j = i; j <= num; j = j + i) {
cnt[j - 1] = cnt[j - 1]++;
}
}
// 5. 결과를 출력
std::cout << cnt[0];
for (int i = 1; i < num; i++) {
std::cout << " " << cnt[i];
}
return 0;
}- 예시(8 입력 시)
- {1,1,1,1,1,1,1,1} : 1은 모두의 약수이므로 제외하고, 개수 공간을 1로 초기화
- {1,2,1,2,1,2,1,2} : 2의 배수 위치 개수 증가(4번 순회->2,4,6,8)
- {1,2,2,2,1,3,1,2} : 3의 배수 위치 개수 증가(2번 순회->3,6)
- {1,2,2,3,1,3,1,3} : 4의 배수 위치 개수 증가(2번 순회->4,8)
- {1,2,2,3,2,3,1,3} : 5의 배수 위치 개수 증가(1번 순회->5)
- {1,2,2,3,2,4,1,3} : 6의 배수 위치 개수 증가(1번 순회->6)
- {1,2,2,3,2,4,2,3} : 7의 배수 위치 개수 증가(1번 순회->7)
- {1,2,2,3,2,4,2,4} : 8의 배수 위치 개수 증가(1번 순회->8)
- 풀이1 vs 풀이2
- 풀이 1 : 48번(7*7) 순회로 계산 가능
- 풀이 2 : 12번 순회(1 제외)로 계산 가능
- 풀이 2가 훨씬 효율적
참고
반응형