Longest Increment Subsequence 오늘 추가로 풀어본 알고리즘 문제는 최장 증가 수열이다. 예젠에도 백준에서 매우 유사한 문제를 풀어봤었다. DP 문제를 빠르게 푸는 방법은 정확한 의미의 점화식을 세우는 것이다. 처음 문제를 풀 때 세웠던 점화식은 i 번째 원소를 시작점로 하면서 j 번째 원소를 끝점으로 하는 최장 증가 수열의 길이라고 정의하고 풀려고 노력해 보았다. 잘못된 점화식을 세웠을 때 가장 빠르게 알 수 있는 문제가 i - 1 또는 j -1 과 현재 dp[i][j]와의 관계를 찾는 것이 불가능하거나 가능하더라도 매우 복잡해진다. 따라서 구글 검색을 통해 내가 생각한 점화식이 틀린지 확인해 보았는데, 역시나 틀린 점화식이었다. 알맞은 점화식은 dp[k], k 번째 원소를 끝으로 하는 최장 증가 수열의 길이이다. 배열 dp는 1로 .. 이전 1 다음