이따금 알고리즘을 개선할 방법이 잘 보이지 않는다. 다음의 사고 전략은 지난 몇 년간 코드를 더 효율적으로 바꾸는 데 큰 역할을 했다. 1. 전체 조건: 현재 빅 오 파악하기 최적화 기법으로 들어가기 전에, 알고리즘 최적화에 앞서 반드시 해야 할 일이 있다. 최적화의 전제 조건(prerequisite)은 현재 코드의 효율성을 파악하는 것이다. 현재 얼마나 빠른지 알아야 알고리즘을 더 빠르게 만들 수 있기 때문이다. 이제부터 현재 알고리즘의 빅 오를 알아내는 단계를 전제 조건(prereq)이라 부르겠다. 2. 시작점: 상상할 수 있는 최상의 빅 오 이 장에서 소개할 기법이 모두 유용하지만 어떤 기법은 특정 시나리오에 도움이 되고, 또 어떤 기법은 다른 시나리오에 효과적이다. 하지만 이 첫 번째 기법만은 모..
알고리즘이 얼마나 많은 메모리를 소모하는가를 나타내는 공간 복잡도는 시간 복잡도 대신 또 다른 효율성 척도가 될 수 있다. 메모리 제한이 있다면 공간 복잡도가 중요한 요인이다. 이상적으로는 빠르면서도 메모리 효율적인 알고리즘만 사용하고 싶지만, 둘 다 만족시킬 수 없는 상황이 있을 것이고 결국 하나를 택해야 한다. 1. 공간 복잡도의 빅 오 시간 복잡도를 표현할 때와 마찬가지로 빅 오 표기법을 사용해 공간 복잡도를 표현한다. 시간 복잡도에서 핵심 질문은 “데이터 원소가 N개일 때 알고리즘에 몇 단계가 필요할까?”였다. 공간 복잡도에서 핵심 질문은 “데이터 원소가 N개일 때 알고리즘은 메모리 단위를 얼마나 소모할까?”이다. 문자열 배열을 받아 모두 대문자로 바꾼 배열을 반환하는 함수를 작성한다고 하자. 새..
친구를 맺어주는 소셜 네트워크를 만든다고 하자. 친구 관계는 상호적이다. 이런 데이터를 가장 잘 조직하는 방법은 무엇일까? 한 가지, 매우 간단한 접근 방식은 2차원 배열로 친구 관계 리스트를 저장하는 것이다. 그러나 2차원 배열로는 A의 친구가 누구인지 빠르게 알 수 없다. 컴퓨터는 목록을 전부 확인해야 하므로 O(N)이 필요하다. 그래프를 사용하면 A의 친구를 O(1)만에 빠르게 찾을 수 있다. 1. 그래프 그래프는 관계에 특화된 자료구조로서 데이터가 서로 어떻게 연결되는지 쉽게 이해시켜 준다. 1.1 그래프 대 트리 그래프는 앞서 다뤘던 트리와 비슷하다. 사실 트리도 그래프의 한 종류다. 모든 트리는 그래프이지만, 모든 그래프가 트리는 아니다. 트리로 규정되는 그래프는 사이클이 없어야 하며, 모든 ..
스마트폰의 자동 완성 기능은 어떻게 동작할까? 특수한 트리 기반 자료 구조를 사용하면 O(1)의 속도로 원하는 단어에 접근할 수 있다.(!) 트라이는 자동 완성이나 자동 수정 같은 중요한 기능을 지원한다. 1. 트라이 트라이는 프리픽스 트리Prefix tree 혹은 디지털Digital tree 트리라고도 부른다. 트라이는 명쾌하게 설명되지 않는다. 교재마다, 설명마다 트라이를 조금씩 다르게 구현한다. 1.1 트라이 노드 트라이도 다른 노드를 가리키는 노드들의 컬렉션이다. 트라이 노드는 이진 트리와 다르게 자식 노드 개수에 제한이 없다. 이 교재의 구현에서는 각 트라이 노드마다 해시 테이블을 포함하며, 해시 테이블에서 키는 알파벳이고 값은 트라이의 다른 노드다. 즉, 해시 테이블에서 키는 개개 문자열이고 ..
힙은 데이터 세트에서 가장 큰, 또는 가장 작은 데이터 원소를 계속 알아내야 할 때 특히 유용하다. 힙의 기능을 제대로 파악하기 위해 지금까지 보지 못했던 새로운 자료 구조인 우선순위 큐부터 살펴보자. 1. 우선순위 큐 9.5장에서 배웠던 큐는 FIFO 방식으로 항목을 처리하는 리스트였다. 근본적으로 큐 끝에서만 데이터를 삽입하고 큐 앞에서만 접근과 삭제를 수행한다. 큐의 데이터에 접근하려면 데이터가 삽입됐던 순서를 따라야 한다. 우선순위 큐(Priority Queue)는 삭제와 접근에 있어 전형적인 큐와 흡사하나 삽입에 있어 정렬된 배열과 비슷한 리스트다. 즉 우선순위 큐 앞에서만 데이터에 접근하고 삭제하되 데이터를 삽입할 때는 데이터를 늘 특정 순서대로 정렬시킨다. 우선순위 큐는 추상 데이터 타입의 ..
