Devlog

해시 테이블 (Hash Table) hash 함수를 통해 key를 해시 코드로 변환하고, 이 해시코드로 인덱스를 계산해 value에 접근한다. hash function : 해시 코드로 변환하는 함수 Hash Function 1. 나눗셈 법 h(k) = k mod m 입력받은 key의 각 문자를 유니코드로 변환 후 HashMap의 size로 나눈 나머지 값으로 사용한다. m은 HashMap의 크기이며 소수를 사용한다. (2의 제곱수와 거리가 먼 소수) 2. 곱셈 법 h(k) = (kA mod 1) * m k는 숫자로 된 키, 0 < A < 1 m은 중요하지 않으며 보통 2의 제곱 수로 정한다. 나눗셈 법보다는 느리고 2진수 연산에 최적화된 컴퓨터 구조를 고려한 해시함수이다. 3. Universal Hash..

1. 배열 인덱스에 해당하는 원소를 빠르게 접근해야 할 때 데이터를 자주 바꾸거나 확인하는 일 없이 쌓아두고 싶을 때 데이터의 삽입/삭제가 빈번하다면 배열 사용은 비효율적 연산의 시간복잡도 a. i번째 원소 확인 : O(1) - 원소가 연속하게 배치되어 있기 때문 b. 원소를 끝에 추가 : O(1) - 배열의 길이를 알기 때문 c. 마지막 원소 제거 : O(1) - 배열의 길이를 알기 때문 d. 임의의 위치에 원소 추가 : O(N) - 원소 추가 후 전부 한 칸씩 뒤로 밀어야 함 e. 임의의 위치에 원소 제거 : O(N) - 원소 제거 후 전부 한 칸씩 앞으로 밀어야 함 2. 연결리스트 (Linked-list) 각 원소가 자신의 다음 원소의 위치까지 가지고 있는 자료구조 Singly Linked List..