정보처리기사 정처기 | 완전수 알고리즘 | 필기&실기 개념

⭕ 정보처리기사 정처기 | 완전수 알고리즘 | 필기&실기 개념

완전수(Perfect Number)는 자연수 중에서 자기 자신을 제외한 양의 약수의 합이 자기 자신과 같은 수를 말합니다. 예를 들어, 28은 완전수입니다. 왜냐하면 28의 양의 약수는 1, 2, 4, 7, 14이고, 이들을 모두 더하면 28이 되기 때문입니다.

 

➡️ 브루트포스(Brute Force) 방식

C 언어를 사용하여 완전수를 찾는 간단한 알고리즘을 작성해 보겠습니다. 아래는 브루트포스(Brute Force) 방식을 사용한 완전수 찾기 알고리즘의 예제 코드입니다.

#include <stdio.h>

// 약수의 합을 계산하는 함수
int getDivisorSum(int number) {
    int sum = 0;
    for (int i = 1; i <= number / 2; i++) {
        if (number % i == 0) {
            sum += i;
        }
    }
    return sum;
}

// 완전수를 찾는 함수
void findPerfectNumbers(int limit) {
    printf("Perfect numbers up to %d:\n", limit);
    for (int i = 2; i <= limit; i++) {
        if (i == getDivisorSum(i)) {
            printf("%d\n", i);
        }
    }
}

int main() {
    int limit;

    printf("Enter the limit to find perfect numbers: ");
    scanf("%d", &limit);

    findPerfectNumbers(limit);

    return 0;
}

---

이 코드는 사용자로부터 한계값을 입력받아 해당 값까지의 완전수를 찾습니다. getDivisorSum 함수는 주어진 숫자의 약수 합을 계산하고, findPerfectNumbers 함수는 주어진 한계값까지의 완전수를 찾아 출력합니다.

 

---

그러나 이 코드는 브루트포스 방식으로 약수를 모두 확인하기 때문에 성능상의 이슈가 있을 수 있습니다. 브루트포스 방식은 모든 가능한 조합을 시도하여 문제를 해결하기 때문에 큰 입력값에 대해서는 효율적이지 않을 수 있습니다. 이러한 성능상의 문제를 개선하기 위해서는 더 효율적인 알고리즘을 고려해 볼 필요가 있습니다.

 

➡️ 개선된 알고리즘: 제곱근 활용

브루트포스 방식의 성능을 향상하기 위해, 약수를 찾을 때 모든 수를 확인하는 대신 제곱근을 이용하여 효율적으로 약수를 찾아내는 방법을 적용한 코드입니다.

#include <stdio.h>
#include <math.h>

// 약수의 합을 계산하는 함수 (제곱근 활용)
int getDivisorSum(int number) {
    int sum = 1; // 1은 모든 자연수의 약수이므로 미리 더해줍니다.
    int sqrtNum = sqrt(number);

    for (int i = 2; i <= sqrtNum; i++) {
        if (number % i == 0) {
            sum += i;
            if (i != number / i) {
                sum += number / i;
            }
        }
    }

    return sum;
}

// 완전수를 찾는 함수
void findPerfectNumbers(int limit) {
    printf("Perfect numbers up to %d:\n", limit);
    for (int i = 2; i <= limit; i++) {
        if (i == getDivisorSum(i)) {
            printf("%d\n", i);
        }
    }
}

int main() {
    int limit;

    printf("Enter the limit to find perfect numbers: ");
    scanf("%d", &limit);

    findPerfectNumbers(limit);

    return 0;
}

 

이 코드에서 getDivisorSum 함수는 주어진 숫자의 약수를 찾아내는데, 기존의 브루트포스 방식과 달리 1부터 해당 숫자의 제곱근까지만 확인합니다. 이는 약수의 특성을 이용한 최적화 방법 중 하나입니다.

---

예를 들어, 16의 약수를 찾을 때, 브루트포스 방식은 1부터 16까지 모두 확인하지만, 제곱근을 이용한 방식은 1부터 4까지만 확인합니다. 왜냐하면 16의 제곱근은 4이기 때문에, 4보다 큰 수에서의 약수는 이미 4보다 작은 수에서의 약수에 포함되어 있기 때문입니다. 이렇게 제곱근을 이용하면 연산 횟수를 크게 줄일 수 있어 성능이 향상됩니다.

 

⭕ [예시] 

➡️ 2023년도 3회 실기 기출 - 4. [C 언어 코드] 알맞은 출력 값을 작성하시오.

#include <stdio.h>

int isPerfect(int num) {
    int sum = 0;
    for (int i = 1; i <= num / 2; i++) {
        if (num % i == 0) {
            sum += i;
        }
    }
    return (sum == num) ? 1 : 0;
}

int main() {
    int limit = 300;
    int sumOfPerfect = 0;

    for (int i = 1; i <= limit; i++) {
        if (isPerfect(i)) {
            sumOfPerfect += i;
        }
    }

    printf("%d", sumOfPerfect);
    return 0;
}

정답

34

해설

1부터 300까지의 숫자 중에서 완전수라는 숫자를 찾아내고, 그 완전수들의 합을 계산하여 출력하는 프로그램입니다. 완전수는 자기 자신을 제외한 양의 약수들의 합이 자기 자신과 같은 수를 말합니다.

---

프로그램의 주요 부분은 isPerfect 함수와 main 함수입니다.

---

isPerfect 함수는 주어진 숫자 num이 완전수인지 여부를 판단합니다. 이를 확인하기 위해 num을 1부터 num의 절반까지의 숫자로 나누며, 나누어 떨어지는 수들의 합을 계산합니다. 만약 이 합이 num과 같다면 함수는 1을 반환하고, 그렇지 않으면 0을 반환합니다.

---

main 함수에서는 1부터 300까지의 숫자 중에서 isPerfect 함수를 이용하여 완전수를 찾아내고, 찾아낸 완전수들의 합을 계산하여 sumOfPerfect 변수에 더합니다. 마지막으로 이 합을 화면에 출력합니다.

---

0부터 300까지의 완전수는 6, 28입니다.

---

[정보처리기사/[최신] 실기 기출] - [2023년도 3회] 정보처리기사 정처기 | 실기 기출 | 회차별 정리

[2023년도 3회] 정보처리기사 정처기 | 실기 기출 | 회차별 정리