소시지

SCC(Strongly Connected Component)란? 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include #include #include #include #include using namespace std;int n, out_len;bool check[10001], check2[10001];vector r[10001], r2[10001];stack S, S2;set out[10001]; void dfs(int x) { check[x] = true; for (auto it = r[x].begin(); it != r[x].end(); it++) if (che..

KMP란?문자열 a와 문자열 b가 있을 때 문자열 a에 문자열 b가 속해있는지 확인할 수 있고, 몇 개 있는지 확인하도록 도와주는 알고리즘입니다.MS의 워드나 브라우져의 찾기 기능을 생각하시면 되겠습니다. 문자열 a에 문자열 b가 속해있는지 알고싶은지 확인하는 간단한 방법은 a의 배열 첫 번째부터 b의 문자열의 길이만큼 일치하나 확인하는 것일 겁니다. 이 경우, 최악의 경우 시간 복잡도는 O(nm)일 것입니다. 그러나, kmp를 사용하면 시간 복잡도를 O(n+m)으로 줄일 수 있습니다. 문자열 a를 "12341234.....", 문자열 b를 "12341235"라 가정해 봅시다.일단 아까 말했던 간단한 방법대로 하면문자열 a의 "1234123"와 문자열 "1234123"이 같은 것을 확인할 수 있을 것입니..

이분 탐색을 간단히 배열에서 숫자를 찾는 정도로만 알고있는 사람들이 많을 것입니다.그러나 이분 탐색을 응용하면 최댓값을 구하는 문제나 최솟값을 구하는 문제를 거의다 풀 수 있습니다. 다음 소스와 문제를 보면서 이해하기를 바랍니다. 123456789101112131415161718192021bool Can(long long x, long long num) { if (x >= M) return false; return (1 + x)*x / 2

upper_bound와 lower_bound함수는 이진 탐색을 하는 함수입니다.자세히 말하면, upper_bound와 lower_bound는 만약 어떤 숫자가 정렬되어 있는 배열에 들어갈 때 그 숫자를 넣어도 정렬이 되어있는 상태가 되도록 하는 위치를 알려주는 함수이죠. 다음과 같은 정렬되어 있는 배열이 있다고 생각해보세요.이 배열에 숫자 7을 넣는데 넣어도 정렬이 되고 싶다면 어디에 넣어야 할까요? 6의 다음에 오도록 하여야 하므로 이전에 9가 있던 위치를 가르킬 것입니다. 이런 상황에서는 upper_bound(), lower_bound() 모두 9가 있는 자리의 포인터를 가르킵니다. 그러면, upper_bound()와 lower_bound()의 차이점은 무엇일까요?이 둘은 배열에 같은 숫자가 여럿일 ..

BFS는 너비우선탐색을 말합니다.이와 반대되는 개념으로는 DFS, 깊이우선탐색이 있습니다. BFS는 위의 그림과 같은 그래프가 있고, 시작 정점이 1번 정점이면1->2->3->4->5->6->7 순서대로 방문합니다. 이를 구현하기위해 자료구조인 Queue를 많이 사용합니다.또한 위의 그림과 달리 그래프나 트리구조가 아니고 2차원 배열에서 BFS를 사용할 경우방향데이터(dy[4]={0,0,1,-1}, dx[4]={1,-1,0,0}) 를 만들어 탐색할 수 있습니다. 다음 소스는 BFS의 소스입니다. 12345678910111213141516int bfs() { int d[101][101], dy[4] = { 0,0,1,-1 }, dx[4] = { 1,-1,0,0 }, yy, xx, ty, tx; bool c..