2352 (1) 썸네일형 리스트형 [백준] 2352 반도체 설계 (JAVA) 풀이 LIS문제를 더풀어보고 DP문제를 더 풀어보자고 생각을해 문제들을 찾아보다가 이문제를 발견하였고 처음보았을때는 LIS를 그냥 적용하면 될것 같아 쉽네~ 이러고 했는데 시간초과까지는 아니지만 너무 오래 걸려서 풀렸다. 그래서 다른 방법이 있나 하고 찾아 보았고 해답은 바이너리 서치와 LIS 를 섞어서 푸는 것이였다. 기존의 LIS방식은 시간복잡도가 O(N*N)이였는데 이번에 풀은 방식의 시간복잡도는 O(NlogN)이다. 전체적인 큰틀은 다음과 같다. 1. 배열탐색하면서 가장큰수를 계속 뒤에 이어붙인다 2. 중간에 끼어들수 있는수는 이분탐색을 이용해, 적절한 위치에 있던 수와 교체한다. 3. 배열을 탐색하면서 맨앞요소보다 작은 요소가 새익면 맨앞요소를 교체한다. 처음에는 두번째와 세번째가 이해가 잘 되.. 이전 1 다음
