본문 바로가기

Computer Science/Data Structure15

[Python] 트라이 자료구조 구현(Trie) 트라이 자료구조는 검색에 최적화된 자료구조이다 자식 노드가 여러 개인 트리 형태로 구성된다고 이해하면 된다. https://leetcode.com/problems/implement-trie-prefix-tree/ Implement Trie (Prefix Tree) - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 위의 문제를 기준으로 구현했다. class TrieNode: def __init__(self): self.word = False self.childre.. 2022. 4. 30.
Python 힙 구현 힙 자료구조를 만족하려면 두 가지 조건(최소 힙 기준) 1. 부모 노드가 자식 노드보다 작다. 2. 트리의 모양이 완전 이진트리의 형태. 완전 이진트리는 마지막 레벨을 제외하고 모든 노드가 왼쪽에서 오른쪽으로 채워져 있는 트리 -> 리스트로 구현 class BinaryHeap: def __init__(self): self.items = [None] def __len__(self): return len(self.items) - 1 # 위로 올라가는거 def _percolate_up(self): index = len(self) parent = index // 2 while parent > 0: if self.items[parent] > self.items[index]: self.items[parent], s.. 2022. 4. 23.
자료구조, 자료형, 추상 자료형 단어가 서로 비슷해 보이지만 차이가 있다. 이를 정리해보자. 자료구조 데이터에 효율적으로 접근하고 조작하기 위한 조직, 관리, 저장 구조를 말함. 예 : 해시 테이블, B-Tree , 배열, 트리, 힙 자료형 컴파일러 또는 인터프리터에게 프로그래머가 데이터를 어떻게 사용하는지를 알려주는 데이터 속성 예 : 정수, 실수, 문자열, 원시 자료형 추상 자료형 Abstract Data Type(ADT)라 부름 자료형에 대한 수학적 모델들을 지칭함. 해당 유형의 자료에 대한 연산들을 명기한 것. OOP의 추상화와 비슷한 개념 - 선풍기는 전원버튼과 미풍, 약풍, 강풍이 있어야 함 + O(1)의 시간복잡도로 수행해야 한다. 라고 명기 하면 추상적 자료 구조가 된다. 예: 스택에는 push, pop, size, fu.. 2022. 3. 25.
이진 탐색 트리 (Binary Search Tree) - 탐색, 삽입, 삭제 이진 탐색 트리(Binary Search Tree) - 각 노드의 왼쪽 subtree의 key 값은 노드의 key 값보다 작거나 같아야 하고 - 각 노드의 오른쪽 subtree의 key 값은 노드의 key 값보다 커야 한다. - 모든 노드에서 만족해야 함. search 연산에서 장점이 있음 O(h) -> 높이를 적정하게 유지하는 것이 중요. class BST: def __init__(self): self.root = None self.size = 0 def __len__(self): return self.size def __iterator__(self): return self.root.__iter__() # yield def find_loc(self, key): # key 값 노드가 있다면 해당 노드 r.. 2022. 1. 2.
이진트리 - 정의와 순회 이진트리를 노드와 링크를 통해 직접 구현하도록 한다. key, left, right, parent class Node: def __init__(self, key): self.key = key self.parent = None self.left = None self.right = None def __str__(self): return str(self.key) 이진트리 순회(trabersal) 1. preorder (전위) 2. inorder (중위) 3. postorder (후위) preorder -> MLR inorder -> LMR postorder -> LRM preoder : F B A D C E G I H inorder : A B C D E F G H I postorder : A C E D B H.. 2022. 1. 1.
힙 자료구조 - insert 연산 1. 힙의 모양성질 만족 2. 모든 부모의 key가 자식의 key 보다 커야함 이러한 힙에서 만약 14가 들어오고자 하면, 새로 들어온 14 때문에 힙 성질을 만족하지 못한다. 따라서 이를 적절히 변경해줘야 함. 14를 위로 올려 보내면서 자기 자리를 찾도록 해야 한다. def insert(14): A.append(14) A.heapify(9) # up # A[k]를 root 방향으로 이동하면서 heapify def heapify(k): # A[k]를 heapify # 아직 루트에 도달하지 않았고, 부모의 key 값이 나보다 작을 때 while k > 0 and A[(k-1)//2] < A[k] : A[k], A[(k-1)//2 = A[(k-1)//2], A[k] k = (k-1)//2 참조 - http.. 2022. 1. 1.
힙 자료구조 - make heap 연산 https://hkim-data.tistory.com/187 힙 자료구조 힙 자료구조 전에 트리 자료구조의 표현법에 대해 좀 더 알아보자. 위와 같은 표현법을 사용하면 인덱스가 정해지게 된다. 즉. 왼쪽, 오른쪽 자식노드와 부모노드를 상수시간안에 접근 가능하다 hkim-data.tistory.com 이전 포스팅에 이어서 make heap 연산에 대해 알아보자 힙 성질을 만족하기 위해, heapify - down을 계속해서 진행하면 된다. 리스트의 맨 오른쪽 인덱스부터 A[0]까지 계속해서 반복 1. 리프노드면 내버려둠 2. 자식 노드가 있을 때 나보다 클 때 A [2*k+1]과 A [2*k+2] 값 중 큰 것이랑 변경 3. 변경 후 리프 노드가 아니면 또 아래랑 비교해줘야 함 def make_heap(A.. 2022. 1. 1.
힙 자료구조 힙 자료구조 전에 트리 자료구조의 표현법에 대해 좀 더 알아보자. 위와 같은 표현법을 사용하면 인덱스가 정해지게 된다. 즉. 왼쪽, 오른쪽 자식노드와 부모노드를 상수시간안에 접근 가능하다. H[k] - 왼쪽 자식 노드 : H[2*k+1] - 오른쪽 자식 노드 : H[2*k+2] - 부모 노드 : H[(k-1) //2] 힙 (heap) : 힙 성질(heap property)를 만족하는 이진트리 힙 성질 1. 모양이 힙의 형태 (왼쪽부터 채운 형태) 2. 모든 부모 노드 키값은 자식 노드 키값보다 커야 함 힙의 루트노드에서는 가장 큰 값이다. A[0] 제공연산: 1. insert : O(logn) 2. find-max : return A[0] - O(1) 3. delete-max : O(logn) 참조 - .. 2021. 12. 31.
트리 자료구조 (용어 설명 및 표현법) 순차적 자료구조 : 배열, 연결 리스트 트리는 부모와 자식의 형태로 나타내는 자료구조 - 연결 리스트는 자식이 최대 1까지 있는 특수한 형태의 트리 자식이 최대 2개까지 있는 경우 이진트리(binary tree) 경로(path) : ex 3에서 12로 갈 때 3 -> 2 -> 7 -> 8 -> 12 경로 길이 (path length) = 4 (경로상의 에지 개수) 이진트리를 코드상에서 저장 표현법 3 : Class 활용 참고 - https://www.youtube.com/watch?v=w-1w4ood7Bc&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=20 2021. 12. 31.
해시 테이블 - collision resolution method 해시 함수에 의해 특정 인덱스 값이 정해지게 되면 c - universal function이기 때문에 충돌이 발생할 수 밖에 없다. 충돌이 발생했다는 것은 내가 삽입하려고 하는 슬롯에 이미 다른 key value 데이터가 저장되어 있는 것. 그럼 다른 어느 곳에 저장해야 될까? 에 대한 것을 collision resolution method이다. 대표적인 방법 중 하나 Open addressing인데 그 방식은 3가지로 나눌 수 있다. 1. linear probing - 한칸씩 2. quadratic probing - 제곱칸씩 3. double hashing - 해시함수 두개 set 함수 : key 값이 해시테이블에 있으면 update하고 아니면 insert (upsert) set(key, value=N.. 2021. 12. 31.
해시 테이블 해시 테이블은 매우 빠른 삽입, 삭제, 탐색 연산을 제공하는 자료구조 python에서는 dict를 사용 key와 value의 형태로 해시 테이블에 저장 ( 해시 테이블은 보통 배열을 사용, 이 슬롯의 크기를 m이라 함) 해시 테이블에 저장할 때 hash Function을 이용해서 특정한 인덱스(Hash Code)를 지정해주게 됨 python에서는 hash(key)를 입력하게 되면 특정 key가 출력됨 hash function 1. perfect hash function : 이상적인 h.f key -> slot 이 1:1로 매치됨 즉, collision이 발생하지 않음 -> 비현실적 2. universal hash function : x란 key 값과 y란 key 값이 있다고 했을 때 f(x) == f(y.. 2021. 12. 29.
양방향 연결 리스트 구현 https://www.youtube.com/watch?v=zWrFVf9_YTQ&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=16 교수님 자료를 보고 리뷰한 포스팅 단방향 연결 리스트의 단점 - 만약 tail 노드를 지우고 싶다고 했을 때, tail 노드를 안다고 하더라도 tail 노드 앞의 prev 노드를 알지 못하기 때문에 결국 head부터 끝까지 search 하며 찾아야 한다. O( n ) 시간 소요 - 이를 해결하기 위해 왼쪽 방향 오른쪽 방향의 양방향 연결 리스트가 필요하게 됨. - 단점 : 링크가 양쪽으로 있어서 복잡성이 증가함 Splice 연산 def splice(self, a, b, x) : 조건 1 : a ->.. -> b : a에서 앞으로 가다 보면 .. 2021. 12. 28.
단방향 연결 리스트 구현 class Node: # 단방향 연결 리스트 위한 노드 def __init__(self,key = None): self.key = key self.next = None def __str__(self): return str(self.key) # v = Node() # print(v.key) # key값 출력 # print(v) -> print(v.__str__()) 와 같음 ''' 보통 이렇게 하지 않음 (매번 변수 선언) a = Node(3) b = Node(9) c = Node(-1) a.next = b b.next = c ''' class SinglyLinkedList: def __init__(self): self.head = None self.size = 0 def pushFront(self,key.. 2021. 12. 13.
스택 큐 자료구조 구현 class Stack: def __init__(self): self.items = [] # 데이터 저장을 위한 리스트 준비 def push(self, val): self.items.append(val) def pop(self): try: return self.items.pop() except IndexError: # IndexError가 발생했다면 print("Stack is empty") def top(self): # 맨 위의 값을 출력 try: return self.items[-1] except IndexError: print("Stack is empty") def __len__(self): # len()로 호출하면 stack의 item 수 반환 return len(self.items) class Q.. 2021. 12. 12.
자료구조와 알고리즘 자료구조와 알고리즘에 대해 알아보자 그 동안 자료구조와 알고리즘을 막연하게 생각해왔는데 본질적으로 알아 봐야겠다 https://www.youtube.com/watch?v=M2mcJvmYpWY 한국외대 신창수 교수님의 자료를 보고 정리해볼까 한다. 자료구조란 어떤 data를 저장하기 위한 구조인데 이는 저장공간(memory) + 연산(읽기, 쓰기, 삽입, 삭제, 탐색) 의 구조를 가지고 있다. 이런 자료구조를 활용해 어떤 입력이 들어왔을 때 이를 유한한 횟수의 연산들을 통해 정답을 출력하는 논리적인 절차를 알고리즘이다. 자료구조의 예: 1. 변수(variable) a = 5 (쓰기연산) print(a) (읽기연산) 변수에는 값이 하나만 들어가기 때문에 삽입, 삭제, 탐색은 의미가 없다 python 내부에서.. 2021. 12. 8.

티스토리툴바