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]..
0. 한 줄 요약 정렬은 STL이 해준다. 코테에서 중요한 건 "어떤 기준으로 줄 세울지"를 비교 함수로 정의하는 것과 정렬한 뒤 무엇이 쉬워지는지 아는 것이다. 1. 정렬(Sort) 정렬이란?정렬(sorting)은 원소들을 정해진 기준에 따라 순서대로 다시 배치하는 것이다. 기준은 오름차순, 내림차순처럼 기본적인 것도 있고, "점수는 내림차순, 같으면 이름 오름차순"처럼 직접 정의할 수도 있다.정렬 전: [3, 1, 4, 1, 5]오름차순: [1, 1, 3, 4, 5]내림차순: [5, 4, 3, 1, 1] C++에서는 sort(begin, end)가 이 일을 하고, 비교 기반 정렬이라 O(N log N)이다. 원본 배열을 그 자리에서 바꾼다. 기준을 직접 정의할 때는 비교 함수를 넘기는데, cmp(..
0. 한 줄 요약스택은 가장 최근 것부터, 큐는 가장 오래된 것부터 꺼낸다. 둘 다 새로운 구조가 아니라, 배열에 "넣고 빼는 규칙"을 붙인 것이다. 1. 스택 (Stack, LIFO) 스택이란?스택(stack)은 데이터를 한쪽 끝에서만 넣고 뺄 수 있는 자료구조다. 가장 나중에 넣은 것이 가장 먼저 나오는 후입선출(LIFO, Last In First Out) 규칙을 따른다. 접시를 쌓고 맨 위에서부터 집는 것과 같다.push(1) → push(2) → push(3) 스택: [1, 2, 3] (3이 맨 위)pop() 3이 나온다 스택은 독립적인 구조라기보다 배열이나 연결리스트에 "한쪽 끝에서만 접근한다"는 규칙을 붙인 것이다. 핵심 연산은 push, ..
