https://www.youtube.com/watch?v=j_sdjivoPs8 

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

int arr[5][5];
int dp[5][5];
char P[5][5];


void path(int x, int y){
    if(x==1 && y==1){
        cout << x << ' ' << y << '\n';
        return;
    }
    else if(P[x][y]=='^'){
        path(x-1,y);
    }
    else if(P[x][y]=='<'){
        path(x,y-1);
    }

    cout << x << ' ' << y << '\n';
    return;
}


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

    arr[1][1] = 6;
    arr[1][2] = 7;
    arr[1][3] = 12;
    arr[1][4] = 5;
    arr[2][1] = 5;
    arr[2][2] = 3;
    arr[2][3] = 11;
    arr[2][4] = 18;
    arr[3][1] = 7;
    arr[3][2] = 17;
    arr[3][3] = 3;
    arr[3][4] = 3;
    arr[4][1] = 8;
    arr[4][2] = 10;
    arr[4][3] = 14;
    arr[4][4] = 9;



    for(int i=1; i<5; i++){
        for(int j=1; j<5; j++){
            cout << arr[i][j] << ' ';
        }
        cout << '\n';
    }

    for(int i=1; i<5; i++){
        for(int j=1; j<5; j++){
            if(i==1 && j==1) dp[i][j] = arr[i][j];
            else if(i==1) dp[i][j] = arr[i][j] + dp[i][j-1];
            else if(j==1) dp[i][j] = arr[i][j] + dp[i-1][j];
            else dp[i][j] = arr[i][j] + min(dp[i-1][j], dp[i][j-1]);
        }
    }

    cout << '\n';

    for(int i=1; i<5; i++){
        for(int j=1; j<5; j++){
            cout << dp[i][j] << ' ';
        }
        cout << '\n';
    }


    int x=4, y=4;



    for(int i=1; i<5; i++){
        for(int j=1; j<5; j++){
            if(i==1 && j==1) P[i][j] = '-';
            else if(dp[i-1][j] < dp[i][j-1] || j==1){
                P[i][j] = '^';
            }
            else{
                P[i][j] = '<';
            }
        }
    }

    cout << '\n';

    for(int i=1; i<5; i++){
        for(int j=1; j<5; j++){
            cout << P[i][j] << ' ';
        }
        cout << '\n';
    }


    path(4, 4);

    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.youtube.com/watch?v=KXolmVUpUQQ 

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

#define STR_LEN 100

//인 수: 패턴문자열
//반환:lps 배열

int* calculate_lps(char* _pattern_str){
    int pattern_len;
    int* _lps = 0; //LPS 배 열
    int i,j;

    pattern_len = strlen(_pattern_str);

    // LPS 배열
    _lps = (int *)malloc(sizeof(int)* pattern_len);

    // LPS 배열초기화
    memset(_lps, 0 , sizeof(int)*pattern_len);

    /*
     LPS 배열 계산
     */

    j = 0;

    for(int i=1; i<pattern_len; i++){
        if(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() {
    int i, j;

    //target string
    char target_str[STR_LEN] = "ABABABABBABABABABCABABABABBABABABABCABABABABBABABABABCABABABABBABABABABC";

    //pattern string
    char pattern_str[STR_LEN] = "ABABABABC";

    int target_len;
    int pattern_len;

    target_len = strlen(target_str);
    pattern_len = strlen(pattern_str);
    int* lps = 0;

    lps = calculate_lps(pattern_str);

    for(i = 0; i< pattern_len; i++){
        cout << i << ' ' << lps[i] << '\n';
    }


    // --- string matching

    printf("------------ start string matching of %s to %s\n", pattern_str, target_str);


    // i : target str의 현재위치 index
    // j : pattern str의 현재위치 index

    j = 0;

    for(i = 0; i< target_len; i++){
        while(j>0 && target_str[i] != pattern_str[j]){
            j = lps[j-1];
        }
        
        if(target_str[i] == pattern_str[j]){
            if(j == (pattern_len - 1)){
                cout << "Found matching at " << i - pattern_len + 1 << '\n';
                j = 0;
            }
            else{
                j++;
            }
        }
    }



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

https://leetcode.com/problems/best-position-for-a-service-centre/submissions/

const double EPSILON = 1e-6;

class Solution {
public:
    double distance(double cx, double cy, int x, int y){
        return sqrt((cx-x)*(cx-x) + (cy-y)*(cy-y));
    }
    
    
    double distanceSum(const vector<vector<int>>& positions, double x, double y){
        double res = 0;
        
        for(auto& v : positions)
            res += distance(x, y, v[0], v[1]);
        
        return res;
    }
    
    
    double findMax(const vector<vector<int>>& positions, double x){
        double y1 = 0, y2 = 100;
        
        while(abs(y2-y1)>EPSILON){
            double midy1 = (2*y1 + y2)/3;
            double midy2 = (y1 + 2*y2)/3;
            double z1 = distanceSum(positions, x, midy1);
            double z2 = distanceSum(positions, x, midy2);
            
            if(z1 > z2) y1 = midy1;
            else y2 = midy2;
        }
        
        return distanceSum(positions, x, (y1+y2)/2);
        
    }
    
    double getMinDistSum(vector<vector<int>>& positions) {
        double x1 = 0, x2 = 100;
        
        while(abs(x1-x2)>EPSILON){
            double midx1 = (2*x1+x2)/3;
            double midx2 = (x1+2*x2)/3;
            double z1 = findMax(positions, midx1);
            double z2 = findMax(positions, midx2);
            
            if(z1 > z2){
                x1 = midx1;
            }
            else{
                x2 = midx2;
            }
        }
        return findMax(positions,(x1 + x2) / 2);
    }
};