공간 복잡도: 자리도 비용이다

답 말고도 알고리즘이 더 쓰는 칸

숫자 여섯 개에서 가장 큰 값을 찾는다고 해 봐요. 답은 결국 숫자 하나죠. 하지만 그 답을 찾는 동안, 어떤 풀이는 작은 메모지 한 장에 지금까지 본 것 중 가장 큰 값을 적어 두고 새 숫자가 나올 때마다 고쳐 써요. 메모지는 늘 한 장이에요. 또 다른 풀이는 큰 순서대로 다시 늘어놓으려고 숫자들을 통째로 한 번 더 베껴 적어요. 이렇게 답 자체가 아니라, 답을 만드는 과정에서 끄적이는 임시 칸들이 바로 자리값이에요. 입력은 어차피 받은 거라 비용으로 안 세고, 그 위에 알고리즘이 더 펼친 칸만 셉니다.

입력(금색)은 그냥 받은 거예요. 임시 칸 켜기를 눌러 알고리즘이 답 말고 더 펼친 칸(파랑)을 보세요. 비용으로 세는 건 이 추가 칸뿐이에요.

자리값을 잴 땐 입력은 빼고 추가 칸만 본다는 게 핵심이에요. 그래야 같은 입력을 받은 두 풀이를 공정하게 비교할 수 있거든요. 그런데 한번 생각해 봐요. 메모지 한 장으로 푸는 풀이가 늘 더 좋은 걸까요? 자리를 아끼면 뭔가 다른 데서 손해를 보는 건 아닐까요? 다음에서 시간과 자리 사이의 거래를 봅시다.

자리를 더 쓰면 빨라지고, 아끼면 느려진다 (맞바꿈)

같은 문제를 두고도, 자리를 어떻게 쓰느냐에 따라 빠르기가 달라져요. 예를 들어 어떤 값을 자주 물어봐야 한다고 해 봐요. 한 가지 방법은 답을 미리 다 계산해서 표로 적어 두는 거예요. 물어볼 때마다 표를 한 번 보면 끝이라 아주 빨라요. 대신 그 표를 담을 자리를 따로 내줘야 하죠. 다른 방법은 표를 안 만들고, 물어볼 때마다 처음부터 다시 계산하는 거예요. 자리는 거의 안 들지만, 매번 같은 일을 반복해서 느려요. 자리를 내주고 시간을 벌거나, 시간을 내주고 자리를 아끼거나. 이걸 시간과 공간의 맞바꿈이라고 해요.

자리 더 쓰기와 자리 아끼기를 눌러 보세요. 미리 표를 둔 쪽(파랑)은 자리를 많이 쓰고 빠르고, 표 없이 매번 세는 쪽(금색)은 자리를 아끼고 느려요. 같은 문제, 다른 거래.

한쪽이 무조건 옳은 게 아니라 상황에 따라 고른다는 걸 봤어요. 자주 물어볼 거면 표를 만들어 자리를 내주는 게 이득이고, 자리가 빠듯하면 좀 느려도 표 없이 푸는 게 나아요. 그런데 자리를 아낀다는 게 구체적으로 뭘까요? 정렬 같은 흔한 작업에서, 자리를 아예 0칸 더 쓰는 풀이와 입력만큼 한 벌 더 쓰는 풀이를 나란히 놓고 비교해 봅시다.

제자리에서 풀기 vs 복사본 만들기

흩어진 숫자들을 작은 순서대로 줄 세운다고 해 봐요. 한 가지 방법은 받은 칸들 안에서 두 숫자의 자리를 서로 바꿔 가며 정리하는 거예요. 새 칸을 단 하나도 안 만들고, 가진 칸 안에서 위치만 바꾸죠. 이걸 제자리 정렬이라고 하고, 추가 자리는 0이에요. 다른 방법은 빈 칸을 입력 개수만큼 새로 마련하고, 작은 것부터 골라 그 새 칸에 옮겨 담는 거예요. 결과는 똑같이 정렬된 줄이지만, 입력만큼 자리를 한 벌 더 썼어요. 추가 자리가 입력 크기만큼 들죠. 두 풀이 다 정답을 내지만, 자리값은 0이냐 입력만큼이냐로 크게 달라요.

제자리 정렬과 복사본 만들기를 골라 정렬 실행을 눌러 보세요. 제자리(금색)는 같은 칸에서 자리만 바꿔 추가 0칸, 복사본(파랑)은 새 칸을 입력만큼 만들어요. 결과는 같아도 자리값이 달라요.

제자리는 추가 0칸, 복사본은 입력만큼. 같은 답인데 자리값이 분명히 갈렸죠. 그런데 0칸과 입력만큼이라는 이 표현, 어딘가 익숙하지 않나요? 지난 강에서 시간을 잴 때 입력이 커져도 일이 안 늘면 어떻고, 입력만큼 늘면 어떻다고 했었죠. 바로 그 렌즈를 자리에 그대로 갖다 댈 수 있어요. 다음에서 입력을 키워 가며 추가 자리가 어떻게 자라는지 봅시다.

자리도 입력 따라 늘어요 (O(1) 또는 O(n))

지난 강의 빅오는 입력이 커질 때 시간이 어떻게 자라는지를 한 글자로 요약한 거였어요. 똑같은 요약을 자리에도 써요. 메모지 한 장으로 가장 큰 값을 찾는 풀이는, 입력이 여섯 개든 백 개든 추가 칸이 늘 한 칸이에요. 입력이 아무리 커져도 추가 자리는 그대로니, 이걸 O(1) 공간이라고 해요. 반면 복사본을 만드는 풀이는 입력이 두 배가 되면 새 칸도 두 배가 돼요. 추가 자리가 입력에 정비례해 자라니, 이건 O(n) 공간이에요. 핵심은 빅오라는 같은 도구로, 이번엔 시간이 아니라 자리가 자라는 모양을 잰다는 거예요.

입력 키우기를 눌러 n을 키워 보세요. O(1)(금색)은 입력이 커져도 추가 칸이 늘 하나, O(n)(파랑)은 입력만큼 같이 늘어나요. 빅오를 자리에 그대로 적용한 거예요.

같은 빅오 표기인데, 이번엔 시간이 아니라 자리에 붙었죠. O(1)이면 입력이 아무리 커도 추가 자리는 작은 상수로 묶여 있고, O(n)이면 입력과 나란히 커져요. 이렇게 우리는 알고리즘 하나를 두 눈으로 보게 됐어요. 시간은 얼마나 걸리나, 자리는 얼마나 쓰나. 이제 이 둘을 한 줄로 정리해 봅시다.

정리: 알고리즘을 보는 두 번째 눈

전체를 한 줄로 보면 이래요. 알고리즘은 답을 내는 동안 답 말고도 임시 칸을 써요. 그 추가 칸이 자리값이고, 입력은 비용에서 빼요. 자리와 시간은 자주 맞바꿔져서, 표를 미리 만들어 자리를 더 쓰면 빨라지고 제자리에서 풀어 자리를 아끼면 느려져요. 그리고 추가 자리도 입력 따라 자라요. 늘 한 칸이면 O(1), 입력만큼이면 O(n)이죠. 그러니까 좋은 알고리즘을 고를 땐 빠르기 하나만 보면 안 돼요. 얼마나 빠른가와 얼마나 자리를 쓰는가, 두 눈으로 함께 봐야 비로소 제대로 고를 수 있어요. 메모리가 빠듯한 작은 기기에서는 느려도 자리를 아끼는 풀이가 정답일 때가 많거든요.

네 단계를 차례로 눌러 한 줄로 꿰어 보세요. 답 말고 더 쓰는 칸, 자리↔시간 맞바꿈, 제자리 vs 복사본, 자리도 입력 따라(O(1)/O(n))까지. 공간 복잡도가 한 장으로 정리돼요.

이제 우리는 알고리즘을 시간과 자리, 두 잣대로 함께 잴 수 있게 됐어요. 같은 답을 내는 여러 풀이 가운데, 무엇을 어떤 상황에서 고를지 판단할 눈이 생긴 거죠. 빠르기만이 아니라 자리값까지 저울에 올리면, 비로소 알고리즘을 어른스럽게 고르는 셈이에요. 다음 강에서는 이 두 잣대를 들고, 실제 문제를 더 영리하게 푸는 방법들로 한 걸음 더 들어가 봅니다.