Problem Solving/알고리즘9 Prefix function, Knuth-Morris-Pratt algorithm Prefix function definition $$ \pi[i] = \max_{k=0 ... i} k: s[0 ... k - 1] = s[i - (k - 1) ... i) \text{ for string }s$$ Implementation vector prefix_function(string s) { int n = (int)s.length(); vector pi(n); for (int i = 1; i 0 && s[i] != s[j]) { j = pi[j - 1]; } if (s[i] == s[j]) { j++; } pi[i] = j; } return pi; } Application 1. Search for a substring .. 2022. 1. 17. Following materials 1. 프로그래밍 대회에서 배우는 알고리즘 문제해결전략 1, 2 - 구종만 알고리즘 문제 해결 전략 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략, 구종만 지음, 인사이트, ISBN 978-89-6626-054-6 새 소식 책 소개 은 새로운 알고리즘 책입니다. 종이에 적힌 의사코드 book.algospot.com 2. Algorithms for Competitive Programming Main Page - Algorithms for Competitive Programming cp-algorithms.com 2022. 1. 17. 동적 계획법 Dynamic Programming (DP) Divde & Conquer 과 같이 문제를 작은 부분문제들로 쪼개는 과정을 거친다. 하지만 DP는 memoization을 사용한다는 차이점이 있다. 여기서 memoization이란 한 번 계산한 값을 저장해 두었다 재활용하는 기법을 의미한다. 종합하자면, Divide & Conquer은 부분 문제들이 서로 겹치지 않을 때 사용하기 좋다. 만약 동일한 부분 문제들이 계산 과정에서 여러 번 등장한다면, 중복 계산을 피하는 DP를 사용하는 것이 좋다. 이항 계수 (binomial coefficient) 계산을 예로 들어보자. $$ \binom{4}{2} = \binom{3}{1} + \binom{3}{2} = (\binom{2}{0} + \binom{2}{1}) .. 2022. 1. 7. 분할 정복 Divide & Conquer 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산 일반적인 재귀 호출은 문제를 한 조각과 나머지 전체로 나누는 반면, 분할 정복은 거의 같은 크기의 부분 문제로 나눔. 세 가지의 구성 요소 문제를 더 작은 문제로 분할하는 과정 (Divide) 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정 (Merge) 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제 (Base case) 가장 대표격이라 할 수 있는 문제는 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사.. 2022. 1. 7. 이전 1 2 3 다음
