본문 바로가기

알고리즘 강의

 (22)
[알고리즘 강의] 파트23. 힙(Heaps) (2) 최대 힙에서 원소의 삭제 1. 루트 노드의 제거 - 이것이 원소들 중 최댓값 2. 트리 마지막 자리 노드를 임시로 루트 노드의 자리에 배치 3. 자식 노드들과의 값 비교와 아래로, 아래로 이동 - 자식은 둘 있을 수도 있는데, 어느 쪽으로 이동? 큰 값 최대 힙에서 원소의 삭제 - 복잡도 원소의 개수가 n인 최대 힙에서 최대 원소 삭제 -> 자식 노드들과의 대소 비교 최대 횟수: 2 * log2n 최악 복잡도 O(logn)의 삭제 연산 최대/최소 힙의 응용 1. 우선 순위 큐 (priority queue) - Enqueue 할 때 "느슨한 정렬" 을 이루고 있도록 함: O(logn) - Dequeue 할 때 최댓값을 순서대로 추출: O(logn) - 제 16강에서의 양방향 연결 리스트 이용 구현과 효율성..
[알고리즘 강의] 파트22. 힙(Heaps) (1) 힙 (Heap) 이란? 이진 트리의 한 종류 (이진 힙 - binary heap) 1. 루트 (root) 노드가 언제나 최댓값 또는 최솟값을 가짐 (모든 서브트리의 루트에서) - 최대 힙 (max heap), 최소 힙 (min heap) 2. 완전 이진 트리여야 함 재귀적으로도 정의됨 (어느 노드를 루트로 하는 서브트리도 모두 최대 힙) 이진 탐색 트리와의 비교 1. 원소들은 완전히 크기 순으로 정렬되어 있는가? 이진탐색: YES, 힙 NO 2. 특정 키 값을 가지는 원소를 빠르게 탐색할 수 있는가? 이진탐색: YES, 힙 NO 3. 부가의 제약 조건은 어떤 것인가? 힙 - 완전이진트리 최대 힙(Max Heap)의 추상적 자료구조 연산의 정의 - __init__() : 빈 최대 힙을 생성 - insert..
[알고리즘 강의] 파트21. 이진 탐색 트리(Binary Search Trees) (2) 이진 탐색 트리에서 원소 삭제 1. 키(key)를 이용해서 노드를 찾는다. - 해당 키의 노드가 없으면, 삭제할 것도 없음 - 찾은 노드의 부모 노드도 알고 있어야 함 (아래 2번 때문) 2. 찾은 노드를 제거하고도 이진 탐색 트리 성질을 만족하도록 트리의 구조를 정리한다. 인터페이스의 설계 입력: 키 (key) 출력: 삭제한 경우 True 해당 키의 노드가 없는 경우 False 이진 탐색 트리 구조의 유지 1. 삭제되는 노드가 leaf 노드인 경우 그냥 그 노드를 없애면 됨 -> 부모 노드의 링크를 조정 (좌? 우?) * 삭제되는 노드 (X)가 root node인 경우는 root에 None 을 넣음 -> 트리 자체가 없어짐 2. 삭제되는 노드가 자식을 하나 가지고 있는 경우 삭제되는 노드 자리에 그 자..
[알고리즘 강의] 파트20. 이진 탐색 트리(Binary Search Trees) (1) 이진 탐색 트리 모든 노드에 대해서, - 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고 - 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 성질을 만족하는 이진 트리 (중복되는 데이터 원소는 없는 것으로 가정) (정렬된) 배열을 이용한 이진 탐색과 비교 - 이진 탐색 트리의 장점: 데이터 원소의 추가, 삭제가 용이 - 이진 탐색 트리의 단점: 공간 소요가 큼 - 항상 O(logn) 의 탐색 복잡도? X 이진 탐색 트리의 추상적 자료구조 데이터 표현 - 각 노드는 (key, value) 의 쌍으로 장점: (1) 키를 이용해서 검색 가능 (2) 보다 복잡한 데이터 레코드로 확장 가능 연산의 정의 - insert(key, data): 트리에 주어진 데이터 원소를 추가 - remove..
[알고리즘 강의] 파트19. 이진 트리 - 넓이 우선 순회(breadth first traversal) 넓이 우선 순회 (breadth first traversal) 원칙 - 수준(level)이 낮은 노드를 우선으로 방문 - 같은 수준의 노드들 사이에는, ㄴ 부모 노드의 방문 순서에 따라 방문 ㄴ왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문 - 재귀적(recursive) 방법이 적합한가? X 한 노드를 방문했을 때, 나중에 방문할 노드들을 순서대로 기록해 두어야 함 -> 큐(queue)를 이용하자 넓이 우선 순회 알고리즘 설계 1. (초기화) traversal
[알고리즘 강의] 파트18. 이진 트리(Binary Trees) 이진 트리의 추상적 자료구조 연산의 정의 - size(): 현재 트리에 포함되어 있는 노드의 수를 구함 - depth(): 현재 트리의 깊이 (또는 높이; height) 를 구함 - 순회 (traversal) 이진 트리의 구현 - 노드 (Node) class Node: def __init__(self, item): self.data = item self.left = None self.right = None 이진 트리의 구현 - 트리 (Tree) class BinaryTree: def __init__(self, r): self.root = r 이진 트리의 구현 - size() - 재귀적인 방법으로 쉽게 구할 수 있음! class Node: def size(self): l = self.left.size() ..
[알고리즘 강의] 파트17. 트리(Trees) 트리 (Tree) 정점 (node) 과 간선 (edge) 을 이용하여 데이터의 배치 형태를 추상화한 자료 구조 용어 정리 - 루트 (root) 노드: A - 리프 (leaf) 노드: G, H, J, E, K - 내부 (internal) 노드 - B,D,C,F - 부모 (parent) 노드 ex. 노드 D는 노드 G,H,J의 부모 - 자식 (child) 노드 ex. 노드 E는 노드 C의 자식 - 노드 G,H,J는 서로 형제간 (sibling) - 조상 (ancestor): 부모의 부모(의 부모의...) - 후손(descendant): 자식의 자식(의 자식의...) 노드의 수준 (Level) Root node가 level 0 이며 아래로 내려갈수록 노드의 level 증가 ex. 위의 트리에서는 위부터 아래 ..
[알고리즘 강의] 파트16. 우선순위 큐(Priority Queues) 우선순위 큐 (Priority Queue) 큐가 FIFO (First-In First-Out) 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식 우선순위 큐의 활용 - 운영체제의 CPU 스케줄러 우선순위 큐의 구현 서로 다른 두 가지 방식이 가능할 듯: (1) Enqueue 할 때 우선순위 순서를 유지하도록 (2) Dequeue 할 때 우선순위 높은 것을 선택 -> 어느 것이 더 유리할까? 1번 서로 다른 두 가지 재료를 이용할 수 있음: (1) 선형 배열 이용 (2) 연결 리스트 이용 -> 어느 것이 더 유리할까? - 시간면에선 (2) - 메모리면에선 (1) -> 시간적으로 유리한 걸 택하는 경우가 많음 실습 과제 - 우선순위 큐의 enqueue 연산 구현 class Node: def..

티스토리툴바