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..

문제 링크 https://www.acmicpc.net/problem/1620 시간, 공간 제한 시간 : 2초 공간 : 256MB 문제 접근 방향 - key와 value 값을 저장하고 해당 자료구조를 탐색하여 적절한 값을 찾는 문제 - 단순히 배열을 자료구조로 선택할 경우 인덱스접근은 O(1)이지만 string을 찾기 위해서는 선형 탐색시 O(n)이된다. - 입력 최대 값이 100,000이고 선형 탐색을 통한 문제 해결시 전체 시간 복잡도는 O(n^2)으로 시간초과 발생한다. - string을 찾기 위해 O(logn)정도의 탐색 시간 복잡도가 필요하고 해당 시간 복잡도를 가진 map 자료 구조를 사용한다. - map은 key, value 한쌍을 저장할 수 있는 자료 구조이고 내부는 레드블랙트리라는 균형 이..

문제 링크 https://www.acmicpc.net/problem/2559 시간, 공간 제한 시간 : 1초 공간 : 128Mb 초기 문제 접근 방향 시간 복잡도 생각 - 일단 최대 들어 올수 있는 입력이 10,0000 이고 완전 탐색으로 모든 경우의 수를 구해 비교하는 것은 O(n^2) 이기 때문에 dp 풀이를 시도함 - ans[i] 값을 i번째 input에서 연속된 k일동안 온도의 합이라고 한다면 - ans[i] = ans[i - 1] - input[i - 1] + input[i + (k - 1)] 이라는 점화식을 도출함 - max_element를 사용하여 ans 범위안의 최댓값을 찾아냄 #include #include #include using namespace std; int main(void) ..