LIS를 lower_bound로 해결하는 가장 효율적인 알고리즘이 있음에도 불구하고, 이 알고리즘을 쓰게 된 이유를 알지 못하는 사람들이 많다. 그저 효율적이라는 이유만으로 이 알고리즘을 사용한다면, 그 배경을 알지 못해 응용도 할 수 없을 뿐더러 사용할 때마다 가슴이 답답함을 느끼게 될 것이다.. (나는 이런 걸 왜 생각하지 못할까.. .) 그래서 이 알고리즘이 등장하게 된 배경에 대해서 설명해보려고 한다. (답답해서 공부했다.) 먼저 동적 프로그래밍으로 알고리즘을 설계하는 방법에 대한 것이다. * 동적 프로그래밍 : 앞으로 푸는 문제에 대해 이전의 데이터를 활용할 수 있다면 cache에 저장하여 사용한다. 푸는 방법: https://ebang.tistory.com/89 동적 프로그래밍을 짜기 위해 수..