0. 한 줄 요약세 도구 모두 "모든 경우를 보는 O(N²)"을 "미리 준비하거나, 한 번에 버려서" 줄이는 방법이다. 누적합은 미리 합을 쌓아 두고, 이분탐색은 절반씩 버리고, 투포인터는 한 칸씩 버린다. 1. 세 도구 정의 누적합(prefix sum) 은 배열의 맨 앞부터 각 위치까지의 합을 미리 계산해 저장한 배열이다. psum[i] = psum[i-1] + a[i]이고, 구간 [l, r]의 합은 psum[r] - psum[l-1]이다. 이분탐색(binary search) 은 정렬된 데이터에서 탐색 범위를 매번 절반으로 줄여 가며 찾는 알고리즘이다. 응용으로, 배열이 없어도 답의 범위에서 "이 값으로 가능한가?"를 판정하며 최솟값/최댓값을 찾는 매개변수 탐색이 있다. 투포인터(two pointer..
0. 한 줄 요약위치를 가리키는 변수 두 개가 한 방향으로만 움직이면서, 이중 for문 O(N²)을 **O(N)**으로 줄인다. 지나온 칸은 다시 볼 필요가 없다고 확신할 근거(정렬 또는 양수)가 있을 때 쓴다. 1. 투포인터 (Two Pointers)투포인터란?투포인터(two pointers)는 배열에서 위치 변수 두 개를 움직여, 조건을 만족하는 쌍이나 구간을 한 번의 순회로 찾는 방법이다. 이중 for문은 모든 (i, j) 조합을 보지만, 투포인터는 포인터가 되돌아가지 않아서 전체 이동 횟수가 약 2N이다.유형포인터대표 문제근거① 양끝에서 좁히기하나는 맨 앞, 하나는 맨 뒤정렬된 배열에서 합이 X인 쌍정렬② 같은 방향으로 움직이기둘 다 앞에서 출발, 구간 [l, r]합이 S 이상(또는 k)인 가장..
1. 매개변수 탐색 (Parametric Search) 매개변수 탐색이란?매개변수 탐색(parametric search)은 "답이 x일 수 있는가?"를 예/아니오로 판정하는 함수 check(x)를 만들고, 답이 될 수 있는 값의 범위에서 이분탐색으로 조건을 만족하는 최솟값 또는 최댓값을 찾는 방법이다. 배열이 아니라 답의 범위를 절반씩 줄인다.문제 종류질문예최적화 문제가장 작은(큰) 값은 얼마인가?질투심의 최솟값은?결정 문제이 값으로 가능한가? (예/아니오)질투심이 3 이하로 나눌 수 있는가?최적화 문제를 결정 문제로 바꾸는 것이 핵심이다. 결정 문제는 풀기 쉽고, 그 결과가 한 번만 바뀌면 이분탐색이 된다. 왜 필요한가막대 [10, 7]을 같은 길이 L로 잘라 조각을 4개 이상 만들 때, L의 최댓값은..
0. 한 줄 요약정렬된 데이터에서 탐색 범위를 매번 절반으로 줄여 **O(log N)**에 찾는다. 배열에 값이 있으면 STL(lower_bound, upper_bound)을 쓰고, 직접 구현은 원리를 이해하는 기본기다. 1. 이분탐색 (Binary Search)이분탐색이란?이분탐색(binary search)은 정렬된 배열에서 탐색 범위를 매번 절반으로 줄여 가며 원하는 값을 찾는 알고리즘이다. 중간 원소를 하나 보고, 찾는 값이 더 작으면 왼쪽 절반만, 더 크면 오른쪽 절반만 남긴다. 이진탐색이라고도 부른다.전제 조건은 배열이 정렬되어 있는 것이다. 정렬되어 있어야 "중간 값보다 작으니 오른쪽은 볼 필요 없다"는 판단이 성립한다. 왜 필요한가정렬된 정수 N = 10⁶개에서 “x가 있는가?”를 10⁶번..
0. 한 줄 요약 같은 배열에서 구간 합을 여러 번 물을 때, 앞에서부터 합을 미리 쌓아 두고 **뺄셈 한 번(O(1))**으로 답한다. 단, 배열이 중간에 바뀌지 않아야 한다. 1. 누적합(Prefix sum)누적합이란?누적합(prefix sum)은 배열의 맨 앞부터 각 위치까지의 합을 미리 계산해서 저장해 둔 배열이다.원본 배열 a에 대해, 누적합 배열 psum의 i번째 값은 a[1] + a[2] + ... + a[i]다. 원본 a와 누적합 psum을 나란히 놓으면 이렇다.위치i12345원본 a[i]25134누적합 psum[i]2781115psum[3] = 8은 “1번부터 3번까지 더한 값 (2+5+1)”이다. 앞의 값에 현재 원소를 더해서 만든다.psum[i] = psum[i - 1] + a[i]..
