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

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

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

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

string shortStr[501];
int lps[501][10001];
int mem[501];

int dp[LEN_MAX];

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

    string longStr;
    int n, Len;
    cin >> longStr >> n;
    Len = longStr.length();

    //BFS 좌표 저장
    for(int N=0; N<n; N++){
        cin >> shortStr[N];

        int sLen = shortStr[N].length();
        for(int i=1, j=0; i<sLen; i++){
            while(j>0 && shortStr[N][i]!=shortStr[N][j]){
                j = lps[N][j-1];
            }
            if(shortStr[N][i]==shortStr[N][j]){
                lps[N][i] = ++j;
            }
        }
    }

    
    
    for(int i=0; i<Len; i++){
        if(i>0) dp[i] = dp[i-1];

        for(int j=0; j<n; j++){
            int sLen = shortStr[j].length();

            while(mem[j]>0 && longStr[i]!=shortStr[j][mem[j]]){
                mem[j] = lps[j][mem[j] - 1];
            }

            if(longStr[i]==shortStr[j][mem[j]]){
                if(mem[j] == sLen - 1){
                    //dp[-1] 방 지
                    int tmp = i -sLen >= 0 ? dp[i-sLen] : 0;
                    tmp += sLen;
                    dp[i] = max(dp[i], tmp);

                    mem[j] = lps[j][mem[j]];
                }
                else{
                    mem[j]++;
                }
            }

        }
    }

    cout << dp[Len-1] << '\n';

    return 0;
}

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

1.문제설명

KMP 알고리즘에 대해 공부하고 예제를 풀던 중

백준 4354번 문자열 제곱 문제를 풀게 되었다.

처음에 이 문제를 어떻게 KMP 알고리즘으로 풀 수 있는지 한참 고민했으나

생각이 나지 않아 구글에 여러 블로그를 뒤져보아도

마땅히 명쾌한 설명을 발견하지 못해 더 한참을 고민했다.

그러다 유튜브를 뒤져보던 중

'개발자영맨' 님의 동영상에서 다음과 같은 KMP 알고리즘의 성질을 발견했다.

말로 설명해주시는 걸 들으면 쉽게 이해할 수 있어서

동영상 31분부터 보면 좋을 것 같다.

출처: https://www.youtube.com/watch?v=OhMFeV8VeAc&t=510s 

실패함수든 lps든 prefix function이든

KMP알고리즘을 사용하기위해

prefix와 suffix를 구하면 그를 통해 반복 패턴의 길이를 구해낼 수 있다.

즉 이 백준문제에서는 단순히 답을 구하기위해

전체 string의 길이에서 위에서 구한 반복 패턴의 길이를 나누었을 때 나머지가 0으로 나누어 떨어진다면

(답 = 전체 string의 길이 / 반복패턴의 길이) 가 된다.

좀 더 자세히 설명하자면 위의 사진과 동일하게

pattern 문자열 = abababa 로 생각해보면

실패함수[n-1] = 5 이고,

전체 string의 길이 = 7 이므로

반복 패턴의 길이는 2 이고

반복 패턴은 ab이며

pattern 문자열(abababa)은 반복 패턴 ab가 반복된 모양이 된다.

즉 KMP 알고리즘에서 실패함수를 유도하는 과정에서 pattern에 대한 반복 패턴도 자연스럽게 얻어진다.

이러한 성질을 통해 코드를 구현하면 된다.

2.문제풀이코드

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

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

    string s;
    while(1){
        cin >> s;
        if(s==".") break;

        int N = s.length();
        int lps[N];
        memset(lps,0,sizeof(lps));

        //prefix function
        int j = 0;
        for(int i=1; i<N; i++){
            while(j>0 && s[i]!=s[j]){
                j = lps[j-1];
            }
            if(s[i]==s[j]){
                j++;
                lps[i] = j;
            }
        }

        int repeatLength = N - lps[N-1];
        if(N % repeatLength == 0){
            cout << N / repeatLength << '\n';
        }
        else{
            cout << 1 << '\n';
        }
    }

    return 0;
}

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

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

int* getLps(const string& _pattern_str){
    int pattern_len = _pattern_str.length();

    int *lps = (int *)malloc(sizeof(int)* pattern_len);
    memset(lps, 0, sizeof(int)*pattern_len);

    int j=0;
    for(int i=1;i < pattern_len; i++){
        while(j>0 && _pattern_str[i]!=_pattern_str[j]){
            j = lps[j-1];
        }

        if(_pattern_str[i] == _pattern_str[j]){
            j++;
            lps[i] = j;
        }
    }

    return lps;
}

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

    //Target, Pattern
    string T, P;
    getline(cin, T);
    getline(cin, P);

    int tLen = T.length();
    int pLen = P.length();
    int *lps = getLps(P);


    int cnt = 0;
    vector<int> v;

    int j = 0;

    for(int i=0; i<tLen; i++){
        while(j>0 && T[i]!=P[j]){
            j = lps[j-1];
        }

        if(T[i] == P[j]){
            if(j==pLen-1){
                v.push_back(i-pLen+1);
                cnt++;
                j = lps[j];
            }
            else{
                j++;
            }
        }

    }

    cout << cnt << '\n';
    for(auto i : v){
        cout << i + 1 << ' ';
    }


    delete lps;

    return 0;
}

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

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

int n,m, sum, maxx;
vector<int> v;


bool decide(int c){
    long long cnt = 0;

    for(int i=0; i<n; i++){
        if(v[i] < c){
            cnt += v[i];
        }
        else cnt += c;
    }

    return cnt <= m;
}

void Input(){
    cin >> n;
    for(int i=0; i<n; i++){
        int t;
        cin >> t;
        v.push_back(t);
        sum+=t;
        maxx = max(maxx, t);
    }
    cin >> m;
}

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

    Input();


    if(sum<=m){
        cout << maxx <<'\n';
    }
    else {
        int lo = 1;
        int hi = 1e9;

        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (decide(mid)) {
                lo = mid + 1;
            } else hi = mid - 1;
        }

        cout << hi << '\n';
    }
    return 0;
}

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

1. 문제설명

공유기를 설치해야하는 최대 거리를 구하기 위해

이분 탐색법으로 가장 작은 거리와 가장 먼 거리를 확인하면서

주어진 조건으로 공유기를 설치할 수 있는 지 확인해야 하는 문제이다.

binary search를 활용한 Decide problem 문제.

2.문제풀이코드

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

int n,c;
vector<int> house;


//O(N)
bool decide(int dist){
    int cnt = 1;
    int x = house[0];

    for(int i=1; i<n; i++){
        if(house[i] - x >= dist){
            x = house[i];
            cnt++;
        }
    }
    return cnt >= c;
}

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

    cin >> n >> c;

    for(int i=0; i<n; i++){
        int t;
        cin >> t;
        house.push_back(t);
    }
    //O(NlogN)
    sort(house.begin(), house.end());

    
    int lo = 0;
    int hi = 1e9;

    //O(NlogN)
    while(lo<=hi){
        int mid = (lo+hi)/2;
        if(!decide(mid)){
            hi = mid-1;
        }
        else{
            lo = mid+1;
        }
    }

    cout << hi << '\n';

    return 0;
}