스택 구현 문제 월요일 구현 내용인데

잘못된 부분을 찾은줄 알았는데, 그게 아니라서 정답을 보니까

문제 해석자체를 잘못한거 같아서 난독증있나 싶었다.

https://www.acmicpc.net/board/view/128983

출제자도 인정했다.

근데 여기 답변을 보면 문제를 보고, 해석이 애매하면 예제를 보고 알 수 있어야 한다고 하는데.

물론 타당한 의견이지만 음... 뭔가 비유로 표현하면 레고 조립설명서 같은 느낌... 설명은 잘못됐지만 그림은 이상없죠?

#include <iostream>
#include <math.h>
using namespace std;

int main(void) {
    int n;
    cin >> n;

    cout << int(sqrt(n));
    return 0;
}

회고

전에 했던 방식으로 21억까지 입력이 들어오면 메모리 할당에 필요한 공간이 약 8000MB = 8GB가 필요한 어마무시한 상황이였다.

이 문제를 어떻게 해결해야하나 고민해봤는데 15분정도 더 고민해도 문제가 풀리지 않아서

인터넷에 검색하여 해답을 보았다.

결과값의 규칙을 찾고 제곱근을 출력하면 되는 규칙을 찾아내면 된다.

간단했다.

진행중

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

int main(void) {
    int n, cnt = 0;
    cin >> n;
    vector<bool> w(n, false);

    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j += i) {
            w[j] = !w[j];
        }
    }

    for (int i = 1; i <= n; i++) {
        if (w[i]) cnt++;
    }
    cout << cnt;

    return 0;
}

어제 말한대로 체 이용해서 문제를 풀었고, 52ms가 나왔는데 한 중간정도 되는거 같다

굿굿

작성 코드

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

int main(void) {
    int max = 1000000;

    vector<bool> isPrime(max, true);

    for (int i = 2; i * i < max; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= max; j += i) {
                isPrime[j] = false;
            }
        }
    }

    int t;
    cin >> t;

    for(int i = 0; i < t; i++){
        int n, cnt = 0;
        cin >> n;
        for(int j = 2; j <= n / 2; j++) {
            if(isPrime[j] && isPrime[n - j]) cnt++;
        }
        cout << cnt << "\n";
    }

    return 0;
}

제출 코드

#include <iostream>
using namespace std;

bool isPrime(int x) {
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

int main(void) {
    int n = 1;

    cin >> n;
    while (n) {
        int cnt = 0;
        for (int i = n + 1; i <= 2 * n; i++) {
            if(isPrime(i)) cnt++;
        }

        cout << cnt << '\n';
        cin >> n;
    }

    return 0;
}

음 풀었는데 시간이 너무 오래걸린다!!

풀이 방식

전 포스트들과 똑같이 소수 판별할 때 그 수의 제곱근까지만 판별하면 되는데

에라토스테네스의 체 방식으로 풀어야 할거 같다

왜냐하면 소수 판별에 필요한 범위가 주워지기 때문이다.

구현이 어려워서 의사코드를 찾아봤다.

algorithm Sieve of Eratosthenes is
    input: an integer n > 1.
    output: all prime numbers from 2 through n.

    let A be an array of Boolean values, indexed by integers 2 to n,
    initially all set to true.

    for i = 2, 3, 4, ..., not exceeding √n do
        if A[i] is true
            for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n do
                set A[j] := false

    return all i such that A[i] is true.

음 영어 어렵지만 하나하나 구현해보자

#include <iostream>
using namespace std;

int main(void) {
    int n;
    cin >> n;

    bool A[n];

    for (int i = 0; i < n; i++) {
        A[i] = true;
    }

    for (int i =2; i * i < n; i++) {
        if (A[i]) {
            // i2, i2+i, i2+2i, i2+3i ???????????
            for (int j = i * i; j <= n; j += i) { //그녀석의 도움
                 A[j] = false;
            }
        }
    }
    return 0;
}

내일은 정말 이 기술을 마스터 해보자.

#include <iostream>
using namespace std;

int main(void) {
    int m, n;
    cin >> m >> n;

    // 체는 소수가 아닌것들을 미리 판단할 수 있음.

    bool isPrime[n - m + 1] = { false };

    for (int i = m; i <= n; i++) {
        if (isPrime[i - m]) continue;

        bool flag = true;
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                flag = false;
                break;
            }
        }

        if (flag) {
            for (int k = i; k <= n; k *= i) {
                isPrime[k - m] = false; // 소수가 아님
            }
        }
    }

    for (int i = 0; i <= n - m; i++) {
        if(!isPrime[i]) continue;
        cout << isPrime[i] << "\n";
    }

    return 0;
}

어제 이 문제를 분석하면서

1. 소수 판별과정에서 제곱근까지만 판별한다.
2. 소수의 배수는 소수 판별에서 제외한다.

2개가 핵심 키 포인트라고 강조했는데

먼저 1번만 대충 구현하고 제출 해봤는데

바로 통과 됐다.

1차 제출

#include <iostream>
using namespace std;

int main(void) {
    int m, n;
    cin >> m >> n;

    if (m == 1) m = 2;

    for (int i = m; i <= n; i++) {

        bool flag = true;
        for (int j = 2; j * j <= i; j++) {
            if(i % j == 0) {
                flag = false;
                break;
            }
        }

        if (flag) {
            cout << i << endl;
        }
    }

    return 0;
}

아무래도 이대로 끝내긴 아쉬워서 내일 2번을 구현을 꼭 해봐야겠다.

1929 소수 구하기

문제 분석

(1 ≤ M ≤ N ≤ 1,000,000)

M이상, N이하의 숫자의 모든 소수를 구하기

이거 보니까.

어제 풀었던 다음 소수 문제에서 해당 숫자의 제곱근까지만 소수를 판별하고, 로직 그대로 사용하면 풀릴것 같은데??

오 근데, 범위가 주어진 케이스라서... 2는 소수야 -> 근데 2의 배수 4, 8, 10, 12 --- 는 소수가 아니니까 이것들을 제외하는 로직도 있어야 하겠지?? 에라토스테네스의 체 라는건데 참고 블로그를 보면 메모리 할당이 많아져서 보통 N이 1,000,000 이하인 경우만 이 방식으로 해결한다고 하는데 혼자 검증해보면 좋을듯.

결론

1. 해당 숫자의 제곱근까지만 소수 판별
2. 소수로 판정된 수의 배수들은 미리 필터링

2가지가 핵심인데...

오늘 아침밥 안 먹으면 아마 영양실조로 숨쉰채 발견이라 밥좀 먹을게요 :>

1차 시도

#include <iostream>
using namespace std;

bool f(unsigned int n){
    unsigned int x = n - 1;

    while(x > 1){
        if(n % x == 0) return false;
        else x--;
    }

    return true;
}

int main(void) {
    int t = 0;
    cin >> t;

    for(int i = 0; i < t; i++){
        unsigned int n;
        cin >> n;

        while(true){
            if(f(n)) break;
            n++;
        }

        if(n < 2) n = 2;
        cout << n << endl;
    }

    return 0;
}

원래 이정도 난이도면 엄청 쉽게 푸는데.... 너무 오랜만에 잡으니까 감을 잃어버렸네요.

시간초과 솔루션

1. 소수 판별 순서변경

일단 n이 주워지면 100일때 99부터 나눠보면서 내려가는게 아니라 2부터 나눠서 소수인지 판별하는게 좀더 빠르게 나오지 않을까?

bool f(unsigned int n){
    unsigned int x = 2;

    while(x < n){
        if(n % x == 0) return false;
        else x++;
    }

    return true;
}

음 해결안됨.

2. 음 소수인지 아닌지를 메모제이션?

알고리즘 책에서 봤던거 같은데... 중복 연산을 피하기 위해서 메모제이션 해서 검사를 통과 시키면 될 것 같은데..

시간 부족해서 구현 안 함.

3. 음 소수에 배수를 곱하면 그 수들은 소수가 아니라는 그런 내용이 있었던거 같은데...

정답 찾아본 결과.

n의 값에(입력 값) 제곱근까지만(소수를 계산할 때) 계산하면 풀리는 문제고,

입력이 0과 1도 포함이라서 여기서 실수가 많이 나오는 것 같은데.. 나는 if(n < 2) n = 2; 이 형식으로 미리 해결을 했어서 시간 초과만 나왔던것 같다.

오랜만에 알고리즘 문제를 풀어서 글씨가 눈에 안들어왔다

오랜만에 봐서 헷갈린 문장들

"첫번째 줄에 테스트케이스가 주어진다"

입력값이 몇번 들어올지 알려준다라고 바로 해석이 됐어야 했는데 그냥 바로 해결해야할 자연수가 주어진다라고 이해해가지고 시간이 좀 걸렸다.

"n보다 크거나 같은 소수 중 가장 작은 소수

이거 문장은 그러니까 100이라면 100부터 101... 102... 103.... 이렇게 쭉 나가면서 소수인 수가 나오면 그때 출력하라는 소리였다.

헷갈린 포인트는 아니 n이 소수가 아닐 수도 있고 소수는 1과 자기자신을 제외한 수로 나누었을때 나누어 떨어지지 않는 수를 말하는데

...?

아하

근데 시간안에 못 풀었음

#include <iostream>
using namespace std;

bool f(int x){
    int div = 
    while(x > 1){

    }
    return true;
}

int main(void) {
    int t = 0;
    cin >> t;

    for(int i = 0; i < t; i++){
        int n;
        cin >> n;

        while(true){
            int x = n;
            if(f(x)) break;
            x++;
        }
    }

    return 0;
}

근데 아마 이렇게 계속 풀면 시간 초과날듯

f에다가 x가 소수면 true 소수가 아니면 false를 반환하는거 만들고, 소수면 출력하면 끝나서

이거 내일 이어서 풀어 볼텐데 내일이 아니라 월요일이 될 것 같습니다. :>

사실 블로그 일상주제로는 몇번 적어봤는데 일단 잡소리 집어치우고.

코딩테스트 준비 계획

제가 원래 코테를 준비했을때 백준에서 "단계별로 풀어보기"를 순서대로 문제를 풀어나갔어요 "약수, 배수와 소수 2"에서 5번 문제부터 풀어나가면 되는데 C++ 기반으로 코딩테스트 문제 풀어나가겠습니다.

알고리즘과 자료구조 책 펴봤는데, 일단 백준 하면서 그 단계에 필요한 내용을 먼저 배운 뒤 다음으로 문제를 푸는 형식으로 진행하겠습니다.

4134번: 다음 소수

수학 브루트포스 알고리즘 정수론 소수 판정

아직 문제는 안읽고 필요한 알고리즘만 빼서 봤는데 브루트포스 알고리즘이 전체를 다 조회하러 다니는 그런 알고리즘으로 알고 있었는데 찾아 보니까 얼추 맞네요

이제 브루투포스 안에서 깊이탐색(DFS)할거냐 너비우선탐색(BFS)할거냐 나뉘는거 같습니다.

근데 DFS, BFS 탐색 알고리즘 공부한적이 없어서 고민 되는데

미리 문제를 잠깐 봐볼게요. ㅋㅋ

음 DFS, BFS 필요 없고 그냥 무식하게 풀어가도 괜찮은데 이제 시간 초과나 메모리 초과 되면 공부하는 것으로 하겠습니다.

일단 소수판정 이거 다시 한번보고 문제를 풀어봐야겠네요.