본문 바로가기

DP52

[algospot][JLIS] 합친 LIS 문제 : https://www.algospot.com/judge/problem/read/JLIS 배열 A, B의 인덱스(indA, indB)를 파라미터로 받는 재귀함수를 만든다. A[indA], B[indB] 는 증가 부분 수열에 반드시 포함된다고 가정한다. 따라서 A[indA], B[indB]의 최대 값보다 큰 배열 요소만이 증가 부분 수열에 추가 될 수 있다. int solve(indA, indB){ int maxNum = max(A[indA], B[indB]); for(nextInd = [indA + 1, N)){ if(maxNum < A[nextInd]) ans = max(ans, solve(nextInd, indB) + 1); } } 위 코드는 배열 A에 정답 배열에 들어갈 수 있는 다음 배열 .. 2019. 6. 7.
[algospot][WILDCARD] Wildcard 문제 : https://algospot.com/judge/problem/read/WILDCARD DP로 풀었다. dp[i][j] = pattern[i~끝] 부분문자열과 s[j~끝] 부분문자열이 같은가(같으면 1, 다르면 0, 아직 탐색 전이면 -1) 패턴문자열(pattern)과 패턴에 맞는지 확인하고자 하는 문자열(s)가 있다고 할 때 DP에 사용할 배열은 위와 같이 나타낼 수 있다. 패턴 문자열에 올 수 있는 문자는 '*', '?', 알파벳이다. 만약 알파벳이라면 pattern[i]와 s[j]가 같은지 체크하고 다르면 false를 반환, 같다면 i+1, j+1 부터 다시 탐색해간다. '?' 인 경우 s[j] 가 어떤 문자가 오던지 정답이 가능하므로 i+1, j+1 부터 다시 탐색해나간다. '*' 인 경.. 2019. 6. 3.
[leetcode][746] Min Cost Climbing Stairs 문제 : https://leetcode.com/problems/min-cost-climbing-stairs/ 기본 dp 문제.i 번째 계단으로 갈 수 있는 계단은 i-1, i-2번째 계단이다.따라서 i번째 계단으로 갈 수 있는 최소 비용은 (i-1번째까지 가는 최소 비용 + i번째 계단을 밟는 비용)과 (i-2번째까지 가는 최소 비용 + i번째 계단을 밟는 비용) 중 작은 비용이다.따라서 점화식은 아래와 같다.d[i] = min(d[i-1], d[i-2]); (d[i] = i번째 비용까지 가는데 드는 최소 비용) 시간복잡도는 O(N). 소스코드 : https://gist.github.com/fpdjsns/58c995f1439d437a2eed60bb517cb882 2018. 11. 11.
[leetcode][62] Unique Paths 문제 : https://leetcode.com/problems/unique-paths/ 학창시절 때 배웠던 것을 떠올려본다. 3*4 그리드가 있다고 하면 일단 가장 위에 행과 가장 왼쪽 행은 1로 갱신한다. 이 부분들은 갈 수 있는 횟수가 전부 1이다. (오른쪽으로만 가거나 아래로만 가거나) 남은 그리드 부분은 왼쪽+위가 갈 수 있는 경우의 수가 된다. (위에서 내려오거나, 왼쪽에서 오른쪽으로 오거나) 이렇게 왼쪽 위에서부터 오른쪽 아래 방향으로 차례대로 모든 그리드를 채웠을 때 가장 오른쪽 아래에 있는 수(10)가 정답이 된다. 시간복잡도는 O(NM). 소스코드 C++ : https://gist.github.com/fpdjsns/7640cc2431977f51ce86007374ddf8e5 pythone .. 2018. 10. 29.