[목차] 완전 탐색과 DP로 푼 LIS LIS 알고리즘 아이디어 알고리즘 알고리즘 분석 예제 정리 1. 완전 탐색과 DP로 구현한 LIS 이 전의 글에서는 LIS를 구하는 알고리즘을 완전 탐색과 동적 계획법으로 구현했었다. 동적 계획법 풀이는 O(N²)의 시간 복잡도를 가졌었다. 하지만 이분 탐색을 이용하면 O(N logN)의 시간 복잡도로 더 빠르게 해결할 수 있다. 이번 글에서는 이분 탐색을 이용하여 O(N log N)의 시간 복잡도로 구현해보려고 한다. 이분 탐색의 LIS를 이해하려면 이분 탐색의 lower_bound() 함수와 upper_bound()함수에 대해 알고 있어야 한다. 또한 DP로 푼 LIS알고리즘도 이해하고 오면 도움이 된다. 따라서 앞의 부분에 대한 이해가 안되어있다면 최소한 이분..

최적화(최대 or 최소)문제를 결정 문제로 바꾸어서 푸는 기법이다. 의심: 완전탐색, DP, 그리디로도 해결할 수 없는 최적화문제의 경우에 두 데이터간의 관계가 단순 비례 반비례에 따른 증감이며 Parameteric Search를 의심해볼 수 있다. 보통 감을 잡기가 매우 어려워서 나중에 돌아와서 떠올리면 베스트 파라메트릭 서치는 STL을 직접 이용할 수 있는 이분탐색과 달리 직접 변수를 설정하고 관계에 따라서 탐색의 범위를 지정해주어야 한다. ??? 예제: 랜선 자르기 백준 1654 주의 사항: 1. 무한 루프 주의: mid를 기준으로 선택의 범위가 균등한지 만약 균등하지 않다면 mid+1로 보정해줘서 무한루프를 방지해줘야함 2. 두 변수간의 관계주의: parameter과 target간의 관계(비례 반..

컴퓨터는 1억번 연산하는데 약 1초가 걸린다. 하지만 알고리즘 문제를 해결하다 보면 입력이 1억번 이상 주어지는 경우가 있다. 이때에는 모두 탐색할 경우 시간 초과가 날 가능성이 크다. 따라서 더 빠른 풀이방법을 생각해야 한다. 이런 경우 보통 이분탐색을 쓴다. 선형 탐색의 시간 복잡도를 O(lon N)으로 만들어준다. [반복문으로 구현한 이분 탐색] while(L arr[M]) L = M + 1; else if(target < arr[M]) R = M - 1; else { result = true; break; } } lower_bound upper_bound