JArchive 프로그래밍 일기

문제

GCD합 백준 9613번

리뷰

최대공약수 GCD를 구할 줄 알면 풀 수 있는 문제였다.

이중 for문으로 2개의 수를 고른다.

두 수의 최소공배수를 리턴해서 sum에 누적한다.

유클리드 호제법으로 최대공약수를 구하기

int GCD(int a, int b){
    if(b == 0) return a;
    else return GCD(b, a%b);
}

유의할 점

누적하는 sum 의 자료형는 int가 아니라 long long 으로 써야한다.

수의 개수 n (1 < n ≤ 100)

입력으로 주어지는 수는 1,000,000을 넘지 않는다.

백만과 그 비슷한 크기 수 n개의 모든 쌍의 최대공약수의 합을 누적하려면 int 로는 안된다.

int의 최대 값은 대략 2,147,000,000 이다. (2,147,483,647)

n개가 99이고, 그 주어진 수는 모두 999999 라면. 가능한 쌍은 99 x 98 해서 9702가지 쌍을 만들 수 있다.

99 x 98 x 990,000 = 9,701,990,298

int 의 범위를 초과하기 때문에 sum 변수는 long long 으로 해야 한다.

맞은 코드

#include <iostream> 
using namespace std;

int TC;
int num[101];


int GCD(int a, int b){
    if(b==0) return a;
    else return GCD(b, a%b);
}

int main(void){

    cin >> TC;     

       while(TC--){ // 테스트 케이스 만큼 반복 

           long long sum = 0; // 모든 쌍의 GCD 값을 누적할 변수 
        int total = 0;

           cin >> total; 

           for(int i = 0; i < total; i++){ // total 개의 수를 배열에 집어넣는다 
               cin >> num[i];
        }

        for(int i = 0; i < total; i++){ // 이중 for문으로 2개의 수를 골라 GCD를 구한다 

            for(int j = i+1; j < total; j++){
                sum += GCD(num[i], num[j]);
            }    
        }

        printf("%lld\n", sum);
    }

    return 0;    
} 

문제

조합 0의 개수 백준 2004번

리뷰

문제를 풀기 전에, 팩토리얼 0의 개수 문제를 다시 풀고 왔다.

아래는 조합을 구하는 식이다. 조합은 팩토리얼의 나눗셈과 곱셈으로 이루어져 있다.

그래서 이 문제는 n! 과 r! 과 (n-r)! 을 각각 계산해야 한다.

nCm의 끝자리 0의 개수는 10이 얼마나 곱해졌는지가 좌우한다.

10은 2x5 다.

그래서 n! 과 r! 과 (n-r)! 이렇게 3개의 팩토리얼에 2와 5가 몇 번 곱해져있는지 계산해야 한다.

five_cnt 함수는 5의 개수를 리턴한다. two_cnt 함수도 똑같은 구조다.

int five_cnt(int n){ // 5의 개수 구한다 
    int cnt = 0;

    for(long long i = 5; 1 <= (n/i); i *= 5){
        cnt += (n/i);
    }

    return cnt;
}

n과 m은 최대 2,000,000,000 의 숫자가 주어진다.

5를 곱해가면서 n을 나눌꺼니까 int의 표현범위를 넘을 것을 감안하여 long long 으로 선언한다.

two_cnt 함수는 2의 개수를 리턴한다.

two_cnt와 five_cnt 함수로 2와 5의 개수를 구하되, 둘 중에 작게 나온 값이 인수 10의 개수가 될 것이다.

n C r 조합에서 유의할 점 2가지

r == 0이면, 항상 1이다. 아무것도 안고르기 때문이다. n개중에 0개.

n == r 이면, 항상 1이다. 전부 고르기 때문이다. n개중에 n개.

따라서 n C m 이 주어졌을 때, m이 1인 경우, 2와 5의 숫자를 안구해도 된다. 어차피 1이기 때문이다.

n==m 인 경우에도 1이니까 2와 5의 숫자를 안구해도 된다.

    // 5, 2의 개수를 각각 구해서 작은 쪽을 출력한다
    five += five_cnt(n);
    if(m > 0) five -= five_cnt(m);
    if(n != m) five -= five_cnt(n-m);

맞은 코드

#include <iostream> 
#include <algorithm>

using namespace std;

int n, m;
int two, five;

int two_cnt(int n){ // 2의 개수 구한다 
    int cnt = 0;

    for(long long i = 2; 1 <= (n/i); i *= 2){
        cnt += (n/i);
    }

    return cnt;
}

int five_cnt(int n){ // 5의 개수 구한다 
    int cnt = 0;

    for(long long i = 5; 1 <= (n/i); i *= 5){
        cnt += (n/i);
    }

    return cnt;
}

int main(void){

    cin >> n >> m;     

    // 5, 2의 개수를 각각 구해서 작은 쪽을 출력한다
    five += five_cnt(n);
    if(m > 0) five -= five_cnt(m);
    if(n != m) five -= five_cnt(n-m);

    two += two_cnt(n);
    if(m > 0) two -= two_cnt(m);
    if(n != m) two -= two_cnt(n-m);

    cout << min(two, five);

    return 0;    
} 

문제

소인수분해 백준 11653번

리뷰

가장 작은 소수 2부터 루트 N까지 나눠보면서 소인수분해 한다.

루트 N까지 나누는 이유는 에라토스테네스의 체를 풀어보면 알 수 있다.

미리 N까지의 모든 소수를 구해놓지 않고서도 반복문만으로 풀 수 있는 문제다.

for(int i = 2; i*i <= N; i++){  // 나누어 떨어지지 않는다면 i 증가 

    while( N % i == 0){ // 나누어 떨어진다면 출력 
        printf("%d\n", i);
        N /= i;
    }
}

예를 들어, N=12 인 경우

12는 2로 나누어 떨어지므로. 2 출력. N == 6

6은 2로 나누어 떨어지므로 2 출력. N == 3

이 때, 루트 N은 3과 4 사이의 값이다. 이미 N을 초과해버린다. 그래서 N이 3인채로 반복문이 종료된다.

따라서 for문이 끝나고 나서 N이 1 초과인 경우에 N을 출력 해줘야 한다.

    for(int i = 2; i*i <= N; i++){  // 나누어 떨어지지 않는다면 i 증가 

        while( N % i == 0){ // 나누어 떨어진다면 출력 
            printf("%d\n", i);
            N /= i;
        }
    }

    if(N > 1) cout << N;  // 위의 반복문이 i*i <= N 까지 동작하기 때문.

맞은 코드 1

#include <iostream> 
using namespace std;

int main(void){

     int N = 0;
    int i = 2; 

    cin >> N;

    if(N == 1) return 0; // 1은 소수가 아니다 

    for(int i = 2; i*i <= N; i++){  // 나누어 떨어지지 않는다면 i 증가 

        while( N % i == 0){ // 나누어 떨어진다면 출력 
            printf("%d\n", i);
            N /= i;
        }
    }

    if(N > 1) cout << N;  // 위의 반복문이 i*i <= N 까지 동작하기 때문.

    return 0;    
} 

맞은 코드 2

N이 더 이상 나눠지지 않을 때 까지 i로 나눈다

#include <iostream> 
using namespace std;

// 소인수분해 11653 

int main(void){

     int N = 0;

    cin >> N;

    if(N == 1) return 0;

    int i = 2; 

    while( N>1 ){

        if( N % i == 0){
            printf("%d\n", i);
            N /= i;
        }else{
            i++;
        }
    }
    return 0;    
} 

문제

골드바흐의 추측 백준 6588번

리뷰

두 홀수 소수의 합으로 N을 나타낼 수 있는지 검사하는 문제다.

짝수 정수 N의 범위 (6 ≤ N ≤ 1000000)

에라토스테네스의 체 문제 소수 구하기 백준 1929번를 풀어보고 나니까 막막하진 않았다.

문제의 풀이과정은 아래와 같다.

1. 에라토스테네스의 체로 백만 까지의 소수를 모두 구한다. (Eratos 함수 )
2. Prime 벡터에 홀수 소수들만 저장한다. (Eratos 함수 )
3. Prime 벡터를 순회하면서 N-Prime[i] 가 Prime 에 있는지 검사한다. ( Gold 함수 )

Gold 함수 case1

2중 for문으로 작성한 형태

bool Gold(int n){ // Prime 을 순회하면서 n을 a+b로 나타낼수 있는지 확인  

    for(int i = 0; Prime[i] < n; i++){ // a와 b는 n보다는 작을테니 n 직전까지만 탐색

        int target = n - Prime[i]; // n = a + b 가 되어야 하니까 b를 찾아본다. 

        for(int j = i; Prime[j] < n; j++){
            if(target == Prime[j]){
                printf("%d = %d + %d\n", n, Prime[i], Prime[j]);
                return true;
            }
        }
    }

    return false;
}

Gold 함수 case2

for문을 1개로 쓴 형태

bool Gold(int n){

    for(int i = 0; Prime[i] < n; i++){ // a와 b는 n보다는 작을테니 n 직전까지만 탐색

        if(n-Prime[i] == A[n-Prime[i]]){  // n-Prime[i] 값이 소수인지 확인한다 
            printf("%d = %d + %d\n", n, Prime[i], n-Prime[i]);
            return true;
        }
    }

    return false;
}

질문게시판에서 도움 받은 글

Gold 함수의 내부 for문에서 j를 i+1로 초기화 하고 시작했다가 틀렸다.

입력으로 6을 넣었을 때, 6 = 3 + 3 으로 표현할 수 있다. 따라서 내부 for문은 j = i로 초기화 해야 한다.

맞은 코드1

#include <iostream> 
#include <vector>
#include <algorithm>
#define MAX 1000001
using namespace std;

int A[1000001];  // 모든 소수
vector<int> Prime;  // 홀수 소수 

void Eratos(void){ // 백만 까지의 소수를 모두 구한다. 

    A[0] = A[1] = 1; // 0과 1은 소수가 아니다.  

    for(int i = 2; i<= MAX; i++){
        A[i] = i; // A배열 값을 '자기 자신'으로 저장한다.  
    }

    for(int i = 2; i*i <= MAX; i++){

        if(A[i] == i){

            for(int j = i*i; j <= MAX; j+=i){
                A[j] = i;  // 소수의 배수들을 지운다  
            } 
        }
    }

    // 홀수인 소수만 Prime에 저장  
    for(int i = 3; i<= MAX; i++){
        if(A[i] == i) Prime.push_back(A[i]);        
    }
}

bool Gold(int n){ // Prime 을 순회하면서 n을 a+b로 나타낼수 있는지 확인  

    for(int i = 0; Prime[i] < n; i++){

        int target = n - Prime[i];

        for(int j = i; Prime[j] < n; j++){
            if(target == Prime[j]){
                printf("%d = %d + %d\n", n, Prime[i], Prime[j]);
                return true;
            }
        }
    }

    return false;
}

int main(void){

     Eratos();

     while(1){
         int n = 0;
         scanf("%d", &n);

        if(n == 0) break;

         if(!Gold(n)) cout << "Goldbach's conjecture is wrong.\n"<<'\n';
    }

    return 0;    
} 

맞은 코드2

#include <iostream> 
#include <vector>
#include <algorithm>
#define MAX 1000001
using namespace std;

int A[1000001];  // 모든 소수
vector<int> Prime;  // 홀수 소수 

void Eratos(void){

    A[0] = A[1] = 1; // 0과 1은 소수가 아니다  

    for(int i = 2; i<= MAX; i++){
        A[i] = i; // 자기 자신을 저장시킨다  
    }

    for(int i = 2; i*i <= MAX; i++){

        if(A[i] == i){

            for(int j = i*i; j <= MAX; j+=i){  // 소수의 배수들을 지운다  
                A[j] = i; 
            } 
        }
    }

    for(int i = 3; i<= MAX; i++){ // 홀수인 소수만 Prime에 저장  
        if(A[i] == i) Prime.push_back(A[i]);        
    }

}

bool Gold(int n){

    // P 를 순회하면서 n을 a+b로 나타낼수 있는지 확인  
    for(int i = 0; Prime[i] < n; i++){

        if(n-Prime[i] == A[n-Prime[i]]){
            printf("%d = %d + %d\n", n, Prime[i], n-Prime[i]);
            return true;
        }
    }

    return false;
}

int main(void){

     Eratos();

     while(1){
         int n = 0;
         scanf("%d", &n);

        if(n == 0) break;

         if(!Gold(n)) cout << "Goldbach's conjecture is wrong.\n"<<'\n';
    }

    return 0;    
} 

문제

소수 구하기 백준 1929번

리뷰

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 1 ≤ M ≤ N ≤ 1,000,000

에라토스테네스의 체 를 이용한 문제다.

소수의 배수들을 전부 지우는 것이 핵심이다.

2는 소수다. 2의 배수를 전부 지운다.

3은 소수다. 3의 배수를 전부 지운다.

4는 2의 배수이므로 이미 지워졌다. 지나간다.

5는 소수다. 5의 배수를 전부 지운다.

6은 2의 배수이므로 이미 지워졌다. 지나간다.

이것을 코드로 나타내면 다음과 같다.

처음에는 전부 소수라고 0으로 초기화된 배열을 만든다.

그리고 0과 1은 소수가 아니니까 1로 만든다.

int A[1000001] = { 0, };

A[0] = 1; // 0과 1은 소수가 아니다. 지운다. 
A[1] = 1;

반복문 i를 2부터 N까지 순회한다.

앞서 소수 찾기 문제 에서 배운대로 N까지의 소수를 구하려면 루트 N까지만 확인하면 된다.

for(int i = 2; i*i <= N; i++){

    if(A[i] == 0) {  // 소수 라면, 

        for(int j = i*i; j <= N; j+=i ){ // 소수 i의 배수들을 전부 지운다  
            A[j] = 1;  
        }
    }
}    

루트 i < = N 는 아래와 같다.

i <= N * N

양변을 제곱한다. i의 루트가 사라진다. N은 제곱이 된다.

루트는 실수니까 오차를 발생시킬 수 있으므로 이렇게 제곱을 이용해 실수 사용을 피하는 것이다.

j는 i의 제곱부터 시작한다.

그 이유는 아래를 다시 읽어보면 된다.

처음에 2의 배수들을 지우면서 소수들의 x 2 는 이미 지워졌다.

또 3이 소수니까. 소수들의 x3은 이미 지워졌다.

이런식으로 지우다 보면 자신의 제곱 부터 지우면 된다.

2는 소수다. 2의 배수를 전부 지운다. -> 2x2, 2x3, 2x4, 2x5 .... 를 지운다

3은 소수다. 3의 배수를 전부 지운다. -> 3x2는 이미 2의 배수 지울 때 지워졌다. 3x3 부터 지운다.

4 ( 2 x 2) 는 2의 배수이므로 이미 지워졌다. 지나간다.

5는 소수다. 5의 배수를 전부 지운다.

​ -> 5x2, 5x3, 5x4 는 이미 2의배수, 3의배수, 4의배수 지울 때 지워졌다. 5x5 부터 지운다.

6 ( 3 x 2 ) 은 2의 배수이므로 이미 지워졌다. 지나간다.

맞은 코드

#include <iostream> 
#include <algorithm>
using namespace std;

int M, N;
int A[1000001] = { 0, };

int main(void){

    cin >> M >> N;

    A[0] = 1; // 0과 1은 소수가 아니다. 지운다. 
    A[1] = 1;

    for(int i = 2; i*i <= N; i++){

        if(A[i] == 0) {  

            for(int j = i*i; j <= N; j+=i ){ // i의 배수들을 전부 지운다  
                A[j] = 1;  
            }
        }
    }    

    for(int i = M; i <= N; i++){ // 0 으로 남은 소수 출력  
        if(A[i] == 0) {
            printf("%d\n", i);
        }
    } 

    return 0;    
} 

백준 1929번 문제 질문게시판에서 다양한 방식으로 풀어나가는 글을 읽어보며 도움이 많이 됬다.
정수를 곱할 때 int 표현범위를 오버플로우 하지 않도록 주의해야 한다는 점도 배웠다.

문제

소수 찾기 백준 1978번

리뷰

소수는 약수가 1과 자기 자신만 있는 수다.

N이 소수가 되는 조건

2이상이고 루트 N보다 작거나 같은 자연수로 나누어 떨어지는지 확인하면 된다.

N이 소수가 아니라고 가정하자.

소수가 아닌 N은 다음과 같이 표현할 수 있다.

N = a x b ( b는 a보다 큰 어떤 수.)

두 수 a와 b의 차이가 가장 작은 경우는 루트 N이다.

따라서 2부터 N까지가 아니라, 2부터 루트 N까지만 검사해보면, 소수인지 여부를 알 수 있다.

a가 루트N보다 크고, b가 루트N보다 크면,

a x b 도 N 보다 크다.

예를 들어 N = 24 이고,  a = 2, b = 12 

2 4 (여기 루트N 자리) 6 8 10 12 14 16 18 20 22 24

루트 24 는 4.xx 와 가까운 수가 될 것이다. 
a와 b 둘 중 하나는 루트 N 보다는 작다. 

코드로 나타내면 다음과 같다.

bool isPrime(int n){

    if(n < 2){
        return false;
    }

    for(int i = 2; i*i <= n; i++){ // 실수는 오차를 발생시킬 수 있으므로, i*i <= N 으로 계산하자.
        if(n % i == 0){
            return false;
        }
    }
    return true;
}

루트i < = N 는 아래와 같다.

i <= N * N

양변을 제곱한다. i의 루트가 사라진다. N은 제곱이 된다.

루트는 실수니까 오차를 발생시킬 수 있으므로 이렇게 제곱을 이용해 실수 사용을 피하는 것이다. 

어떤 수가 소수인지 확인하는데 걸리는 시간 복잡도는 O(루트N) 이다.

코드

#include <iostream> 
using namespace std;

bool isPrime(int n){

    if(n < 2){
        return false;
    }

    for(int i = 2; i*i <= n; i++){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}

int main(void){

    int CNT = 0;
     int answer = 0;

    cin >> CNT;

    while(CNT--){
        int num = 0;
        cin >> num;
        if(isPrime(num)) answer++;
    }

    cout << answer;
    return 0;    
}

문제

팩토리얼 0의 개수 백준 1676번

리뷰

숫자 뒤 쪽에 0의 개수가 몇개가 되냐는건 소인수분해 했을 때 10이 몇번 곱해졌느냐에 따라 결정된다.

예를 들어, (팩토리얼 값은 아니지만) 34200 는 10이 2번 곱해진 것이다. 따라서 답은 2다. 2059000은 답이 3이다.

그런데, 10은 2x5 이다.

주어진 N을 5로 계속 나누는데, 나누어 떨어지는 개수를 세면 된다. == N! 을 소인수분해 했을때 5가 몇 승일까.

2의 개수를 안세도 되는 이유

10은 2x5니까 2의 개수도 세야 하지 않을까? 했다.
하지만, 소인수분해 했을 때 2를 인수로 가진 수의 개수 보다는, 5를 인수로 가진 수의 개수가 훨씬 적다.

7 팩토리얼을 예로 든다. 

7! = 7 x 6 x 5 x 4 x 3 x 2 x 1 

5의 배수는 딱 1개 
2의 배수는 3개 (2,4,6) 

예를 들어, 125 팩토리얼을 구한다

5 * 25 * 125 까지만 곱해봐도 5로 나누어 떨어지는 것의 개수를 셀 수 있다.

125!

125/5 =>  25개
25/5  =>  5개
5/5  =>  1개
따라서 답은 31이 된다. 

따라서 반복문의 i는 5씩 곱하면서 증가시킨다.

KSJ14님의 해설을 읽고 도움받았다.

코드

#include <iostream> 
using namespace std;

int main(void){
     int N = 0;
    int cnt = 0;

     cin >> N;

    for(int i = 5; i <= N; i *= 5){
        cnt += (N/i);
    }

    cout << cnt;

    return 0;    
}