시카로의 공부방

어떠한 값을 순차탐색하면 확실히 데이터를 얻을 수 있지만, 모든 데이터를 살펴봐야하는 경우가 있으므로 효율적이지 않다. 그러므로 해시는 어떠한 기준(함수)로 변환한 값을 인덱스로 삼아서, 그 인덱스에 해당하는 배열에 키와 값을 저장해 빠른 데이터 탐색을 제공하는 자료구조다. 여기서 탐색에 특화되었다는 게 중요하다. 리스트 자료구조의 경우, 보통 검색에 O(n), 추가에 O(1)이자만, 여기서는 반대이다. 물론 리스트도 중간 추가면 O(n)이긴 하다. 그러나 차이점을 아는 게 중요하다. 해시의 시간복잡도 삽입(Insert): 평균 O(1), 최악의 경우 O(n) 검색(Search): 평균 O(1), 최악의 경우 O(n) 삭제(Delete): 평균 O(1), 최악의 경우 O(n) 해시의 특징 해시는 키를 통..

배열은 1차원도, 2차원도, 3차원도 메모리에 할당될 때는 메모리가 1차원이므로 메모리에 연속 할당된다. 1차원 배열은 낮은 주소에서 높은 주소로 연이어서 할당된다. 2차원 배열은 1행이 낮은 주소에서 높은 주소로 연이어서 할당된 후, 2행이 낮은 주소에서 높은 주소로 할당된다. 배열의 효율성 배열은 메모리에 임의 접근할 수 있으므로(메모리 특성상 주소를 특정해서 접근할 수 있으므로) 접근에는 시간 복잡도가 O(1)이다. 데이터의 추가, 삭제에는 어디에 있느냐에 따라 다르다. 맨 뒤에 추가할 때는 빈 자리에 그냥 넣으면 되므로 O(1). 그러나 맨 앞에 삽입하려면, 다른 녀석들을 한칸씩 뒤로 옮겨야 하므로 O(n)이 된다. 따라서 append(),pop() 연산은 O(1), pop(0) 연산은 O(n)이..

힙은 특정한 규칙을 가지는 트리이다. 규칙에 따라 최대힙, 최소힙으로 나뉘며, 최대 힙은 부모 노드가 자식 노드보다 크고, 최소 힙은 부모 노드가 자식 노드보다 작다. 최대힙이나 최소힙을 구축하기 위해서는 규칙만 다르고 모두 동일하다. 무작위 배열에서의 최대 힙은 max.heapify(n) 연산을 통해 생성되는데, 과정은 아래와 같다. 1. 현재 노드와 자식 노드의 값을 비교한다. 2. 현재 노드의 값이 가장 크지 않으면 자식 노드 중 가장 큰 값과 현재 노드의 값을 바꾼다. 3. 만약 자식 노드가 없거나 현재 노드의 값이 가장 크면 연산 종료. 4. 맞바꾼 자식 노드의 위치를 현재 노드로 하여 1~3을 반복. 계속해서 맞바꿔가면 되기에 이론은 생각보다 쉽다. 참고로 max.heapifiy(n)에서 n은..