본문 바로가기
728x90

Computer Science39

[자료구조] Binary Tree(이진트리) 구현과 traversal(순회) 구현 python [자료구조] Binary Tree(이진트리) 구현과 traversal(순회) 구현 python 살펴볼 주요 개념: 더보기 - Binary Tree 구현 방법 - Tree traversal의 종류와 구현 방법 1. Binary Tree 구현 방법 리스트, 재귀적 리스트, 노드 클래스 구현의 방법이 있다. 노드 클래스 구현만 살펴본다. class Node: def __init__(self, key): self.key = key self.parent = self.left = self.right = None def __str__(self): return str(self.key) 2. Tree traversal의 종류와 구현 방법 Traversal(순회) : 노드들을 순서에 따라 방문하며 key 값을 출력하는 것.. 2022. 5. 15.
[자료구조] Heap 기초 개념 알아보기(python) [자료구조] Heap 기초 개념 알아보기(python) 살펴볼 주요 개념: 더보기 - 힙이란? - 힙을 충족하는 트리 형태 - 힙 직접 구현 1. 힙이란? 힙 성질(heap property)을 만족하는 이진트리(Binary Tree)이다. * 힙 성질 - 모양성질 : 레벨 별로 모든 노드가 꽉 차있고, 마지막 레벨의 노드만 왼쪽에서부터 차있는 형태 - heap 성질 : 모든 부모노드의 key값이 자식노드의 key값보다 작지 않다. 힙 성질을 만족하는 트리를 리스트화 해서 표현하면 다음과 같다. A = [15, 12, 6, 11, 10, 2, 3, 1, 5] 루트 노드에는 리스트에서 가장 큰 값이다. 힙은 insert와 remove(최대값 삭제), maxHeapify 연산을 지원한다.(max heap) 각.. 2022. 5. 15.
[자료구조] Tree 기본 개념 알아보기 [자료구조] Tree 기본 개념 알아보기 살펴볼 주요 개념: 더보기 - 트리의 개념 - 트리의 표현법(python) 1. 트리의 개념 트리(tree)는 부모 - 자식 간의 관계의 노드로 구성되어 있다. 한 방향 연결리스트와 비슷하다. 한 방향 연결리스트의 경우, 한 부모에 한 자식 밖에 없는 트리구조인 것이다. 트리는 두 개 이상의 자식 노드를 가질 수 있다. 세 개 이상의 자식을 가지는 2, 3, 4 트리와 같은 것도 존재한다. 각각의 노드에는 key값이 들어가 있다. 각각의 용어 설명을 해보자면 다음과 같다. 루트 노드 : 맨 꼭대기에 위치한 조상과 같은 노드 링크 or 에지 : 부모 노드와 자식 노드 사이를 이어주는 선 리프 노드 : 더 이상의 자식 노드가 없는 노드 형제 노드 : level이 같고.. 2022. 5. 15.
[자료구조] hash table(해시 테이블) python class 구현하기 [자료구조] hash table(해시 테이블) python class 구현하기 살펴볼 주요 개념: 더보기 - 해시 테이블의 개념, 특징, 용도 - 해시 함수 - 해시 충돌 회피 - 해시 테이블 클래스 구현(python) 1. 해시 테이블의 개념, 용도, 중요 요소 (1) 해시 테이블의 개념 : 해시 테이블이란 키값에 데이터를 저장하는 데이터 구조이다. key를 통해 데이터(value)를 받아올 수 있으므로 삽입, 삭제, 탐색 연산이 획기적으로 빨라진다. 파이썬에서는 딕셔너리 타입이 해시 테이블의 특징을 가지고 있다. : 해시 테이블은 테이블 사이즈 만큼 배열을 생성하여 사용한다. 특정한 함수(해시 함수)를 통해 key를 인덱스로 mapping을 하고, 테이블 내의 공간에 데이터를 저장하는 것이다. : 파.. 2022. 5. 15.
[자료구조] 배열, 한 방향 연결리스트, 양 방향 연결리스트 시간복잡도 [자료구조] 배열, 한 방향 연결리스트, 양 방향 연결리스트 시간복잡도 배열 (Array) 한 방향 연결리스트 (Singly Linked List) 양 방향 연결리스트 (Double Linked List) search O(1) O(n) O(n) pushFront pushBack O(1) O(1) O(1) popFront popBack O(1) O(1) O(1) insert O(n) O(n) O(1) ※ splice 연산 활용 remove O(n) O(n) O(1) ※ splice 연산 활용 데이터의 접근, 탐색이 중요하다면 배열을 쓰는 것이 좋다. 데이터의 추가, 삭제가 중요하다면 연결리스트를 쓰는 것이 좋다. 2022. 5. 15.
[자료구조] Double Linked List(양 방향 연결리스트) python class 구현하기 [자료구조] Double Linked List(양 방향 연결리스트) python class 구현하기 살펴볼 주요 개념: 더보기 - 양 방향 연결리스트의 특징 - 양 방향 연결리스트 클래스 구현(Node, Double Linked List) 1. 양 방향 연결리스트의 특징 양 방향 연결리스트는 이중 연결 리스트, 원형 연결 리스트로 나누어 진다. 여기서는 원형 연결 리스트만을 살펴볼 것이다. 양 방향 연결리스트는 tail 노드를 알지 못해도 순차적인 탐색 연산이 필요 없다. 삽입될 앞 뒤의 노드만 알고 있다면, 상수 시간 내에 삽입 또는 삭제 연산이 가능하다. 원형 연결리스트의 맨 앞 노드는 '더미 노드'이다. 원형 연결리스트의 순서를 정확하게 매길 수 없는 특징 때문에, head 노드를 정확하게 설정할 .. 2022. 5. 14.
728x90

티스토리툴바