Homile

완전 탐색?

• 컴퓨터의 빠른 계산 능력을 이용하여 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 말합니다.
• 효율성 관점에서는 최악의 방법입니다.
• '무식하게 답을 찾는다'라고 하여 Brute-Force(브루트 포스)라고도 불립니다.

완전 탐색 기법

• 완전 탐색 기법을 이용하기 위해서는 여러 알고리즘 기법이 사용된다.
• 완전 탐색 기법만을 가지고는 알고리즘 문제를 풀기에는 적합하지 않습니다.

주로 사용되는 알고리즘 기법

1. 단순 Brute-Force
   • 알고리즘 기법을 사용하지 않고 단순히 반복문을 통해 답을 구하는 방법입니다.
2. 비트 마스크(Bitmask)
   • 2진수를 이용하는 컴퓨터의 연산을 이용하는 방식입니다.
3. 재귀 함수
   • 재귀 함수를 통해서 문제를 만족하는 경우들을 만들어가는 방식입니다.
   • 무한루프에 빠질 수 있음을 주의해서 작성해야 합니다.
4. 순열(Permutation)
   • 완전 탐색의 대표적인 유형으로 서로 다른 N개를 나열하는 순열을 구하는 방식입니다.
5. BFS / DFS
   • 완전 탐색과 BFS/DFS 문제가 코딩 테스트에 많이 나오고 있으며, 대표적인 문제로 길 찾기 문제가 있습니다.

📌 힙(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

스택(Stack)

데이터를 차곡차곡 쌓아 먼저 들어간 데이터가 나중에 나가는 후입선출(Last In First Out, LIFO) 방식을 사용하는 자료구조이다.

JavaScript Code 및 사용 메서드

• push(): 삽입
• pop(): 삭제

let stack = [];

stack.push('data 1');	
console.log(stack);			// ['data 1']	
stack.push('data 2');
console.log(stack);			// ['data 1', 'data 2']
stack.push('data 3');
console.log(stack);			// ['data 1', 'data 2', 'data 3']

stack.pop()
console.log(stack);			// ['data 1', 'data 2']

큐( Queue)

먼저 들어온 데이터가 먼저 나가는 선입선출(First In First Out, FIFO)방식을 사용하는 자료구조이다.

현실에서 줄을 설때 앞사람부터 나가는 형식이라고 생각하면 된다.

JavaScript Code 및 사용 메서드

• push(): 삽입
• shift(): 삭제

let queue = [];

queue.push('data 1');			
console.log(queue);			// ['data 1']
queue.push('data 2');
console.log(queue);			// ['data 1', 'data 2']
queue.push('data 3');
console.log(queue);			// ['data 1', 'data 2', 'data 3']

queue.shift();
console.log(queue);			// ['data 2', 'data 3']

덱(Deque)

스택과 큐의 결합형 자료구조이며, 어디서든 데이터가 나가고 들어올 수 있다.

JavaScript Code 및 사용 메서드

• push(): 삽입
• unshift(): 삽입
• pop(): 삭제
• shift(): 삭제

let deque = [];

deque.push('data 1');		
console.log(deque);				// ['data 1']
deque.unshift('data 2');
console.log(deque);				// ['data 2', 'data 1']
deque.push('data 3');
console.log(deque);				// ['data 2', 'data 1', 'data 3']

deque.shift();
console.log(deque);				// ['data 1', 'data 3']
deque.pop();
console.log(deque);				// ['data 1']

캐시(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#