Devlog

HashMap의 함수 put(key, value) : key와 value를 해시맵에 추가한다. getValue(key) : 입력받은 key의 value를 반환한다. keys() : 해시맵의 모든 key를 반환한다. remove(key) : 입력받은 key와 key에 해당하는 value를 삭제한다. replace(key, value) : 입력받은 key의 value를 입력받은 value로 변경한다. size() : 해시맵의 value의 갯수를 반환한다. isEmpty() : 해시맵의 데이터가 0인지 확인한다. clear() : HashMap의 모든 데이터를 삭제한다. contains() : 입력받은 key가 HashMap에 있는지 확인한다. Map vs HashMap vs HashTableMap vs Tr..

(1) Stack (스택) 나중에 넣은 데이터를 먼저 반환하도록 설계된 메모리 구조 Last In First Out 데이터의 입력을 push → append(), 출력을 pop() (2) Queue (큐) 먼저 넣은 데이터를 먼저 반환하도록 설계된 메모리 구조 First In First Out 스택과 반대 개념 파이썬은 리스트를 사용해 큐 구조를 사용 put → append(), get → pop(0) (3) Tuple (튜플) 값의 변경이 불가능한 리스트 선언 시 "( )" 사용 리스트의 연산, 인덱싱, 슬라이싱 등 동일하게 사용 프로그램을 작동하는 동안 변경되지 않은 데이터의 저장 함수의 반환 값 등 사용자의 실수에 의한 에러를 사전에 방지 (4) 집합 (Set) 값을 순서없이 저장, 중복을 불허하는..

해시 테이블 (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..