얼렁뚱땅 Data Science

힙 (Heaps) 이진 트리의 한 종류로 다음 조건을 만족시킴 : 루트 노드가 언제나 최댓값 또는 최솟값을 가짐 - max heap / min heap 완전 이진 트리여야 함 재귀적 정의 : 어느 노드를 루트로 하는 서브 트리도 모두 최대 힙이면 된다. 이진탐색트리 힙 원소들은 완전히 크기 순으로 정렬되어 있는가? O X 특정 키 값을 가지는 원소를 빠르게 검색할 수 있는가? O X 부가의 제약 조건은 어떤 것인가? - 완전 이진트리여야함 최대 힙의 추상적 자료 구조 __init__() : 빈 최대 힙을 생성 insert(item) : 새로운 원소를 삽입 remove() : 최대 원소(root)를 반환 배열을 이용한 이진 트리의 표현 최대 힙에 원소 삽입 원소의 개수가 n인 최대 힙에 새로운 원소를 삽입..

원소삭제 키를 이용해서 노드를 찾는다. 해당 키의 노드가 없으면, 삭제할 것도 없음 찾은 노드의 부모 노드도 알고 있어야함 찾은 노드를 제거하고도 이진 탐색 트리 성질을 만족하도록 트리의 구조를 정리한다. 삭제되는 노드가 말단 노드일 경우 -> 부모 노드의 링크를 조정 자식을 하나 가지고 있는 경우 -> 자식이 left, right인지, 가져다 부모노드의 링크를 조정 (자신의 자리로 child node를 가져옴) 자식을 둘 가지고 있는 경우 -> 삭제되는 노드보다 바로 다음 큰 키를 가지는 노드를 찾아 그 노드를 삭제되는 노드 자리에 대신 배치하고 이 노드를 대신 삭제 삭제되는 노드가 루트 노드 일 경우 -> 대신 들어오는 자식이 새로운 루트가 된다. 루트보다는 크지만 나머지 키들보다는 작은 키를 찾아 ..

이진 탐색 트리 (Binary Search Tree) 모든 노드에 대해서, 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고, 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값도가 큰 성질을 만족하는 이진트리 (중복데이터는 없는 것으로 가정) 정렬된 배열을 이용한 이진 탐색과의 비교 장점 : 데이터 원소의 추가, 삭제가 용이 단점 : 공간 소요가 큼 항상 O(logn)의 탐색 복잡도를 가지는가? --> NO 각 노드는 (key, value)의 쌍으로 키를 이용하여 검색 가능. 보다 복잡한 데이터 레코드로 확장 가능 연산의 정의 insert(key, data) - 트리에 주어진 데이터 원소를 추가 remove(key) - 특정 원소를 트리에서 삭제 lookup(key) - 특정 원소를 검색 ..

넓이 우선 순회의 원칙 수준이 낮은 노드를 우선으로 방문 같은 수준의 노드들 사이에서는, 부모노드의 방문 순서에따라 방문, 왼쪽 자식 노드 우선 따라서 재귀적 방법이 적합하지 않음! 한 노드를 방문했을때, 나중에 방문할 노드들을 순서대로 기록해 두어야 함 --> queue를 이용 구현 방법 (초기화) traversal

이진트리의 추상적 자료구조 연산의 정의 size() : 현재 트리에 포함되어 있는 노드의 수를 구함 재귀적으로 구하기 쉬움 전체 이진트리의 사이즈 = left subtree의 size() + right subtree의 size() + 1(자기 자신) depth() : 현재 트리의 깊이 (또는 높이)를 구함 이도 재귀적은 방법으로 쉽게 구할 수 있음 max(left subtree의 depth(), right subtree의 depth()) + 1 traversal() : 현재 트리의 노드를 방문하여 리스트에 추가함 깊이 우선 순회 (depth first traversal) 중위 순회(in-order traversal) : left subtree -> 자기 자신 -> right subtree 전위 순회(pr..

트리(Trees) 노드(node)와 에지(edge)를 이용하여 데이터의 배치 형태를 추상화한 자료구조 노드들 사이에는 parent-child 관계가 존재한다. 만약, 두 노드가 에지로 연결되어 있을때, 뿌리 노드에 더 가까운 노드가 parent node, 먼 노드가 child node이다. 같은 parent node를 가지는 child node는 서로 slibling 관계에 있다고 한다. 트리 주요 용어 루트 노드(root node) : parent node가 없는 트리의 가장 윗 노드 리프 노드(leaf node) : child node가 없는 트리의 가장 아래 노드 내부 노드(internal node) : 루트 노드, 리프 노드가 아닌 나머지 노드 노드의 수준(level) : 이 강의에서는 root ..

우선순위 큐 (Priority Queue) 큐가 FIFO(First in First out) 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식 ex) 운영체제의 cpu 스케줄러 우선순위 큐 구현 방식 enqueue할때 우선순위 순서를 유지하도록 --> 더 유리함. dequeue할때 우선순위 높은 것을 선택 자료 형태에 따라서 선형 배열 --> 공간적으로는 더 유용 연결 리스트 이용 --> 시간적으로는 더 유용 16강 실습: 우선순위 큐의 enqueue 연산 구현 class Node: def __init__(self, item): self.data = item self.prev = None self.next = None class DoublyLinkedList: def __init__(s..

큐의 활용 1. 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적(asychronously)으로 일어나는 경우 2. 자료를 생성하는 작업이 여러 곳에서 일어나는 경우 3. 자료를 이용하는 작업이 여러 곳에서 일어나는 경우 4. 자료를 생성하는 작업과 그 자료를 이용하는 작업이 양쪽 다 여러 곳에서 일어나는 경우 5. 자료를 처리하여 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업의 경우 환형 큐 (circular Queue) : 정해진 개수의 저장 공간을 돌려가며 이용 큐가 가득차면 더이상 원소를 넣을 수 없음 (큐 길이를 기억하고 있어야 함) 기존 큐 연산에 다음을 추가한다. isFull() : 큐에 데이터 원소가 꽉차있는지를 판단 rear는 가장 최근에 enqueue된 데이..

큐(Queue) 자료를 보관할 수 있는 선형 구조. 즉, 선입선출 (FIFO - First in First Out)의 특징을 가지는 선형 자료구조 넣을 때에는 한 쪽 끝에서 넣어야함 -> enqueue 연산 꺼낼 떄에는 반대 쪽에서 뽑아 꺼내야 하는 제약이 있음 -> dequeue 연산 큐의 추상적 자료구조 구현 (1) 배열 (2) 연결리스트 이용해 구현 연산의 정의 size() - 현재 큐에 들어있는 데이터 원소 수를 구함 isEmpty() - 현재 큐가 비어있는지 판단 enqueue(x) - 데이터 원소 x를 큐에 추가 dequeue() - 큐의 맨 앞에 저장된 데이터 원소를 제거 peek() - 큐의 맨 앞에 저장된 데이터 원소를 반환 (제거하지 않음) 배열로 구현한 큐의 연산 복잡도 연산 복잡도 ..

중위 표기법 (infix notation) 우리가 일반적으로 사용하는 표기법으로 연산자가 피연산자들의 사이에 위치 (A + B) * (C + D) 후위 표기법 (postfix notation) 연산자가 피연산자들 뒤에 위치 A B + C D + * 스택을 이용하여 중위 표현식을 후위표현식으로 바꾸기 중위 표현식 후위 표현식 A * B + C A B * C + A + B * C A B C * + A + B + C A B + C + 괄호의 처리 여는 괄호는 스택에 push, 닫는 괄호를 만나면 여는 괄호가 나올 때까지 pop 연산자를 만났을 때, 여는 괄호 너머까지 pop하지 않도록 여는 괄호의 우선순위는 가장 낮게 설정 중위 표현식 후위 표현식 (A + B) * C A B + C * A * (B + C) ..