Homile

📌 힙(Heap)이란? 최댓값과 최솟값을 빠르게 찾기 위해 고안된 자료구조 힙은 최대힙, 최소힙으로 나눠집니다. 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.) 시간복잡도 = O(log n) ✅ 최대힙 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 key(부모) >= key(자식) ✅ 최소힙 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완진 이진트리 key(부모)

📌 해시 테이블(Hash Table)? 어떤 특정 값을 받으면 그 값을 해시 함수에 통과 시켜 나온 인덱스에 저장하는 자료구조 해시 함수를 사용하여 특정 값을 신속하게 찾는 자료구조 자바스크립트 객체는 해시 테이블과 같은 방식으로 키와 해당 키의 연관된 값을 정의하는 방식으로 동작한다. ✅ 해시 함수 (Hash Function) = 해시(Hash) 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수 해시 함수의 특성 압축성: 다양한 가변 길이의 입력에 대해 고정된 크기의 결과값을 반환하는 성질을 가진다. 효율성: 어떤 입력 값에 대해서도 많은 자원과 시간이 소요되지 않고 처리되는 성질을 가진다. 저항성: 결과값을 바탕으로 입력 값을 찾는 것이 불가능한 성질을 가진다. ✅ 해시 충돌(Hash Co..

캐시(Cache)란 무엇인가? 캐시는 데이터나 값을 미리 복사해 놓는 임시 저장소를 가리킨다. 캐시(Cache)의 특징 사용했던 데이터가 임시 저장소에 담겨있기 때문에 다시 사용할 때 빠르게 접근하여 데이터를 불러올 수 있다. 계산된 값이 저장되어 있어 다시 계산하는 시간을 줄일 수 있다. LRU(Least Recently Used Algorithm)란 무엇인가? 가장 오랬동안 참조되지 않은 페이지를 교체하는 알고리즘 기법이다. 캐시에 공간이 부족할 때 가장 오랫동안 참조되지 않은 항목을 제거하고 새로운 항목을 삽입하는 형식으로 동작된다. LRU 동작 과정 빈 캐시안에 순차적으로 캐시를 채워준다. 4번째 값인 8을 사용할때 참조할 수 있는 캐시가 없으므로 가장 오랫동안 참조되지 않은 값인 1을 삭제 후 ..