서론

알고리즘에 대한 성능 평가는 어디서나 중요한 개념이지만, PS(Problem Solving)분야에 있어서 더욱 중요하다고 언급되는 개념이다. 특히, 실제 개발에 있어서 만나기 힘든 제약들을 걸어두는 경우가 많기 때문에 어느정도 PS를 해보았다면 시간 복잡도나 공간 복잡도를 고려해보았을 확률이 높다. 그 중에서 조금은 덜 중요한 공간복잡도에 대한 이야기를 해보고자 한다.

공간 복잡도란?

공간 복잡도란 작성한 프로그램이 얼마나 많은 공간을 차지하는지를 분석하는 방법이다. 서론에서 말했듯이 이 공간 복잡도는 시간 복잡도에 비해서 중요도가 조금 떨어진다. 예전에 비해서 컴퓨터의 성능이 많이 발전되었기 때문에 메모리 공간을 굳이 신경쓸 필요가 없어졌기 때문이다. 그러나 PS에서는 인위적으로 공간 소모에 제약을 두기 때문에 공간 복잡도를 계산하고 고려할 수는 있어야한다.

공간 복잡도를 계산하는 방법

공간 복잡도를 계산하는 방법은 간단하다. 주어지는 변수에 따라서 사용되는 공간의 크기가 얼마나 변하는 지를 판단하는 것이다.

maximum = 0
for _ in range(100):
	maximum = max(int(input()), maximum)

위의 코드에서 공간복잡도는 $O(1)$이다. 100번 코드가 반복되지만, 실제 사용되는 공간은 maximum변수 하나이다.

n = int(input())
list = [0 for _ in range(n)]

위의 코드에서 공간복잡도는 $O(N)$이다. 입력되는 변수 n에 따라서 사용되는 공간이 달라진다.

def factorial(n):
	if n == 1:
    	return 1
	return n * factorial(n - 1)

위의 코드도 마찬가지로 파라미터 n에 따라서 사용되는 공간의 크기가 달라진다. 따라서 $O(N)$이다.