가장 긴 증가하는 부분 수열 2는 이분법을 사용하여(솔직히 이 문제의 핵심은 이분법이 아닌 것 같습니다. 이분법만 아는 것으로는 조금 부족할 수도 있을 것 같습니다.;) 풀 수 있는 문제입니다. 원래 문제인 가장 긴 증가하는 부분 수열(LIS)문제는 동적계획법(완전탐색 + 메모이제이션)으로 해결할 수 있으나 N의 개수가 100만이 되어서 더 빠른 방식의 알고리즘을 고안해야 합니다. 문제를 곰곰히 생각해보면 다음과 같은 통찰을 얻을 수 있습니다. 수열의 어떠한 위치를 탐색하고 있다고 가정하면 우리는 그 이전의 수들로만 구성된 수열들을 상상할 수 있습니다. 어떤 수열은 1개의 숫자로만 이루어질 수도 있고, 어떤 수열을 2개, 3개 혹은 그 이상의 숫자로 만들어질 수 있을 것입니다. 우리가 구하고자 하는 것은..