1787번: 문자열의 주기 예측 - KMP, DP 문자열이 주어질 때 이 문자열의 모든 접두사에 대하여 추정할 수 있는 주기 중 가장 긴 것의 길이의 합을 출력하는 문제이다.KMP에서 다뤘던 광고문제나 Slot Machines문제에서 비슷한 유형을 다뤄본 적이 있다.문자열에서 주기를 구하는 방법은 S - pi[S-1]로 계산하였다.그러나 이 때의 답은 S-pi[S-1]값이 작을 때였고, 우리가 구해야할 답은 S-pi[S-1]의 값이 클 때가 되어야한다.즉 pi는 접미사도 되고 접두사도 되는 최대 길이이기에 최소 길이를 구하여야 한다는 것을 알 수 있다. ababa의 pi[S-1]은 3이다. S[:3], S[2:]이 모두 aba로 같기 때문이라는 것을 알 수 있다.이 때 aba의 pi값은 1이 되는데,S[..
1351번: 무한 수열 - DP N, P, Q가 주어질 때,A[0] = 1A[i] = A[i/P] + A[i/Q]인 점화식을 만족하는 A[N]을 구하는 문제이다. 이와 같이 간단한 점화식은 중복되는 부분문제를 저장하는 DP기법을 사용하려고 접근하지만N이 최대 10^12이기에 부분문제를 저장하는 배열을 선언할 수 없다.그러나 점화식을 자세히 보면 i가 계속 P, Q로 나누어지는데P와 Q가 최소값인 2일 때에도 2^40 >= 10^12이기에 각각 40보다 많은 항을 보지 않는 것을 알 수 있다.이에 부분문제를 담는 배열을 지수에 대한 값을 인자로 두어dp[41][41]와 같이 표현한 뒤 점화식을 세워 문제를 풀 수 있다. 또다른 방법으로는 적은 값만 참조하기에 map을 이용하여value값이 0이라면 값을 업..
DP
DP(Dynamic Programming)는 동적계획법이라고도 불리며중복되는 부분문제를 저장하는 기법입니다.문제의 답을 구하는 방법이 점화식을 이용하여 이전의 값들이 반복적으로 쓰이는 문제일 경우기저사례, 점화식을 기반으로 반복적으로 쓰이는 값들을 저장하면서 코드를 작성합니다.푸는 방법은 크게 재귀적 동적 계획법, 반복적 동적 계획법이 있으며재귀적 동적 계획법은 메모이제이션 기법을 사용하여 점화식을 그대로 코드로 옮기기에 직관적이다는 장점,반복적 동적 계획법은 슬라이딩 윈도우라는 기법을 이용하여 공간복잡도를 줄일 수 있다는 장점이 있습니다.DP를 응용한 문제 중 어떠한 방법을 거쳐서 이러한 최적화 답을 구하였는지,조건에 맞는 k번째 답을 계산하고 싶을 경우에도 작성했던 DP의 함수를 조금만 변형하여 구할..