알고리즘
-
해시 테이블(Hash Table)ALGORITM 2022. 4. 18. 09:41
키(Key)에 데이터(Value)를 저장하는 데이터 구조 Key를 통해 데이터를 바로 받아올 수 있음 → 속도가 획기적으로 빨라짐 파이썬 딕셔너리(Dictionary) 타입이 해쉬 테이블의 예 - Key를 가지고 바로 데이터(Value)를 꺼냄 보통 배열로 미리 Hash Table 사이즈만큼 생성 후 사용(공간과 탐색 시간을 맞바꾸는 기법) 파이썬에서는 해쉬를 별도로 구현할 필요 없음 - 딕셔너리 타입을 사용하면 되기 때문 해쉬 테이블 시간 복잡도 일반적인 경우(Collision이 없는 경우)는 O(1) 최악의 경우(Collision이 모두 발생하는 경우)는 O(n)
-
스택(stack)과 큐(queue)ALGORITM 2022. 4. 18. 09:40
스택(stack) 나중에 들어간 데이터를 먼저 빼내는 데이터 구조 (LIFO: Last In First Out) 파이썬에서는 list[]로 구현되어있다 자료구조 class stack: def __init__(self): # 스택 객체 생성 self.items = [] def push(self, item): # 스택 요소 추가 push(.append()) self.items.append(item) def pop(self): # 스택 요소 삭제 pop() return self.items.pop() def peek(self): # 스택 맨 앞 요소 리턴 return self[0] def isEmpty(self): # 스택이 비었는지 확인(비었으면 True 리턴) return not self.items a_li..
-
연결리스트(linked list)ALGORITM 2022. 4. 18. 09:29
배열의 단점을 개선하기 위해 생긴 자료구조 연결 리스트 / Linked List는 C언어에서 중요한 데이터 구조였는데 파이썬은 리스트에서 연결 리스트의 모든 기능을 지원한다. Node: 데이터와 데이터 주소(Pointer)로 이루어져있다. Head: 시작 데이터 Tail: 마지막 데이터 Next = None(또는 Null): 다음 데이터가 없을 경우 데이터 주소(Pointer) 값이 None 또는 Null이다. 장점 배열은 미리 데이터 공간을 할당해야하는데 연결리스트는 미리 할당 할 필요가 없다. (유동적으로 데이터 추가 및 삭제가 가능) 연결 리스트 수정 시 시간복잡도 O(1)을 갖는다. (항상 일정한 속도) 단점 다음 데이터를 연결하기 위해선 주소(Pointer) 공간이 필요하다. (저장공간 효율이 ..