Cost Amortization

원래 경영쪽 용어로 알고 있는데, Cost amortization은 어떤 큰 지출을 여러달 (또는 시간, 일, 년도등 맘대로) 에 나눠서 적는걸 말한다. 예를들어 적당히 큰 회사가 슬랙 메신저의 standard 플랜을 구독한다고 생각해보자. 지금 얘네들 가격 정책에 따르면 한 명의 액티브 유저당 한달에 $6.67를 1년마다 지불하게 되어있는데, 이걸 고대로 장부에 적으면 11개월동안 아무 일 없이 잠잠하다가 12개월째 되는달에 수백 달러를 지출하는 꼴이 되어버린다. 이러면 보기에도 안 좋고 달마다 얼마나 썼는지 알 수도 없으니 이 금액을 나머지 잠잠한 11개월에 적당히 뚝 떼어서 공평하게 나눠서 적는다. 대충 이런식인걸로 알고 있다.

하지만 원래 뜻을 알기 전에는 computer science쪽 용어인줄 알고 있었는데, 2013년에 자료구조 수업에서 교수님이 컴퓨터쪽 용어의 의미를 잠깐 설명해줬지만 듣자마자 까먹었기 때문인듯.

CS에서의 Amortized analysis도 위에서 대충 설명한 경영쪽 의미랑 비슷한데, (여기에서의 비용은 시간 복잡도) 마찬가지로 어떤 연산의 실제 비용을 다른 연산에 부과하는걸로 퉁치는 방법이다. 수업시간에 교수님이 설명했던 예시를 고대로 컨닝하기엔 문맥이 필요해서 위키에 있는 예시를 훔쳐오자면, 예를들어 어떤 동적 배열에 원소를 하나씩 집어넣는다고 생각해보자. 처음에 동적 배열 크기는 적당히 4로 해놨을때 1, 2, 3, 4 번째 원소를 넣는 연산에는 각각 상수시간 O(1)이 걸린다. 그러다 5번째 원소를 집어넣기 위해선 동적배열은 다음과 같은 동작을 하게 되는데

1. 두배크기의 새로운 배열을 할당 받고 (더블링)
2. 지금까지 있던 모든 값들을 그놈의 새로운 배열에 전부 복붙한 다음
3. 기존 배열을 해제하고
4. 원소를 넣는다

1,3 번은 OS나 VM이 알아서 해줄테니 논외로 치고, 4번은 알다시피 금방 할 수 있는데, 2번을 하는데 O(n)의 시간이 들어간다. 그럼 이 동적 배열 원소 삽입 알고리즘은 최악의 경우에 O(n)의 복잡도를 가지게 되는데, 이게 좀 생각해보면 억울하다고 생각할 수 있다. 사실 더블링도 나중에 가면 그렇게 많이 일어나는 일도 아니고 어쩌다 한번 공간이 부족해서 좀 오래 걸린다는데 O(n) 취급 받기엔 좀 그렇기도 하니. 그래서 더블링에 들어가는 O(n) 의 비용을 그 앞에 있던 n번의 삽입 연산에 나눠서 부과하는걸로 생각하기로 해서 평균적으로 각각의 삽입 연산이 O(n/n) => O(1)인걸로 하자는 이야기다.

무슨 이상한 사기꾼이 나와서 이리저리 퉁쳐서 있던 빚을 없애는것 같은 느낌이지만, 위의 동적할당 예시나 (이번엔 수업자료를 컨닝하자면) 정렬처럼 개별 연산이 중요하다기보단 전체적으로 걸리는 시간이 더 중요한 경우에는 이렇게 amortization을 적용하는게 더 현실적이라는 말.

이게 생각난 이유는.. 며칠전에 월급 들어와서 지난달 지출 내역을 정리하고 있었는데 지출 내역에 현금 지출로 12,000원이 찍혀있었다. 생각해보니 여자친구랑 같이 넷플릭스 12,000원 요금제로 같이 보기로 해놓고 돈을 줘야 했던 상황이었는데, 당시 가지고 있던 현금으로 6,000원을 만들 수 없는 상황이라 그냥 만 이천원 줘 버리고 '11월달거 먼저 낸걸로 하자'라고 했었고, amortization이 생각나서 이번달 지출에 6,000원을 적어놓고 다음달 지출 항목으로 6,000원을 적어놨기 때문이다. 미드나 봐야지.