Prefix Sum 배열에서 i 번째 까지의 값의 합을 가지고 있는 새로운 배열 prefix sum 배열을 만드는 것을 pre-processing이라고 볼 수 있고 main 로직에서 시간 복잡도를 줄여주는 역할을 한다. i ~ j 까지 합을 O(1)에 구할 수 있음 prefix[j] - prefix[i - 1] // 0이하로 out of bound되는 것을 막고 싶다면 prefix[j] - prefix[i] + nums[i] prefix sum 만들기 prefix sum이 없다면 query를 수행하는데 O(n) 만큼이 들고 query의 갯수가 m개라면 총 O(n*m) prefix sum을 사용함으로서 O(n + m)으로 시간복잡도를 낮출 수 있음.(O(n) 만큼의 공간을 추가 사용) vector answ..

Sliding Window 유형 subarray를 유효하게 만드는 조건이 주어 진다. 합해서 몇 이하, 어떤 숫자의 포함 빈도 등 여러 subarray안에서 최적의 subarray 를 찾는 문제가 나옴 혹은 몇개의 subarray가 나오는지? 예시 합이 k보다 작거나 같은 가장 긴 하위 배열을 구합니다. "0"이 하나 이상 있는 가장 긴 부분 문자열을 구합니다. k보다 작은 곱을 갖는 서브 배열의 개수 찾기 수도 코드 function fn(arr): left = 0 for (int right = 0; right < arr.length; right++): Do some logic to "add" element at arr[right] to window while WINDOW_IS_INVALID: Do so..