컴공댕이 공부일지
[ 정수론 ] 필수 과제 해결 📚유클리드 호제법, 아리스토테네스의 체 본문
백준 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언어가 아직은 부족해 쉬운 구현도 더 어렵게 느껴진다...ㅠㅠ
자프실 과목 때문에 자바도 잊으면 안돼서 문제 풀 때 틈틈이 쓰고 있다.
프로그래밍 언어는 뭐 조금만 안쓰면 자꾸 까먹기 마련이니깐..ㅎ
이번 학기 좀 힘든 시간표지만,, 끝까지 견뎌 이겨내 해내..! 알튜비튜도 끝까지 가보자! 아자아자ㅏ아
'기록 > 알고리즘 스터디 알튜비튜 5기✨' 카테고리의 다른 글
[ 우선순위 큐 ] 구현 과제 (백준 2607 비슷한 단어 c++) +멘토 코멘트 (0) | 2023.09.20 |
---|---|
[ 브루트포스 ] 도전 과제-1 ( 백준 14620 꽃길 c++) (0) | 2023.09.13 |
[ 브루트포스 ] 필수과제 해결하기 ( 백준 1063, 1436, 11723 c++) (0) | 2023.09.12 |
[ 정렬 ] 🔎BubbleSort / MergeSort / sort() 사용법 (0) | 2023.08.23 |
[ OT ] c++과 시간복잡도 , 깃허브 기초 (0) | 2023.08.19 |