** 충돌(Collision) 해결 알고리즘 1) Chaining 기법 Open hashing 기법 중 하나로 해시 테이블 저장공간 외의 공간을 활용 충돌시, 링크드 리스트로 데이터로 연결시켜서 저장함 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_address = hash_function(index_key) if hash_table[hash_address] != 0: for index in range(len(hash_table[hash_a..

** 해시 테이블(Hash Table) 구조 - 키(Key)에 데이터(Value)를 저장하는 데이터 구조 - 장점: 키를 통해 바로 데이터에 접근할 수 있음 - 보통 배열로 미리 해쉬 테이블 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 맞바꾸는 기법) - 파이썬의 딕셔너리(Dictionary) 타입 ** 관련 용어 해시(Hash): 임의의 값을 고정 길이로 변환하는 것 해시 테이블: 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 해싱 함수: 키에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수 해시 값(= 해시 주소): 키를 해싱 함수로 연산하여, 해시 값을 알아내고, 이를 기반으로 해시 테이블에서 해당 키에 대한 데이터 위치를 일관성 있게 찾을 수 있음 슬롯(Slot): 한 개의 ..

** 알고리즘 복잡도 계산이 필요한 이유 - 하나의 문제를 푸는 알고리즘은 다양할 수 있음 ex) 정수의 절대값 계산 방법 1) 제곱 후 루트 씌우기 2) 음수일 때만, -1 곱하기 - 어느 알고리즘이 더 좋은지 분석하기 위해, 복잡도를 정의하고 계산함 ** 알고리즘 복잡도 계산 항목 1) 시간 복잡도: 알고리즘 실행 속도 ---> 반복문이 주요 결정 요소 2) 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈 ** 알고리즘 성능 표기법 Big O (빅-오) 표기법: O(N) 알고리즘 최악의 실행 시간을 표기 가장 많이/일반적으로 사용함 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미이기 때문 Ω (오메가) 표기법: Ω(N) 오메가 표기법은 알고리즘 최상의 실행 시간을 표기 Θ (세타) 표기법:..

** 더블 링크드 리스트(Doubly Linked List) - 장점: 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능 class Node: def __init__(self, data, prev=None, next=None): self.prev = prev # 앞 노드와의 연결 정보 self.data = data self.next = next class NodeMgmt: def __init__(self, data): self.head = Node(data) self.tail = self.head def insert(self, data): if self.head == None: self.head = Node(data) self.tail = self.head else: node = self.hea..

** 링크드 리스트의 복잡한 기능 - 링크드 리스트는 유지관리에 부가적인 구현이 필요함 - 중간 데이터 삽입, 삭제시 ** 파이썬 객체지향 프로그래밍으로 링크드 리스트 구현 class Node: def __init__(self, data, next=None): self.data = data self.next = next class NodeMgmt: def __init__(self, data): self.head = Node(data) # 노드 삽입 def add(self, data): if self.head == '': self.head = Node(data) else: node = self.head while node.next: node = node.next node.next = Node(data) #..

** 링크드 리스트(Linked List) - 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조 cf) 배열: 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조 / 예약 필요 - 본래 C언어에서 주요한 데이터 구조이지만, 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원 ** 링크드 리스트의 구성 요소 및 구조 - 노드(Node): 데이터 저장 단위로 (데이터 값, 포인터)로 구성 - 포인터(Pointer): 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간 - 일반적인 링크드 리스트의 형태 ** 링크드 리스트 간단한 구현 # 노드 구현 class Node: def __init__(self, data, next=None): self.data = data self.ne..