[ 알튜비튜 6기 ] 6개월 전엔 못풀고 끙끙대던 코드를.. 다시 풀어보다 !

 

일단 먼저.. 6개월 전의 나..

c++ 도 낯설고 자료구조도 못배웠던 시절이라 참.. 끙끙거리고 있는게 애잔하군

https://somde.tistory.com/98

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

 

 

2024.3월 알튜비튜 5기를 수료하고 6기를 수강하는 자의 코드 수정

 

구현 문제 쉽던데.. 이땐 왜 못풀었지...? ㅋㅋㅋ ㅠㅠ 이땐 자료구조 수강 전이라 원형을 배열로 구현할 방법조차 몰랐던 것 같다. 이런 과거 기록을 보니 새삼 내가 많이 성장한 것 같아 뿌듯하다 ㅋㅋ 6달만에 꽤 컸구나 너 !

 

 

그리고.. 6달 전엔 못풀었던ㅋㅋ 구현문제부터 풀이해보자

 

 

자세한 나의 풀이는 요기로 !  https://somde.tistory.com/168

[ C++/cpp ] 백준 (2840 행운의 바퀴) ⭐구현, 시뮬레이션 💥💦

 

(정답코드) 

#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;
}

 

 

 

 

---

 

 

 

골드바흐의 추측도 쪼끔 더 효율적인 코드로 수정 !

 

과거엔 그냥 맞추면 맞아따~ 했지만 이젠.. 에라토스테네스의 체도 깊게 공부해서 완전히 이해해따 :)

자세한 공부한 내용은 요기 !

https://somde.tistory.com/165

[ 정수론 ] 소수 구하기 - 에라토스테네스의 체, 제곱근 기준 소수 판별, 구현까지

 

 

 

수정사항
- 에라토스테네스의 체, 제곱근까지만 계산하고, 제곱수부터 배수 지워나가는 걸로 수정

- 홀수만 취하니 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개월 전의 김은솜 기록이 웃겨서..ㅋㅋ 써보는 글

성장했따 !