NeuroWhAI의 잡블로그

이 알고리즘은 우연히 알게되었다. 구현은 참으로 간단한데 이게 왜 되는지 이해가 안돼서 한참을 삽질했다. 정리할 겸 글을 적어본다. 일단 알고리즘의 목적은 유향 그래프든 연결 리스트든 그 속에 순환이 존재하는지, 존재한다면 그 시작 지점은 어딘지 찾는 것이다. 1. 먼저 시작 노드를 가리키는 포인터 2개를 준비한다. 2. 노드의 간선을 따라 포인터를 이동시킬 것인데 하나는 1칸씩, 다른 하나는 2칸씩 옮긴다. 3. 순환이 없다면 두 포인터가 만나는 일은 없겠지만 순환이 존재하면 결국 만나게 된다. 4. 이때 느린 포인터를 다시 시작 노드로 옮기고 이번엔 둘 다 1칸씩 이동시킨다. 5. 그럼 또 결국 어떤 지점에서 만나게 되는데 놀랍게도 여기가 순환이 시작되는 곳이다. 이 방법으로 순환을 찾을 수 있다는 ..

https://www.acmicpc.net/problem/6591 정답 비율이 낮아서 겁먹고 미뤘던 문제입니다. 그런데 다른 쉬웠던 이항 계수 문제랑 거의 똑같이 했는데도 패스가 나네요. 무엇?? 그냥 캐시를 사용한 동적계획법으로 풀었더니 시간, 공간 복잡도가 안습이긴 하지만 패스는 되더라고요. 이후에 검색해서 공부한 방법으로 다시 풀었더니 정석대로 패스된 것 같습니다. 동적계획법으로 풀때의 아이디어는 위키백과에서 봤던 C(n, r) = C(n, n-r)이라는 점을 이용해서 중복 계산을 피하는 것이고 r = 0, r = 1, n = r일때는 답이 명확하므로 조건문을 써줬다는 것? 캐시는 최대한 크게 할당하고 n, r이 범위에 있을때만 캐시를 검사하도록 했습니다. 2번의 메모리 초과는 적절한 캐시 크기를 ..

#include #include #include #include using namespace std; // Knuth-Morris-Pratt Algorithm // bush의 앞에서부터 needle의 최초 위치를 찾아 반환합니다. size_t kmp(string_view bush, string_view needle) { const size_t needleLen = needle.length(); const size_t bushLen = bush.length(); // string::find는 패턴 문자열이 비어있을 경우 0을 반환함. if (needleLen == 0) { return 0; } // pi[match] == needle[:match+1]의 최대 동일 접두접미사 길이 vector pi(need..