코딩테스트2 알고리즘 - 투포인터, 슬라이딩 윈도우 투 포인터 (슬라이딩 윈도우, 부분합, 시간복잡도)"연속한 부분 배열 중 합이 가장 큰 것", "합이 정확히 K인 구간의 개수", "중복 없는 가장 긴 부분 문자열" — 이런 문제를 만나면 초보자는 본능적으로 이중 반복문을 떠올린다. 모든 시작점과 끝점을 다 시도하면 O(N²)이다. 그러나 배열을 한 번만 훑으면서 두 개의 포인터를 적절히 움직이면 같은 문제를 O(N)에 풀 수 있다. 이것이 투 포인터(Two Pointer)와 그 특수형인 슬라이딩 윈도우(Sliding Window)다. 본 글은 두 기법의 동작 원리, 고정 크기와 가변 크기 윈도우의 차이, 그리고 단조성이라는 적용 조건을 세심하게 정리한다(출처: 위키백과 — Maximum subarray problem). 제가 코딩 테스트를 처음 준비할.. 2026. 5. 24. 알고리즘 - 이분 탐색, 매개변수 탐색 이분 탐색 (이진 탐색, 매개변수 탐색, 경계 조건)정렬된 데이터에서 원하는 값을 찾을 때, 처음부터 끝까지 훑는 선형 탐색은 100만 개 자료에서 최악 100만 번을 비교한다. 같은 상황에서 이분 탐색(Binary Search)은 단 20번이면 끝난다. 탐색 범위를 절반씩 잘라 내며 후보를 지수적으로 줄이는 이 단순한 발상이 데이터베이스 인덱스, 표준 라이브러리의 bisect, git의 bisect 명령, 그리고 코딩 테스트 단골 기법인 매개변수 탐색까지 떠받친다. 본 글은 이분 탐색의 정확한 구현과 가장 자주 틀리는 경계 조건, 그리고 최적화 문제를 탐색 문제로 바꾸는 매개변수 탐색을 세심하게 정리한다(출처: 위키백과 — Binary search algorithm). 제가 학교 알고리즘 과제에서 이분.. 2026. 5. 23. 이전 1 다음