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

답 말고 더 쓰는 칸

숫자 여섯 개 가운데 가장 큰 값을 찾는다고 하자. 답은 결국 숫자 하나지만 찾아가는 과정은 풀이마다 다르다. 어떤 풀이는 지금까지 본 가장 큰 값을 메모지 한 장에 적어 두고, 더 큰 수가 나오면 그 자리에 고쳐 쓴다. 메모지는 끝까지 한 장이다. 더 큰 수가 나올 때마다 새 칸에 적어 두는 풀이라면 칸이 그만큼 늘고, 숫자들을 큰 순서로 늘어놓으려고 통째로 베껴 적는 풀이라면 입력만큼 칸이 더 든다. 이렇게 답을 만드는 동안 끄적이는 임시 칸이 자리값이에요. 입력은 어차피 받은 것이라 비용으로 세지 않고, 알고리즘이 그 위에 더 펼친 칸만 센다.

입력(금색)은 받은 것이라 비용이 아니다. 임시 칸 켜기를 누르면, 더 큰 수가 나올 때마다 새 칸에 적어 둔 기록(파랑)이 나타난다. 비용으로 세는 것은 이 추가 칸뿐이에요.

자리값을 잴 때 입력을 빼고 추가 칸만 보는 것은 공정하게 견주기 위해서다. 같은 입력을 받은 두 풀이를 비교하려면 각자 더 쓴 칸만 세야 한다. 그렇다면 메모지 한 장으로 푸는 풀이가 늘 더 좋을까요? 자리를 아끼면 다른 데서 손해를 보지는 않을까? 다음은 시간과 자리 사이의 거래다.

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

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

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

어느 한쪽이 늘 옳은 것이 아니라 상황에 따라 고른다. 자주 물어볼 거라면 표를 만들어 자리를 내주는 편이 이득이고, 자리가 빠듯하면 조금 느려도 표 없이 푸는 편이 낫다. 그렇다면 자리를 아낀다는 것은 구체적으로 무엇일까요? 정렬처럼 흔한 일에서 추가 자리를 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))까지 이어지면 공간 복잡도가 한 장에 정리돼요.

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