this.code();

🧐 백준 2581 (소수의 원리 이용)

🤫 해결의 실마리 

🤔 소수의 원리 
소수의 원리 => 약수의 개수가 2개 (1과 자기자신)

🤔 Algorithm 과정 
1. num이라는 빈 리스트에 입력된 M ~ N까지의 숫자를 넣는다.
2. 약수의 개수를 세는 cnt라는 변수를 선언, 0으로 초기화한다.
3. 소수를 담을 리스트 dec을 선언한다.
4. num리스트의 원소를 차례로 돌면서 i % j == 0 즉, 약수일 때, cnt값을 증가시킨다.
5. 이렇게 약수의 개수가 담긴 cnt변수에 대해 만약 약수의 개수가 2개라면(cnt == 2) 소수인것!
따라서 소수라면 dec 리스트에 원소를 추가해주고 cnt==0이라면 소수가 없는 것이므로 0을 출력!

🤫  solution_2581

 

M, N = int(input()), int(input())
num = []
for i in range(N-M+1):
    num.append(i+M)

dec = []
for i in num:
    cnt = 0
    for j in range(1, i+1):
        if i % j == 0:
            cnt += 1
    if cnt == 2:
        dec.append(i)
if len(dec) == 0:
    print(-1)
else:
    print(sum(dec))
    print(min(dec))

🧐 백준 1929 (에라토스테네스의 체) _ 앞으로 계속 이 문제에서 파생하여 문항을 해결함

🤫 해결의 실마리 

🤔 에라토스테네스의 체 (Sieve of Eratosthenes)

 

에라토스테네스의 체 원리는 다음과 같다.
1. 소수가 아닌 1을 지운다.
2. 2의 배수를 지운다.
3. 앞서 지운 2의 배수가 아닌 것들 중 최소값인 3의 배수를 지운다.
4. 앞서 지운 2, 3의 배수가 아닌 값들 중 최소값인 5의 배수를 지운다.
5. 이 과정을 반복하여 걸러지는 것들이 비로소 소수가 된다.

이러한 에라토스테네스의 체는 "특정 구간이 주어졌을 때" 매우 빠르게 소수를 도출할 수 있다.
위의 2581번처럼 풀면 시간복잡도는 O(n)으로 비교적 시간이 오래 걸린다.
하지만 에라토스테네스의 체의 시간복잡도는 O(nlog(log n))으로 매우 빠르게 도출이 가능하다.
또한 약수의 경우, 2*4, 4*2 처럼 반복이 되기 때문에
가장 중요한 것은 범위의 마지막 수의 루트 값까지만 반복함으로 시간을 더욱 줄일 수 있다!


🤔 Algorithm 과정 
알고리즘과정은 위에서 설명하는 에라토스테네스의 방식을 차용하였다.
또한 코드에 대한 설명은 아래 그림으로 대체하겠다.

🤫  solution_1929

m, n = map(int, input().split())
num = [i for i in range(max(2, m), n+1)]  # m ~ n사이 숫자를 넣은 리스트 (단, 1은 제외)
dec_sqr_n = []   # n의 제곱근까지의 범위안에서 소수를 집어 넣을 리스트

for i in range(2, int(n**0.5) + 1):   # 2에서 n의 제곱근까지만 반복
    if i in num:
        dec_sqr_n.append(i)
    num = [j for j in num if j % i != 0]

print(*(dec_sqr_n + num), sep = "\n")

 

 

🧐 백준 4948 (에라토스테네스의 체)

🤫 해결의 실마리 

🤔 에라토스테네스의 체 (Sieve of Eratosthenes)

🤔 Algorithm 과정 
위 1929와 거의 동일한 방식으로 풀었지만 방법은 다음과 같다.
1. n의 범위 사이의 자연수를 저장하는 num 리스트를 생성한다. (1 ≤ n ≤ 123456)
2. 리스트 num을 1929번 풀이처럼 소수만 존재하도록 만들어준다.
3. 1929와 같은 방식으로 n의 범위사이에 존재하는 모든 소수가 담긴 decimal이라는 리스트를 생성해준다.
4. 0이 들어오기 전까지 while문을 이용해 입력을 받아주고
5. decimal 리스트에서 입력의 범위에 해당하는 값들의 개수를 세어 출력해준다.

 

🤫  solution_4948 (시간초과)

def decimal(N):
    n = N+1
    num = [i for i in range(n, 2*N + 1)]
    dec_half = []
    for i in range(2, int((2*N)**0.5) + 1):
        if i in num:
            dec_half.append(i)
        num = [j for j in num if j % i != 0]
    return len(dec_half+num)

num = -1
while True:
    num = int(input())
    if num == 0:
        break
    else:
        print(decimal(num))

 

처음 짠 코드로 1929와 비슷하게 함수를 생성하여 풀었으나 시간초과가 발생하였다.
시간복잡도를 염두하지 않고 머리를 장식으로 두고 문제에 접근한 결과라 생각할 수 밖에 없다.
함수에서 2중 for문을 사용한 것을 while문에서 계속 받으니 그럴 수 밖에...

🤫  solution_4948

from math import sqrt

# 1 <= n <= 123456 사이 자연수를 담은 리스트 생성
num = [i for i in range(2, 123456 * 2)]

# 리스트 num을 이전처럼 소수만 있게 만들어주기.
dec_half = []
for i in range(2, int(sqrt(123456*2)) + 1):
    if i in num:
        dec_half.append(i)
    num = [j for j in num if j%i != 0]

decimal = dec_half + num

n = -1
while True:
    n = int(input())
    if n == 0:
        break
    # decimal 리스트에서 입력의 범위에 해당하는 값들의 개수를 세어 출력
    print(len([i for i in decimal if n < i <= 2*n]))

🧐 백준 9020 (에라토스테네스의 체)

🤫 해결의 실마리 

🤔 에라토스테네스의 체 (Sieve of Eratosthenes)

🤔 Algorithm 과정 
두 소수의 차이가 가장 작은 것의 의미를 생각해보면 다음과 같다.
소수간의 차이가 작을수록 최대값의 절반과 가까워진다! 
16으 예로 들자면 다음과 같다.
[3, 13], [5, 11]  =>  3  5  (8)  11  13

따라서 핵심은 시간초과가 걸리지 않으려면 소수의 절반만 훑어야 한다.

 

🤫  solution_9020 (시간초과)

T = int(input())
n = [int(input()) for _ in range(T)]

num = [i for i in range(2, 10001)]
dec_half = []
for i in range(2, 100 + 1):
    if i in num:
        dec_half.append(i)
    num = [j for j in num if j % i != 0]
decimal = dec_half + num

for i in n:
    dec = []
    for j in range(len(decimal)):
        for k in range(j, len(decimal)):
            if i == decimal[j] + decimal[k]:
                dec.append([decimal[j], decimal[k]])
    print(*dec[-1])

처음 짠 코드로 문제점은 소수의 전체를 계속 훑으면서 비교를 진행하기 때문에 위의 알고리즘보다 2배 이상의 시간이 걸릴 가능성이 높다.
먼저 위의 코드를 짠 과정은 다음과 같다.
1. 먼저 범위에 해당하는 모든 소수를 담는 리스트를 생성하고 
2. 그 리스트 안에서 두 소수간의 덧셈이 입력값과 동일한 것을 찾아서 dec이라는 리스트에 넣는다.
3. dec에는 [[3, 5]], [[3, 7], [5, 5]], [[3, 13], [5, 11]] 처럼 들어간 것이므로 
4. 각 리스트의 마지막 인덱스에 해당하는 리스트가 차이가 가장 작은 소수 리스트인것.
이를 for문을 이용해 출력하였다.

🤫  solution_9020

num = [i for i in range(2, 10000 + 1)]
dec_half = []
for i in range(2, 100 + 1):
    if i in num:
        dec_half.append(i)
    num = [j for j in num if j%i != 0]
decimal = dec_half + num

T = int(input())
for i in range(T):
    n = int(input())
    n_half = n // 2
    for j in range(n_half, 1, -1):
        if j in decimal and n - j in decimal:
            print(j, n - j)
            break

🫠 백준 1065 (https://www.acmicpc.net/problem/1065)

🧐 Algorithm 
1. 먼저 등차수열이어야 하므로 자리수간의 공차가 같아야 하기에 a-b와 b-c의 값이 동일해야함.
2. 이를 위해 함수 hansu를 만들었고 이를 100의자리수에서 사용.
3. 100~999까지 기준일 때 등차수열조건을 만족시켜야 하므로 다음과 같이 함수를 사용한다.

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

bool hansu (int num){
    int a = num / 100;
    int b = (num - a*100) / 10;
    int c = num % 10;
    return a-b == b-c;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int cnt = 0;
    int num;    cin >> num;

    if (num <= 99){
        cout << num;
    }
    else if (num >= 100 && num <= 999) {
        for (int i = 100; i <= num; i++) {
            cnt += hansu(i);
        }
        cout <<  cnt + 99;
    }
    else
        cout << 144;
}

🫠 백준 1978(https://www.acmicpc.net/problem/1978)

🧐 Algorithm _ 소수를 찾는 법
1. a % b == 2라는 식은 약수를 구하는 식이며 
2. 이 약수의 개수를 세는 cnt라는 변수를 이용해 x의 약수개수를 구하고
3. 소수의 특징 (약수의 개수가 1과 자기자신)을 이용해 약수 개수가 2인 자연수 값들을 세준다.

#include <iostream>
using namespace std;

int main() {
   ios_base::sync_with_stdio(0);

    int num;    cin >> num;
    int count = 0;
    for (int i = 0; i < num; i++) {
        int cnt = 0;
        int x; cin >> x;
        for (int j = 1; j <= x; j++)
            if (x % j == 0)
                cnt++;
        if (cnt == 2)
            count++;
    }
    cout << count << endl;
    return 0;
}

🫠 백준 2581(https://www.acmicpc.net/problem/2581)

🧐 Algorithm _ 소수를 찾는 법
1. a % b == 2라는 식은 약수를 구하는 식이며 
2. 이 약수의 개수를 세는 cnt라는 변수를 이용해 x의 약수개수를 구하고
3. 소수의 특징 (약수의 개수가 1과 자기자신)을 이용해 약수 개수가 2인 자연수 값들을 세준다.

이를 이용해 값들의 전체 합을 구해주고 가장 최소값은 작은 순서대로 vector에 넣어줬으므로
당연히 vector의 첫번째 원소에 들어있는 값이 최소값이 된다.

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


int main() {
   ios_base::sync_with_stdio(0);

    int M, N;   cin >> M >> N;
    int sum = 0;

    vector<int> v;

    for (int i = M; i <= N; i++) {
        int cnt = 0;
        for (int j = 1; j <= i; j++)
            if (i % j == 0)
                cnt++;
        if (cnt == 2){
            v.push_back(i);
            sum += i;
        }
    }

    if (v.size() == 0)
        cout << -1 << endl;

    else {
        cout << sum << endl;
        cout << v[0] << endl;
    }
}

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

pair<int, string> p[100000];

bool compare (pair<int, string> p1, pair<int, string> p2) {
    return p1.first < p2.first;
}

int main() {
   ios_base::sync_with_stdio(0);
    cin.tie(0);

    int num;
    cin >> num;

    for (int i = 0; i < num; i++) {
        int num; string str;  cin >> num >> str;
        p[i] = { num, str };
    }

    stable_sort(p, p+num, compare);

    for (int i=0; i<num; i++) {
        cout << p[i].first << " " << p[i].second << "\n";
    }
}

※ 이번 문제에서 알게된 점

§  재귀함수로 구현하는 gcd, lcm 함수

// 최대공약수
auto gcd(long long A, long long B){
    if (B == 0)
        return A;
    else
        return gcd(B, A%B);
}

// 최소공배수
auto lcm (long long A, long long B){
    return A*B/gcd(A,B);
}

§ my solution

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

// 최대공약수
auto gcd(long long A, long long B){
    if (B == 0)
        return A;
    else
        return gcd(B, A%B);
}

// 최소공배수
auto lcm (long long A, long long B){
    return A*B/gcd(A,B);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    long long A, B;   cin >> A >> B;
    cout << lcm(A,B);
}

§ my solution

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

auto gcd(long long a, long long b){
    if (b == 0)
        return a;
    else
        return gcd(b, a%b);
}

auto lcm(long long a, long long b){
    return a*b / gcd(a, b);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int num;    cin >> num;
    vector<long long> v1;
    vector<long long> v2;

    for (int i = 0; i < num; i++) {
        int a, b;   cin >> a >> b;
        v1.push_back((a));
        v2.push_back((b));
    }

    for (int i = 0; i < num; i++) {
        cout << lcm(v1.at(i), v2.at(i)) << '\n';
    }
}

※ 이번 문제에서 알게된 점

§  sort(v.begin(), v.end(), custom_func) 함수

1. 먼저 vector에 include 되어 있는 pair를 선언해 입력을 받으면 다음과 같다.

vector< pair<int, int> > p;

for (int i = 0; i < num; i++) {
    int n1, n2; cin >> n1 >> n2;
    p.push_back(make_pair(n1, n2));
}

2. 그 후 sort를 해줘야 하는데, 이때 문제는 sort를 해주면 p.first를 기준으로 정렬 된다는 것.

그래서 사용자가 만든 함수로 sort(v.begin(), v.end(), custom_func) 의 custom_func에 넣어서

p.second 기준으로 정렬되도록 해야한다. 이때, custom_func의 결과값은 0, 1이 나와야 하며 보통 bool type이다.

bool compare(pair<int, int> a, pair<int, int> b) {
    if (a.second == b.second)
        return a.first < b.first;  // a.first가 작으면 true. 즉 작은게 앞에 배치가 된다.
    return a.second < b.second;       // a.second가 더 작으면 true. 즉 작은게 앞에 배치가 된다.
}

sort(p.begin(), p.end(), compare);

\

§ my solution 

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

bool compare(pair<int, int> a, pair<int, int> b) {
    if (a.second == b.second)
        return a.first < b.first;  // a.first가 작으면 true. 즉 작은게 앞에 배치가 된다.
    return a.second < b.second;       // a.second가 더 작으면 true. 즉 작은게 앞에 배치가 된다.
}

int main() {
    ios_base::sync_with_stdio(0);
    int num; cin >> num;

    vector< pair<int, int> > p;

    for (int i = 0; i < num; i++) {
        int n1, n2; cin >> n1 >> n2;
        p.push_back(make_pair(n1, n2));
    }
    sort(p.begin(), p.end(), compare);

    for (auto x:p) {
        cout << x.first << " " << x.second << '\n';
    }
}

§ my solution 

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

int main() {
    ios_base::sync_with_stdio(0);
    int N, A;   cin >> N >> A;
    vector<int> v;
    for (int i = 0; i < N; i++) {
        int num;    cin >> num;
        v.push_back(num);
    }
    sort(v.begin(), v.end());
    cout << v[A-1];
}

§ my solution 

- endl 대신 '\n'을 애용하자!

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int N;  cin >> N;
    vector<int> v;
    for (int i = 0; i < N; i++) {
        int num;    cin >> num;
        v.push_back(num);
    }
    sort(v.begin(), v.end());
    for(auto x:v)
        cout << x << '\n';
}

§ my solution 

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int N; cin >> N;
    vector<int> v;
    for (int i = 0; i < N; i++) {
        int num;    cin >> num;
        v.push_back(num);
    }
    sort(v.begin(), v.end(), greater<int>());
    for(auto x:v)
        cout << x << '\n';
}

※ 이번 문제에서 알게된 점

§  unique() 함수

https://chan4im.tistory.com/51

§ my solution 

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

int main() {
    ios_base::sync_with_stdio(0);

    int N;  cin >> N;
    vector<int> v;
    for(int i = 0; i < N; i++){
        int num;    cin >> num;
        v.push_back(num);
    }

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    for(auto x:v)
        cout << x << " ";
}

이번 문제는 문제 난이도 자체는 평이, 아니 쉬운 수준이었다.

그냥 배열을 합치고 algorithm 헤더의 sort만 해주면 끝나는 문제였다.

문제는 다름이 아니라 시간초과 발생 때문에 대략 2시간을 잡아먹은 것이다.

코드의 길이를 정말 최대로 줄일 수 있을만큼 줄이고 vector도 사용해보고 배열도 사용해 보았다.

하지만 그렇게 짜본 코드가 모두 시간초과가 떠버렸다.

결과적으로 위에 내가 짰던 코드가 틀린 것은 아니지만,

키워드 3줄만 적어주었더니 시간초과가 뜨지 않았다.

※ 이번 문제에서 알게된 점

§  ios_base::sync_with_stdio() 함수

먼저 C++의 <iostream>은 C의 <stdio.h>와 다르다. 

C++의 입출력 작업 시, C의 입출력과 동기화 되도록 설계되어 상당히 느린 입출력과정을 겪는다.

추가적으로 endl도 출력문자 출력+출력buffer를 함께 비워 시간이 많이 걸려 \n사용을 권장한다.

이때 말하는 "동기화"를 뜻하는 코드가 ios_base::sync_with_stdio이고, 이 동기화를 풀어주는 코드이다.

따라서 동기화가 풀어진다면?  => 당연히 속도를 올릴 수 있다!

ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

큰 힘에는 큰 책임이 따른다고, 이런 ios_base::sync_with_stdio에도 치명적인 단점이 있다.

1. 그건 바로 싱글 쓰레드 (single thread) 환경은 괜찮지만, 멀티 쓰레드 (Multi Thread)환경에서는 출력순서가 어그러진다.

즉, 멀티쓰레드 환경에서의 출력순서가 보장될 수 없다는 것이다!

cf-1) 코딩테스트에서는 싱글쓰레드만 사용하기에 사용해도 무방하다.

cf-2) 다만 실무에서는 ios_base::sync_with_stdio를 쓰기보단, 속도를 올리기 위해 C입출력 방식을 권장한다.

2. 버퍼가 분리되었기에 cin과 scanf, gets, getchar 등의 C문법 (당연히 출력코드도 동일)을 같이 사용할 수 없다!

cf-2) 싱글, 멀티쓰레드란? https://chan4im.tistory.com/35

§  cin.tie(NULL)  /  cout.tie(NULL) 함수

[정의]: istream, ostream 즉, stream을 untie 하여 자동으로 입출력 버퍼를 비우지 않게 함

cin과 cout간의 tie를 끊어주는, 즉 다른 입출력이 온다면 기존의 입출력을 비워주도록 하는 것이다.

이 tie를 끊어줌으로써 시간을 많이 절감할 수 있다.

[예시]

왼쪽을 보면 cout으로 "입력"이란 문구가 출력된 후 cin이 나오는 것을 알 수 있고, 이는 익숙한 방식이다.

하지만 우측은 입력 후 출력이 모두 동시에 되는 것을 알 수 있다.

우리가 tie를 끊어서 입력 전에 출력관련 문구가 아무리 입력보다 먼저 적혀있었더라도 출력이 되지 않는다.

만약 입력전에 출력되게 하고 싶다면 cout buffer를 수동적으로 비워줘야 한다.

https://hegosumluxmundij.tistory.com/54

§ reserve() 와 resize() 의 차이

가장 고생했던 부분이 있는데 다음과 같다.

https://hoondev.tistory.com/7

§ reserve() 와 resize() 의 차이

capacity: 미리 할당해놓은 배열공간

size: 배열에 들어있는 원소의 수

대부분의 컨테이너 STL 자료구조들은 일정 크기를 할당(capacity)한 후 

size가 capacity를 넘으면 2배정도의 크기를 늘려 이동하는 방식으로 구현되어 있다.

§ reserve(N)

- vector의 capacity를 N으로 설정하는 것.

- N이 현재 capacity보다 클 때만 작동, 작으면 아무 일도 발생X

- N이 현재 capacity보다 크다면 모든 원소 reference와 iterator가 전부 무효화(invalidate)된다.

§ resize(N)   /   resize(N, value)

- size > N인 경우, 원소의 개수를 줄인다.

- size < N인 경우, 입력된 value가 없으면 default값인 0으로 할당한다. 있다면 value로 할당.

  그 후, size가 N이 되도록 늘린다.

§ my solution 

총 3가지 방식으로 해결하였다.

1. 배열과 배열의 포인터(주소값)로 sort 후 해결 (메모리 9708KB  /  시간 636ms)

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, M;   cin >> N >> M;
    int arr[N+M];

    for (int i = 0; i < N+M; i++) {
        cin >> arr[i];
    }
    sort(arr, arr+N+M);

    for (const auto& x:arr) {
        cout << x << " ";
    }
}

2. 배열을 벡터로만 바꿈 (메모리 9836KB  /  시간 688ms)

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, M;   cin >> N >> M;
    vector<int> v(N+M);
    for (int i = 0; i < N+M; i++)
        cin >> v[i];

    sort(v.begin(), v.end());

    for (int i = 0; i < N+M; i++) {
        cout << v[i] << " ";
    }
}

3. 정말 벡터 2개를 생성, 합친 후 정렬! (메모리 17656KB  /  시간 644ms)

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, M;   cin >> N >> M;
    vector<int> v1(N);
    vector<int> v2(M);

    for (int i = 0; i < v1.size(); i++){
        cin >> v1[i];
    }
    for (int i = 0; i < v2.size(); i++){
        cin >> v2[i];
    }

    vector<int> v3;

    v3.reserve(v1.size() + v2.size());
    v3.insert(v3.end(), v1.begin(), v1.end());
    v3.insert(v3.end(), v2.begin(), v2.end());

    sort(v3.begin(), v3.end());

    for (const auto& x:v3) {
        cout << x << " ";
    }
}

4. 2개의 vector를 merge와 sort를 이용해 정렬(메모리 24684KB  /  시간 544ms)

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); 
    cout.tie(0);

    vector<int> v1;
    vector<int> v2;

    int N, M;   cin >> N >> M;

    for (int i = 0; i < N; i++) {
        int num;    cin >> num;
        v1.push_back(num);
    }
    for (int i = 0; i < M; i++) {
        int num;    cin >> num;
        v2.push_back(num);
    }
    vector<int> v3;

    merge(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(v3));

    sort(v3.begin(), v3.end());

    for (const auto& x:v3) {
        cout << x << " ";
    }
}

§ my solution 

추출,삽입이 빠른 덱으로 size가 1이 되기 전까지 진행

제일 처음 삭제

dq.erase(dq.begin());

처음값 back으로 push

dq.push_back(dq[0]);

제일 front pop

dq.pop_front();

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

deque<int> dq;

int main(){
    int n;  cin >> n;
    for (int i = 0; i < n; i++) {
        dq.push_back(i+1);
    }
    while (dq.size() > 1){
        dq.erase(dq.begin());
        dq.push_back(dq[0]);
        dq.pop_front();
    }
    cout << dq[0];
}