단원 27 — 실전 패턴 (코딩 테스트 최빈출)

lo, hi = 0, n - 1
while lo < hi:
    s = arr[lo] + arr[hi]
    if s == target:
        # 찾음
    elif s < target:
        lo += 1
    else:
        hi -= 1

lo = total = 0
for hi in range(n):
    total += arr[hi]
    while total >= target:
        # [lo, hi] 구간 처리
        total -= arr[lo]
        lo += 1

window_sum = sum(arr[:k])
max_sum = window_sum
for i in range(k, n):
    window_sum += arr[i] - arr[i - k]  # 오른쪽 추가, 왼쪽 제거
    max_sum = max(max_sum, window_sum)

from collections import deque
dq = deque()   # 인덱스 저장 (단조 덱)
for i in range(n):
    while dq and arr[dq[-1]] >= arr[i]:  # 단조 증가 덱
        dq.pop()
    dq.append(i)
    if dq[0] <= i - k:   # 창 밖으로 나간 인덱스 제거
        dq.popleft()
    if i >= k - 1:
        print(arr[dq[0]])  # 창의 최솟값

# dp[mask][v] = mask 집합을 방문하고 v에 있을 때 최소 비용
dp = [[INF] * n for _ in range(1 << n)]
dp[1][0] = 0   # 출발점 0만 방문

for mask in range(1 << n):
    for u in range(n):
        if dp[mask][u] == INF:
            continue
        for v in range(n):
            if mask >> v & 1:  # 이미 방문
                continue
            new_mask = mask | (1 << v)
            dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + dist[u][v])

prefix = [0] * (n + 1)
for i in range(n):
    prefix[i + 1] = prefix[i] + arr[i]

# [l, r] 구간 합 (0-indexed)
def query(l, r):
    return prefix[r + 1] - prefix[l]

# ps[i][j] = 좌상단 (0,0) ~ (i-1,j-1) 합
ps = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        ps[i][j] = (arr[i-1][j-1]
                    + ps[i-1][j] + ps[i][j-1]
                    - ps[i-1][j-1])

# (r1,c1) ~ (r2,c2) 구간 합 (0-indexed 원본)
def query2d(r1, c1, r2, c2):
    return (ps[r2+1][c2+1] - ps[r1][c2+1]
            - ps[r2+1][c1] + ps[r1][c1])

ps[i][j] 는 포함-배제 원리 적용:
┌─────────────┐
│     A       │  ps[i-1][j]
├────┬────────┤
│ B  │ target │  target = arr[i-1][j-1]
│    │        │
└────┴────────┘
   ps[i][j-1]

ps[i][j] = arr + ps_위 + ps_왼쪽 - ps_대각선위왼쪽

python src/01_two_pointer.py
python src/02_sliding_window.py
python src/03_bitmask.py
python src/04_prefix_sum.py

실전 패턴 요약
━━━━━━━━━━━━━━━━━━━━━
투 포인터      : O(n),  두 인덱스 이동
슬라이딩 윈도우: O(n),  창 이동 + deque O(n) min/max
비트마스킹     : O(2ⁿ), 집합/상태 표현, TSP
구간 합        : O(n) 전처리, O(1) 쿼리, 2D 포함-배제

1. 백준 워크북 도전
   - 각 Part별 추천 문제 5개를 반드시 직접 풀기
   - 골드 IV~II 문제를 목표로 업솔빙 진행

2. 프로그래머스 Lv.3 도전
   - 카카오 블라인드, PCCP 기출 문제 풀기

3. 실전 모의 코딩 테스트
   - Codeforces Round (Div.2), Atcoder ABC 참가
   - 시간 제한(2시간) 안에 4문제 풀기 목표

4. 취약 단원 재학습
   - 틀린 유형을 노트에 정리하고 반복 학습
   - 시간 복잡도와 공간 복잡도를 항상 먼저 계산

5. 코드 최적화 연습
   - PyPy 제출 가능 문제는 Python 최적화 먼저
   - sys.stdin.readline, 출력 버퍼링 기법 숙지