# [07-06] 상각 분석 (Amortized Analysis)
상각 분석은 연속된 연산들의 평균 비용을 계산하여, 가끔 발생하는 비싼 연산의 영향을 전체적으로 분석하는 기법입니다.
🎯 상각 분석이란 무엇인가
상각 분석의 기본 개념
상각(償却, Amortize)의 사전적 의미는 "빚을 나누어 갚다"입니다.
프로그래밍에서는 "비싼 연산의 비용을 여러 연산에 나누어 계산한다"는 의미입니다.
실생활 비유:
자동차 유지비 계산:
방법 1: 매월 비용 따로 계산
- 1월: 10만원 (기름값)
- 2월: 10만원
- 3월: 10만원
- 4월: 410만원 (보험료 400만원 + 기름값)
- 5월: 10만원
→ "4월이 너무 비싸다!"
방법 2: 1년 평균으로 계산 (상각)
- 총 비용: 450만원
- 월 평균: 450 ÷ 12 = 37.5만원
→ "매달 평균 37.5만원"
상각 분석은 방법 2처럼 비싼 연산을 평균으로 계산!프로그래밍 예시:
# Python의 list를 사용해 봅시다
arr = []
# 1번째 추가
arr.append(1) # 빠름 (0.001초)
print(f"크기: {len(arr)}") # 1
# 2번째 추가
arr.append(2) # 빠름 (0.001초)
print(f"크기: {len(arr)}") # 2
# 3번째 추가
arr.append(3) # 빠름 (0.001초)
print(f"크기: {len(arr)}") # 3
# 4번째 추가 - 갑자기 느림!
arr.append(4) # 느림 (0.100초) ← 왜?
print(f"크기: {len(arr)}") # 4
# 이유: 내부적으로 더 큰 배열을 만들고 기존 데이터를 복사
# 5번째 추가
arr.append(5) # 다시 빠름 (0.001초)패턴 발견:
대부분은 빠름 (0.001초)
가~끔만 느림 (0.100초)
100번 추가하면?
- 빠른 거: 95번
- 느린 거: 5번
→ 평균적으로는 빠르다!왜 상각 분석이 필요한가?
문제 상황: 너무 비관적인 분석
상황: 리스트에 100개 추가하기
방법 1: "최악의 경우만 보기" (너무 비관적)
-----------------------------------------------
"append가 최악의 경우 느리네?
그럼 100번 하면 엄청 느리겠다!"
계산:
- append 1번: 최악 0.1초
- 100번: 0.1 × 100 = 10초!
→ "와... 10초나 걸려? 쓰지 말아야겠다"
실제로 측정해보니:
- 100번 append: 0.2초
→ "어? 10초가 아니라 0.2초네?"
방법 2: "상각 분석" (현실적)
-----------------------------------------------
"느린 경우는 가끔만 발생하니까
전체 평균을 보자!"
계산:
- 빠른 append: 95번 × 0.001초 = 0.095초
- 느린 append: 5번 × 0.02초 = 0.1초
- 총: 0.195초
- 평균: 0.195 ÷ 100 = 0.00195초
→ "평균적으로 매우 빠르네!"왜 차이가 날까?
핵심: "느린 경우가 자주 발생하지 않는다"
예시: 1,000번 append
---------------------------------------
1번째: 빠름
2번째: 빠름
3번째: 느림 ← 확장!
4번째: 빠름
5번째: 빠름
6번째: 빠름
7번째: 느림 ← 확장!
...
(중간 생략)
...
1000번째: 빠름
확장 횟수: 약 10번만!
빠른 경우: 990번
→ 대부분은 빠르다!상각 vs 평균의 차이 (쉽게!)
쉬운 비유: 버스 타기
평균 경우 분석 (Average Case):
---------------------------------------
"버스가 평균적으로 몇 분에 올까?"
전제:
- 버스는 랜덤하게 온다
- 5분에 한 대씩 온다고 가정
계산:
- 평균 대기 시간: 2.5분
- 확률 분포를 가정함!
예: "운이 좋으면 바로 오고, 나쁘면 5분 기다림"
상각 분석 (Amortized):
---------------------------------------
"버스를 10번 타는데 총 얼마나 걸릴까?"
전제:
- 확률 가정 없음
- 실제 발생하는 일만 봄
계산:
1번: 1분 대기
2번: 1분 대기
3번: 1분 대기
4번: 5분 대기 ← 한 번만 오래 걸림
5번: 1분 대기
...
10번: 1분 대기
총 시간: 20분
평균: 20분 ÷ 10번 = 2분
예: "가끔 오래 걸리지만, 여러 번 타면 평균 2분"차이 요약
평균 경우:
- "운이 어떨까?" (확률)
- 입력이 랜덤하다고 가정
- 예: "절반쯤에 있을 거야"
상각:
- "여러 번 하면 평균이 어떨까?" (실제)
- 확률 가정 안 함
- 예: "100번 했더니 이렇게 걸렸어"
쉽게:
평균 = 예측 (운에 달림)
상각 = 측정 (실제 평균)실생활 예시
영화관 줄서기
평균 경우:
"줄이 평균적으로 몇 명일까?"
→ 예측, 운에 달림
상각:
"나는 한 달에 4번 가는데, 평균 대기 시간은?"
1번째: 5분
2번째: 3분
3번째: 20분 ← 한 번만 오래 걸림
4번째: 2분
평균: 30분 ÷ 4번 = 7.5분
→ 실제 측정, 여러 번 평균📊 집계 방법 (Aggregate Method)
집계 방법이란?
집계 방법은 가장 직관적인 상각 분석 방법입니다.
방법:
1. n번 연산의 총 비용 계산
2. n으로 나누기
3. 연산 1번의 상각 비용
공식:
상각 비용 = (총 비용) / (연산 횟수)예제 1: 동적 배열
문제 상황:
# 동적 배열 (크기가 자동으로 늘어남)
class DynamicArray:
"""
일반 배열: 크기 고정
[1, 2, 3] ← 3개만 저장 가능
동적 배열: 크기 자동 증가
[1, 2, 3] ← 가득 참
→ 더 큰 배열로 자동 확장!
[1, 2, 3, _, _, _] ← 새 배열 (크기 2배)
"""
def __init__(self):
self.capacity = 1 # 현재 배열 크기
self.size = 0 # 실제 저장된 원소 개수
self.array = [None] * self.capacity
def append(self, item):
"""
원소 추가
케이스 1: 공간 있음 → 빠름 (O(1))
케이스 2: 공간 없음 → 느림 (O(n))
새 배열 만들고 복사해야 함
"""
# 1. 배열이 가득 찼는지 확인
if self.size == self.capacity:
# 가득 참! 크기를 2배로 확장
self._resize()
# 2. 원소 추가 (빠름)
self.array[self.size] = item
self.size += 1
def _resize(self):
"""
배열 크기를 2배로 확장
과정:
1. 2배 큰 새 배열 만들기
2. 기존 원소들을 새 배열로 복사
3. 기존 배열 버리기
시간: O(n) - n개 원소 복사
"""
# 1. 새 크기 = 기존 크기 × 2
self.capacity *= 2
# 2. 새 배열 생성
new_array = [None] * self.capacity
# 3. 기존 원소들 복사 (O(n) 시간)
for i in range(self.size):
new_array[i] = self.array[i]
# 4. 새 배열로 교체
self.array = new_array
# 사용 예시
arr = DynamicArray()
# 1번째 append
arr.append(1) # 크기 1 → 2로 확장 (1개 복사)
# 2번째 append
arr.append(2) # 공간 있음 (빠름)
# 3번째 append
arr.append(3) # 크기 2 → 4로 확장 (2개 복사)
# 4번째 append
arr.append(4) # 공간 있음 (빠름)
# 5번째 append
arr.append(5) # 크기 4 → 8로 확장 (4개 복사)상각 분석 (집계 방법):
n번 append할 때 총 비용 계산:
예: n = 8번 append
연산 크기 확장? 복사 개수 비용
------------------------------------------------
1 1 → 2 1 1
2 없음 0 1
3 2 → 4 2 1 + 2 = 3
4 없음 0 1
5 4 → 8 4 1 + 4 = 5
6 없음 0 1
7 없음 0 1
8 없음 0 1
총 비용 = 1 + 1 + 3 + 1 + 5 + 1 + 1 + 1 = 14
일반화:
n번 append 시, 확장은 log₂(n)번 발생
복사 총 개수: 1 + 2 + 4 + ... + n/2
= 2^0 + 2^1 + 2^2 + ... + 2^(log n - 1)
= n - 1
< n
추가 연산: n번 (각 append마다 1번)
총 비용 = n (추가) + n (복사) = 2n
상각 비용 = 2n / n = 2 = O(1)
결론: append 1번의 상각 비용은 O(1)증명:
def count_operations(n):
"""
n번 append 시 총 연산 횟수 계산
n: append 횟수
Returns: 총 연산 횟수 (복사 + 추가)
"""
total_ops = 0 # 총 연산 횟수
capacity = 1 # 현재 배열 크기
for i in range(1, n + 1):
# 1. 추가 연산 (항상 1번)
total_ops += 1
# 2. 확장이 필요한가?
if i > capacity:
# 확장 필요! 기존 원소들 복사
total_ops += capacity # capacity개 복사
capacity *= 2 # 크기 2배로
print(f"{i}번째 append: 확장 발생! "
f"{capacity//2} → {capacity} "
f"(복사: {capacity//2}개)")
return total_ops
# 테스트
n = 16
total = count_operations(n)
print(f"\n{n}번 append 총 연산: {total}")
print(f"평균 (상각): {total/n:.2f}")
# 출력:
# 1번째 append: 확장 발생! 1 → 2 (복사: 1개)
# 3번째 append: 확장 발생! 2 → 4 (복사: 2개)
# 5번째 append: 확장 발생! 4 → 8 (복사: 4개)
# 9번째 append: 확장 발생! 8 → 16 (복사: 8개)
#
# 16번 append 총 연산: 31
# 평균 (상각): 1.94 ← 거의 2 (O(1))예제 2: 스택의 다중 Pop
문제 상황:
class Stack:
"""
스택: 후입선출(LIFO) 자료구조
연산:
- push(x): 원소 추가 - O(1)
- pop(): 원소 제거 - O(1)
- multipop(k): k개 제거 - O(k) ← 분석 대상
"""
def __init__(self):
self.items = [] # 내부적으로 리스트 사용
def push(self, item):
"""
원소 추가
시간: O(1) - 리스트 끝에 추가
"""
self.items.append(item)
def pop(self):
"""
원소 제거 및 반환
시간: O(1) - 리스트 끝에서 제거
Returns: 제거된 원소 (스택이 비어 있으면 None)
"""
if not self.is_empty():
return self.items.pop()
return None
def multipop(self, k):
"""
k개 원소를 한 번에 제거
k: 제거할 원소 개수
시간: O(min(k, n))
k개 제거하려 해도 n개 밖에 없으면 n개 만
"""
result = []
# k번 반복하거나 스택이 빌 때까지
for _ in range(k):
if self.is_empty():
break # 스택이 비었으면 중단
result.append(self.pop())
return result
def is_empty(self):
"""스택이 비어 있는지 확인"""
return len(self.items) == 0
# 사용 예시
stack = Stack()
# push 5번
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
stack.push(5)
# 스택: [1, 2, 3, 4, 5]
# multipop(3) - 3개 제거
removed = stack.multipop(3)
print(f"제거된 원소: {removed}") # [5, 4, 3]
# 스택: [1, 2]
# multipop(10) - 10개 제거하려 했지만 2개만 있음
removed = stack.multipop(10)
print(f"제거된 원소: {removed}") # [2, 1]
# 스택: []상각 분석:
n번의 연산 (push, pop, multipop 혼합)
질문:
multipop(k)은 O(k)인데,
n번 연산하면 O(nk)?
분석:
핵심 통찰: "원소는 push로만 추가되고, 한 번 제거되면 다시 제거할 수 없다"
n번 연산 중:
- push: 최대 n번 → n개 원소 추가
- pop/multipop: 최대 n개만 제거 가능
(추가된 것만 제거 가능하므로)
총 비용:
- push: n번 × O(1) = O(n)
- pop: 총 n개 제거 × O(1) = O(n)
총 = O(n) + O(n) = O(2n) = O(n)
상각 비용 = O(n) / n = O(1)
각 연산의 상각 비용: O(1)!예시로 확인:
def simulate_stack_operations(operations):
"""
스택 연산 시뮬레이션 및 비용 계산
operations: 연산 리스트 예: [('push', 1), ('multipop', 3), ...]
Returns: 총 연산 비용
"""
stack = Stack()
total_cost = 0 # 총 비용
for op_type, value in operations:
if op_type == 'push':
# push: 비용 1
stack.push(value)
total_cost += 1
print(f"push({value}): 비용 +1, 총 {total_cost}")
elif op_type == 'multipop':
# multipop(k): 비용 = 실제 제거된 개수
before_size = len(stack.items)
stack.multipop(value)
after_size = len(stack.items)
removed_count = before_size - after_size
total_cost += removed_count
print(f"multipop({value}): "
f"{removed_count}개 제거, "
f"비용 +{removed_count}, "
f"총 {total_cost}")
return total_cost
# 테스트
operations = [
('push', 1),
('push', 2),
('push', 3),
('push', 4),
('push', 5), # 5번 push: 비용 5
('multipop', 3), # 3개 제거: 비용 3
('push', 6),
('push', 7), # 2번 push: 비용 2
('multipop', 10), # 4개만 있음: 비용 4
]
total = simulate_stack_operations(operations)
n = len(operations)
print(f"\n총 {n}번 연산, 총 비용: {total}")
print(f"상각 비용: {total/n:.2f}")
# 출력:
# push(1): 비용 +1, 총 1
# push(2): 비용 +1, 총 2
# push(3): 비용 +1, 총 3
# push(4): 비용 +1, 총 4
# push(5): 비용 +1, 총 5
# multipop(3): 3개 제거, 비용 +3, 총 8
# push(6): 비용 +1, 총 9
# push(7): 비용 +1, 총 10
# multipop(10): 4개만 있음, 비용 +4, 총 14
#
# 총 9번 연산, 총 비용: 14
# 상각 비용: 1.56 ← 거의 1.5 (O(1))💰 회계 방법 (Accounting Method)
회계 방법이란?
회계 방법은 각 연산에 "크레딧(신용)"을 할당하는 방법입니다.
비유: 은행 계좌
저렴한 연산:
- 실제 비용: 1원
- 청구 비용: 3원
- 차액 2원 → 저축!
비싼 연산:
- 실제 비용: 100원
- 청구 비용: 3원
- 부족분 97원 → 저축한 돈으로 지불!
핵심:
"저축한 돈(크레딧)이 항상 0 이상이면 청구 비용이 상각 비용!"원리:
각 연산에 상각 비용 할당:
- 실제 비용보다 많이 청구
- 여분의 크레딧 저축
- 비싼 연산 시 크레딧 사용
조건:
크레딧 ≥ 0 (항상!)
→ 상각 비용으로 모든 실제 비용 충당 가능예제: 동적 배열 (회계 방법)
class DynamicArrayWithCredit:
"""
동적 배열 - 크레딧 개념으로 분석
비용 모델:
- 원소 추가: 1 크레딧
- 원소 복사: 1 크레딧
상각 비용 (청구 비용):
- append 한 번: 3 크레딧
크레딧 사용:
- 추가 시: 1 사용
- 나머지 2: 저축 (미래의 복사에 사용)
"""
def __init__(self):
self.capacity = 1
self.size = 0
self.array = [None] * self.capacity
self.total_credit = 0 # 저축된 크레딧 (설명용)
def append(self, item):
"""
원소 추가 (상각 비용: 3)
크레딧 사용:
1. 추가 작업: 1 크레딧
2. 저축: 2 크레딧 (미래의 복사용)
"""
print(f"\n--- append({item}) ---")
print(f"청구: 3 크레딧")
# 1. 추가 작업에 1 크레딧 사용
print(f"사용: 1 크레딧 (추가 작업)")
actual_cost = 1
# 2. 확장이 필요한가?
if self.size == self.capacity:
print(f"확장 필요! {self.capacity} → {self.capacity * 2}")
# 확장 시 복사 비용: size개 복사
copy_cost = self.size
print(f"복사 비용: {copy_cost} 크레딧")
print(f"저축된 크레딧으로 지불: {copy_cost} 크레딧")
# 실제로 저축된 크레딧 사용
self.total_credit -= copy_cost
actual_cost += copy_cost
self._resize()
# 3. 원소 추가
self.array[self.size] = item
self.size += 1
# 4. 나머지 크레딧 저축
# 청구 3 - 사용 actual_cost = 저축
saved = 3 - actual_cost
self.total_credit += saved
print(f"저축: {saved} 크레딧")
print(f"현재 저축 총액: {self.total_credit} 크레딧")
# 검증: 크레딧은 항상 0 이상!
assert self.total_credit >= 0, "크레딧 부족!"
def _resize(self):
"""배열 크기 2배로 확장"""
self.capacity *= 2
new_array = [None] * self.capacity
for i in range(self.size):
new_array[i] = self.array[i]
self.array = new_array
# 시뮬레이션
arr = DynamicArrayWithCredit()
# 8번 append 실행
for i in range(1, 9):
arr.append(i)
# 출력 예시:
# --- append(1) ---
# 청구: 3 크레딧
# 사용: 1 크레딧 (추가 작업)
# 확장 필요! 1 → 2
# 복사 비용: 1 크레딧
# 저축된 크레딧으로 지불: 1 크레딧
# 저축: 1 크레딧 (3 - 1 - 1 = 1)
# 현재 저축 총액: 1 크레딧
#
# --- append(2) ---
# 청구: 3 크레딧
# 사용: 1 크레딧 (추가 작업)
# 저축: 2 크레딧
# 현재 저축 총액: 3 크레딧
#
# --- append(3) ---
# 청구: 3 크레딧
# 사용: 1 크레딧 (추가 작업)
# 확장 필요! 2 → 4
# 복사 비용: 2 크레딧
# 저축된 크레딧으로 지불: 2 크레딧
# 저축: 0 크레딧 (3 - 1 - 2 = 0)
# 현재 저축 총액: 1 크레딧
# ...
# 결론: 크레딧이 항상 0 이상!
# → 상각 비용 3 크레딧 = O(1) 성공!왜 3 크레딧인가?
분석:
append 시:
1. 추가 작업: 1 크레딧 (항상)
2. 저축: 2 크레딧
저축된 2 크레딧의 용도:
- 이 원소를 복사할 때: 1 크레딧
- 이전 원소 하나를 복사할 때: 1 크레딧
확장 시 복사되는 원소들:
- 각 원소는 추가될 때 저축한 1 크레딧
- 이전 원소들도 각자 저축한 1 크레딧
→ 복사 비용 완전히 충당!
수학적:
n개 원소가 있을 때 확장하면
- 복사 비용: n 크레딧
- 저축: n개 원소 × 1 크레딧 = n 크레딧
→ 정확히 일치!⚡ 포텐셜 방법 (Potential Method)
포텐셜 방법이란?
포텐셜 방법은 가장 수학적인 방법으로, "잠재 에너지" 개념을 사용합니다.
비유: 물리학의 위치 에너지
공을 높이 들어올림:
- 에너지를 저장 (포텐셜 증가)
- 나중에 떨어뜨리면 에너지 방출
알고리즘:
- 저렴한 연산: 포텐셜 증가 (에너지 저장)
- 비싼 연산: 포텐셜 감소 (에너지 사용)정의:
Φ(D): 자료구조 D의 포텐셜 함수
조건:
1. Φ(D₀) = 0 (초기 상태)
2. Φ(Dᵢ) ≥ 0 (항상 음수 아님)
상각 비용:
ĉᵢ = cᵢ + Φ(Dᵢ) - Φ(Dᵢ₋₁)
여기서:
- cᵢ: i번째 연산의 실제 비용
- Φ(Dᵢ) - Φ(Dᵢ₋₁): 포텐셜 변화예제: 동적 배열 (포텐셜 방법)
포텐셜 함수 정의:
Φ(D) = 2 × size - capacity
직관:
- size가 capacity에 가까우면 → Φ 증가 (확장이 임박, 에너지 저장)
- 확장 직후 → Φ 감소 (에너지 방출)분석:
class DynamicArrayWithPotential:
"""
동적 배열 - 포텐셜 방법으로 분석
포텐셜 함수:
Φ(D) = 2 × size - capacity
초기: size=0, capacity=1
→ Φ = 2×0 - 1 = -1 (음수!)
수정: Φ(D) = 2 × size - capacity + 1
→ 초기 Φ = 2×0 - 1 + 1 = 0 ✓
"""
def __init__(self):
self.capacity = 1
self.size = 0
self.array = [None] * self.capacity
def potential(self):
"""
현재 포텐셜 계산
Returns: 2 × size - capacity + 1
"""
return 2 * self.size - self.capacity + 1
def append_with_analysis(self, item):
"""
append 연산의 상각 비용 계산
상각 비용 = 실제 비용 + 포텐셜 변화
"""
print(f"\n--- append({item}) ---")
# 1. 현재 포텐셜
phi_before = self.potential()
print(f"이전 포텐셜: {phi_before}")
print(f" (size={self.size}, capacity={self.capacity})")
# 2. 실제 비용 계산
actual_cost = 1 # 추가 작업
if self.size == self.capacity:
# 확장 필요
print(f"확장 발생!")
actual_cost += self.size # 복사 비용
self._resize()
# 3. 원소 추가
self.array[self.size] = item
self.size += 1
# 4. 새 포텐셜
phi_after = self.potential()
print(f"이후 포텐셜: {phi_after}")
print(f" (size={self.size}, capacity={self.capacity})")
# 5. 상각 비용
phi_change = phi_after - phi_before
amortized_cost = actual_cost + phi_change
print(f"실제 비용: {actual_cost}")
print(f"포텐셜 변화: {phi_change}")
print(f"상각 비용: {amortized_cost}")
return amortized_cost
def _resize(self):
"""배열 크기 2배로 확장"""
self.capacity *= 2
new_array = [None] * self.capacity
for i in range(self.size):
new_array[i] = self.array[i]
self.array = new_array
# 시뮬레이션
arr = DynamicArrayWithPotential()
total_amortized = 0
for i in range(1, 9):
cost = arr.append_with_analysis(i)
total_amortized += cost
print(f"\n총 상각 비용: {total_amortized}")
print(f"평균: {total_amortized / 8:.2f}")
# 출력 예시:
# --- append(1) ---
# 이전 포텐셜: 0
# (size=0, capacity=1)
# 확장 발생!
# 이후 포텐셜: 2
# (size=1, capacity=2)
# 실제 비용: 1 (확장 시 복사할 원소 없음)
# 포텐셜 변화: 2
# 상각 비용: 3
#
# --- append(2) ---
# 이전 포텐셜: 2
# (size=1, capacity=2)
# 이후 포텐셜: 3
# (size=2, capacity=2)
# 실제 비용: 1
# 포텐셜 변화: 1
# 상각 비용: 2
#
# --- append(3) ---
# 이전 포텐셜: 3
# (size=2, capacity=2)
# 확장 발생!
# 이후 포텐셜: 2
# (size=3, capacity=4)
# 실제 비용: 3 (1 추가 + 2 복사)
# 포텐셜 변화: -1
# 상각 비용: 2
# ...수학적 분석:
케이스 1: 확장 없음 (size < capacity)
실제 비용: c = 1
포텐셜 변화: Φ(Dᵢ) - Φ(Dᵢ₋₁)
= (2×size - capacity + 1) - (2×(size-1) - capacity + 1)
= 2×size - 2×size + 2
= 2
상각 비용: ĉ = 1 + 2 = 3
케이스 2: 확장 발생 (size = capacity)
실제 비용: c = 1 + size (추가 + 복사)
포텐셜 변화:
이전: Φ(Dᵢ₋₁) = 2×size - size + 1 = size + 1
이후: Φ(Dᵢ) = 2×(size+1) - 2×size + 1
= 2×size + 2 - 2×size + 1
= 3
변화: 3 - (size + 1) = 2 - size
상각 비용: ĉ = (1 + size) + (2 - size)
= 3
결론: 모든 경우 상각 비용 = 3 = O(1)!📊 세 가지 방법 비교
비교 표
방법 직관성 수학적 엄밀성 사용 난이도
----------------------------------------------------------
집계 방법 높음 중간 쉬움
회계 방법 중간 중간 중간
포텐셜 방법 낮음 높음 어려움
추천:
- 입문: 집계 방법
- 실무: 회계 방법
- 연구: 포텐셜 방법동일한 문제, 다른 접근
# 동적 배열의 상각 비용: 모두 O(1)
# 1. 집계 방법
# "n번 연산의 총 비용을 세자"
# 총 비용: 2n
# 평균: 2n/n = 2 = O(1)
# 2. 회계 방법
# "각 연산에 3 크레딧을 청구하자"
# 1 크레딧: 추가
# 2 크레딧: 저축 (복사용)
# 항상 충분! → O(1)
# 3. 포텐셜 방법
# "Φ(D) = 2×size - capacity + 1"
# 실제 비용 + 포텐셜 변화 = 3
# → O(1)
# 결론: 모두 같은 답! O(1)💡 실무 팁
언제 상각 분석을 사용하는가?
# 사용해야 할 때:
# 1. 가끔 비싼 연산이 있는 경우
# 예: 동적 배열 append
# 2. 연속된 연산을 분석할 때
# 예: n번 연산의 총 비용
# 3. 최악의 경우가 너무 비관적일 때
# 예: multipop은 O(k)지만 상각 O(1)
# 사용하지 않아야 할 때:
# 1. 단일 연산만 볼 때
# 예: 한 번만 append → O(n) 가능
# 2. 최악의 경우가 중요할 때
# 예: 실시간 시스템 (지연 시간 보장)
# 3. 독립적인 연산들
# 예: 서로 영향 없는 연산Python 내장 자료구조
# Python의 list
# - append: 상각 O(1)
# - insert(0, x): O(n) (상각 아님!)
arr = []
arr.append(1) # 빠름 (상각 O(1))
arr.insert(0, 1) # 느림 (O(n))
# collections.deque (양방향 큐)
# - append: O(1)
# - appendleft: O(1) (양쪽 모두 빠름!)
from collections import deque
dq = deque()
dq.append(1) # 빠름
dq.appendleft(1) # 빠름!
# dict
# - 삽입: 상각 O(1)
# - 조회: 평균 O(1), 최악 O(n)
d = {}
d['key'] = 'value' # 상각 O(1)🎯 핵심 정리
상각 분석의 본질
목적:
- 여러 연산의 평균 비용 계산
- 가끔 발생하는 비싼 연산 포함
vs 평균 경우:
- 평균: 확률 분포 가정
- 상각: 확률 무관, 연속 연산세 가지 방법
1. 집계 방법 (Aggregate):
총 비용 / 연산 횟수
→ 가장 직관적
2. 회계 방법 (Accounting):
크레딧으로 비용 관리
→ 실무적
3. 포텐셜 방법 (Potential):
수학적 함수로 분석
→ 가장 엄밀대표 예시
동적 배열 append:
- 최악: O(n) (재할당)
- 상각: O(1)
- 이유: 재할당이 드물게 발생
스택 multipop:
- 최악: O(k)
- 상각: O(1)
- 이유: 추가된 것만 제거 가능실무 적용
Python list:
- append: 상각 O(1) ✓
- insert(0): O(n) (상각 아님) ✗
실시간 시스템:
- 상각 분석 신중히
- 최악의 경우도 중요!알고리즘 분석 섹션 완료!
지금까지 배운 내용:
- 시간 복잡도: 알고리즘이 얼마나 빠른가
- 공간 복잡도: 메모리를 얼마나 사용하는가
- 점근적 표기법: Big-O, Big-Ω, Big-Θ의 수학적 의미
- 최선/평균/최악 분석: 입력에 따른 성능 차이
- 상수 계수와 실제 성능: 이론과 실제의 간극
- 상각 분석: 여러 연산의 평균 비용
🔗 다음 글에서는
다음 섹션: [08] 계산 복잡도 이론
이제 알고리즘이 아닌 문제 자체의 난이도를 분석합니다.
[08-01] 결정 문제 (Decision Problems)
- 결정 문제의 정의: 답이 Yes 또는 No인 문제로 복잡도 이론의 기본 단위
- 최적화 문제 변환: "최단 경로는?"을 "k 이하 경로가 있나?"로 바꾸는 방법
- 형식 언어 표현: 문제를 수학적으로 엄밀하게 정의하는 집합론적 접근
- 이진 탐색 활용: 결정 문제를 반복해서 풀어 최적값 찾기
이전 글: [07-05] 상수 계수와 실제 성능
다음 글: [08-01] 결정 문제
시리즈: P1. Computer Science
AI 전문가를 꿈꾸는 도전자