"좋은 알고리즘을 평가하는 또 하나의 기준"
Intro
오늘은 지난 번에 다뤘던 시간 복잡도와 함께 좋은 알고리즘을 평가하는 또 하나의 기준인 공간 복잡도를 간략하게 다뤄보려고 합니다.
알고리즘과 관련하여 단순하게 복잡도라고 말할 때는 주로 공간 복잡도가 아닌 시간 복잡도를 의미한다고 하는데요. 상대적으로 공간 복잡도가 조금 덜 중요하게 판단된다고도 볼 수 있습니다.
그래서인지 위키백과의 설명도 번역본 없이 영어로만 이루어져 있더라구요. 시간 복잡도는 번역이 다 되어있는데 말이죠. 어려운 내용을 완전히 다 이해해야만 하는 것은 아니니 공간 복잡도를 어떻게 설명하고 있는지만 인용해보도록 하겠습니다.
The space complexity of an algorithm or a computer program is the amount of memory space required to solve an instance of the computational problem as a function of characteristics of the input. It is the memory required by an algorithm until it executes completely.
공간 복잡도
공간 복잡도는 어떤 문제를 연산하는데 필요한 메모리의 양을 말합니다. 컴퓨터는 문제를 해결할 때 연산을 반복해서 진행하고(시간 복잡도), 필요한 정보들을 메모리에 저장해서(공간 복잡도) 활용하는데요. 이 두 가지가 작을 수록 좋은 알고리즘이라고 할 수 있는 것이죠.
시간 복잡도와 마찬가지로 공간 복잡도를 나타낼 때에도 Big O Notation (표기법) 을 사용한다고 합니다. 참고로 복잡도는 보통 최악의 경우를 기준으로 산정하기 때문에 늘 그 정도의 시간이나 메모리를 필요로 하는 것은 아닙니다. 가능한 가장 안 좋은 경우를 대비한다고 이해할 수 있겠네요.
앞서 말한 것처럼 시간 복잡도에 비해 상대적으로 덜 중요하게 여겨지는 탓에, 시간 복잡도를 줄이기 위해 공간 복잡도를 인위적으로 늘리는 접근 방법도 있다고 합니다. 그런 방법 중 하나가 앞서서 시간복잡도에서도 언급했던 메모이제이션 이라는 기법이라고 하네요.
메모이제이션
메모이제이션은 한 번 구한 결과를 메모리에 저장하고서 필요할 때 다시 가져오는 것을 말합니다. 똑같은 연산을 반복하는 대신, 메모리에 저장해두고 필요할 때 꺼내 쓰는 것이죠. 반복 연산이 줄어들어 시간 복잡도가 내려가는 대신, 그만큼 메모리의 공간을 차지하기 때문에 공간 복잡도는 늘어나는 것이라고 이해할 수 있습니다.
메모이제이션을 위해 자주 사용되는 것이 배열입니다. 그런 만큼 배열을 잘 다룰 수 있어야 효과적인 알고리즘 구현이 한층 더 쉬워지는데요. 생성하고 (new Array), 채워넣고(fill), 값을 넣고(push, unshift) 빼는(pop, shift) 배열의 기초와 그 외의 배열 관련된 메소드들을 잘 활용할 수 있어야 하겠습니다.
참고 자료
"이것이 취업을 위한 코딩 테스트다" written by 나동빈, 한빛미디어
