📌읽고 나면 진짜 쉬워지는 자료 구조 - 16. 결론

책 마무리!

🔖 16.1 데이터의 구조가 미치는 영향

• 데이터에 약간의 구조만 추가해도 알고리즘 성능이 크게 달라질 수 있다.

• 자료 구조는 값에 빠르게 접근하거나, 여러 값을 효율적으로 결합하거나, 불필요한 탐색을 줄이는 데 도움이 된다.

• 예를 들어 이진 탐색 트리, 트라이, 쿼드 트리, k-d 트리는 탐색 중에 불필요한 경로를 미리 잘라낼 수 있게 한다.

• 트리 기반 자료 구조는 복잡한 탐색 공간에서 단순한 조건 검사만으로 많은 부분을 제외시킬 수 있다.

🔖 16.2 동적 자료 구조의 필요성

• 동적 자료 구조는 크기가 유동적으로 변할 수 있어 유연한 접근이 가능하다.

• 미리 크기를 정해 메모리를 할당하지 않아도 되기 때문에, 메모리 낭비를 줄일 수 있다.

• 대신, 여러 위치에 흩어진 메모리 블록을 포인터로 연결해야 하므로 구조가 복잡해질 수 있다.

• 포인터 연결 방식에 따라 접근 속도나 연산 성능이 달라지기도 한다.

🔖 16.3 분할 상환 비용

• 자료 구조를 사용할지 결정할 때는, 구축 비용과 얻을 수 있는 이점을 함께 고려해야 한다.

• 예를 들어, 배열을 정렬하거나 이진 탐색 트리를 만들면 초기 비용은 크지만, 이후 반복적인 탐색에서는 훨씬 효율적이다.

• 반면 단 한 번만 값을 찾는 상황이라면, 굳이 복잡한 자료 구조를 만드는 것보다 단순한 순차 탐색이 나을 수도 있다.

• 반복적으로 데이터를 탐색해야 한다면, 초기 비용을 들일 가치가 충분히 있다.

🔖 16.4 자료 구조를 구체적인 문제에 맞게 적응시키기

• 기본 자료 구조는 다양한 문제에 응용할 수 있는 기반을 제공한다.

• 공간 자료 구조처럼, 자료 구조를 변형하거나 조합하면 특정 상황에 더 특화된 성능을 낼 수 있다.

• 결국 자료 구조는 문제 해결에 맞게 계속 진화시킬 수 있는 도구다.

🔖 16.5 메모리와 실행 시간 사이의 트레이드오프

• 연산 속도를 높이기 위해 계산 결과를 미리 저장하거나, 메모리를 더 쓰는 방식으로 접근할 수 있다.

• 예를 들어 힙을 사용하면 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있다.

• 또 공간 분할 트리에서는 각 노드의 범위를 미리 계산해서 저장해두면, 불필요한 탐색을 줄일 수 있다.

• 결국, 시간을 아끼기 위해 메모리를 더 쓰는 전략이라고 볼 수 있다.

🔖 16.6 자료 구조 튜닝 방법

• 일부 자료 구조는 성능에 영향을 주는 매개변수를 가지고 있다.

• 이런 매개변수를 어떻게 조정하느냐에 따라 성능이 크게 달라질 수 있다.

• 예를 들어 최근접 이웃 탐색에서 격자의 셀 크기는 정밀도와 성능에 영향을 준다.

• B-트리의 경우, 노드 크기를 적절히 조절해 캐시 효율을 높일 수 있다.

• 자료 구조의 내부 설정이 문제의 특성과 얼마나 잘 맞는지가 중요하다.

🔖 16.7 무작위화가 기대 동작에 미치는 영향

• 어떤 문제는 입력 데이터에 따라 성능이 극단적으로 달라질 수 있다.

• 이런 경우, 자료 구조나 알고리즘에 무작위성을 도입하면 최악의 경우를 피할 수 있다.

• 예를 들어 스킵 리스트처럼 무작위 높이를 사용하면, 성능이 한쪽에 치우치는 것을 방지할 수 있다.

• 하지만 무작위화가 항상 좋은 건 아니고, 문제의 성격에 따라 적절히 써야 한다.

🔖 16.8 마무리

• 프로그래밍 언어나 알고리즘만큼이나 자료 구조도 프로그램 성능과 복잡도에 큰 영향을 준다.

• 따라서 자료 구조 하나하나의 내부 동작 원리를 이해하고, 그것이 어떤 상황에서 가장 효과적인지를 파악하는 것이 중요하다.

• 결국 좋은 프로그램은 문제에 맞는 자료 구조 선택과 응용에서 출발한다.