https://www.acmicpc.net/problem/15990

1.문제설명

이 문제에서는 덧셈을 할 때 숫자가 중복되면 안되므로

마지막으로 끝난 숫자가 중요하다.

즉 합의 상태를 저장하면서 동시에 마지막 숫자의 상태를 저장해줄 필요가 있다.

이를 점화식으로 나타내면

dp[합][마지막 숫자] = 합을 나타낼 수 있는 경우의 수

로 나타낼 수 있고

더해지는 숫자는 1, 2, 3이기 때문에

dp[i][3] = (dp[i-3][1] + dp[i-3][2]);
dp[i][2] = (dp[i-2][1] + dp[i-2][3]);
dp[i][1] = (dp[i-1][2] + dp[i-1][3]);

이렇게 나타낼 수 있다.

2.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000009;

long long dp[100001][4];

void calDP(){
    dp[1][1] = 1, dp[1][2] = 0, dp[1][3] = 0;
    dp[2][1] = 0, dp[2][2] = 1, dp[2][3] = 0;
    dp[3][1] = 1, dp[3][2] = 1, dp[3][3] = 1;

    for(int i=4; i<=100000; i++){
        dp[i][3] = (dp[i-3][1] + dp[i-3][2]) % mod;
        dp[i][2] = (dp[i-2][1] + dp[i-2][3]) % mod;
        dp[i][1] = (dp[i-1][2] + dp[i-1][3]) % mod;
    }
}

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

    calDP();

    int t;
    cin >> t;
    for(int T=0; T<t; T++){
        int a;
        cin >> a;

        cout << (dp[a][1] + dp[a][2] + dp[a][3]) % mod << '\n';
    }



    return 0;
}

https://www.acmicpc.net/problem/14226

1. 문제설명

한 번에 3가지 연산을 할 수 있다.

screen과 clipboard의 정보를 저장해서 BFS를 수행하면

원하는 이모티콘의 개수를 만들기 위한 최소 단계를 구할 수 있다.

2. 문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;
#define MAX_NUM 2003


int s;
struct Emoticon{
    int screen, copied;
};

int vis[MAX_NUM][MAX_NUM];

int BFS(int x){
    queue<Emoticon> Q;
    Q.push({1,0}); vis[1][0] = 1;

    while(!Q.empty()){
        auto cur = Q.front(); Q.pop();
        int curValue = vis[cur.screen][cur.copied];

        if(cur.screen == x){
            return curValue - 1;
        }


        //1. 클립보드에 복사하여 저장
        if(!vis[cur.screen][cur.screen]){
            vis[cur.screen][cur.screen] = curValue + 1;
            Q.push({cur.screen, cur.screen});
        }

        //2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.,클립보드는 그대로 유지
        if(cur.screen+ cur.copied < MAX_NUM && !vis[cur.screen+cur.copied][cur.copied]){
            vis[cur.screen+cur.copied][cur.copied] = curValue + 1;
            Q.push({cur.screen + cur.copied, cur.copied});
        }

        //3. 화면에 있는 이모티콘 중 하나를 삭제한다.
        if(cur.screen-1 > 0 && !vis[cur.screen-1][cur.copied]){
            Q.push({cur.screen-1, cur.copied});
            vis[cur.screen-1][cur.copied] = curValue + 1;
        }

    }

    return -1;
}


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

    cin >> s;
    cout << BFS(s) << '\n';

    return 0;
}

나는 BFS로 이 문제를 풀었는데

DP로도 이 문제를 풀 수 있다.

BFS와 DP의 교집합에 놓인 문제라면

DP가 규칙만 빠르게 발견하면 훨씬 간결하게

풀 수 있는 장점이 있는 것 같다.

시간 절약을 위해 DP 공부를 더 해야할 필요가 있어보인다.

https://www.acmicpc.net/problem/1963

1.문제설명

에라토스테네스 체를 이용하여 미리 소수를 구분할 수 있는 배열을 만들어두고

입력받은 두 소수 A와 B에서

A를 시작점으로 하여 자리수를 하나씩 바꿔가면서 소수인지 판별하고 BFS를 돌면서

B로 도착할 수 있는지 확인하는 문제

다음 숫자를 구하는 식을 꼼꼼하게 잘 세워야 한다.

8033

1. 1000의 자리숫자 바꿔가면서 확인

0033 1033 2033 3033 4033 5033 6033 7033 8033 9033

2. 100의 자리숫자 바꿔가면서 확인

8033 8133 8233 ... 8933

3. 10의 자리 숫자 바꿔가면서 확인

8003 8013 8023 8033 ... 8093

4. 1의자리 숫자 바꿔가면서 확인

8030, 8031, 8032, ... 8039

즉 8033이 시작 숫자면

위의 모든 숫자를 한번 씩 보면서

소수인지 확인하고, 1000이상인지 확인하고, 이전에 방문했던 숫자인지 확인하여

BFS를 돌면 된다.

2.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

bool Prime[10000];


void eratos(){
    fill(Prime, Prime+10000, 1);

    Prime[0] = 0; Prime[1] = 0;
    int sqrtn = int(sqrt(10000));

    for(int i=2; i<=sqrtn; i++){
        for(int j=i*i; j<10000; j+=i){
            Prime[j] = 0;
        }
    }
}


int BFS(int a, int b){
    if(a==b) return 0;

    int vis[10000];
    memset(vis, 0 , sizeof(vis));

    queue<int> Q;
    Q.push(a); vis[a] = 1;


    while(!Q.empty()){
        int cur = Q.front(); Q.pop();
        if(cur==b){
            return vis[cur]-1;
        }

        int minus = 1000;
        for(int i=0; i<4; i++){
            //숫자 계산 확인하기
            int minusedNum = cur - ((cur%(minus*10))/minus)*minus;

            for(int j=0; j<=9; j++){
                int nextNum = minusedNum + j*minus;

                if(Prime[nextNum] && vis[nextNum]==0 && nextNum>=1000){
                    vis[nextNum] = vis[cur] + 1;
                    Q.push(nextNum);
                }
            }
            minus/=10;
        }
    }
    return -1;
}

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

    int t;
    cin >> t;


    eratos();


    for(int T=0;T<t; T++){
        int a, b;
        cin >> a >> b;

        int tmp = BFS(a, b);

        if(tmp<0){
            cout <<"Impossible\n";
        }
        else{
            cout << tmp << '\n';
        }
    }

    return 0;
}

https://www.acmicpc.net/problem/1600

1. 문제설명

일반적인 BFS문제는 상하좌우로 네칸만 움직인다.

이 문제는 원숭이가 평소에는 상하좌우로 네칸을 움직일 수 있다가

K번의 기회로 말처럼 더 넓은 범위를 움직일 수 있다.

이런 문제를 표현하기 위해서는 최대 K번 말처럼 움직일 수 있으므로

현재까지 원숭이가 총 몇 번 말처럼 움직였는지 상태를 저장해줄 필요가 있다.

그래서 이러한 문제 유형을 나는 상태 추가 BFS라고 부르기로 했다.

그냥 저 혼자 부르는 거니까 다른데 가서 유식한 척 말하시면 안됩니다.

2. 상태추가?

왜 상태추가라고 하냐면

보통 일반적으로 BFS를 돌 때는

x,y 좌표를 방문했는지 여부를 저장하면서 중복된 행동을 하지 않도록 합니다.

이 문제도 단지 x,y좌표를 방문했는지 여부와 동일하게

x,y좌표 방문 여부 + '말처럼 움직인 횟수' 라는 상태가 추가되어

중복된 행동을 하지 않으면서 BFS를 돈다고 생각하면 편합니다.

그리고 또한 이 문제를 왜 BFS로 해결 할 수 있냐면

원하는 답이 원숭이가 총 몇번 움직이는 행동을 했는 지 구하는 것이기 때문에

말처럼 움직이든 원숭이처럼 움직이든 특정 행동엔 관심없고

움직임 단계별로 일정하게 증가시키면서 답을 구하면 되기 때문에

너비우선탐색으로 해결 할 수 있습니다.

3.문제풀이코드 C++

#include <bits/stdc++.h>

using namespace std;

struct Position {
    int x, y, k, d;

    Position(int a, int b, int c, int dd) {
        x = a, y = b, k = c, d = dd;
    }
};

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
//horse
int hdx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int hdy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};

queue<Position> Q;

int K, W, H;
int arr[203][203];
bool vis[203][203][32];


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

    cin >> K >> W >> H;

    // 행H , 열W
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> arr[i][j];
        }
    }

    Q.push({0, 0, 0, 0});

    while (!Q.empty()) {
        auto cur = Q.front();
        Q.pop();

        if (cur.x == H - 1 && cur.y == W - 1) {
            cout << cur.d << '\n';
            return 0;
        }

        for (int i = 0; i < 4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];

            if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
            if (vis[nx][ny][cur.k] || arr[nx][ny] == 1) continue;

            vis[nx][ny][cur.k] = 1;
            Q.push({nx, ny, cur.k, cur.d + 1});
        }

        if (cur.k + 1 <= K) {
            for (int i = 0; i < 8; i++) {
                int nx = cur.x + hdx[i];
                int ny = cur.y + hdy[i];

                if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
                if (vis[nx][ny][cur.k + 1] || arr[nx][ny] == 1) continue;

                vis[nx][ny][cur.k + 1] = 1;
                Q.push({nx, ny, cur.k + 1, cur.d + 1});
            }
        }
    }

    cout << -1 << '\n';


    return 0;
}

https://www.acmicpc.net/problem/1325

1. 문제설명

입력으로 노드간의 단방향 연결관계가 주어진다.

입력으로 들어오는 노드는 최대 만개 이하, 간선 관계는 10만개 이하다.

처음 문제를 봤을 때 시간제한이 5초이고 노드가 최대 만개이므로

단순히 모든 노드에 대해 BFS를 돌릴 때 계산량을 생각해보면

10000*10000 = 1억 정도 되므로 2초정도 있으면 충분히 시간제한에 들어올 거라 생각했다.

그런데 정답률이 좀 낮은 걸 보고 이렇게 하면 틀릴까 곰곰히 생각을 해보다가

시간을 줄일수 있는 방법으로 DP를 생각했는데

DP를 사용하면 안된다! 이 문제는 DP를 적용할 수 없는 문제이다.

2. DP를 사용하면 안되는 이유

처음에 계산을 줄이는 방법으로

탐색한 노드에서 연결된 노드(신뢰관계에 놓여진 노드)의 수를 저장하는 방식으로

DP를 이용할 수 있지 않을까 생각했다.

이는 만약 그래프가 단방향 그래프라면 이용할 수 있다.

그림을 보면 쉽게 이해할 수 있다.

위 그림과 같이 단방향 그래프인 경우 노드3번을 통해 노드 1번과 2번의 값을 구할 수 있는

DP 알고리즘을 이용하면 된다.

하지만 이 문제에서는 단방향그래프라는 말이 없었기 때문에

빨간색 같은 간선이 존재할 수 있다.

이럴 경우 사이클이 생기기 때문에 DP를 이용한다면

3번 노드에서 값은  3이 나오는데 이때 3에는 1번 노드가 포함되어 있고,

또 1번 노드를 3번 노드 기반해서 값을 구하면 자기 자신을 포함한 채

실제정답은 3인데 4가 되버리는 현상이 나타난다.

그렇기 때문에 DP를 이용할 수 있는지 없는지

그래프의 특성을 잘 생각해봐야 올바르게 풀 수 있는 문제였다.

이렇게 그냥 무지성으로 DP를 푸는게 아니라

어떻게 풀어야할지 사고과정을 배울 수 있는 좋은 문제인 것 같다.

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, m;
int mem[10001];
vector<int> adj[10001];

int BFS(int x){
    int ret = 0;
    bool vis[n+1];
    memset(vis,0, sizeof(vis));

    queue<int> Q;
    Q.push(x); vis[x] = 1;

    while(!Q.empty()){
        int cur = Q.front(); Q.pop();
        for(auto nx : adj[cur]){
            if(!vis[nx]){
                ret++;
                vis[nx]=1;
                Q.push(nx);
            }
        }
    }

    return ret;
}

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

    cin >> n >> m;

    for(int i=0; i<m; i++){
        int a, b;
        cin >> a >> b;

        adj[b].push_back(a);
    }


    int ans = 0;
    for(int i=1; i<=n; i++){
        mem[i] = BFS(i);
        ans = max(ans, mem[i]);
    }

    for(int i=1; i<=n; i++){
        if(mem[i] == ans){
            cout << i << ' ';
        }
    }


    return 0;
}

https://www.acmicpc.net/problem/16563

1.문제설명

에라토스테네스의 체를 이용하여 소인수분해를 해야하는 문제이다.

빠른 소인수분해를 위해 에라토스테네스의 체를 이용해서

단순히 소수를 판별하는 것을 넘어서

Prime[x] = y , x의 소인수 중 가장 작은 소수 y값을 저장하면

이를 바탕으로 소인수분해를 빠르게 할 수 있다.

예를 들어 10을 소인수 분해 할 때

Prime 배열은 다음과 같다

int x = 10 이라고 하면

Prime[x] == 2 이므로

2를 출력하고 x = x/2를 해준다

그러면 Prime[x] =5 이므로

5를 출력하고 x = x/5

x==1 이므로 종료한다.

이런식으로 에라토스테네스체를 이용하여 빠른 소인수분해를 할 수 있다.

2.문제풀이코드

#include <bits/stdc++.h>
using namespace std;
#define LEN 5000001


//Fast Factorization

int Prime[LEN];

//O(nloglogn)
void erathostenes(){
    Prime[0] = Prime[1] = -1;

    for(int i=2; i<LEN; i++){
        Prime[i] = i;
    }
    int sqrtn = int(sqrt(LEN));

    for(int i=2; i<=sqrtn; i++){
        for(int j=i*i; j<LEN; j+=i){
            if(Prime[j] == j){
                Prime[j] = i;
            }
        }
    }
}

//아마도 O(n) 이하
void Factorization(int num){

    while(num > 1){
        cout << Prime[num] << ' ';
        num /= Prime[num];
    }

    cout << '\n';
}

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

    int t;
    cin >> t;

    erathostenes();

    for(int T=0;T<t; T++){
        int num;
        cin >> num;
        Factorization(num);
    }


    return 0;
}

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
bool ch[200];
bool Prime[200];


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


//소인수분해
vector<ll> factorSimple(ll n){
    vector<ll> ret;

    ll sqrtn = ll(sqrt(n));
    for(ll div = 2; div<=sqrtn; div++){
        while(n%div==0){
            n/=div;
            ret.push_back(div);
        }
    }
    if(n>1) ret.push_back(n);

    return ret;
}

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

    ch[0] = 1;

    for(int i=2; i<100; i++){
        cout << i << ' ';
        if(isPrime(i)) cout << "is Prime" << '\n';
        else cout << "is not Prime" << '\n';
    }

    
    
    //slow erathostenes
    for(int i=2; i<200/2 + 1; i++){
        if(ch[i]==0){
            for(int j=i+i; j<200; j+=i){
                ch[j] = 1;
            }
        }
    }

    //fast erathostenes;
    int sqrtn = int(sqrt(200));
    for(int i=2; i<=sqrtn; i++) {
        if (Prime[i])
            for (int j = i * i; j <= 200; j++) {
                Prime[i] = 1;
            }
    }
    
    
    return 0;
}

i 가 루트 n보다 큰 경우에는

이미 이전에 계산한 적이 있기 때문에 생략할 수 있고,

j가 i*i보다 작은 경우도 마찬가지로

i가 i-1이하일 때 이미 계산된 적이 있기 때문에 생략할 수 있다.

그래서 보다 에라스토테네스 알고리즘을 최적화 할 수 있다.

https://www.acmicpc.net/problem/2470

1. 문제설명

두 용액의 합이 가장 0에 가까울 때의 두 용액의 값을 출력하는 문제이다.

단순하게 나올 수 있는 모든 용액의 합을 구하면 시간복잡도가 O(N^2)이 되기 때문에 틀린다.

우선 모든 용액의 값을 받아 정렬하고

가장 작은값과 가장 큰값을 start 지점과 end지점으로 두어서 더해본다.

v[start] + v[end] > 0 이라면 두 용액의 합이 0에 가까워지기 위해서

두용액의 합을 줄여야한다.

이 때 이미 모든 용액은 오름차순으로 정렬되어 있기 때문에 두 용액의 합을 줄이기 위해서는

end의 값을 줄여야한다

반대로 v[start] + v[end] < 0 일 때는 두 용액의 합이 0에 가까워지기 위해

두 용액의 합을 키워야하므로

start의 값을 키워야한다.

이 과정을 start < end 인 동안 반복한다.

두 용액은 다른 용액을 사용해야 하기 때문에 start==end가 되어서는 안된다.

이 과정을 반복하면 abs(v[start] + v[end])가 최소가 되는 지점을 찾을 수 있다.

이를 코드로 옮기면 된다.

정렬할 때 시간복잡도 O(NlogN)

start, end를 찾는 과정 O(N) 이므로

O(NlogN)으로 이 문제를 해결 할 수 있다.

2.문제풀이코드

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> v;

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

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

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


    int st = 0, en = n-1;

    int ans_val = INT_MAX;

    int ans1, ans2;
    while(st < en){
        int sum = v[st] + v[en];
        if(sum==0) {
            cout << v[st] << ' ' << v[en];
            return 0;
        }

        if(ans_val >= abs(sum)){
            ans_val = abs(sum);
            ans1 = v[st];
            ans2 = v[en];
        }

        //두합이 0보다 크다면 en의 값을 줄여야하고 0보다 작다면 st의 값을 증가시킨다.
        if(sum > 0){
            en--;
        }
        else{
            st++;
        }
    }

    cout << ans1 << ' ' << ans2;


    return 0;
}