공부할 겸 알고리즘을 풀면서 해당 요구조건이 있었다.
Follow up: Could you implement a solution that runs in O(n) time complexity and O(1) space complexity?
후속방안 : O(n) 시간복잡도와 O(1) 공간복잡도로 문제를 해결할 수 있는가?
해당 문제는 이 링크에 존재하며, 추가적인 요구조건으로 시간복잡도와 공간복잡도를 제시했다. 대부분 국내 코딩테스트가 시간복잡도만 보지만, 해외의 경우 이와 같이 공간복잡도도 함께 요구한다.
이 글에서는 두 개념에 대해 조금 심도있게 다루고자 한다. 조금 심화내용에 관심이 있거나, 해당 개념을 확실하게 끝내고 싶은 분, 그리고 면접에 대비할 생각이라면 한번 보고 넘어갔으면 한다.
복잡도의 개념과 목적
아마 대다수가 알겠지만 일단 개념을 간단히 정리하고 가겠다.
시간복잡도: 입력값과 수행 시간의 관계
공간복잡도: 입력값과 사용된 자원의 관계
'복잡도'라고 언급한 만큼 이 수치가 낮을수록 좋다. 그만큼 사용하는 자원의 양이 줄어든다. 이 값은 입력값 n 에 대한 복잡도를 표한하는 빅오표기법[O(n)]으로 나타낸다. 빅오표기법의 결과값은 다음과 같이 나타낸다.
O(log n) <
코드로 표현되는 복잡도
이 복잡도를 이해하기 쉬운 예시가 바로 피보나치 수이다. 피보나치 수열을 통하여 시간복잡도와 공간복잡도를 전부 설명할 예정이다. 피보나치 수의 원리를 설명하면 다음과 같다.
f(1) = 1, f(2) = 1
f(n) = f(n-1) + f(n-2) (단, n > 2)
피보나치 수열은 이 조건을 만족하는 값을 말한다. f(3)은 간단히 f(2) + f(1)를 하면 된다. 그 이상의 수는 이전에 사용한 값을 쓰면서 계산한다.
이 피보나치 수열이 유명한 이유는 바로 재귀를 사용했을 때와 반복문을 사용했을 때 값이 다르기 때문이다. 일단 한번 코드로 이해해보자.
먼저 재귀를 사용했을 때다. 재귀를 사용했을때 가장 큰 장점은 사람의 관점에서 코드해석이 쉽다는 것이다.
def Fibonacci(n: int) -> int:
if n <= 2: return 1
return Fibonacci(n-1) + Fibonacci(n-2)
구현하는데 단 두 줄이면 충분하다. 해석도 금방 가능하다. 하지만 사람이 해석하기 쉽다해서 꼭 좋은 코드는 아니다. 이 코드의 시간복잡도와 공간복잡도는 무려 O(2^n)이다.
일단 n <= 2일 경우 함수를 한번만 사용하기에 넘어간다. 그러나 n=3일 경우 2번, n=4일경우 4번, n=5일경우 8번을 사용하게 된다. 이렇듯 n이 늘어날 수록 연산횟수는 기하급수적으로 늘어난다.
이 원인은 한번 했던 계산을 다시하는데 있다. 간단히 f(6)을 구할 때 f(3)을 3번이나 새로 계산한다. 명확한 자원낭비라고 볼 수 있다.
해당 단점을 해결하기 위해서 피보나치는 반복문을 사용하는게 더 좋다. 해당 함수는 시간복잡도는 O(n), 공간복잡도는 O(1)을 만족한다.
def Fibonacci(n : int) -> int:
if n <= 2: return 1
result, prev, prev_prev = 0, 1, 1
for _ in range(n-2):
result = prev + prev_prev
prev_prev = prev
prev = result
return result
여기서 개선의 여지는 없는가? 만약 n의 값을 한정시킬수 있다면 나는 시간복잡도를 O(1)로 만들 수 있다. 이 경우 공간 복잡도는 O(k)(k는 n의 최댓값)이 된다.
나는 처음에 시간과 공간복잡도 모두 O(n)인 결과를 만들었다. 배열을 하나 만들고 [f(1), f(2), f(3), f(4), ... , f(n-1)]을 저장하는 형식이다. 하지만 매번 배열을 만들기에 시간복잡도가 O(n)이 된다. 그리고 이 배열을 재활용을 할 수 있다면 시간복잡도를 O(1)로 줄이는게 가능하다 생각했다.
def Fibonacci(input : int) -> int:
fibonacci_memory = [1, 1]
def inner_fibonacci(n : int) -> int:
while len(fibonacci_memory) < n:
fibonacci_memory.append(fibonacci_memory[-1] + fibonacci_memory[-2])
return fibonacci_memory[n-1]
return inner_fibonacci(input)
위의 함수는 '클로저'라는 지식을 이용해서 구성했다. 자바스크립트에서 배운 개념이지만, 정말 많이 쓰이는 지식 중 하나다. fibonacci_memory라는 변수는 전역변수가 아니라 오직 피보나치를 계산할 때만 쓰인다.
이 계산의 경우 처음에는 O(n)의 시간복잡도를 가지지만, 점차 O(1)의 시간복잡도를 갖춰간다. 이는 한번 경험했던 수는 다시 계산하지 않는 방식이다. 그러나 공간복잡도의 경우 기존에 입력했던 가장 큰 n값을 가지게 된다.
이 두 가지 방법은 시간복잡도와 공간복잡도 중 더 우선시하는 곳에 맞춰 사용하면 된다. 시간복잡도가 낮은게 중요한 코딩테스트의 경우 내가 쓰는 방법이 더 좋을 것이다. 그러나 메모리 자원이 한정된 곳은 기존의 방법인 공간복잡도가 O(1)인 방법이 더 좋다. 그럼 어디는 공간복잡도가 우선시 되고, 어디는 시간복잡도가 우선시 될까?
시간복잡도는 프로세스(CPU)의 성능, 공간복잡도는 메모리(RAM)의 성능에 좌우된다. 여기까지는 다 이해했을 것이다. 그래서 빠른 반응이 필요한 곳은 시간복잡도, 공간을 아껴야 하는 곳은 공간복잡도가 중요해진다.
먼저 시간복잡도를 보자. 시간복잡도가 좋을 수록 연산시간이 확 줄어든다는건 누구나 알 것이다. 그리고 대부분의 서비스는 이 시간복잡도를 중요시한다. 우리가 쓰는 어플이나 메신저, 게임등은 모두 얼마나 빠르게 반응하는지가 관건이다. 즉, 서비스를 하는 서버에서는 시간복잡도와 프로세서를 중요시한다. 대부분의 국내 서비스가 사용자 입장으로 설계된 만큼, 코딩테스트에서도 이 부분을 중요하게 본다.
그럼 공간복잡도는 어떨까? 해외코테를 보면 이 공간복잡도를 요구하는 경우를 적지않게 볼 수 있다. 임베디드 시스템에서는 이 공간복잡도가 중요한 건 예측이 간다. 그러나 나는 최근에 유행하는 딥러닝에 이 공간복잡도가 중요하다고 느껴진다.
딥러닝을 하는 분의 경우 가장 많이 보는 것이 바로 메모리 관련 오류다. 딥러닝의 경우 학습을 위해 Ram에 저장된 가중치를 VRAM에 옮겨야 하는데, VRAM의 용량은 한정되어 있다. 램과 달리 VRAM은 늘리기 힘든 자원중에 하나다. 그래서 코드를 통해서 이 공간복잡도를 줄여야한다. 주로 배치사이즈를 줄이거나, 가중치 갯수를 줄이는 등의 방법으로 공간을 절약한다.
처음에는 복잡도에 대해 간단히 정리해보려고 글을 시작했다. 그러나 이틀동안 약간 텀을 둬서 글을 쓰니 생각할 부분이 많다는 걸 알았다. 개념을 공부하는 것에 그치는 게 아니라, 왜 필요한지 생각을 해보니 꽤 많은 결론을 내릴 수 있었다.
댓글