분할 상환 분석 (Amortized Analysis) - 개념과 예시

개념

분할 상환 분석(Amortized Analysis)은 알고리즘이나 자료구조에서 여러 연산의 평균적인 실행 시간을 분석하는 기법이다. 특정 연산 하나의 최악의 경우가 아니라, 일련의 연산 전체를 고려해 평균적으로 한 번의 연산이 얼마만큼의 비용이 드는지를 평가한다.

• 평균 시간 복잡도와는 다르다: 입력 분포가 아닌, 연산 시퀀스 전체의 누적 비용을 나누는 방식
• 대표적인 예: 동적 배열의 크기 증가, 두 스택으로 큐 구현 등

분석 방법

1. Aggregate Method (총합법)
   • 전체 연산의 총 비용을 계산한 뒤, 연산 수로 나눔
2. Accounting Method (계좌법)
   • 각 연산에 가상의 비용(크레딧)을 할당해, 비싼 연산의 비용을 싼 연산이 미리 일부 부담
3. Potential Method (잠재적 에너지법)
   • 자료구조의 상태에 따라 잠재적 에너지를 정의하고, 연산마다 변화량을 계산

예시: 동적 배열의 삽입

동적 배열(예: vector, ArrayList 등)은 공간이 부족할 때마다 크기를 두 배로 늘린다.

• 대부분의 삽입은 O(1)이지만, 크기 확장 시 O(n) 복사가 필요
• 하지만 n번의 삽입 전체를 보면, 평균적으로 한 번의 삽입은 O(1)

간단한 증명 (Aggregate Method)

• 크기가 1, 2, 4, 8, …로 증가할 때마다 전체 복사 비용은 1+2+4+…+n = O(n)
• n번 삽입의 총 비용은 O(n), 평균은 O(1)

실전 예시: 두 스택으로 큐 구현

• LeetCode 232번 문제(Implement Queue using Stacks)에서 pop/peek 연산의 평균 시간 복잡도도 O(1)
• 비싼 연산이 가끔 발생하지만, 전체적으로 보면 저렴한 연산이 많아 평균이 낮아짐

마치며

분할 상환 분석은 자료구조의 효율성을 제대로 이해하고 설명하는 데 필수다.
실제 코딩 테스트나 면접에서도 자주 등장하니, 개념과 대표 예시를 꼭 익혀두자!

---

작성일: 2025.06.22
작성자: Cho Donghyun (Unity 클라이언트 개발자 지망생)

• algorithm
• 자료구조
• 분석