19장 공간 제약 다루기

• 알고리즘이 얼마나 많은 메모리를 소모하는가를 나타내는 공간 복잡도는 시간 복잡도 대신 또 다른 효율성 척도가 될 수 있다.
• 메모리 제한이 있다면 공간 복잡도가 중요한 요인이다.
• 이상적으로는 빠르면서도 메모리 효율적인 알고리즘만 사용하고 싶지만, 둘 다 만족시킬 수 없는 상황이 있을 것이고 결국 하나를 택해야 한다.

1. 공간 복잡도의 빅 오

• 시간 복잡도를 표현할 때와 마찬가지로 빅 오 표기법을 사용해 공간 복잡도를 표현한다.
• 시간 복잡도에서 핵심 질문은 “데이터 원소가 N개일 때 알고리즘에 몇 단계가 필요할까?”였다.
• 공간 복잡도에서 핵심 질문은 “데이터 원소가 N개일 때 알고리즘은 메모리 단위를 얼마나 소모할까?”이다.
• 문자열 배열을 받아 모두 대문자로 바꾼 배열을 반환하는 함수를 작성한다고 하자.
  1. 새로운 배열을 만들어서 기존의 배열의 문자를 대문자로 변환하여 저장한다고 생각해 보자.
     • 이 함수를 공간 복잡도 관점에서 분석하면 원소 N개를 포함하는 새로운 배열을 생성한다.
     • 원소 N개를 포함하는 원래 배열 이외에 메모리를 더 소모한다.
     • 그렇다면 데이터 원소가 N개일 때 알고리즘은 메모리 단위를 얼마나 소모할까?
     • 함수가 데이터 원소 N개를 추가로 생성했으니 이 함수의 공간 효율성은 O(N)이다.
  2. 새 배열을 생성하지 않고 원래 배열 내에서 한 번에 하나씩 대문자로 바꾸면서 각 문자열을 수정한다고 생각해 보자.
     • 이 함수는 어떤 메모리도 추가로 소모하지 않으니 메모리 소모 관점에서 엄청난 성능 향상이다.
     • 이 함수는 배열의 원소 개수와 상관없이 소모하는 메모리가 0이므로 O(1)이다.
• 공간 복잡도를 빅 오 표기법으로 나타낼 때 알고리즘에서 새로 생성한 데이터만 고려한다.
• 즉, 알고리즘에서 추가로 소모하는 공간이 중요하다. 즉, 원래 데이터 원소 N개는 빅 오로 나타낼 때 고려하지 않는다.
• 추가로 소모한 공간을 더 공식적으로는 보조 공간auxiliary space이라고 부른다.

2. 시간과 공간 트레이드오프

• 공간 복잡도와 시간 복잡도는 서로 트레이드오프 관계일 때가 잦다.
• 물론 상황에 따라 중요한 요소를 고려하여 알맞은 알고리즘을 선택해야 한다.
• 하지만 데이터를 추가로 생성하지 않고도 알고리즘에서 공간을 소모하기도 한다.

3. 재귀에 숨겨진 비용

• 10장 재귀를 사용한 재귀적 반복에서 내부적으로 재귀가 어떻게 동작하는지 설명했다.
• 이미 배웠듯 이 함수는 재귀적으로 자신을 호출할 때마다 호출 스택에 항목을 추가한다.
• 호출 스택은 소모되지만 애초에 항목 100개를 호출 스택에 저장하려면 메모리가 충분해야 한다.
• 즉 재귀 함수는 최대 O(N)의 공간을 차지한다.
• 즉, 재귀 함수는 재귀 호출 횟수만큼 단위 공간을 차지한다.
• 이렇게 은밀하게 재귀는 메모리를 눈 깜짝할 새에 집어삼킨다.
• 함수에서 새 데이터를 명시적으로 생성하지도 않았는데 재귀는 호출 스택에 새로운 데이터를 생성한다.
• 재귀 함수가 얼마나 많은 공간을 차지하는지 정확히 계산하려면 호출 스택이 최대 얼만큼 커지는지 알아내야 한다.
• 재귀를 사용하여 숫자 20000부터 1까지 출력하는 함수를 실행해 보면 약 5000까지 실행하고 스택 오버플로우로 종료되는 것을 볼 수 있다.
• 즉 호출 스택 크기가 대략 15000쯤 되었을 때 컴퓨터 메모리가 고갈되었다는 뜻이다.
• 동일한 함수를 간단한 루프 방식으로 완수하게 해 보면 메모리를 추가로 사용하지 않으므로 아주 큰 숫자를 잘 실행한다.
• 이러한 점을 고려하면 퀵 정렬이 왜 O(logN)공간을 차지하는지 이해가 간다.
• 퀵 정렬은 재귀 호출을 O(logN)번 수행하므로 최고점에서 호출 스택 크기가 log(N)이다.
• 함수를 재귀로 구현하려고 할 때는 재귀가 갖는 문제점 대비 이득을 따져봐야 한다.
• 재귀에는 11장 재귀적으로 작성하는 법에서 배웠던 “마법 같은” 하향식 사고방식을 적용할 수 있지만 재귀 함수를 실행할 수 있는 적절한 환경도 필요하다.

4. 마무리

• 시간과 공간을 포함해 모든 관점에서 알고리즘의 효율성을 측정하는 법을 배웠다.
• 이제 알고리즘을 다른 알고리즘과 비교하고 정보에 입각해 현재 애플리케이션에 사용할 방식을 결정할 수 있는 분석 능력을 갖췄다.