Table of Contents 개요 O(n^2) 풀이 더 알아보기 : O(n log n) 풀이 1 더 알아보기 : O(n log n) 풀이 2 1. 개요 최장 증가 부분 수열 (longest increasing subsequence) 문제는 유명한 동적 계획법 활용 예시입니다. LIS 문제는 말 그대로 수열이 주어졌을 때, 수가 점점 증가하는 가장 긴 부분 수열을 찾는 문제입니다. 정확한 문제는 아래의 링크를 통해 확인할 수 있습니다. [BOJ 11053] 가장 긴 증가하는 부분 수열 2. O(n^2) 풀이 dp [ i ] = A [ i ] 를 마지막 원소로 하는 증가 부분 수열의 최장 길이 간단하게 위와 같이 dp 문제를 정의하면 해결할 수 있습니다. 이 dp의 정의는 A[1] ~ A[i] 수열의 L..
Table of Contents 개요 DP 기본 예제 – 피보나치 수열 DP 구현하기 DP 문제 - 1 DP로 문제에 접근하기 DP 문제 - 2 유명한 DP 응용 주의할 점 DP 문제 - 3 1. 개요 동적 계획법, 영어로 Dynamic programming 다이나믹 프로그래밍, 줄여서 DP. 문제를 여러 개의 하위 문제들로 나누어 먼저 처리한 후, 그 하위 문제들의 답을 이용해 원래 문제를 처리하는 방법을 뜻합니다. 하위 문제를 처리하는 과정에서 같은 문제를 여러 번 처리하게 되는데, 한 번 수행한 문제들의 답을 저장해 놓으면 그 다음부터는 답을 바로 알아낼 수 있어 속도를 비약적으로 빨라지게 할 수 있습니다. 2. DP 기본 예제 – 피보나치 수열 피보나치 수열을 DP로 구하는 과정을 통해서 DP에 ..
DP[i] = 1 ~ i 병사들로 얻을 수 있는 조정된 전투력의 최댓값 위와 같은 간단한 DP를 구하면 된다. SUM[i] = X[1]+X[2]+...+X[i] 로 미리 sum 배열을 구해 놓으면 SUM[i] - SUM[j] = X[j+1]+X[j+2]+...+X[i] 가 성립하므로 아래와 같이 DP[i]를 구할 수 있다. 이 식을 전개하여 컨벡스 헐 트릭을 사용할 수 있게 i 와 관련된 함수( = SUM[i]가 곱해진 항) , j와 관련된 함수, 상수를 나누면 위와 같이 된다. 이제 A[i] = SUM[i], B[j] = -2*a*sum[j]+b, C[j] = DP[j]-b*sum[j]+a*sum[j]^2, D[i] = a*sum[i]^2+c 로 대응시킬 수 있다. min 함수가 아닌 max 함수이지만..
m^2 = m+m+m+...+m (총 m개) 이므로 m 개의 O가 연속되어 있을 때, 한번에 m^2을 획득한 게 아니라 m 번의 클릭(O) 이 각각 m 점을 획득한 것이라고 바꿔 생각할 수 있다. 이러면, 정답 = ∑ ( i 번째 클릭이 얻은 점수의 기댓값) = ∑ ( i 번째 클릭이 속한 O 그룹의 길이의 기댓값) 이 된다. 이제 쉽게 DP를 설정해보면, DP[i] = i 번째가 클릭이 속한 O 그룹의 길이의 기댓값. 그런데 이 DP[i] 를 구하려고 해보면 (i-1) 번째 클릭의 성공률이 DP[i] 에 영항을 끼치고, i 번째 클릭의 성공률이 DP[i-1]에 영향을 끼쳐서 결국 상호 간에 영향을 끼치기 때문에 까다로워짐을 알 수 있다. DP[i] 의 부분 문제로 DP[i-1]을 설정해놓고, DP[i-..
일단 입력으로 트리가 주어지고 있으므로 가장 흔하고 쉽게 생각할 수 있는 DP설정을 사용하면 DP( i ) = i 를 root로 하는 subtree 의 최소 얼리 어답터 수,하위문제 = DP( i 의 자식들 ) 이와 같이 설정해 볼 수 있다. 이 상태에서 하위 문제들로 DP(i) 를 구하려고 해보면 일단, i가 얼리어답터인지 여부에 따라 경우가 달라지므로 i 가 얼리어답터인 경우와 아닌 경우의 답을 구한 후 종합해야 문제가 쉬워짐을 알 수 있다. 우선 i가 얼리어답터인 경우엔 자식 노드들에 대한 아무런 제약이 걸리지 않으므로 ‘ DP(i 의 자식들 )의 총합 + 1 ‘ 임을 쉽게 알 수 있다. 이제 문제는 i가 얼리어답터가 아닌 경우인데, 이 때는 문제 조건에 따라 자식 노드가 무조건 얼리어답터 여야만 ..
문제의 특성을 파악하기 위해 우선, 어떤 위치 i를 저장했다고 가정하자. 그러면 i를 기준으로 왼쪽과 오른쪽이 갈리게 된다. 왼쪽인 0 ~ i 번지의 오차를 계산할 때를 생각해 보면, 이미 i 가 저장되어 있기 때문에 i+1 ~ n-1 번지 중 어떤 위치가 저장되었는지는 상관이 없어진다. 다시 말해서 0 ~ i 번지와 i ~ n-1 번지 사이의 연결 고리는 ‘저장한 집이 몇 개인가’ 가 유일하게 된다. 이 것만 확정되면 나머지 요소들은 모두 독립적으로 작용한다. 그리고 이 정도 정보는 충분히 저장할 수 있기 때문에 다음과 같이 DP 문제를 정의해 볼 수 있다. DP( i, j ) = 0 ~ i 번지의 집 중에 j 개를 저장했을 때 오차의 합의 최솟값( 단, 0 과 i 번지는 반드시 저장 해야 함. ) 이..