[ 정수론 ] 필수 과제 해결 📚유클리드 호제법, 아리스토테네스의 체

백준 1735

최대공약수를 구해 연산하는 문제. 이번 주차에서 배운 유클리드 호제법을 재귀함수의 형태로 구현하였다!

#include <iostream>

using namespace std;

//최대공약수 구하는 함수
int getGcdRecur(int a, int b)  {
    if (b == 0) {
        return a;
    }
    return getGcdRecur(b, a%b);
}

int main()
{

    int u1, u2, d1, d2; //입력받을 분자와 분모
    int uRes, dRes; //최종 분자와 분모


    //입력
    cin >> u1 >> d1 >> u2 >> d2;

    //Part.1
    uRes = u1*d2 + u2*d1;
    dRes = d1 * d2;

    //일단 더한 후(Part.1), 이 값을 기약분수로 정리(Part.2)


    //Part.2 : 분자와 분모를 두 수의 최대공약수로 나눈다!
    int gcd = getGcdRecur(uRes,dRes);

    uRes/=gcd;
    dRes/=gcd;

    cout << uRes << " " << dRes ;


    return 0;
}

 

 

 

백준 6588

아리스토테네스의 체를 활용해 소수 판별 함수를 만들었다!

이후 문제 조건에 맞게 반복문과 조건문을 써서 최종 정답을 구현했다 히히 

아무래도 C++은 처음이라 아직 엄청 능숙하지 못하다ㅠㅠ

간단하게지만, C++의 처음 배우는 개념이었던 벡터를 활용해보았다!

#include <iostream>
#include <vector>

using namespace std;

//소수들을 남기고, 나머지는 지워나가는 벡터
    vector<bool> is_prime(1000001, true); 


int findPrime() {

    is_prime[0]=0;
    is_prime[1]=0;

    for(int i=2; i<=1000001; i++) {
        if(!is_prime[i]) { //이미 false이면 검토 X
            continue; //아래 무시하고 바로 다음 반복
        } 

        for(int j=i+i; j<=1000001; j+=i) {
            if(!is_prime[i]) { //이미 false이면 검토 X
                continue;
            }

            is_prime[j]=false;
        }
    }

    return 0;
}


int main()
{
    //시간초과 해결
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

   //소수 판별 (아리스토테네스의 체)
    findPrime();


    int n;
    cin >> n;


    while(n!=0) {

        int flag=0;

        int a=0;
        int b=0;


        //n 미만의 소수 b, 그리고 a=n-b. a가 소수면 그대로 a,b 확정 및 출력

        for(int i=n-1; i>=2; i--) {
            flag=0;

            if(is_prime[i]) { //소수면 true
                b=i;
                a=n-b;
                if(is_prime[a]) {
                    flag=1;
                }
            }

            if(flag==1) {
                cout << n << " = " << a << " + "<< b << '\n';
                break;
            }
        }

        if(flag==0) {
            cout << "Goldbach's conjecture is wrong." << "\n";
        }

        //다시 또 입력받고 반복
        cin >> n;

    }

    return 0;
}

 

 

짧은 소감)

그래도 이제 점점 C++ 을 사용하는 것과 함수화해서 코드를 짜는 것에 점차 익숙해지고 있다!

처음엔 꺽쇠 방향도 헷갈려 입출력도 버벅이던 나 였는데..ㅋㅋㅋ 히히

 

글로벌 탐방 서류 마감이랑 수강신청, 각종 장학금 신청, 정정 증원 청강메일... 등등으로 바쁜 하루하루지만

그만큼 뿌듯하다! 또 컴퓨터 사이언스 공부의 본격 시작인 학기라 두려우면서도.. 디게 설렌다!

컴구.. 시소실.. 자구.. 나름 재밌을지도..!ㅎ  하 근데 이번학기 시간표.....................

 

이번 주차 구현 문제는 저번 것들보다 조금 어려워 아직 코너케이스와 반례를 찾진 못하였지만,

정수론의 두 가지 내용을 활용하는 필수 과제 2문제는 해결해 뿌듯하다 :)

하아 근데 구현문제 진짜아... C언어가 아직은 부족해 쉬운 구현도 더 어렵게 느껴진다...ㅠㅠ

자프실 과목 때문에 자바도 잊으면 안돼서 문제 풀 때 틈틈이 쓰고 있다.

프로그래밍 언어는 뭐 조금만 안쓰면 자꾸 까먹기 마련이니깐..ㅎ

이번 학기 좀 힘든 시간표지만,, 끝까지 견뎌 이겨내 해내..! 알튜비튜도 끝까지 가보자! 아자아자ㅏ아