Searching Algorithm

데이터 집합에서 원하는 값(Key)을 찾는 과정.대상 데이터는 배열, 리스트, 트리 등 다양한 형태일 수 있으며, 데이터의 정렬 여부와 분포에 따라 적절한 탐색 알고리즘을 선택한다. 모두 추가 공간은 일반적으로 O(1)이다.처음부터 끝까지 순차적으로 탐색한다.정렬 여부

Parametric Search(Binary Search on Answer) > Binary Search on Answer는 배열에서 특정 값을 찾는 일반적인 이분 탐색과 달리, 정답이 될 수 있는 값의 범위 자체를 이분 탐색하는 기법이다. 1. 핵심 개념 일반

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