JArchive 프로그래밍 일기

문제

진법변환 백준 2745번

리뷰

B진법 수 N을 10진법으로 바꿔서 출력하는 프로그램 작성하기.

B진법은 2진법 부터 최대 36진법까지 입력된다.

N을 10진법으로 바꾸면 항상 10억보다 작거나 같다.

문자열로 N을 입력받고, 마지막 자리 문자 부터 B의 0승, B의 1승, B의 2승... 이렇게 곱해서 누적한 결과를 출력했다.

string 을 char 배열로 바꾸는 것은 cstring 의 strcpy 를 이용했다.

#include <cstring>
#include <string>

string N;
char ch[30];
strcpy(ch, N.c_str()); // string 을 char N에 복사  

*문자 '9'는 57에 대응하고 문자 'A'는 65 임을 이용했다. *

    if('9' < ch[i]){ // 알파벳으로 표현한 경우, A는 65임을 이용 
        answer = answer + ( pow(B, n) * (ch[i]-55) );
    }else{ // 문자 '9'는 57임을 이용 
            answer = answer + ( pow(B, n) * (ch[i]-48) );
    }

char 배열 길이 때문에 런타임 에러 발생

string 을 char 배열로 변환해서 쓰는 부분에서 런타임 에러를 이 글을 읽고 도움받았다.

예를 들어, 2진법이면 0과 1밖에 표현 안하니까 다른 진법에 비해 문자열이 길게 들어올 것이다.

N은 항상 10억보다 작거나 같다. 10억 ( 1,000,000,000)을 2진수으로 표현하면

0011 1011 1001 1010 1100 1010 0000 0000

따라서 char 배열은 30자리 이상으로 만드는 것이 안전하다.

맞은 코드

#include <iostream> 
#include <string>
#include <cstring> // strcpy()
#include <cmath> // pow()
using namespace std;

string N;
char ch[30];
int B, answer;

int main(void){

    cin >> N >> B;

    strcpy(ch, N.c_str()); // string 을 char N에 복사  
    int n = 0; // B의 자승 표현을 위한 변수 

    for(int i = N.length()-1; i >= 0; i--){

        if('9' < ch[i]){ // 알파벳으로 표현한 경우, A는 65임을 이용 
            answer = answer + ( pow(B, n) * (ch[i]-55) );
        }else{ // 문자 '9'는 57임을 이용 
            answer = answer + ( pow(B, n) * (ch[i]-48) );
        }
        n++;
    }

    cout << answer;

    return 0;    
} 

백준 질문게시판에 글 올려주시고 댓글 달아주시는 분들 모두 다 감사하다.

문제

진법변환2 백준 11005번

리뷰

10진수 N을 B진수로 바꾸려면, N을 B로 나눈 나머지를 적어주다가 거꾸로 출력하면 된다.

계속 B로 나누는 것이다.

    while( N > 0){
        answer.push_back( N % B );
        N /= B; 
    }

문제의 조건에서 10 부터는 알파벳으로 표현하라고 했다.

그래서 10부터는 아스키코드를 이용해서 출력했다. 10일 때는 'A'를, 11 일 때는 'B' 로 출력해야 한다.

'A'는 65니까, 10 + 55 로 'A' 를 표현할 수 있다.

    for(int i = answer.size()-1; i >= 0 ; i--){ // 거꾸로 출력  

        if(answer[i] < 10){
            cout<< answer[i];
        }else{
            printf("%c", answer[i]+55);  // char 로 'A'는 10진수 65와 같다 
        }
    }

맞은 코드 1

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

int main(void){

      int N = 0, B = 0; 
    vector<int> answer; 

    cin >> N >> B;

    while( N > 0){
        answer.push_back( N % B );
        N /= B; 
    }

    for(int i = answer.size()-1; i >= 0 ; i--){ // 거꾸로 출력  

        if(answer[i] < 10){
            cout<< answer[i];
        }else{
            printf("%c", answer[i]+55);
        }
    }

    return 0;    
} 

stack을 이용한 다른 풀이

어차피 거꾸로 출력해야 하니까 '나머지 계산'한 것을 전부 스택에 push 하고,

스택일 빌 때까지 전부 pop 하면 된다.

알파벳을 출력하는 경우를 고려해서 char 를 저장하는 스택을 이용했다.

그런데 0부터 9까지는 어떻게 스택에 넣지? 싶어서 구글링 해보니까 4, 5 같은 숫자를 넣을때 앞에 문자로 '0'을 넣어준다.

맞은 코드 2

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

int main(void){

      int N = 0, B = 0; 

    cin >> N >> B;

    //printf("%d %d\n", '9', 'A'); // 57 65  7차이  
    stack<char> answer;

    while(N){

        int temp = N % B;

        if(temp >= 10){
            temp += 7;
        }

        answer.push('0'+temp);

        N /= B;
    }    

    while(!answer.empty()){
        cout << answer.top();
        answer.pop();
    }

    return 0;    
} 

문제

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 표현범위를 오버플로우 하지 않도록 주의해야 한다는 점도 배웠다.