[algorithm 풀이] 1. 모두의 약수 구하기

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 와 같이 출력한다.

1. 입력설명
   • 첫 번째 줄에 자연수 N(5<=N<=50,000)가 주어진다.
2. 출력 설명
   • 첫 번째 줄에 1부터 N까지 약수의 개수를 순서대로 출력한다.
3. 입력 예제1
   • 8
4. 출력 예제1
   • 1 2 2 3 2 4 2 4
5. 문제 풀이 핵심
   • 순서 대로 약수를 구하면 속도가 너무 느리다.
   • i는 1~num 을 순회하며, i의 배수의 자리 개수를 더해주자.!

1. 풀이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 : 배수를 이용하는 방법

1. 사용자에게 num을 입력 받음
2. num개의 숫자에 대한 약수 개수를 가지고 있는 공간 할당
   • num 개수 만큼 공간 확보 및 1로 초기화
3. i는 2 에서 num 까지 순회
   • j는 i 에서 num 까지 i의 배수로 순회
   • j의 위치 공간에 count를 +1함
4. 최종 출력

#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;
}

5. 예시(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)
6. 풀이1 vs 풀이2
   • 풀이 1 : 48번(7*7) 순회로 계산 가능
   • 풀이 2 : 12번 순회(1 제외)로 계산 가능
   • 풀이 2가 훨씬 효율적

참고

1. it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비