[DP] LIS (최장 공통 부분 수열)
LIS (Longest Increasing Subsequence) 수열 안에 있는 증가 하는 부분 수열 중 가장 긴 것을 찾는 문제 Idea1 완전탐색입니다. 1) 수열을 처음부터 하나씩 증가하면서 (a[]의 모든 원소마다), 각 경우마다는 첫번째 수 a[i]를 정하고, 인덱스를 1씩 늘려가면서(a[i+1] ... ) 첫번째 수보다 큰 숫자들을 컨테이너(sub_a[])에 담습니다. 2) sub_a를 1)번 과정을 되풀이하는 재귀함수를 구현합니다. a[] = {3, 2, 1, 7, 5, 4, 2, 6} 첫번째 원소 3을 기준으로, 그 다음 가능한 7 5 4 6 중 다시 재귀적으로 LIS를 뽑습니다. #include #include using namespace std; /* LIS의 길이를 반환 */ int..
2019. 9. 6.
9251 LCS
LCS 또한 교재에서 볼 수 있는 DP의 전형적인 문제이다. 길이가 각각 i, j인 문자열 x, y가 있다고 해보자. LCS(i, j) 는 문자열 x, y의 최장 공통 부분 수열(LCS)이라고 할 때, 다음과 같이 점화식을 세울 수 있다. LCS(i, j) = LCS(i-1, j-1) + 1 if x[i] == y[j] max( LCS(i-1, j), LCS(i, j-1) ) otherwise 이렇게 만들어놓고, i와 j에 따른 dynamic programming을 구현하기 위하여 d[i][j]를 만든다. 그리고 이 행렬을 잘 채워나가다가, 맨 마지막 오른쪽 부분 즉, d[i][j]가 우리가 원하는 LSC 값이다. #include #include #include using namespace std; in..
2019. 6. 9.
