목록백준 12015 (1)

Devlog_by_0giru

[boj] 가장 긴 증가하는 부분 수열2_12015

가장 긴 증가하는 부분 수열1 에 이은 시리즈 문제다. 처음에는 11053번처럼 dp로 접근하려고 했지만 입력 데이터의 수가 너무 많아 dp로 해결할 수 없는 문제임을 깨달았다. dp를 이용하려면 전체 리스트(배열)에서 i번째와 i-1번째까지의 데이터를 중복해서 탐색해 O(N^2)의 시간 복잡도를 가지게 된다. 11053번의 경우 입력 데이터의 개수가 1000개 까지라 시간 초과에 걸리지 않지만 12015번의 경우 입력 데이터가 훨씬 많아 O(N^2)의 시간복잡도를 가진 알고리즘을 사용할 경우 시간 초과가 발생한다. 따라서 O(NlogN)의 시간 복잡도로 해결해야 하고 이를 위해 i-1번째까지의 데이터를 이진탐색을 통해 시간을 단축해줘야 했다. 사실 위 부분까지는 이해가 되는 부분이나, 아래 부터 나오게..
[PS] 2021. 3. 8. 08:50
이전 Prev 1 Next 다음