No.9 모두의 약수 개수

인프런에 있는 김태원님의 강의 IT 취업을 위한 알고리즘 문제풀이 with C/C++ 를 듣고 문제를 푼 후 정리한 오답노트입니다. 😀

9. 모두의 약수

문제 설명

제한 시간 1초

8 을 입력하면 1 ~ 8 범위의 8 개 정수의 각각 약수의 개수를 순서대로 출력한다. 제한시간은 1초다.

입력 👉 8
출력 👉 1 2 2 3 2 4 2 4

내 답안

입력되는 숫자가 큰 수면 1 초를 넘어가므로 내 답은 틀린 답변. 작은 숫자 에서나 괜찮음.

int N = 0, count = 1;
scanf("%d", &N);

printf("%d ", count);  // 1의 약수는 1개

for (int i = 2; i <= N; i++)
{
    count = 0;
    for (int j = 2; j <= i/2; j++)  // 2 ~ i/2 까지의 수 중 약수가 있는지 검사한다. i의 약수 범위는 1~i/2 를 넘지 않는다.
    {
        if (i % j == 0)
            count++;
    }
    printf("%d ", count + 2);  //  1 과 자기 자신은 언제나 약수. 이 둘을 count에 더해줌.
}
printf("\n");

• 이중 for 문을 사용하여 일일이 약수를 구하기
  • 👉 입력 숫자가 커지면 1 초 넘어간다.
  • 전부 검사하지 않고 어떤 규칙을 이용하여 꼼수를 쓰는 것이 좋다.

정답 풀이

6 의 약수는 1, 2, 3, 6. 👉 6 은 1, 2, 3, 6 의 배수

• N 의 약수 개수 = 1 ~ N 까지의 각각의 수들 中 N 이 배수가 되는 것의 총 개수
• 1 ~ 6 중 4 의 약수 개수를 구한다면
  • 1 의 배수들
    • 1 2 3 4 5 6
      • cnt[4] = cnt[4] + 1
  • 2 의 배수들
    • 2 4 6
      • cnt[4] = cnt[4] + 1
  • 3 의 배수들
    • 3 6
  • 4 의 배수들
    • 4
      • cnt[4] = cnt[4] + 1
  • 5 의 배수들
    • 5
  • 6 의 배수들
    • 6
  • 4의 약수는 3 개다.
    • 4 는 1, 2, 4 의 배수이다.
      • cnt[4] 👉 3

cnt[j] : j 가 어떤 수의 배수가 될 때마다 이 cnt[j]를 1씩 증가시킨다. 연산을 다 완료하고나면 최종적으로 cnt[j]는 j 의 약수 개수가 된다.

N 의 배수들은 N, N+N, N+N+N, … 이다. N의 배수들의 약수는 N 을 포함한다.

#include<stdio.h>
using namespace std;
int cnt[50001];
int main(){
	//freopen("input.txt", "rt", stdin);
	int n, i, j;
	scanf("%d", &n);
	for(i=1; i<=n; i++){
		for(j=i; j<=n; j=j+i){
			cnt[j]++;
		}
	}
	for(i=1; i<=n; i++){
		printf("%d ", cnt[i]);
	}
	return 0;
}

• j = j + i
  • i = 2 일 때, 2의 배수들을 알려면 2 부터 시작해서 2 씩 더해나가야 한다.
    • 2 에서 시작하여 2 씩 더한 “2 4 6 8” 은 2 의 배수.
    • cnt[2], cnt[4], cnt[6], cnt[8] 1 씩 증가시킴
• n = 8 이었을 때
  • 그냥 i 마다 모든 1 ~ i 를 검사했다면 8 * 8 = 64 번의 연산으로 약수인지 검사했어야 할 것이다.
  • j = j + i 즉, 각각의 배수들만 검사하면 총 연산이 8 + 4 + 2 + 2 + 1 + 1 + 1 + 1 = 20 번의 연산으로 크게 줄어드는 것을 볼 수 있다.
    • 이렇게 하면 큰 숫자를 입력해도 1 초를 넘기지 않는다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기