LCS (2) 썸네일형 리스트형 [문제해결기법] 11. 동적 계획법 동적 계획법 (DP) 최적화 문제, 분할 정복 한 문제를 똑같은 문제이면서 크기만 작은 것으로 바꿀 수 있을지 생각해본다. 금화 모으기 문제 D[i][j] : (i, j)까지 오는 동안 모을 수 있는 금화의 최댓값 D[i][j] = max( D[i-1],[j] , D[i][j-1] ) + map[i][j]; 최대 공백 정사각형 (흰색으로만 이루어진 가장 큰 정사각형) mm 크기의 정사각형이 있다면, 4개의 (m-1)(m-1) 크기 정사각형이 있어야 한다는 점에서 착안한다. D[x][y]는 (x,y)가 가장 오른쪽 아래 꼭지점인 정사각형의 최대 크기라고 가정한다. (x,y)가 검은색이면, D[x][y] = 0 흰색이면, x==1 && y==1 : D[x][y] = 1 else : D[x][y] = min(.. [C++/BOJ] 9251 : LCS (DP) https://www.acmicpc.net/problem/9251 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다. 백준 골드5티어. 처음에 시간제한이 0.1초길래 완탐으로는 못풀겠구나 했는데 역시 틀림 그래서 얌전히 DP로 해결했습니다.. 점화식을 떠올리기 힘들었는데, 한 블로거의 잘 정리된 글을 읽고 이차원.. 이전 1 다음