코딩/컨닝페이퍼 (5) 썸네일형 리스트형 문자열의 Suffix Array와 LCP 연산 알고리즘 http://deque.tistory.com/82 #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; const int MAX = 1000000; int sa[MAX], temp[MAX], pos[MAX], N, delta, lcp[MAX]; char S[MAX]; //pos[x] : S[x:-1]의 그룹 번호 //sa[x] : suffix들을 정렬했을때, x번째 suffix의 index //temp[x] : suffix들을 정렬했을때, x번째 suffix의 그룹번호 //delta : delta*2의 자릿수만 비교할 것이다 bool cmp(int i, int j) { //pos[i]와 pos[j]를 delta 자릿.. KMP 알고리즘 http://mygumi.tistory.com/61http://bowbowbow.tistory.com/6 text = input() pattern = input() pi = [0 for i in range(0, len(pattern))] result = list() count = 0 j=0 for i in range(1,len(pattern)): while(j > 0 and pattern[i] != pattern[j]): j = pi[j - 1] if(pattern[i] == pattern[j]): j+=1 pi[i] = j j = 0; patternLength = len(pattern) textLength = len(text) for i in range(0, textLength): while(j > 0.. 벨만 포드 알고리즘 모든 간선을 탐색하면서 A->B 보다 A->V[i]->B가 더 빠를때 갱신.한편 dist[A]가 INT_MAX일 경우 계산해봤자 어차피 false일테니까 컨티뉴.위의 계산을 V-1번 반복하여 최적화된 답을 찾음.한편 마지막 V번 반복을 하였을 때 만약 값이 갱신되는 Vertex가 있다면 음수 사이클이 있다는 것을 의미한다. template class triple { public: FIRST first; SECOND second; THIRD third; triple(FIRST a, SECOND b, THIRD c) { first = a; second = b; third = c; } }; bool BellmanFord(vector &dist, vector &edge, int V, int E, int Star.. 다익스트라 알고리즘 #dist배열을 INT_MAX로 초기화한다우선순위 큐를 하나 선언한다.우선순위 큐에 시작하는 노드와 거리(0)쌍을 push한다.우선순위 큐가 빌때까지 다음을 반복한다.##우선순위 큐에서 거리가 최소인 노드(now)와 거리(cost)를 뽑는다.기존의 now까지 가는 거리보다 방금 큐에서 뽑은 거리가 더 멀면 무시하고 컨티뉴(dist[now] < cost : continue)now와 연결된 모든 노드에 대해 다음을 반복한다.###(now까지의 거리 + now에서 다음노드까지의 거리)보다 dist[다음노드]가 더 짧다면 갱신해줘야 하는 노드이다.따라서 dist[다음노드]를 갱신해주고, 우선순위 큐에 (dist[다음노드], 다음노드)를 push해준다.###### 주의할점은 두가지 1. 우선순위 큐의 기본 정렬은.. 위상정렬 알고리즘 #처음엔 indegree가 0인 노드를 indegree[N]을 순회하면서 찾는다.그 후 위상정렬 큐(topoloQ)가 빌때까지 무한루프를 수행. ##위상정렬 큐의 머리에 있는 노드를 뽑고, 그 노드와 연결된 노드들의 indegree를 1씩 줄인다.한편, 방금 뽑은 노드의 indegree도 1을 줄인다.이때 indegree가 0이 되는 노드가 있다면 바로 위상정렬 큐에 넣는다.이렇게 함으로써 indegree가 0인 노드를 찾기 위해 N번의 루프를 수행하는것을 막는다.### 추가로, 방향그래프에서 모든 노드를 탐색하지 않았는데 큐가 비어있다면 그 그래프는 사이클이 있는 것이다. int N, M; int indegree[35002]; vector adj[35002]; int main() { queue topo.. 이전 1 다음