최선을다하는

KMP 알고리즘은 한 문자열(s)에 다른 문자열(p)이 몇번 나타나는지를 확인 할 수 있는 알고리즘이다. 문자열 p 의 앞과 뒤가 얼마나 같은지 미리 확인한 다음 두 문자열 s 와 p를 확인하다가 맞지 않는 부분이 나오면 한칸 옮기는 것이 아니라 겹치는 부분을 제외하고 넘어 갈 수 있다. #include #include #include using namespace std; vector getPi(string p) { int m = p.size(); int j = 0; vector pi(m, 0); for (int i = 1; i 0 && p[i] != p[j]) j = pi[j - 1]; if (p[i] == p[j]) pi[i] = ++j; } return pi..

위상 정렬은 선행되어야 하는 조건들이 주어지고 그 수들의 순서를 구해야 할 때 사용할 수 있다. 위상 정렬을 활용하기 위해서는 진입 차수와 인접한 노드를 알아야 한다. 진입 차수란 해당 노드가 실행되기 위해서 선행되어야 하는 노드의 개수를 뜻한다. 진입차수가 주어지면 진입 차수가 0 인 노드들부터 큐에 넣는다. 그다음 큐에서 원소 하나씩 확인하게 되는데 큐에서 pop 된 순서가 최종 순서가 되며 pop 이 되었다면 인접한 노드들의 진입 차수를 1 감소시킨다. 이때 인접한 노드의 진입 차수가 0이 되었다면 큐에 추가하여 자신의 순서가 확정되길 기다린다. 아래의 코드는 백준 2252번 줄세우기의 코드이다 #include #include #include using namespace std; int n,m, i..

LCA 알고리즘은 트리 혹은 DAG에서 사용하는 알고리즘으로 최소 공통 조상을 구하는 알고리즘이다. 1. 각 트리의 깊이를 구한다. 루트 노드의 깊이는 0이다. 깊이를 구하면서 각 노드의 부모 노드도 저장해둔다. - BFS 와 DFS 등으로 구현할 수 있다. 2. 그 다음 각 노드의 2^K 승만큼의 부모 노드를 저장해둔다. - 모든 부모 노드를 저장할 필요가 없는 이유는 이진수가 모든 수를 표현할 수 있듯 3번째 조상을 구하려면 1번째 조상의 2번째 조상을 구하면 되기 때문이다. 3. 공통 조상을 구하는 두 노드 u v 중 더 깊은 노드를 같은 높이의 부모노드로 변경한다. 이는 비트 연산자로 구현할 수 있다. 그다음 두 노드들의 가장 윗 노드들부터 내려오면서 확인한다. 이때 두 숫자가 달라지는 시점이 공..

- LIS (Longest Increasing Subsequence) 1~N 번까지 순서대로 i번째 dp값을 최신화해준다. j는 i보다 작은 수 즉 배열의 앞에 있는 숫자라고 할 때 i번째 숫자가 j번째보다 크고 dp [i]가 dp [j] + 1보다 작다면 dp [i]의 값을 dp [j]+1로 최신화해준다. int arr[101]; int dp[101] ; int N,ans = 0; void LIS() { for (int i = 0; i arr[j]) { if (dp[i] < dp[j] + 1) dp[i] = dp[j] + 1; } } ans = max(ans, dp[i]); } } 위의 ..