LOG
- 드디어 못 풀어내던 LIS 알고리즘을 어느 정도 감을 잡은 것 같다. 바이토닉 수열 문제는 내 힘으로 못 풀었지만.. 그것보다 쉬운 전깃줄 문제는 5분 만에 풀어냈다! 얼마나 기억을 유지할 수 있을지... 이분탐색으로 LIS 푸는 거 이해했다고 생각했는데 또 그렇지도 않은 것 같아서 슬픔 ㅠ
배운 것
- dp로 LIS 풀기
dp = [1 for _ in range(n)]
for i in range(n):
for j in range(i):
if arr[i] > arr[j]:
dp[i] = max(dp[i], dp[j] + 1)i번째보다 작은 값들을 돌면서 현재 i 값보다 작은 경우 현재 dp 값, 이전 dp값 + 1 중 최댓값을 확인한 후 업데이트한다.