배열/리스트 PS 기법

Cheatsheet Content

### 투 포인터 기법 소개 - **정의**: 두 개의 인덱스(포인터)를 사용하여 데이터 구조를 동시에 순회하는 기법입니다. - **적용 시점**: - 입력이 정렬되어 있을 때. - 양쪽 끝에서 스캔할 때. - **목표**: 시간 복잡도를 $O(N^2)$에서 $O(N)$으로 줄입니다. - **포인터 이동**: 문제별 조건에 따라 포인터를 이동합니다. - **직관**: 두 포인터를 양쪽 끝에 시작하여 서로를 향해 이동시킵니다. - `left = 0`, `right = n - 1`로 초기화합니다. - `while (left ### 투 포인터 예시: 목표 합 찾기 - **문제**: 정렬된 배열 `arr`와 목표 `target`이 주어졌을 때, `arr[i] + arr[j] = target`을 만족하는 쌍 `(arr[i], arr[j])`이 존재하는지 찾습니다. #### Naive 접근 (비효율적) - 가능한 모든 쌍을 확인합니다. - 시간 복잡도: $O(N^2)$ - 공간 복잡도: $O(1)$ ```cpp bool twoSum(vector &arr, int target) { int n = arr.size(); for (int i = 0; i target`: 합을 줄이기 위해 `right` 포인터를 왼쪽으로 이동합니다 (`right--`). - **정렬된 배열의 이점**: - `left`를 늘리면 합이 증가합니다. - `right`를 줄이면 합이 감소합니다. - 쌍을 찾지 못하면 `false`를 반환합니다. ```cpp bool twoSum(const vector & arr, int target) { int left = 0, right = arr.size() - 1; while (left ### 슬라이딩 윈도우 기법 소개 - **정의**: 서브 배열(윈도우)을 유지하고 효율적으로 이동시키는 기법입니다. - **사용 시점**: - 연속적인 서브 배열/부분 문자열을 처리할 때. - 시간 복잡도를 $O(N^2)$ 대신 $O(N)$으로 줄이고 싶을 때. - **핵심 아이디어**: 이전 계산을 재사용하여 다시 계산하는 것을 피합니다. - 슬라이딩 윈도우는 투 포인터 기법의 특수화된 형태입니다. #### 문제 예시: 크기 K의 서브 배열의 최대 합 - **문제**: 크기 N의 배열과 정수 K가 주어졌을 때, 크기 K의 서브 배열의 최대 합을 찾습니다. #### Naive 접근 - 크기 K의 모든 서브 배열에 대해 합을 계산합니다. - 시간 복잡도: $O(N^2)$ - 문제점: 중복 계산이 발생합니다. #### 최적화된 접근 (슬라이딩 윈도우) 1. **초기 윈도우 계산**: 인덱스 0부터 $K-1$까지의 첫 번째 크기 K 서브 배열의 합을 계산합니다. 2. **윈도우 이동**: 각 반복에서 윈도우를 한 칸씩 오른쪽으로 이동하고 합을 업데이트합니다. - **이전 계산 재사용**: 새 윈도우의 합을 다시 계산하는 대신, 이전 윈도우의 합을 사용하여 업데이트합니다. - **업데이트 방법**: 윈도우의 가장 왼쪽 요소를 제거하고 가장 오른쪽 새 요소를 추가합니다. - 이 작업은 $O(1)$ 시간에 수행됩니다. ### 슬라이딩 윈도우 기법 사용 방법 #### 고정 크기 윈도우 1. **초기 윈도우 계산**: 첫 번째 윈도우의 합/결과를 계산합니다. 2. **각 단계**: - 윈도우의 가장 왼쪽 요소를 **제거**합니다. - 윈도우의 다음 요소를 **추가**합니다. 3. **결과 업데이트**: 현재 윈도우의 결과로 전체 답을 업데이트합니다. #### 가변 크기 윈도우 (예: 합이 x보다 큰 가장 작은 서브 배열) - **문제**: 정수 배열 `arr[]`와 숫자 `x`가 주어졌을 때, 합이 `x`보다 엄격히 큰 가장 작은 서브 배열의 길이를 찾습니다. #### Naive 접근 - 두 개의 중첩 루프를 사용합니다. - 외부 루프는 시작 요소를 선택하고, 내부 루프는 현재 시작 요소의 오른쪽에 있는 모든 요소를 끝 요소로 고려합니다. - 현재 시작과 끝 사이의 요소 합이 `x`보다 커지면, 현재 길이가 가장 작은 길이보다 작으면 결과를 업데이트합니다. - 시간 복잡도: $O(N^2)$ - 공간 복잡도: $O(1)$ ```cpp int smallestSubWithSum(int x, const vector & arr) { int n = arr.size(); int res = INT_MAX; for (int i = 0; i x) { res = min(res, (j - i + 1)); break; // 현재 i에 대해 더 이상 확장할 필요 없음 } } } return (res == INT_MAX) ? 0 : res; } ``` #### 슬라이딩 윈도우 접근 (두 포인터) - 슬라이딩 윈도우를 유지하기 위해 두 포인터 접근 방식을 사용합니다. - 합이 `x`보다 커질 때까지 요소를 추가하여 윈도우를 **확장**합니다. - 합이 `x`보다 큰 조건을 유지하면서 시작부터 윈도우를 **축소**하여 윈도우를 최소화합니다. - 가능한 모든 서브 배열을 탐색하고 가장 작은 유효한 길이를 추적합니다. - 시간 복잡도: $O(N)$ - 공간 복잡도: $O(1)$ ```cpp int smallestSubWithSum(int x, const vector & arr) { int i = 0, j = 0; int sum = 0; int ans = INT_MAX; while (j x 조건을 유지하면서 while (i x) { ans = min(ans, (j - i)); // 현재 윈도우 길이 sum -= arr[i++]; } } return (ans == INT_MAX) ? 0 : ans; } ```