목록자료구조 (9)

zuchive

해시테이블(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
링크드 리스트(Linked list) 4

https://zuha.tistory.com/entry/링크드리스트Linkedlist3 링크드 리스트(Linked list) 3 https://zuha.tistory.com/entry/링크드리스트LinkedList2 링크드 리스트(Linked List) 2 https://zuha.tistory.com/entry/링크드리스트LinkedList1 링크드 리스트(Linked List) 1 1. 링크드 리스트 (Linked List).. zuha.tistory.com 7. 다양한 링크드 리스트 구조 - 더블 링크드 리스트(Double linked list) 기본 구조 - 이중 연결 리스트 - 장점 : 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능함. class Node: def __init__(se..
코딩테스트/자료구조 2022. 7. 8. 00:20
링크드 리스트(Linked list) 3

https://zuha.tistory.com/entry/링크드리스트LinkedList2 링크드 리스트(Linked List) 2 https://zuha.tistory.com/entry/링크드리스트LinkedList1 링크드 리스트(Linked List) 1 1. 링크드 리스트 (Linked List) 구조 - 연결 리스트 - 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조.. zuha.tistory.com 이전 포스팅에 이어서! 6. 링크드 리스트의 복잡한 기능 2 (특정 노드를 삭제) 다음 코드는 이전 코드에서 delete 메서드만 추가한 것이므로 해당 메서드만 확인하면 됨. 1. head 삭제 2. 마지막 노드 삭제 3. 중간 노드 삭제 위의 사진처럼 링크드 리스트 A, B, C가 있다..
코딩테스트/자료구조 2022. 7. 7. 00:20
이전 Prev 1 2 Next 다음