Jeff's Inovation Lab Jeff's Inovation Lab

목차 Tree 구조 Tree의 종류 1.Tree 구조 트리: Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 실제로 어디에 많이 사용되나? 트리 중 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨 2.Tree의 종류 이진 트리: 노드의 최대 Branch가 2인 트리 이진 탐색 트리 (Binary Search Tree, BST): 이진 트리에 다음과 같은 추가적인 조건이 있는 트리 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음 3.장점과 용도 주요 용도: 데이터 검색(탐색) 장점: 탐색 속도를 개선할 수 있음 https://bit.ly/37BpXiC

목차 개선된 해쉬 함수 Hash Table의 시간 복잡도 1.개선된 해쉬 함수 파이썬의 hash() 함수는 실행할 때마다, 값이 달라질 수 있음 유명한 해쉬 함수들이 있음: SHA(Secure Hash Algorithm, 안전한 해시 알고리즘) 어떤 데이터도 유일한 고정된 크기의 고정값을 리턴해주므로, 해쉬 함수로 유용하게 활용 가능 SHA-1 import hashlib data = 'test'.encode() hash_object = hashlib.sha1() hash_object.update(data) hex_dig = hash_object.hexdigest() print (int(hex_dig, 16)) SHA-256 import hashlib data = 'test'.encode() hash_ob..

목차 Collision 해결 알고리즘 간단한 구현 1.Collision 해결 알고리즘 Linear Probing기법 폐쇄 해슁 또는 Close Hashing 기법 중 하나: 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법 충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈공간에 저장하는 기법 저장공간 활용도를 높이기 위한 기법 2.간단한 구현 hash_table = list([0 for i in range(8)]) def get_key(data): return hash(data) def hash_function(key): return key % 8 def save_data(data, value): index_key = get_key(data) hash_add..

목차 Collision 해결 알고리즘 간단한 구현 1.Collision 해결 알고리즘 해쉬 테이블의 가장 큰 문제는 충돌(Collision)의 경우입니다. 이 문제를 충돌(Collision) 또는 해쉬 충돌(Hash Collision)이라고 부릅니다. Chaining 기법 개방 해슁 또는 Open Hashing 기법 중 하나: 해쉬 테이블 저장공간 외의 공간을 활용하는 기법 충돌이 일어나면, 링크드 리스트라는 자료 구조를 사용해서, 링크드 리스트로 데이터를 추가로 뒤에 연결시켜서 저장하는 기법 2.간단한 구현 hash_table = list([0 for i in range(8)]) def get_key(data): return hash(data) def hash_function(key): return k..

목차 간단한 구현 1. 간단한 구현 hash_table = list([0 for i in range(8)]) def get_key(data): return hash(data) def hash_function(key): return key % 8 def save_data(data, value): hash_address = hash_function(get_key(data)) hash_table[hash_address] = value def read_data(data): hash_address = hash_function(get_key(data)) return hash_table[hash_address] https://bit.ly/37BpXiC

목차 Hash Table 장단점 1. Hash Table Hash Table: 키(Key)에 데이터(Value)를 저장하는 데이터 구조 Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐 파이썬 딕셔너리(Dictionary) 타입이 해쉬 테이블의 예: Key를 가지고 바로 데이터(Value)를 꺼냄 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 맞바꾸는 기법) 2. 장단점 장점 데이터 저장/읽기 속도가 빠르다. (검색 속도가 빠르다.) 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움 단점 일반적으로 저장공간이 좀더 많이 필요하다. 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요함 주요 용도 검색이 많이 ..

목차 Big-O 표기법 1. Big-O 표기법 빅 오 표기법, Big-O 표기법 이라고도 부름 O(입력) 입력 n 에 따라 결정되는 시간 복잡도 함수 O(1), O(logn), O(n), O(nlogn), O(n2), O(2n), O(n!)등으로 표기함 입력 n 의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있음 O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(2n) < O(n!) 참고: log n 의 베이스는 2 - log2n 단순하게 입력 n에 따라, 몇번 실행이 되는지를 계산하면 됩니다. 표현식에 가장 큰 영향을 미치는 n 의 단위로 표기합니다. O(n) def sum_all(n): total=0 for num in range(1,n+1): total+=nu..

목차 알고리즘 복잡도 계산이 필요한 이유 알고리즘 복잡도 계산 항목 알고리즘 시간 복잡도의 주요 요소 알고리즘 성능 표기법 1. 알고리즘 복잡도 계산이 필요한 이유 하나의 문제를 푸는 알고리즘은 다양할 수 있음 다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석하기 위해, 복잡도를 정의하고 계산함 2. 알고리즘 복잡도 계산 항목 시간 복잡도: 알고리즘 실행 속도 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈 가장 중요한 시간 복잡도를 꼭 이해하고 계산할 수 있어야 함 3.알고리즘 시간 복잡도의 주요 요소 반복문이 지배합니다. 4.알고리즘 성능 표기법 Big O (빅-오) 표기법: O(N) 알고리즘 최악의 실행 시간을 표기 가장 많이/일반적으로 사용함 아무리 최악의 상황이라도, 이정도의 성능은 보장한다..