devbelly

문제 https://www.acmicpc.net/problem/3033 알고리즘 라빈 카프 풀이 https://www.acmicpc.net/problem/1701 길이 제한을 제외하고, 위 문제와 동일합니다. 우리는 1701번 문제를 $O(N^2)$에 해결했지만, 이 문제는 길이 제한이 20만 이므로 다른 전략을 택하도록 합시다. 만약 길이$m$인 문자열이 두 번 이상 등장한다고 해봅시다. 그러면 $m$보다 작은 $n$은 두 번 이상 등장함을 알 수 있을까요? 네. 이는 너무나도 확실합니다. 예를 들어 문자열 $aabaa$에서 부분 문자열 $aa$는 두번 등장함을 알 수 있고, 이보다 짧은$a$는 $aa$가 등장한 인덱스를 제외하고도 더 등장할 수가 있죠. 그렇다면 길이$m$보다 긴 길이$k$는 몇 번 ..

문제 https://www.acmicpc.net/problem/2300 알고리즘 동적 계획법 풀이 기지국들을 하나의 통신 범위로 묶을 때, $x$ 좌표를 정렬한 후 묶어야 함을 알 수 있습니다. 건물$i$와 건물$j$를 하나의 통신 범위 안에 넣을 때, 사용하는 길이는 두 건물의 $x$좌표 차와 그사이에 있는 빌딩들의 $y$좌표*2 중 최댓값이 되어야 합니다. $cache[i]$= 현재 건물 $i$부터 세워나갈 때, 필요로 하는 최소 길이 $solve()$ 함수는 최대 $N$번 호출되고 함수 내부에서 $for$은 최대 $N$번 반복하므로 시간 복잡도는 $O(N^2)$입니다. 코드 #include #define rep(i,n) for(int i=0;i> x >> y; vt.emplace_back(x, ab..

문제 https://www.acmicpc.net/problem/10710 알고리즘 동적 계획법 풀이 날씨가 궂으면 쉬고, 좋으면 현재 도시에서 다음 도시로 가는 그리디한 해는 금방 반례가 나오게 됩니다. 현재 날씨가 좋지 않더라도 나중에 거리가 짧은 도시 사이를 좋은 날씨로 가게 되는 케이스가 있다면 걸리기 때문입니다. 즉 모든 상황을 고려할 수 있는 동적 계획법으로 해결하도록 합시다. $cache[i][j]$= $i$날에 $j$ 도시에 위치할 때, 얻게 되는 최소 피로도 ++ $cache$ 값을 갱신할 때, 우리가 필요로 하는 정보는 직전 날에 대한 정보뿐 입니다. 2일 전, 3일 전 정보가 필요가 없습니다. 슬라이딩 윈도우를 통하여 $cache[2][1000]$로 메모리를 최적화할 수 있습니다. 코드..

문제 https://www.acmicpc.net/problem/1796 알고리즘 Dynamic programming 해설 $cache[i][j]$ = $i$번째 알파벳부터 해결해야 하고, 현재$idx$위치가 $j$ 일 때 필요한 최소 이동 횟수 현재 커서 위치에서 다음 단계의 알파벳으로 가기 위해선 현재 해결해야하는 알파벳의 $lo$ 위치와 $hi$ 위치를 들러야 합니다. 두 위치를 들른다면, 그 사이에 있는 현재 단계의 알파벳은 모두 해결 가능함을 알 수 있습니다. $dist(a,b,c,d)$= 현재 위치 $a$에서 $c$와 $d$를 들른 후 $b$까지 가기 위해 필요한 커서 거리 $dist$함수를 통해 현재 단계에서 필요한 최소 커서 이동거리를 구할 수 있고, 다음 단계로 나아가 문자$z$까지 처리를..

문제 https://www.acmicpc.net/problem/1787 알고리즘 KMP, 동적 계획법 풀이 추정할 수 있는 문자열의 길이가 가장 길기 위해선 일치하는 prefix와 suffix가 가장 짧아야 함을 알 수 있습니다. 우리가 실패함수를 만들게 되면 일치하는 prefix와 suffix가 가장 긴 길이가 담겨 있게 됩니다. 문제에서 요구하는 것과는 정반대입니다. prefix와 suffix가 일치하는 길이가 1 이상인 가장 짧은 길이를 얻는 것은 동적 계획법을 통해 해결 가능합니다. $cache[i]$ = 문자열의 길이가 $i+1$ 일 때, 동일한 prefix와 suffix의 길이중 0을 제외한 가장 짧은 값 현재 문자열의 길이를 $k$라 할 때, 일치하는 가장 긴 길이는 $fail[k-1]$ 이..

문제 https://www.acmicpc.net/problem/16229 알고리즘 KMP, Z 풀이 실패 함수의 다양한 특징들을 사용해서 푸는 문제입니다. 이 이상 어떻게 응용되는지는 모르겠으나, 제가 느끼기론 모든 성질을 다 사용한 것 같습니다. 이 문제에서 실패 함수를 $1-BASED$로 구현하게 되면 깔끔해지는 이유를 알 수 있습니다. 실패 함수의 특징에 대한 설명은 아래 사진으로 대체하겠습니다. (설명을 자세하게 해주신 doju님 감사합니다) 이제 위 사진의 모든 정보를 이용해 접근을 해봅시다. 우리는 1번 특징을 사용해 실패 함수를 계속 반복하게 되면 주어진 문자열 $S$ 에 대해 suffix와 prefix가 동일한 모든 길이$a$를 얻게 됩니다. $a$를 안다면 당연히 2번 특징을 사용해 모든..

문제 https://www.acmicpc.net/problem/2401 알고리즘 KMP, 동적 계획법 풀이 직관적인, 나이브한 방법으로 생각을 해봅시다. 짧은 문자열들을 긴 문자열의 각 위치마다 일일이 매칭을 시도해보는 방법을 떠올릴 수 있습니다. 긴 문자열 $L$에서 짧은 문자열$I$이 시작할 수 있는 위치를 찾는데 한 개가 아닌 $N$개의 문자열에 대해서 해야 합니다. 우리는 이 방법을 최적화할 수 있는 방법을 알고 있습니다. 긴 문자열에서 짧은 문자열을 찾는 알고리즘. 즉 KMP입니다. 매칭은 빠르게 했으니 일일이 시도하는 문제는 동적 계획법을 통하여 풀 수 있습니다. 시간 복잡도는 $O(N(L+I)+NL)$입니다. 매칭한 결과를 저장할 수 있는 효율적인 방법을 생각해보도록 합시다. 처음에 저는 벡..

문제 https://www.acmicpc.net/problem/4354 알고리즘 KMP 풀이 드디어 만나게 된 $S$에서 $W$를 찾는 단순한 KMP가 아닌, 실패 함수 자체만을 사용하는 문제입니다. 실패 함수에는 여러 성질 및 특징이 있지만, 자주 만나게 되는 세 가지 큰 특징이 있습니다. 그 중 하나를 소개하겠습니다. 문자열에서 A글자의 패턴을 만들 수 있음과 문자열의 앞쪽(N-A)글자와 뒤쪽 (N-A)글자가 같음은 동치 이 문제를 풀땐 위 특징을 적극 활용하여 풀어봅시다. 주어진 문자열 $S$에 대하여 실패함수를 구했다면, 우리는 $fail[slen-1]$ 이 가장 긴 접두사, 접미사의 길이임을 알게 됩니다. 문제에서 원하는 가장 큰 $n$을 구하기 위해선 반복되는 문자열의 길이가 가장 짧아야 하므..