알고리즘이 얼마나 많은 메모리를 소모하는가를 나타내는 공간 복잡도는 시간 복잡도 대신 또 다른 효율성 척도가 될 수 있다. 메모리 제한이 있다면 공간 복잡도가 중요한 요인이다. 이상적으로는 빠르면서도 메모리 효율적인 알고리즘만 사용하고 싶지만, 둘 다 만족시킬 수 없는 상황이 있을 것이고 결국 하나를 택해야 한다. 1. 공간 복잡도의 빅 오 시간 복잡도를 표현할 때와 마찬가지로 빅 오 표기법을 사용해 공간 복잡도를 표현한다. 시간 복잡도에서 핵심 질문은 “데이터 원소가 N개일 때 알고리즘에 몇 단계가 필요할까?”였다. 공간 복잡도에서 핵심 질문은 “데이터 원소가 N개일 때 알고리즘은 메모리 단위를 얼마나 소모할까?”이다. 문자열 배열을 받아 모두 대문자로 바꾼 배열을 반환하는 함수를 작성한다고 하자. 새..
11장에서는 재귀적으로 작성하는 법과 재귀로 보다 복잡한 문제를 해결하는 법을 배웠다. 그러나 재귀로 어떤 문제를 해결할 수는 있어도 제대로 사용하지 않으면 또 다른 문제가 발생하기도 한다. 재귀를 잘못 사용할 경우 알고리즘의 시간 복잡도가 O(2^N)과 같은 가장 느린 빅 오 카테고리에 속하게 될 수 있다. 12장에서는 재귀의 속도를 느리게 만드는 가장 흔한 걸림돌을 찾고 그러한 알고리즘을 빅 오 관점에서 어떻게 나타내는지, 어떻게 개선하는지를 배운다. 1. 불필요한 재귀 호출 동일한 하위 문제의 계산 결과를 여러 번 호출하는데, 동일한 인자를 넣었을 때 항상 동일한 결과가 나올 때 2. 빅 오를 위한 작은 개선 이러한 추가적인 재귀 호출을 전부 없앨 수 있는 방법이 있다. 코드에서 결과를 변수에 저장..
이 챕터에서는 “재귀적으로 작성하는” 법을 쉽게 익힐 수 있는 몇 가지 비법을 배우게 된다. 11장에서는 재귀의 효율성은 논하지 않는다. 사실 재귀는 알고리즘의 시간 복잡도에 몹시 부정적인 영향을 미친다. 1. 재귀 카테고리: 반복 실행 가장 쉬운 카테고리로, 반복적으로 한 작업을 실행하는 알고리즘이다. 10장에서 잠깐 훑어본 디렉토리 출력 알고리즘 역시 반복 실행 카테고리의 한 예다. 1.1 재귀 트릭: 추가 인자 넘기기 숫자 배열을 받아 배열 내 각 숫자를 두 배로 만드는 알고리즘을 수행하려고 한다. 단 새 배열을 만드는 것이 아니라 배열 자체에서 수정하겠다. 제자리(in-place) 수정 데이터를 조작(변경)하는 기본적인 방식은 일반적으로 두 가지다. 첫 번째 방법은 원래 배열은 그대로 두고 “두 ..
재귀는 함수가 자기 자신을 호출할 때를 뜻하는 용어다. 1. 루프 대신 재귀 루프를 사용할 수 있는 경우라면 거의 대부분 재귀도 쓸 수 있다. 재귀를 쓸 수 있다고 해서 무조건 재귀를 써야 한다는 것은 아니다. 재귀는 명쾌한 코드를 작성할 수 있는 하나의 도구다. 2. 기저 조건 기저 조건(base case): 함수가 반복되지 않는 경우 모든 재귀 함수에는 함수가 무한대로 호출되지 않게 하는 기저 조건이 적어도 하나 있어야 한다. 3. 재귀 코드 읽기 재귀 코드를 읽는 방법 기저 조건을 찾는다. 기저 조건에서 함수가 어떻게 동작하는지 살펴본다. “끝에서 두 번째” 조건을 찾는다. 곧 보이겠지만 이는 기저 조건 바로 전 조건이다. “끝에서 두 번째” 조건에서 함수가 어떻게 동작하는지 살펴본다. 방금 분석한..
