컴공댕이 공부일지
[ 알튜비튜 6기 ] 6개월 전엔 못풀고 끙끙대던 코드를.. 다시 풀어보다 ! 본문
일단 먼저.. 6개월 전의 나..
c++ 도 낯설고 자료구조도 못배웠던 시절이라 참.. 끙끙거리고 있는게 애잔하군
[ 정수론 ] 필수 과제 해결 📚유클리드 호제법, 아리스토테네스의 체
백준 1735 최대공약수를 구해 연산하는 문제. 이번 주차에서 배운 유클리드 호제법을 재귀함수의 형태로 구현하였다! #include using namespace std; //최대공약수 구하는 함수 int getGcdRecur(int a, int b) { if (
somde.tistory.com
2024.3월 알튜비튜 5기를 수료하고 6기를 수강하는 자의 코드 수정
구현 문제 쉽던데.. 이땐 왜 못풀었지...? ㅋㅋㅋ ㅠㅠ 이땐 자료구조 수강 전이라 원형을 배열로 구현할 방법조차 몰랐던 것 같다. 이런 과거 기록을 보니 새삼 내가 많이 성장한 것 같아 뿌듯하다 ㅋㅋ 6달만에 꽤 컸구나 너 !
그리고.. 6달 전엔 못풀었던ㅋㅋ 구현문제부터 풀이해보자
자세한 나의 풀이는 요기로 ! https://somde.tistory.com/168
[ C++/cpp ] 백준 (2840 행운의 바퀴) ⭐구현, 시뮬레이션 💥💦
백준 2840번 행운의 바퀴(실버 4) https://www.acmicpc.net/problem/2840 2840번: 행운의 바퀴첫째 줄에 마지막 회전에서 화살표가 가리키는 문자부터 시계방향으로 바퀴에 적어놓은 알파벳을 출력한다. 이때,
somde.tistory.com
(정답코드)
#include <iostream>
#include <vector>
using namespace std;
// 시계 방향으로 바퀴가 돌면, 바퀴를 고정된 배열로 뒀을 때, 화살표는 반시계로 도는 것이다.
// 양의 방향을 반시계방향이라 가정하고, 모듈러 연산을 통해 바퀴를 채워나갈 것이다.
// 바퀴에 같은 글자는 두 번 이상 등장하지 않는다 !!!!!!!!
int setWheel(int n, vector<char> &wheel, const vector<pair<int, char>> &info) {
wheel[0] = info[0].second; // 첫 알파벳 배열에 고정 ! 얘 기준으로 이제 돌기.알
int arrow = 0;
vector<int> use_alphabet (26, -1); // 이미 쓰인 알파벳의 인덱스 표기 !
// 0번은 이미 위에서 처리함. 1번 정보부터 확인하며 배열 채우기
for(int i=1; i<info.size(); i++) {
arrow = (arrow + info[i].first) % n ; // 모듈러 연산
//이미 다른값이 채워져있다면,
if(wheel[arrow]!='?' && wheel[arrow]!=info[i].second ) {
return -1;
}
// 같은 알파벳이 중복되어 또 사용된다면,
if( use_alphabet[info[i].second-'A'] != -1 && use_alphabet[info[i].second-'A'] != arrow) {
return -1;
}
wheel[arrow] = info[i].second;
// 현재 화살표가 가리키는 인덱스. 즉 알파벳이 적힌 위치를 저장해줌 !
use_alphabet[info[i].second-'A']=arrow;
}
return arrow; // 화살표 인덱스 리턴
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n, k, s;
char c;
cin >> n >> k ;
vector<char> wheel (n, '?'); // 바퀴 벡터
vector<pair<int, char>> info; // 입력 정보 저장할 pair 벡터
while(k--) {
cin >> s >> c ;
info.push_back(make_pair(s,c));
}
char ans = setWheel (n, wheel, info);
if( ans == -1 ) {
cout << "!";
} else {
// 화살표가 가리키는 곳부터 시계방향(음의 방향) 출력
for(int i=0; i<wheel.size(); i++) {
cout << wheel[ans%n];
if((--ans)<0) {
ans += n; // 음의 방향으로 인덱스 이동하다가, 음수가 되면, 바퀴 칸 수만큼 더하기 !
}
}
}
return 0;
}
골드바흐의 추측도 쪼끔 더 효율적인 코드로 수정 !
과거엔 그냥 맞추면 맞아따~ 했지만 이젠.. 에라토스테네스의 체도 깊게 공부해서 완전히 이해해따 :)
자세한 공부한 내용은 요기 !
[ 정수론 ] 소수 구하기 - 에라토스테네스의 체, 제곱근 기준 소수 판별, 구현까지
📝 에라토스테네스의 체 소수를 구하는 쉽고 빠른 방법 소수를 판별할 때, 아래와 같이 배수들을 지워나가면서 남은 수들을 소수로 판별하는 과정 ! 이거 중딩? 때 다 해봤을거다ㅎㅎ 위의 그림
somde.tistory.com
수정사항
- 에라토스테네스의 체, 제곱근까지만 계산하고, 제곱수부터 배수 지워나가는 걸로 수정
- 홀수만 취하니 a, b 판별할 때 i값도 2씩 빼준다
#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*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-=2) {
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;
}
블로그 정리하다 6개월 전의 김은솜 기록이 웃겨서..ㅋㅋ 써보는 글
성장했따 !
'기록 > 알고리즘 스터디 알튜비튜 5기✨' 카테고리의 다른 글
[ 11주차 투포인터🚩] 개념 + 활용 문제 ( 백준 c++ 11659 구간 합 구하기 4 / 21921 블로그 / 2470 두 용액 ) #누적합 #슬라이딩윈도우 (0) | 2023.11.10 |
---|---|
[ 이분탐색🚩] 개념 + 활용 문제 ( 백준 c++ 1920 수 찾기 / 10816 숫자 카드 2 ) #UpperBound #LowerBound (2) | 2023.11.06 |
[ 8주차 DFS & BFS ] 개념 정리 (0) | 2023.10.10 |
[ 우선순위 큐 ] 개념 + 필수 과제 ( 백준 14235 크리스마스 선물 c++) (0) | 2023.09.23 |
[ 우선순위 큐 ] 구현 과제 (백준 2607 비슷한 단어 c++) +멘토 코멘트 (0) | 2023.09.20 |