리루

[참조] http://hyeonstorage.tistory.com/265 ---------------------------------------------------------------------------------------------------------- 1. Hash - 해시를 보기에 앞서 대표적인 자료구조의 배열과 리스트를 본다. - 배열의 경우에는 인덱스를 이용하여 자료의 검색이 한번에 이루어지기 때문에 빠른 검색 속도를 보이는 반면 데이터의 삽입, 삭제 시 많은 데이터가 밀리거나 빈자리를 채우기 위해 이동해야 하기 때문에 많은 시간이 소요된다. - 연결 리스트의 경우에는 삽입, 삭제 시 인근 노드들의 참조값만 수정해줌으로써 빠른 처리가 가능하다. 단 처음과 마지막 노드 이외의 위치에서 데..

삽입과 삭제가 빈번하게 발생하는 집합에서 가장 크거나 가장 작은 원소를 빨리 결정할 수 있는지에 의존하는 문제들이 많이 있다. 이 문제들에 접근하는 한 방법은 정렬된 집합을 유지하는 것이다. 이 방법에서 가장 크거나 가장 작은 항목을 정렬하는 순서에 따라 항상 집합의 가장 첫 원소가 된다. 그러나 매번 집합을 정렬하는 것은 비싸다. 게다가 모든 항목들이 정렬되는 것이 목표가 아니므로 실제로 필요한 것보다 더 많은 일을 하게된다. 가장 크거나 가장 작은 항목만 빨리 결정하려면 그 항목을 찾을 수 있는 위치에 유지만 시켜주면 된다. 힙(heap)과 우선순위 큐(priority queue)를 이용하면 이것을 효율적으로 할 수 있다. 힙 가장 큰(작은) 값의 노드를 빠르게 결정할 수 있도록 구조화된 트리이다. ..

정의 트리는 노드(node)라는 항목들이 계층적으로 배치되어 구성된다. 계층의 가장 상위 노드를 루트(root)라고 한다. 루트의 바로 아래 노드들은 루트의 자식들(children)이고, 보통 이 노드들도 자식이 있다. 루트를 제외한 모든 노드들은 하나의 부모(parent)를 갖는데 부보는 바로 상위 노드이다. 부모가 가질 수 있는 자식 노드의 수는 트리의 형태에 따라 다른다. 트리에서 이 숫자를 분기계수(branching factor)라고 한다. 응용 1. 이진트리 자식을 두 개까지 가질 수 있는 노드들로 이루어진 트리이다. 2. 트리 평형 주어진 수의 노드들에 대해 트리를 가능한 짧게 유지하는 데 사용되는 방법이다. 트리의 높이가 전체 성능에 영향을 미치기 때문에 필요한 부분이다. 3. 사용자 인터페..