배열은 1차원도, 2차원도, 3차원도 메모리에 할당될 때는 메모리가 1차원이므로 메모리에 연속 할당된다. 1차원 배열은 낮은 주소에서 높은 주소로 연이어서 할당된다. 2차원 배열은 1행이 낮은 주소에서 높은 주소로 연이어서 할당된 후, 2행이 낮은 주소에서 높은 주소로 할당된다. 배열의 효율성 배열은 메모리에 임의 접근할 수 있으므로(메모리 특성상 주소를 특정해서 접근할 수 있으므로) 접근에는 시간 복잡도가 O(1)이다. 데이터의 추가, 삭제에는 어디에 있느냐에 따라 다르다. 맨 뒤에 추가할 때는 빈 자리에 그냥 넣으면 되므로 O(1). 그러나 맨 앞에 삽입하려면, 다른 녀석들을 한칸씩 뒤로 옮겨야 하므로 O(n)이 된다. 따라서 append(),pop() 연산은 O(1), pop(0) 연산은 O(n)이..
[트리] 힙 자료구조 / 파이썬의 heapq 모듈
힙은 특정한 규칙을 가지는 트리이다. 규칙에 따라 최대힙, 최소힙으로 나뉘며, 최대 힙은 부모 노드가 자식 노드보다 크고, 최소 힙은 부모 노드가 자식 노드보다 작다. 최대힙이나 최소힙을 구축하기 위해서는 규칙만 다르고 모두 동일하다. 무작위 배열에서의 최대 힙은 max.heapify(n) 연산을 통해 생성되는데, 과정은 아래와 같다. 1. 현재 노드와 자식 노드의 값을 비교한다. 2. 현재 노드의 값이 가장 크지 않으면 자식 노드 중 가장 큰 값과 현재 노드의 값을 바꾼다. 3. 만약 자식 노드가 없거나 현재 노드의 값이 가장 크면 연산 종료. 4. 맞바꾼 자식 노드의 위치를 현재 노드로 하여 1~3을 반복. 계속해서 맞바꿔가면 되기에 이론은 생각보다 쉽다. 참고로 max.heapifiy(n)에서 n은..