Table of Contents 개요 1D sparse table 쿼리를 O(1)으로 처리하기 2D sparse table 문제 1. 개요 스파스 테이블은 배열 Array[1...N], 함수 Function, 범위 [L, R] 이 주어질 때 Function(Array[L], Array[L+1], ..., Array[R]) 계산을 빠르게 하기 위한 자료구조입니다. 간단하게 예를 들면, 'A[3] ~ A[7] 사이의 최소값을 구하라.'같은 식입니다. 여기에서 함수는 최소값 찾기, L = 3, R = 7이 되겠지요. 스파스 테이블은 아래의 두 조건이 성립할 때 사용할 수 있습니다. 조건 1) Array에 저장된 값이 변하지 않야야 한다. 조건 2) Function은 결합 법칙이 성립해야 한다. (즉, F(a,..
1. DP[i][j] = (i, j)가 오른쪽 밑 모서리인 정사각형의 최대 크기 1-(1). (i,j) 가 0인 경우 -> DP[i][j]=0; 1-(2). (i,j) 가 1인 경우 -> min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1 2. parametric search 3. 쿼리의 정답이 특정 값 mid 이상인지 여부는 DP 배열을 소스로 만든 sparse table을 통해 바로 알 수 있음. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384..