Searching Algorithm

Search Algorithm Linear Search Binary Search Two pointers

LIS(Longest Increasing Subsequence) arr = \[ 1, 4, 2, 3, 6 ] 이런 수열에서 어떻게 하면 LIS를 찾을 수 있을까? Naive 1 0부터 순서대로 조사하여, 매번 arr[i]를 포함하거나, 포함하지 않는 경로를 각각 살펴

먼저 구간 합을 구해야한다.prefix sum vs segment tree 뭐가 좋을까?업데이트 없이 조회만 하면 된다. 조회 시간이 O(1)인, prefix sum을 사용하는 것이 좋을 것이다.다음으로, 구간 합의 경계인 l 과 r을 찾아야한다.naive한 방법은 n

Naive하게 풀면 어떨까? 가능한 \[i, j]의 수열을 모두 조사하면 된다.이중 루프로 구사할 수 있을 것이다.시간 복잡도는 O(N^2)으로, 시간 내에 풀 수가 없다.그러나 잘 생각해보면, i는 0~N-1 까지 한번씩 조사하는데, j는 매 i마다 다시 조사하여 중

Naive한 방법은 모든 a, b, c, d 조합을 시도해보는 것이다.다만, 시간복잡도가 O(N^4) 이기 때문에 제한시간 내에 풀 수 없다.Naive한 풀이를 조금더 살펴보면 (0,0,\*,\*), (0,1,\*, \*) 만 살펴봐도 중복해서 c, d를 전수 조사하고

가장 긴 증가하는 부분 수열의 길이는 기본적인 LIS 알고리즘으로 찾을 수 있다. 그러나 이 문제는 실제 수열을 출력하는 것이 관건이다.각 원소가 LIS에 몇번에 속하는 지 기록한다.이후 reverse로 돌면서 LIS의 N번째 원소부터 1번째 원소까지 출력하면 된다.L