# HashTable
Leetcode - 41. First Missing Positive
정렬이 되지 않은 integer값의 배열이 주어진다. 이 배열에 존재하지 않는 양수값 중 가장 작은 값은?(시간복잡도 O(n)에 해결 해야한다.)만약 정렬을 했다면 O(nlogn)이겠지만 hashtable을 사용하면 O(n)에 가능하다. 단 모든 hashtable을 순
Leetcode - 1570. Dot Product of Two Sparse Vectors
두 sparse vector(대부분 값이 0인)를 dot product연산한 결과를 출력해라. 두 벡터는 1차원벡터이다.대부분의 값이 0이기 때문에 <인덱스, 값> 해시테이블에 값이 0이 아닌 요소만 넣는다. 그 뒤 테이블을 순회하며 둘다 0이 아닌 값만 곱해서
[Database] 인덱스(Index)
칼럼의 값과 해당 레코드가 저장된 주소를 Key-Value 쌍의 인덱스로 만들어두어 해당 테이블에 대한 탐색을 빠르게 해주는 자료 구조이다.Index는 항상 정렬된 상태를 유지하기 때문에 원하는 값을 탐색하는 것은 빠르지만 새로운 값의 추가, 삭제, 수정이 발생할 경
[JAVA] Hash
💡 Hash Function : 임의의 데이터를 고정된 길이의 데이터로 매핑하는 단방향 함수. Hashing : 해시함수를 이용해서 데이터를 해시 테이블에 저장하고 검색하는 기법.보통 복잡하지 않은 알고리즘으로 구현되기 때문에 상대적으로 시스템 자원 소모가 덜하다.해
어서와! 자료구조 알고리즘은 처음이지? 파트 3-2
Hashtable<K, V> MAP = new Hashtable<K, V>();Hashtable 선언할 경우 <K,V> 안에 는 generic 타입을 사용하셔야 합니다.제네릭이란?클래스에서 사용할 타입을 클래스 외부에서 설정하도록 만드는 것제네릭으로
[Algorithm] Hash - Python
: Key와 Value의 쌍으로 데이터를 저장하는 자료구조언어에 따라 HashMap이라고도 불리며, 파이썬의 Dictionary도 HashTable로 구현되어 있음.⭐️ HashTable(HashMap, Dictionary)의 특징순차적으로 데이터를 저장하지 않음Key
Pramp - Merging 2 Packages
주어진 배열값 두개를 더해서 lim값이 되는 인덱스 한쌍을 찾아라. i, j 라면 i>j 이어야 한다. 모든 가능성의 조합 중에 가장 마지막 조합을 리턴해야함(문제에는 표기가 안됐음)
Leetcode - 418. Sentence Screen Fitting
문장과 스크린 사이즈가 주어진다. 해당 문장을 스크린에 몇번 담을 수 있는지 파악하라.brute force 방법. 아래 예제에서 TLE발생.
[자료구조] Hash Table
hash는 내부적으로 배열을 사용해 데이터를 저장해 빠른 검색 속도특정한 값을 검색 하는데 고유 인덱스로 접근해 평균적으로 시간 복잡도 O(1)collision이 발생하는 경우 O(n) 해시 함수를 이용해 데이터와 연관된 고유한 숫자를 만들어 이를 인덱스로 사용해시 함
Leetcode - 128. Longest Consecutive Sequence
정렬되지 않은 integer배열 값중에 가장 긴 연속된 수 갯수는? (O(n)에 해결하라)hashtable에 값을 저장하고 table을 순회하면서 연속된 수들을 찾음. 아래 순회 방식을 주석과 함께 잘 살펴보기. 가지치기가 필요.
Leetcode - 49. Group Anagrams
같은 anagram인 문자열끼리 묶어라.정렬된 문자열을 키로 하고, original index를 value로 하는 해시테이블을 생성.
Leetcode - 139. Word Break
주어진 문자열이 wordDict에 포함된 문자열로만 구성되어있는지 파악하라.https://leetcode.com/problems/word-break문자열을 두부분으로 나누고 왼쪽이 hash table에 있는지 파악, 그리고 오른쪽은 recursive 함수가 결
Leetcode - 287. Find the Duplicate Number
딱 한개의 숫자만 중복된 배열이 주어진다. 그 값이 무엇인지 리턴하라.https://leetcode.com/problems/find-the-duplicate-number/freq 를 값으로하는 해시테이블 생성해서 O(n)에 체크
Leetcode - 75. Sort Colors
주어진 배열은 색정보(red:0, white:1, blue:2)를 가지고 있다. 배열을 red/white/blue순으로 정렬하라.3개의 hashtable을 만들고 빈도수를 저장한뒤, nums배열을 순차적으로 변경
해시 테이블(Hash Table)
해시 테이블해시 테이블은 해시 함수와 배열을 사용하여 Map을 구현한 자료 구조이다.배열에 보관한 데이터에 접근하는데 걸리는 시간복잡도는 O(n)이다. Map은 key와 value로 쌍을 이루고 있는 ADT(추상자료구조)로, key를 통해 O(1)의 시간복잡도로 데이터
getElementById, querySelector가 DOM tree를 검색하는 방법
querySelector와 getElementById의 내부 알고리즘호스트 객체와 네이티브 객체id를 이용해 DOM을 찾고 싶을떄, 어떻게 할까 요? DFS 와 hash table 을 이용해 브라우저가 DOM 을 찾는 방법