격자판 슬라이딩 탐색 — 브루트포스 + 2D 패턴 매칭1. 이 유형이 나오는 상황두 개의 격자(grid)가 주어지고, 한 격자를 다른 격자 위에 겹쳐가면서 최적의 위치를 찾아야 할 때 등장한다.핵심 질문은 항상 이것이다.*"두 격자를 어떻게 겹쳐야 공통 원소가 최대가 되는가?"*대표 문제:동전 퍼즐 — 현재 배치 → 목표 배치로 만들 때 최소 이동 횟수자물쇠와 열쇠 — 열쇠를 회전/반전해서 자물쇠에 맞추기2. 핵심 아이디어 — 왜 "겹치기"인가?동전 퍼즐을 예로 들면:현재(vec1): 목표(vec2):O . . . O .. O . . . O동전을 옮기는 최소 횟수를 구하려면 반대로 생각한다."이미 목표 위치에 있는 동전이 많을수록 → 옮길 동전이 적다"따라서:정답 =..

슬라이딩 윈도우란?배열/문자열 위에 window를 올려놓고, 오른쪽으로 밀면서 탐색하는 기법이다.완전탐색 $O(N²$) → $O(N)$ 으로 줄이는 게 핵심이다.빈출 유형연속된 구간에서 최대/최소/개수를 구할 때 등장한다1) 고정 크기 윈도우예) "크기 K인 연속 부분 배열의 최대 합"창문 크기 K가 고정되어 있다.right가 움직이면 left도 같이 움직인다.2) 가변 크기 윈도우예) "합이 S 이하인 가장 긴 연속 부분 배열", 개미 집합의 지름 문제조건에 따라 창문 크기가 늘었다 줄었다한다.left/right 독립적으로 움직인다.3) 반대 방향 투 포인터예) "두 수의 합이 target인 쌍 찾기", "3Sum"정렬 후 left/right를 양 끝에서 좁혀오는 방식이다.투 포인터가 슬라이딩 윈도우를..

이진 탐색이란?핵심 정의정렬된 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 찾는 알고리즘이때, 데이터가 반드시 정렬되어 있어야 한다예시) 1~ 100 사이 숫자를 맞출 때 “50보다 커?” 라고 묻는 것동작 방식중간값 선택비교: 찾고자 하는 값(Target)과 비교Target == 중간값: 탐색 종료Target : 왼쪽 절반을 새로운 범위로 설정Target > 중간값: 오른쪽 절반을 새로운 범위로 설정반복: 값을 찾거나 범위가 남지 않을 때까지 반복시간 복잡도O(\log n)한 번 시행할 때마다 남은 데이터의 개수가 1/2로 줄어듦데이터 개수가 n개일 때, k번 시행하면 남은 데이터는 $\frac{n}{2^k}$개가 됨최악의 경우 데이터가 1개 남을 때까지 탐색하므로, $\frac{n}{2^k} = ..

문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr- 모든 사람이 심사를 받는데 걸리는 시간의 최솟값 구하기 풀이고득점 Kit에서 이분탐색으로 분류된다기본적으로 이분탐색은 최솟값/최댓값 탐색, 또는 TTTFFF 로 이분적으로 분류되는 경우에 사용할 수 있는 알고리즘이다 순차탐색에 비해서 탐색 범위를 절반으로 좁혀가면서 찾기 때문에 O(logN)의 시간 복잡도를 가진다따라서 하나의 특징이 있는데, 대부분의 문제에서 데이터의 범위가 엄청 큰 편이다(제한 사항: 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하) 이런 경우에 여기서 힌트를 찾아서 이분 탐색으로 풀어야 한다는 아이디어를 얻을 수도 ..

프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제- 주어진 사각형의 모서리만 따라서 이동하여 아이템 줍기 풀이 1. 모든 좌표를 2배수 하기 그림과 같은 모서리가 주어졌을 때, 좌표 기준으로 방문 가능 여부를 채우게 된다면모서리가 아닌 부분까지 방문 가능하다고 착각할 수 있으므로 모든 좌표를 2배수 해야 한다. 2. 이동 가능한 범위 구하기 (사각형)이동 가능한 범위는 사각형들의 모서리이다.간단히 생각해서 사각형 범위들을 전부 1로 채우고, 내부는 0으로 채우면 끝!! 내가 여기서 의문이었던 것은, 그럼 겹치는 부분은 어떻게 되는거지?.. 였는데예를 들어 아래와 같은 경우다. [B 사각형 내부에 있는 A 사..