목록2025/07/11 (1)
Elevation
solved.ac Class 4 all solve
4단계를 다 풀었다. 난이도는 실버 상위~골드 하위 수준이고 dp, 그래프 탐색, 백트래킹, 구현 위주의 문제가 많았다. 한문제씩 풀 때는 그렇게 오랜 시간이 걸리지 않았는데, 확실히 정해진 48문제를 다 푸는 것은 마냥 쉽지는 않은 것 같다. 푼 문제 수가 늘어갈수록 남아있는 문제들은 더 까다롭게 다가오는 느낌이었다. 아이디어가 떠오르지 않아서 자력으로 푸는 데 꽤 많은 시도를 한 문제들도 있었다. 아무튼 이번에 새로 배웠거나 헷갈리는 개념(문제)들 위주로 간단히 정리해 본다. LIS(Longest Increasing Subsequence, 가장 긴 증가하는 부분 수열)LIS 자체는 dp로 $O(N^2)$만에 해결 가능하다. 수열 $A$에 대해 $dp[i]$=($A[i]$까지의 LIS)라고 생각하면,..
ps/문제풀이 및 후기
2025. 7. 11. 17:26