가장 긴 증가하는 부분 수열

백준 11053 풀이 (가장 긴 증가하는 부분 수열, LIS)

요것은 머랄까 LIS인데, 나도 처음 들어봤다. 애당초 알고리즘 수업도 들어본 기억이 없기 때문에 무엇을 듣던지 생소하다. 그래서 맘편히 구글링을 해보았다. LIS는 최장 증가 수열을 의미한다. Longest increasing Subsequence 라고 하는데 A = {10, 20, 10, 30, 20, 50} 가 존재하면 10, 20, 30, 50 이 가장 긴 수열로 존재한다. 그래서 이렇게 긴 수열이 무엇인지 찾아내는 알고리즘이다. dp로 푸는 방법과 다른 방법도 존재한다고 하는데 나는 다이나믹 프로그래밍인 DP를 연습하고 있기 때문에 DP로 풀어보았다. 10, 20, 10, 30, 20, 50 이 존재한다면 각 항목별로 dp를 저장해서 누적시키는 느낌으로 풀어야 한다고 생각했다. number 10..