바닐라코딩 프랩/자료구조2 HashTable (해시테이블) 해시테이블? key, value로 데이터를 저장 빠른 검색속도를 제공. O(1) 각각의 key갑셍 해시함수를 적용해 배열의 고유한 index를 생성하고 이 index를 활용해 value를 저장/탐색한다. 해시함수 key를 해시함수에 넣어서 가공하면 index값이 출력된다. 해시함수의 성능이 곧 hastTable의 성능이라고 할 수 있다. Division Method : 나눗셈을 이용. 입력값을 테이블의 크기로 나누어 계산 Digit Folding : 각 key의 문자열을 ASCII코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용 Multiplication Method : 숫자로 된 key값 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 계산. h(k) = (kAmod1) x m Un.. 2022. 2. 14. LinkedList (연결리스트) 연결리스트? 포인터를 사용해서 데이터(아이템)들이 메모리공간에 연속적으로 있지 않아도 되는 자료구조. 데이터들은 포인터를 통해 데이터 i를 인접항목 i+1과 연결하여 인덱스 0 ~ N-1까지 정렬된다. -> 저장장치에 물리적으로 한 줄로 세우는 것이 불필요. 연결리스트는 노드로 이루어져 있는데, 노드는 데이터, 포인터로 구성된다. head pointer는 a0를 가리킨다. tail pointer는 a(N-1)을 가리킨다(tail item 이후에는 아무것도 없다.) 연결리스트의 동작과 시간복잡도 검색 : head에서부터 원하는 노드가 나올 때 까지 검색. O(N) 추가 : 추가동작만 한다면 O(1). 검색과 추가를 합친다면 O(N). 제거 : 제거동작만 한다면 O(1). 검색과 제거를 합친다면 O(N). .. 2022. 2. 14. 이전 1 다음
