Ch 8. 알고리즘 설계 기법 (Algorithm Design Topics)

← 수업 목록

Ch 8. 알고리즘 설계 기법 (Algorithm Design Topics)

수업 목표

본 수업은 시간 복잡도 분석의 고급 기법인 분할 상환 분석(Amortized Analysis)의 원리를 이해하고, 이와 연계된 투 포인터(Two Pointers), 비트 평행(Bit-Parallel) 최적화, 그리고 삼분 탐색(Ternary Search)을 활용한 볼록 함수 극값 찾기 기법을 학습하는 것을 목표로 합니다. - 전체 연산량을 기준으로 평균 속도를 분석하는 분할 상환 기법의 개념을 파악합니다. - 슬라이딩 윈도우 기법에 딕셔너리를 결합하여 조건 만족 서브배열의 개수를 $O(N)$에 세는 법을 습득합니다. - 파이썬 대형 정수의 비트 연산 특성을 활용하여 부분집합의 합 문제를 고속화하는 비트셋 기법을 적용합니다. - 삼분 탐색을 통해 볼록 함수의 최솟값 또는 최댓값을 실수 및 정수 오차 없이 안정적으로 찾는 탐색 프로세스를 구현합니다.

학습 동기부여

단순히 모든 단계를 독립적으로 보고 시간 복잡도를 계산하면 $O(N^2)$ 처럼 지나치게 비관적인 수치가 도출될 수 있습니다. 그러나 각 단계의 개별 연산량이 다를지라도 '전체 단계 동안 일어나는 총 연산량'의 합이 작다면 평균 복잡도를 대폭 낮출 수 있습니다. 이를 분할 상환 분석이라고 하며, 투 포인터나 슬라이딩 윈도우 알고리즘의 타당성을 증명하는 기초가 됩니다. 또한, 하드웨어 연산 구조를 활용해 64비트 정수 연산 한 번으로 64개의 연산을 일시에 처리하는 비트셋 최적화나, 기울기의 증감을 기반으로 극값을 찾는 삼분 탐색은 수학과 알고리즘이 결합되어 실질 성능을 극대화하는 강력한 방법들입니다.

도입 스토리

기차 놀이를 할 때, 기차의 맨 앞 머리와 맨 뒤 꼬리를 조절하며 기차 안에 들어있는 아이들의 고유 색상 개수가 제한값을 넘지 않게 조절하는 과정을 상상해 봅시다. 기차가 앞으로 나아가면서 머리가 한 칸 전진하고 꼬리가 한 칸 따라올 때, 머리와 꼬리가 기차 전체를 훑는 횟수는 총 2번($2N$)을 넘지 않습니다. 따라서 개별 단계에서 꼬리가 여러 칸 움직이더라도 전체 기차 이동 속도는 $O(N)$에 비례합니다. 또한, 여러 건물의 높이를 통일시키는 최소 조절 비용 함수처럼, 어떤 점 $X$를 기준으로 비용이 점차 감소했다가 다시 증가하는 볼록한 골짜기 형태의 그래프를 마주했을 때, 우리는 골짜기의 중앙 삼등분점을 탐색하며 아주 영리하게 최소 비용을 만족하는 지점을 찾아낼 수 있습니다. 본 수업에서는 이러한 연산 최적화 설계 방식을 다룹니다.

1. 분할 상환 분석과 슬라이딩 윈도우 — 중복 없는 서브배열

서로 다른 원소의 개수가 최대 $K$개 이하인 연속된 부분 배열(서브배열)의 개수를 구합니다. 투 포인터를 사용하여 오른쪽 포인터 r을 전진시키며 딕셔너리에 빈도를 기록하고, 고유 원소 개수가 $K$를 초과하면 왼쪽 포인터 l을 당겨 고유 원소 개수를 $K$ 이하로 리셋합니다. r과 l은 각각 최대 $N$번만 전진하므로 전체 연산 횟수는 $2N$에 수렴하여 $O(N)$ 복잡도를 보장받습니다.

# 8045번: 중복 없는 서브배열 — O(N) 투 포인터
import sys
from collections import deque
input = sys.stdin.readline

n, k = map(int, input().split())
arr = list(map(int, input().split()))

counts = {}
l = 0
ans = 0
unique_cnt = 0

for r in range(n):
    val = arr[r]
    counts[val] = counts.get(val, 0) + 1
    if counts[val] == 1:
        unique_cnt += 1
        
    # 고유 원소 개수가 K를 초과하는 동안 왼쪽 포인터를 축소
    while unique_cnt > k:
        left_val = arr[l]
        counts[left_val] -= 1
        if counts[left_val] == 0:
            unique_cnt -= 1
        l += 1
        
    # r을 끝자리로 갖는 만족 서브배열의 개수 누적
    ans += (r - l + 1)

print(ans)

2. 투 포인터 심화 — 세 수의 합

배열의 서로 다른 세 수의 합이 정확히 $X$가 되는 위치를 찾을 때, 정렬을 거친 뒤 첫 번째 수 i를 고정하고 나머지 부분 구간에 대해 양방향 투 포인터를 탐색하는 방식을 적용하여 $O(N^2)$ 복잡도 안에 풀 수 있습니다.

# 8046번: 세 수의 합 — 정렬 후 O(N^2) 투 포인터
import sys
input = sys.stdin.readline

n, x = map(int, input().split())
vals = list(map(int, input().split()))

# 원래 인덱스를 유지하기 위해 (값, 원래 인덱스) 리스트 구성 후 정렬
arr = sorted([(vals[i], i + 1) for i in range(n)])

found = False
for i in range(n - 2):
    target = x - arr[i][0]
    l = i + 1
    r = n - 1
    while l < r:
        curr_sum = arr[l][0] + arr[r][0]
        if curr_sum == target:
            # 1-based 인덱스 출력
            res = sorted([arr[i][1], arr[l][1], arr[r][1]])
            print(*res)
            found = True
            break
        elif curr_sum < target:
            l += 1
        else:
            r -= 1
    if found:
        break

if not found:
    print("IMPOSSIBLE")

3. 비트 평행 알고리즘 — 부분집합의 합 (Bitset 최적화)

파이썬의 정수형은 메모리가 허용하는 한 비트 크기에 제한이 없습니다. 부분집합 합 문제에서 1차원 DP 테이블의 모든 값들을 거대한 하나의 정수(비트열)로 표현하면, 새로운 무게 $w$를 가산하는 전이 연산을 비트 시프트 연산 dp |= (dp << w) 단 한 줄로 수행할 수 있어 대량의 연산을 상수 시간에 가깝게($O(X \cdot N / 64)$) 한꺼번에 처리하는 비트 평행(Bit-Parallel) 효과를 냅니다.

# 8047번: 부분집합의 합 — 파이썬 고속 비트셋 연산
import sys
input = sys.stdin.readline

n, x = map(int, input().split())
w = list(map(int, input().split()))

# dp 비트셋 생성 (0번째 비트 1로 켜짐, 즉 dp[0]=True)
dp = 1

for val in w:
    # dp |= (dp << val)
    # val만큼 비트를 왼쪽으로 밀어서(시프트) 교집합 비트 합산
    dp |= (dp << val)

# 목표 값 x번째 비트가 켜져있는지 확인
if (dp >> x) & 1:
    print("YES")
else:
    print("NO")

4. 볼록 함수 극값 탐색 — 삼분 탐색 (Ternary Search)

삼분 탐색은 오목하거나 볼록한 함수에서 극값을 찾을 때 유용합니다. 탐색 구간 $[low, high]$를 3등분하는 m1, m2 위치에서의 비용을 비교하여 최소 비용을 포함하는 3분의 2 영역으로 탐색 구간을 좁혀나갑니다. $O(N \log(\text{max\_H}))$ 시간에 동작합니다.

# 8048번: 건물 높이 통일 — 삼분 탐색 구현
import sys
input = sys.stdin.readline

def get_cost(x, h, c):
    return sum(c[i] * abs(h[i] - x) for i in range(len(h)))

def solve():
    n = int(input())
    h = list(map(int, input().split()))
    c = list(map(int, input().split()))
    
    low = 0
    high = 10000
    
    # 정수 범위 삼분 탐색
    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
            
    # 후보 정수 범위 내에서 최소값 검색
    ans = min(get_cost(x, h, c) for x in range(low, high + 1))
    print(ans)

t = int(input())
for _ in range(t):
    solve()

자주 하는 실수 & 오류 예방

- 비트 시프트 오프셋 초과 오류: 비트 연산 기반의 최적화를 적용할 때 목표값 $X$의 크기가 지나치게 커지면(예: $10^9$ 이상) 메모리 초과를 일으킵니다. $X \le 10^5$ 수준의 한도 조건이 있을 때만 비트셋 기법을 안전하게 적용하십시오. - 삼분 탐색 정수 나눗셈 소실 경계: 삼분 탐색 구간 $[low, high]$가 3 미만으로 좁혀졌을 때 정수 나눗셈 // 3을 반복하면 무한 루프에 빠지거나 경계 계산 오류를 유발합니다. 반드시 high - low > 2 조건으로 루프를 끊고 남은 3개 이하의 정수 후보들에 대해 직접 최솟값을 계산하십시오. - 투 포인터의 자료형 오버플로우: 중복 없는 서브배열 문제에서 결과 가짓수 ans는 최댓값 $N(N+1)/2$에 달해 32비트 정수 범위($2 \times 10^9$)를 가볍게 넘을 수 있습니다. 결과 누적용 변수 할당 시 오버플로우가 나지 않도록 구현하십시오.

핵심 정리

알고리즘 유형	대표 기법	핵심 시간 복잡도	주요 작동 방식 및 의의
분할 상환 분석	투 포인터 / 슬라이딩 윈도우	$O(N)$	포인터들의 단방향 이동을 통해 평균 시간 소요 단축
비트 평행 최적화	정수 비트셋 연산	$O(N \cdot X / 64)$	메모리 비트 시프트를 통해 DP 전이 루프 병렬화
삼분 탐색	Ternary Search	$O(N \log H)$	삼등분점 함수값 비교를 통해 볼록 영역 극값 추출

실습 문제

문제 번호	문제 제목	출처	난이도	핵심 알고리즘
8045	중복 없는 서브배열	CSES	보통	투 포인터 & 슬라이딩 윈도우
8046	세 수의 합	CSES	보통	정렬 & 투 포인터 응용
8047	부분집합의 합	SPOJ	보통	부분집합 DP & 비트셋 최적화
8048	건물 높이 통일	SPOJ	보통	볼록 함수 비용 계산 & 삼분 탐색