Yang 코딩 공부

Heap 이란 -> 이진 트리의 한 종류로 (이진 힙 - binary heap) 이라고도 함 조건 1. 루트(root) 노드가 언제나 최댓값 또는 최솟값을 가진다 (최대 힙 - max heap, 최소 힙 - min heap) 2. 완전 이진 트리여야 한다. max heap -> 재귀적으로 정의 가능 : 어느 노드를 루트로 하는 서브트리도 모두 max heap 이다 이진 탐색 트리와의 비교 1. 원소들은 완전히 크기 순으로 정렬되어 있는가 ? X (이진 탐색 트리는 가능 ) 2. 특정 키 값을 가지는 원소를 빠르게 검색할 수 있는가 ? X (이진 탐색 트리는 가능) 3. 부가의 제약 조건은 어떤 것인가 -> heap은 완전 이진트리여야한다는 조건을 가진다 Max Heap의 추상적 자료 구조 연산의 정의 -..

: 정점 (node)과 간선(edge) 을 이용하여 데이터의 배치 형태를 추상화한 자료구조 노드는 루트노드, 내부노드, 리프노드 로 나뉜다 루트노드 : 가장 최상위에 위치한 노드 내부노드(Internal) : 루트도 리프도 아닌 노드 (중간 노드 들) 리프노드 : 더 이상 하위 노드가 없는 최하위 노드 노드들 사이에는 부모노드와 자식 노드가 존재하고 더 선택한 노드를 기준으로 더 상위에 가까운 노드를 부모(Parent)노드 더 하위에 가까운 노드를 자식(Child) 노드라고한다 (루트 노드는 자식노드만 리프노드는 부모 노드만 존재한다) 형제노드 : 같은 부모 아래 존재하는 노드를 형제(sibling) 노드라고 부른다 조상(ancestor) 노드 : 부모의 부모(의 부모의 ...) 후손(descendant..

원소의 삽입 원소의 삭제 두 리스트 합치기 원소의 삽입 코드 구현 주의 사항 (1) 사입하려는 위치가 리스트 맨 앞일 때 prev 없음 Head 조정 필요 (2) 삽입 하려는 위치가 리스트 맨 끝일 때 Tail 조정 필요 (3) 삽입 하려는 리스트가 빈 리스트인 경우 def insertAt(self, pos, newNone) # pos가 옳바른 위치에 잇는가 if pos self.nodeCount + 1: return False # 첫 위치에 삽입하는 경우 if pos == 1: newNode.next = self.head self.head = newNode else: if pos == self.nodeCount + 1: prev = self.tail else: prev = self.getAt(pos -..