19장. 공간 제약 다루기

Deah (김준희)·2024년 6월 12일

누구나 자료구조와 알고리즘 (개정2판)

목록 보기

16/17

이 책은 전반적으로 다양한 알고리즘의 효율성을 분석하며 '얼마나 빠른가'의 시간 복잡도 측면에 초점을 맞춰 다뤄왔다. 하지만 알고리즘이 '얼마나 많은 메모리를 소비하는가'의 공간 복잡도(Space Complexity) 개념이 있다.

메모리 제한이 있거나 대량의 데이터를 다룰 때에는 공간 복잡도가 중요한 요인으로 작용한다.

속도도 빠르고 메모리 측면에서도 효율적인 알고리즘이 이상적이지만 둘다 만족하는 상황이 있기는 쉽지 않다. 문제 상황마다 분석을 통해 속도와 메모리 측면을 고려하여 우선순위를 매겨야 하는 시점을 파악하는 것이 좋다.

19.1 공간 복잡도의 빅 오

공간 복잡도도 시간 복잡도와 같이 빅 오 표기법을 사용한다.

시간 복잡도에서 핵심은 "데이터 원소가 $N$ 개일 때, 알고리즘에 몇 단계가 필요한가?" 이지만,
공간 복잡도에서는 "데이터 원소가 $N$ 개일 때, 메모리 단위를 얼마나 소모할까?"로 접근한다.

function makeUpperCase1(array) {
	let newArray = [];
  
  	for (let i = 0; i < array.length; i++) {
    	newArray[i] = array[i].toUpperCase();
    }
  	
  	return newArray;
}

위와같이 문자열 배열을 받아 모두 대문자로 바꾼 배열을 반환하는 함수가 있을 때,
makeUpperCase1 함수는 array를 받고, newArray라는 새로운 배열을 생성하여 array의 각 문자열을 대문자로 변환하여 배열에 넣는다. 그리고 이 함수의 실행이 끝났을 때 메모리에는 두 개의 배열이 들어있게 된다. (array와 newArray)

공간 복잡도 관점에서 분석하면 makeUpperCase1 함수는 원소 N개를 포함하는 새로운 배열을 생성한다.
즉 원소 $N$ 개를 가지고 있는 기존 배열(= array) 이외에 메모리 소비를 더 하는 것이다.

여기에 "데이터 원소가 $N$ 개일 때, 메모리 단위를 얼마나 소모할까?" 측면으로 접근해보면
함수가 데이터 원소 $N$ 개를 추가로 생성했으니 이 함수의 공간 효율성은 $O(N)$ 이다.

Y축이 시간이 아니라 소모된 메모리라는 점을 제외하고는 시간 복잡도의 $O(N)$ 그래프와 동일하다.

function makeUpperCase2(array) {
	for (let i = 0; i < array.length; i++) {
    	array[i] = array[i].toUpperCase();
    }
  	return array;
}

makeUpperCase2 함수는 새로운 배열을 생성하지 않고 기존 array의 요소를 순회하면서 각 문자열을 대문자로 수정한다. 그리고 수정된 array를 반환한다. 이 경우는 메모리를 추가로 소비하지 않기 때문에 메모리 소모 관점에서 엄청난 성능 향상이라고 할 수 있다.

makeUpperCase2와 같은 함수의 공간 복잡도를 빅 오로 표기하면 $O(1)$ 이다.

시간 복잡도에서 $O(1)$ 은 데이터의 크기와 상관없이 알고리즘 속도가 상수라는 의미였다. 공간 복잡도에서도 비슷하게 데이터의 크기에 상관없이 알고리즘이 소모하는 메모리가 항상 상수라는 의미이다.

makeUpperCase2 함수는 기존 array의 원소가 몇 개든 추가로 소모하는 공간이 상수이다. (정확히는 0이다). 따라서 이 함수의 공간 효율성은 $O(1)$ 이다.

중요한 점은 공간 복잡도를 빅 오로 표기할 때 '새로 생성한 데이터'만 고려한다는 점이다.

makeUpperCase1 함수와 makeUpperCase2 함수 모두 입력 받은 배열의 데이터 원소 $N$ 개를 똑같이 처리하지만, 입력 받은 배열은 메모리에 이미 존재하고 '추가로 소모하는' 것이 중요하기 때문에 빅 오에서는 기존 배열의 데이터는 고려하지 않는다. 그리고 추가로 소모한 공간을 보조 공간(Auxiliary Space)라고 부른다.

(하지만 원래 입력도 포함해서 공간 복잡도를 계산하는 이론도 있다는 것을 알아두자.)

두 함수 비교

함수	시간 복잡도	공간 복잡도
makeUpperCase1	$O(N)$	$O(N)$
makeUpperCase2	$O(N)$	$O(1)$

두 함수 모두 데이터 원소가 $N$ 개일 때 $N$ 단계가 걸리므로 시간 복잡도는 $O(N)$ 이다.
하지만 공간 복잡도가 $O(N)$ 인 makeUpperCase1 함수에 비해 makeUpperCase2 함수는 $O(1)$ 로 효율적이다. 두 함수에서는 makeUpperCase2를 사용하는 것이 좋다.

19.2 시간과 공간 트레이드 오프

function hasDuplicateValue(array) {
	for (let i = 0; i < array.length; i++) {
    	for (let j = 0; j < array.length; j++) {
        	if (let i !== j && array[i] === array[j] {
            	return true;
            }
        }
    }
  	return true;
}

이 함수는 배열을 받아 중복 값이 있는지 여부를 확인하여 반환하는 함수이다.
중첩 루프를 사용하며 시간 복잡도가 $O(N^2)$ 이다

function hasDuplicateValue2(array) {
	let existingValues = {};
  
  	for (let i = 0; i < array.length; i++) {
    	if (!existringValues[array[i]) {
        	existringValues[array[i]] = true;
        } else return true;
    }
  	return false;
}

hasDuplicateValue2 함수는 빈 해시 테이블을 생성한다. 배열의 원소를 순회하면서 새로운 값이 나올 때마다 해시 테이블에 키로 저장하고, 값이 해시 테이블에 있을 때에는 원소가 중복됐다는 의미이므로 true를 반환한다.

hasDuplicateValue1과 hasDuplicateValue2 중 어떤 알고리즘이 더 효율적일까?

시간과 공간 중 어느 것을 더 고려할 것인가에 따라 다르다.

시간을 고려하면 hasDuplicateValue1 함수는 $O(N^2)$ 이기 때문에 $O(N)$ 인 hasDuplicateValue2 함수가 더 효율적이다.

하지만 공간을 고려하면 hasDuplicateValue1 함수가 더 효율적이다.
hasDuplicateValue2 함수에서는 해시 테이블을 생성하고, 또 함수에 전달된 배열 내 원소를 모두 순회하면서 원소 $N$ 개를 모두 해시 테이블에 넣을 수 있으므로 공간 $O(N)$ 까지 소모한다. (hasDuplicateValue1 함수는 추가 공간을 소모하지 않아 $O(1)$ 이다.)\

둘 사이의 선택

그렇다면 어떤 알고리즘을 고를지는 어떻게 결정할까?

물론 상황에 따라 다르다는 것이 정답이지만, 애플리케이션이 빨라야하고 처리할 메모리가 충분하다면 hasDuplicateValue2 함수를 선택하는 것이 낫다. 반대로 속도가 크게 중요치 않고 메모리를 절약해서 사용해야 하는 경우에는 hasDuplicateValue1 함수를 사용하는 것이 올바른 선택일 수 있다. 모든 기술적 결정이 그러하듯이 트레이드오프가 있을 때는 전체적인 상황을 봐야 한다.

function hasDupicateValue3(array) {
	array.sort((a, b) => (a < b) ? -1 : 1);
  
  	for (let i = 0; i < array.length - 1; i++) {
    	if (array[i] === array [i + 1]) return true;
    }
  
  	return false;
}

hasDupicateValue3 함수는 가장 먼저 배열을 정렬한다. 그리고 배열의 원소를 각각 순회하면서 해당 원소가 다음 원소와 같은지를 비교한다.

hasDupicateValue3 함수는 시간 복잡도 관점에서 $O(NlogN)$ 이다. 정렬 알고리즘이 $O(NlogN)$ 이고, 배열을 순회하는데 걸리는 $N$ 단계는 정렬에 비하면 미미하므로 속도 관점에서는 $O(NlogN)$ 이라고 할 수 있다.

정렬 알고리즘마다 소비하는 메모리 양이 다르기 때문에 공간 효율성은 조금 더 복잡하다. 버블 정렬과 선택 정렬 같은 알고리즘은 제자리에서 정렬하기 때문에 공간을 추가로 소모하지는 않지만, 흥미롭게도 더 빠른 정렬일수록 공간을 더 많이 차지한다. 퀵 정렬 구현이 대부분 $O(logN)$ 공간을 소모한다.

세 함수 비교

함수	시간 복잡도	공간 복잡도
hasDupicateValue1	$O(N^2)$	$O(1)$
hasDupicateValue2	$O(N)$	$O(N)$
hasDupicateValue3	$O(NlogN)$	$O(logN)$

hasDupicateValue3 함수는 시간과 공간 사이에서 흥미로운 균형을 이룬다. 시간 관점에서는 hasDupicateValue1 함수보다 빠르지만 hasDupicateValue2 함수보다 느리다. 공간 관점에서는 hasDupicateValue2 함수보다 효율적이지만 hasDupicateValue1 함수보다는 비효율적이다.

hasDupicateValue3은 언제 사용하는 것이 좋을까?

바로 시간과 공간을 모두 고려해야 할 때 좋은 선택지가 될 수 있다.

근본적으로는 각 상황마다 최소 허용 속도와 메모리 한도를 알아야 한다. 제약을 이해해야 다양한 알고리즘 중에서 선택할 수 있고, 속도와 메모리 요구사항에 맞는 효율성을 유지할 수 있기 때문이다.

19.3 재귀에 숨겨진 비용

데이터를 추가로 생성하지 않고도 알고리즘에서 공간을 소비하기도 한다.

function recurse(n) {
	if (n < 0) return;
  
  	console.log(n);
  	recurse(n - 1);
}

이 함수는 숫자 $n$ 을 받아서 0까지 거꾸로 세며 각 숫자를 출력하는 재귀 함수이다.
$n$ 만큼 함수를 실행하기 때문에 속도는 $O(N)$ 이다. 또한 새로운 자료구조를 생성하지 않으니 공간을 추가로 차지하지 않아보인다.

🧐 정말 그럴까?

10장-재귀를 사용한 재귀적 반복에서 재귀가 내부적으로 어떻게 동작하는지를 알았다. 재귀 함수는 재귀적으로 자신을 호 출할 때마다 호출 스택에 항목을 추가한다. 내부 함수가 끝났을 경우 외부 함수로 컴퓨터가 다시 돌아가야 하기 때문이다.

recurse 함수에 숫자 100을 전달하면 recurse(99)를 실행하기 전에 recurse(100)을 스택에 추가하고, recurse(98)을 실행하기 전에 스택에 recurse(99)를 추가한다.

호출 스택은 추후 풀리긴 인자로 받은 수만큼 저장하기 위해서는 메모리가 충분해야 한다.
즉 재귀 함수는 최대 $O(N)$ 의 공간을 차지하게 된다. 이때 N은 함수에 전달된 값이다.

재귀 함수는 재귀 호출 횟수만큼 단위 공간을 차지한다.
함수에서 새 데이터를 명시적으로 생성하지 않았음에도 호출 스택에 데이터를 추가하면서 많은 공간을 차지하게 된다.

재귀 함수가 얼마나 많은 공간을 차지하는지를 정확히 계산하기 위해서는 호출 스택이 최대 얼만큼 커지는지 확인해야 한다.

위에 있는 recurse 함수에서 호출 스택은 숫자 n만큼 커진다. 사소해보일 수 있지만 정말 그럴까?
최신 노트북에서 숫자 20,000을 recurse 함수에 전달했더니 처리하지 못했다. 20,000은 별로 큰 수가 아니지만 recurse(20000)을 실행하니 다음과 같은 에러와 함께 프로그램이 멈춘다.

RangeError: Maximum call stack size exceeded

20000부터 약 5000까지 재귀를 실행했으니 호출 스택 크기가 약 15,000 쯤 됐을 때 컴퓨터 메모리가 고갈됐다는 의미이다. 즉 저자의 컴퓨터는 15,000개 항목 이상이 포함된 호출 스택을 감당하지 못한다.

function loop(n) {
	while (n >= 0) {
    	console.log(n);
      	n--;
    }
}

위 루프 함수는 재귀로 풀어냈던 recurse 함수와 동일하게 동작한다. 재귀를 사용하지 않는 함수기 때문에 메모리를 추가로 차지하지 않으므로 컴퓨터 공간이 고갈되는 일 없이 잘 실행된다. 이러한 점을 고려하면 퀵 정렬이 왜 $O(logN)$ 공간을 차지하는지 이해가 갈 것이다. 퀵 정렬은 재귀 호출을 $O(logN)$ 번 수행하므로 최고점에서 호출 스택 크기가 $logN$ 이 된다.

함수를 재귀로 작성할 때는 재귀가 가지고 있는 문제점 대비 이득을 따져봐야 한다. 재귀는 11장에서 설명한 것 처럼 마법 같은 하향식 사고방식을 적용할 수 있지만 그 일을 해낼 함수도 필요하다.

다시 말해 재귀가 효율적이지 않다는 것이 아니라 어떤 상황에서 각 알고리즘의 장단점을 골고루 따져봐야 한다는 것이다.

Deah (김준희)

기록 중독 개발자의 기록하는 습관

다음 포스트