Chapter 11. 이진 탐색 트리
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 이진 트리의 구조를 보면, 트리는 탐색에 효율적이라는 사실을 쉽게 알 수 있습니다. 이진 트리에 저장된 데이터의 수가 10억 개 수준에 이른다 해도 트리의 높이는 30을 넘지 않기 때문입니다. 예를 들어서 연결 리스트에 10억 개의 데이터가 저장되어 있다고 가정해 보겠습니다. 그리고 찾고자 하는 데이터가 이 리스트의 정중앙에 위치한다는 정보를 얻었다고 가정해 보겠습니다. 이는 분명 유용한 정보입니다. 하지만 이러한 정보를 가지고 있음에도 불구하고 데이터에 이르기 위해서는 약 5억 개의 노드를 지나야 합니다. 반면 이진 트리의 경우에..
Chapter 11. 탐색의 이해와 보간 탐색
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 우리는 이전에 '순차 탐색'과 '이진 탐색'에 대해 배웠습니다. 따라서 이번에 탐색에 대해 배운다고 하면 순차 탐색이나 이진 탐색 이외의 다른 탐색 알고리즘들을 배울 것이라고 생각하기 쉽습니다. 하지만 이번에 배울 탐색에 대한 내용은 사실 '트리'에 대한 뒷 이야기에 더 가깝습니다. 탐색은 굳이 따지자면 알고리즘보다는 자료구조에 더 가까운 주제입니다. 왜냐하면 효율적인 탐색을 위해서는 효율적인 탐색을 가능하게 하는 효율적인 저장 방법에 대해 필수적으로 고민해야 하기 때문입니다. 그런데 효율적인 탐색이 가능한 가장 대표적인 저장 방법..
Chapter 10. 복잡하지만 효율적인 정렬 알고리즘
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 앞서 단순한 정렬 알고리즘으로 버블 정렬, 선택 정렬, 삽입 정렬에 대해 알아보았습니다. 세 정렬 방법 모두 성능이 좋지 못한 정렬 알고리즘이라는 것을 알 수 있었습니다. 물론 데이터의 수가 적은 경우에는 간단하게 사용할 수 있는 좋은 알고리즘이지만 데이터의 수가 많아지면 이보다 더 효율적인 알고리즘이 필요하게 됩니다. 이번에 소개하는 알고리즘이 바로 그러한 알고리즘들입니다. 우리는 이전에 '힙'에 대해 배웠습니다. 바로 이 힙을 이용한 정렬 방법이 '힙 정렬'입니다. 힙에 대해서는 앞서 설명했기 때문에 다음의 예제만 보아도 쉽게 ..
Chapter 10. 단순한 정렬 알고리즘
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 다음과 같이 네 개의 숫자가 나열되어 있다고 가정하겠습니다. 3 2 4 1 위와 같이 나열된 숫자를 오름차순으로 정렬해 보겠습니다. 먼저 맨 앞의 3과 그 다음의 2를 비교합니다. 비교 결과 오름차순에 위배되면 두 숫자의 위치를 바꿉니다. 따라서 다음과 같이 됩니다. 2 3 4 1 이번에는 두 번째 숫자와 그 다음 숫자를 비교합니다. 비교하면 3과 4로 오름차순에 위배되지 않으므로 두 숫자의 위치를 바꾸지 않습니다. 바로 다음으로 넘어가 이번에는 세 번째 숫자와 그 다음의 숫자를 비교합니다. 비교 결과 오름차순에 위배되므로 두 숫자..