수업 목표 및 핵심 역량

- 전체 연산량의 한도를 분석하여 균일한 평균 시간 복잡도를 유도합니다. - 슬라이딩 윈도우의 상태를 딕셔너리로 갱신하며 고유값 개수 제한을 처리합니다. - 비트 연산으로 DP 배열 전이 과정을 64배 이상 고속 최적화합니다. - 삼분 탐색의 구간 좁히기 논리를 통해 정밀하게 볼록 극값의 높이를 포착합니다.

투 포인터 슬라이딩 윈도우

- 윈도우 상태 딕셔너리 관리 및 고유값 수 초과 시 꼬리(left) 당김

# 8045번: 중복 없는 서브배열 발췌
for r in range(n):
    counts[arr[r]] = counts.get(arr[r], 0) + 1
    if counts[arr[r]] == 1:
        unique_cnt += 1
    while unique_cnt > k:
        counts[arr[l]] -= 1
        if counts[arr[l]] == 0:
            unique_cnt -= 1
        l += 1
    ans += (r - l + 1)

비트셋을 이용한 부분집합 DP 고속화

- 1차원 테이블의 무게 상태를 정수 비트로 압축하여 dp |= (dp << w) 형태로 일괄 갱신

# 8047번: 부분집합의 합 발췌
dp = 1
for val in w:
    # 각 물건을 추가할 수 있는 상태들을 비트 시프트로 한 줄에 병렬 계산
    dp |= (dp << val)

if (dp >> x) & 1:
    print("YES")

볼록 함수 삼분 탐색

- 두 개의 삼등분점 m1, m2의 비용 함수값 대소를 비교해 볼록 골짜기 구간을 3분의 2씩 압축

# 8048번: 건물 높이 통일 발췌
while high - low > 2:
    m1 = low + (high - low) // 3
    m2 = high - (high - low) // 3
    cost1 = get_cost(m1, h, c)
    cost2 = get_cost(m2, h, c)
    if cost1 < cost2:
        high = m2
    else:
        low = m1

오류 해결 및 오답 방지

- **삼분 탐색 정수 탈출**: 무한 루프 방지를 위해 high - low <= 2 구간 도달 시 직접 최소값 평가 수행 - **비트 연산 적용 범위**: 목표 상수 $X$가 대단히 클 때 메모리 폭발에 주의 (소규모 $X \le 10^5$ 한정 활용) - **오버플로우 대비**: $N=200,000$일 때 가짓수가 32비트 범위를 벗어나므로 변수 정수 스케일 유의