목록코딩테스트 (16)

zuchive

트리(Tree) 2

Python 객체지향 프로그래밍으로 링크드 리스트 구현하기 5-1. 노드 클래스 만들기 class Node: def __init__(self, value): self.value = value self.left = None self.right = None 5-2. 이진 탐색 트리에 데이터 넣기 class NodeMgmt: def __init__(self, head): self.head = head def insert(self, value): self.current_node = self.head while True: if value < self.current_node.value: if self.current_node.left != None: self.current_node = self.current_node..
코딩테스트/자료구조 2022. 9. 8. 23:25
트리(Tree) 1

1. 트리 (Tree) 구조 - Node와 Branch를 이용해서 사이클을 이루지 않도록 구성한 데이터 구조 - 실제로 트리 중 이진트리(Binary Tree) 형태의 구조로 탐색(검색) 알고리즘 구현을 위해 많이 사용된다. 2. 용어 - Node : 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함) - Root Node : 트리 맨 위에 있는 노드 - Level : 최상위 노드를 Level 0으로 했을 때 하위 Branch로 연결된 노드의 깊이를 나타낸다 - Parent Node : 어떤 노드의 다음 레벨에 연결된 노드 - Child Node : 어떤 노드의 상위 레벨에 연결된 노드 - Leaf Node (Terminal Node) : Child Node..
코딩테스트/자료구조 2022. 9. 7. 23:55
해시테이블(Hash Table) 5

https://zuha.tistory.com/entry/해시테이블HashTable4 해시테이블(Hash Table) 4 https://zuha.tistory.com/entry/해시테이블HashTable3 해시테이블(Hash Table) 3 https://zuha.tistory.com/entry/해시테이블HashTable2 해시테이블(Hash Table) 2 https://zuha.tistory.com/entry/해시테이블Has.. zuha.tistory.com 6-3. 빈번한 충돌을 개선하는 기법 - 해시 함수를 재정의 및 해시 테이블 저장공간을 확대 hash_table = list([None for i in range(16)]) def hash_function(key): return key % 16 (..
코딩테스트/자료구조 2022. 9. 6. 22:54
해시테이블(Hash Table) 4

https://zuha.tistory.com/entry/해시테이블HashTable3 해시테이블(Hash Table) 3 https://zuha.tistory.com/entry/해시테이블HashTable2 해시테이블(Hash Table) 2 https://zuha.tistory.com/entry/해시테이블HashTable1 해시 테이블 (Hash Table) 1 해시라는 기능을 확장한 여러 가지 함수들이.. zuha.tistory.com 6-1. Chaining 기법 해시 테이블 밖에 충돌이 일어났을 경우, 밖에 데이터를 저장할 수 있는 공간을 링크드 리스트로 만든 것. 6-2. Linear Probing 기법 (가장 많이 언급되는 기법) 해시 테이블 안에 충돌이 일어났을 경우, 안에 빈 공간에 충돌된 데..
코딩테스트/자료구조 2022. 9. 5. 23:43
해시테이블(Hash Table) 3

https://zuha.tistory.com/entry/해시테이블HashTable2 해시테이블(Hash Table) 2 https://zuha.tistory.com/entry/해시테이블HashTable1 해시 테이블 (Hash Table) 1 해시라는 기능을 확장한 여러 가지 함수들이나 알고리즘들이 있다. 이런 해시 기능을 기반으로 하여 만들어진 것이 블록체인 zuha.tistory.com 6. 충돌(Collision) 해결 알고리즘 (좋은 해시 함수 사용하기) 해시 테이블의 가장 큰 문제는 충돌(Collision)이 있는 것이다. 이러한 문제를 충돌(Collision) 또는 해시 충돌(Hash Collision)이라고 부른다. 6-1. Chaining 기법 - 개방 해싱 또는 Open Hashing 기..
코딩테스트/자료구조 2022. 7. 12. 00:30
해시테이블(Hash Table) 2

https://zuha.tistory.com/entry/해시테이블HashTable1 해시 테이블 (Hash Table) 1 해시라는 기능을 확장한 여러 가지 함수들이나 알고리즘들이 있다. 이런 해시 기능을 기반으로 하여 만들어진 것이 블록체인이다. 1. 해시 구조 Hash Table : 키(Key)에 데이터(Value)를 저장하는 데이 zuha.tistory.com 4. 자료 구조 해시 테이블의 장단점과 주요 용도 장점 - 데이터 저장/읽기 속도가 많이 빠르다. (검색 속도가 빠르다.) - 해시는 키에 대한 데이터가 있는지(중복) 확인이 쉽다. 단점 - 일반적으로 저장공간이 좀 더 많이 필요하다. - 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요하다. 주요 용도 - 검..
코딩테스트/자료구조 2022. 7. 11. 19:47
해시 테이블 (Hash Table) 1

해시라는 기능을 확장한 여러 가지 함수들이나 알고리즘들이 있다. 이런 해시 기능을 기반으로 하여 만들어진 것이 블록체인이다. 1. 해시 구조 Hash Table : 키(Key)에 데이터(Value)를 저장하는 데이터 구조 (키만 알면 어디에 데이터를 저장해야하는지 또는 어디에 저장이 되어있는지를 바로 알 수 있는 구조) - Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐 - 파이썬 딕셔너리 타입이 해시 테이블의 예: Key를 가지고 바로 데이터(Value)를 꺼냄 - 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 맞바꾸는 기법) - 단, 파이썬에서는 해시를 별도로 구현할 이유가 없다. 딕셔너리 타입을 사용하면 됨. 16개의 데이터를 담을 ..
코딩테스트/자료구조 2022. 7. 10. 01:53
시간 복잡도 1

1. 알고리즘 복잡도 계산이 필요한 이유 하나의 문제를 푸는 알고리즘은 다양할 수 있다. - 정수의 절대값 구하기 - 1, -1 → 1 - 방법1 : 정수값을 제곱한 값에 다시 루트를 씌우기 - 방법2 : 정수가 음수인지 확인해서 음수일 때만 -1을 곱하기 다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석하기 위해서 복잡도를 정의하고 계산한다. 2. 알고리즘 복잡도 계산 항목 1) 시간 복잡도 : 알고리즘 실행 속도 2) 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈 (변수를 몇개 선언했는지 계산 등) 가장 중요한 시간 복잡도를 꼭 이해하고 계산할 수 있어야한다. ▶ 알고리즘 시간 복잡도의 주요 요소 : 반복문을 가지고 시간 복잡도를 계산한다. 생각해보기 : 자동차로 서울에서 부산을 가기 위해 다음..
코딩테스트/자료구조 2022. 7. 9. 00:32
이전 Prev 1 2 Next 다음