다이나믹프로그래밍
-
[백준] 14002번 가장 긴 증가하는 부분 수열 4 (by Python)Programming/Algorithm 2021. 2. 21. 21:52
문제 이 문제의 원형인 11053번에서 꽤나 애를 먹어서 어떻게 꼬아놨을까 조금 긴장했지만 생각외로 쉽게 풀렸던 문제. 경로를 기억해두는 장치만 해두면 되는 문제였다. 풀이 n = int(input()) arr = list(map(int, input().split())) dp = [[1, i] for i in range(n)] for i in range(n): for j in range(i): if arr[i] > arr[j] and dp[i][0] < (dp[j][0] + 1): dp[i] = [dp[j][0] + 1, j] temp = dp.index(max(dp)) route = [temp] while dp[temp][1] != temp: route.insert(0, dp[temp][1]) temp..
-
[백준] 11053번 가장 긴 증가하는 부분 수열 (by Python)Programming/Algorithm 2021. 2. 21. 21:22
문제 내가 생각했던 것은 bottom-up 방식으로 for loop으로 0번째부터 i번째까지의 LIS(Longest Increasing Subsequence) 값을 저장해둔다는 것. 그렇지만 점화식을 세우는 것이 쉽지 않았는데, 이전 원소들의 정보를 충분히 활용할 수 없었기 때문이었다. 그래서 이코테 책을 보다가 알게 된 점화식은 내 기존 생각에 한 가지를 덧붙인 것이었는데, i번째 원소를 사용한다는 제약조건을 추가하는 것이다. 그렇게 마지막 원소까지 반복문을 수행한 후 max값을 찾으면 LIS의 길이를 구할 수 있다. 점화식을 생각할 때 정보가 충분하지 않은 것 같다면 정답으로 이어질 수 있으면서 고려할 범위를 좁혀줄 수 있는 제약조건을 주라는 것이 내가 이 문제에서 얻은 팁이다. 풀이 n = int(..