Homile

📌 힙(Heap)이란?

• 최댓값과 최솟값을 빠르게 찾기 위해 고안된 자료구조
• 힙은 최대힙, 최소힙으로 나눠집니다.
• 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)
• 시간복잡도 = O(log n)

✅ 최대힙

부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

key(부모) >= key(자식)

✅ 최소힙

부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완진 이진트리

key(부모) <= key(자식)

🍀 힙의 구현

• 힙을 저장하는 표준적인 자료구조는 배열이다.
• 구현을 쉽게하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다.
• 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
  • 루트 노드의 오른쪽 노드의 번호는 항상 3이다.
• 부모 노드와 자식 노드의 관계
  • 왼쪽 자식 인덱스 = (부모의 인덱스) * 2 
  • 오른쪽 자식 인덱스 = (부모의 인덱스) * 2 + 1 
  • 부모의 인덱스 = (자식의 인덱스) / 2

✅ 삽입 연산

1. 삽입하고자 하는 값을 트리의 가장 마지막 원소에 추가한다.
2. 부모 노드와의 대소관계를 비교하면서 만족할 때까지 자리 교환을 반복한다.

✅ 삭제 연산

1. 힙에서는 루트 노드만 삭제가 가능하므로 루트 노드를 제거한다.
   1. 최대 힙에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것이다.
2. 삭제된 루트 노드에는 힙의 마지막 노드를 가져온다.
3. 자식노드와 비교하여 조건이 만족할 때까지 이동시킨다.

📝 추가자료

• 힙구현

📌 해시 테이블(Hash Table)?

• 어떤 특정 값을 받으면 그 값을 해시 함수에 통과 시켜 나온 인덱스에 저장하는 자료구조
• 해시 함수를 사용하여 특정 값을 신속하게 찾는 자료구조
• 자바스크립트 객체는 해시 테이블과 같은 방식으로 키와 해당 키의 연관된 값을 정의하는 방식으로 동작한다.

✅ 해시 함수 (Hash Function) = 해시(Hash)

임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수

• 해시 함수의 특성
  • 압축성: 다양한 가변 길이의 입력에 대해 고정된 크기의 결과값을 반환하는 성질을 가진다.
  • 효율성: 어떤 입력 값에 대해서도 많은 자원과 시간이 소요되지 않고 처리되는 성질을 가진다.
  • 저항성: 결과값을 바탕으로 입력 값을 찾는 것이 불가능한 성질을 가진다.

✅ 해시 충돌(Hash Collision) 

데이터를 Key로 간소화하여 저장하지만 다른 ㅐㄴ용의 데이터가 같은 키를 갖는 경우 생기는 것을 해시 충돌이라고 한다.

해시테이블의 성능능을 떨어뜨리는 원인이 된다.

• 해결방법
  • 해시 함수 변경: 더 큰 숫자의 공간과 모듈 산술 값을 이용해 충돌을 최소화한다.
    (같은 수가 나오는 경우의 수를 줄인다.)
  • 자료구조 확장: 선형 조사법, 이중해시, 채이닝
• 구현 메서드(Method)
  • clear
  • size
  • getBuffer
  • print
  • put
  • remove
  • get

캐시(Cache)란 무엇인가?

• 캐시는 데이터나 값을 미리 복사해 놓는 임시 저장소를 가리킨다.

캐시(Cache)의 특징

• 사용했던 데이터가 임시 저장소에 담겨있기 때문에 다시 사용할 때 빠르게 접근하여 데이터를 불러올 수 있다.
• 계산된 값이 저장되어 있어 다시 계산하는 시간을 줄일 수 있다.

LRU(Least Recently Used Algorithm)란 무엇인가?

• 가장 오랬동안 참조되지 않은 페이지를 교체하는 알고리즘 기법이다.
• 캐시에 공간이 부족할 때 가장 오랫동안 참조되지 않은 항목을 제거하고 새로운 항목을 삽입하는 형식으로 동작된다.

LRU 동작 과정

1. 빈 캐시안에 순차적으로 캐시를 채워준다.
2. 4번째 값인 8을 사용할때 참조할 수 있는 캐시가 없으므로 가장 오랫동안 참조되지 않은 값인 1을 삭제 후 맨 뒤에 8을 추가한다.
3. 7번째 값인 3을 사용할때 참조할 수 있는 캐시가 2번째에 있으므로 해당 값을 참조하여 맨 뒤로 옮겨준다.

Python 코드

• cache hit(캐시 적중): 참조할 데이터가 존재한다.
• cache miss(캐시 부적중): 참조할 데이터가 존재하지 않는다.

Number = [1, 4, 5, 8, 3, 4, 3]
cache_size = 3
cache = []
for data in Number:
    if data not in cache:	# 참조할 데이터가 없는 경우
        # cache miss
        if len(cache) < cache_size:	# 빈 캐시가 존재할 경우
            cache.append(data)
        else:		# 빈 캐시가 존재하지 않을 경우
            cache.pop(0)		# 가장 오래된 데이터 삭제
            cache.append(data)		# 새로운 데이터 추가
    # cache hit
    else:		# 참조할 데이터가 있는 경우
        cache.remove(data)		# 참조된 데이터를 삭제
        cache.append(data)		# 참조된 데이터를 맨 뒤로 이동
        
# [1]
# [1, 4]
# [1, 4, 5]
# [4, 5, 8]
# [5, 8, 3]
# [8, 3, 4]
# [8, 4, 3]

응용문제

https://programmers.co.kr/learn/courses/30/lessons/17680

참고자료

• 위키백과: https://ko.wikipedia.org/wiki/%EC%BA%90%EC%8B%9C
• https://gingerkang.tistory.com/26#