📍 키워드
가상화
가상화(假像化, virtualization)는 컴퓨터에서 컴퓨터 리소스의 추상화를 일컫는 광범위한 용어이다.
이것은 다중 논리 리소스로서의 기능을 하는 것처럼 보이는 서버, 운영 체제, 응용 프로그램,
또는 저장 장치와 같은 하나의 단일 물리 리소스를 만들어 낸다.
아니면 단일 논리 리소스처럼 보이는 저장 장치나 서버와 같은 여러 개의 물리적 리소스를 만들어 낼 수 있다. / Wikipedia정리해보자면, 가상화란
1. 컴퓨팅 리소스를 '추상화' 시켜서
2. 하나의 물리 리소스를 여러개의 논리 리소스처럼 기능시키거나,
3. 여러 개의 물리 리소스를 하나의 논리 리소스처럼 기능하게 하는 것.
➡️ 예를들어 1000GB의 스토리지를 200GB씩 나눠, 5개의 스토리지인 것처럼 사용 가능.
일상생활속 가상화의 예시.
구글 클라우드, 네이버 클라우드등 클라우스 서비스. 자신들의 데이터 센터에 있는 컴퓨팅 자원들을 가상화 하여, 사용자들에게 나누어 주는 서비스. 할당받은 가상 cpu를 사용해 애플리케이션을 실행하기도 하고, 가상 스토리지에 데이터를 저장할 수도 있음.
AVL 트리
➡️ 스스로 균형을 잡는 이진 탐색 트리.
한쪽으로 치우친 편향 이진트리가 되면 트리의 높이가 높아지기 때문에 이를 방지하고자 높이 균형을 유지하는 AVL 트리를 사용함.
AVL 트리의 속성.
- AVL 트리는 이진 탐색 트리의 속성을 가짐.
- 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이다.
- 어떤 시점에서 높이 차이가 1보다 커지면 회전을 통해 균형을 잡아 높이 차이를 줄임.
- AVL 트리는 높이를 logN으로 유지하기 때문에 삽입, 검색, 삭제의 시간 복잡도는 O(logN) 임.
Balance Factor(BF)
➡️ balance factor는 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값.
Balance Factor(k) = height(left(k)) -height(right(k))
- BF가 1 이면, 왼쪽 서브트리가 오른쪽 서브트리보다 높이가 한 단계 높음.
- 0 이라면, 왼쪽, 오른쪽 서브트리의 높이가 같다.
- -1 이라면, 오른쪽 서브트리가 왼쪽 보다 한 단계 높다는 것.
회전
➡️ rb-tree와 회전하는 방법이 정확히 같다.
-
척추가 휘어있다면 척추 펴
-
척추가 펴지면, 드리프트 돌기
1, 2 과정은 좌우가 바뀌어도 마찬가지로 수행하면 됨.
rb-tree와 시간복잡도 차이.
- 데이터가 적은 경우
-삽입 : RB 트리의 평균 회전수가 AVL 트리에 비해 적어 RB 트리가 유리하다.
-탐색 : AVL 트리의 높이가 더 낮아 AVL 트리가 유리하다.
-삭제 : 최악의 경우 AVL 트리의 회전수가 더 많아 RB 트리가 유리하다.
- 데이터가 많은 경우
-삽입 : 삽입하기 전 어디에 데이터를 삽입할지 탐색이 필요하므로 높이가 낮은 AVL 트리가 유리하다.
-탐색 : AVL 트리가 유리하다.
-삭제 : 삭제할 데이터를 찾아야 해 일반적으로 AVL 트리가 유리하지만, 최악의 경우 회전수가 많아 RB 트리가 유리할 수도 있다.
힙영역(Heap)
컴퓨터 프로그램이 실행될 때 동적으로 메모리를 할당받는 영역을 의미함. 이는 주로 프로그램이 실행되는 동안 런타임에 동적 메모리 할당을 필요로 할 때 사용됨.
보이어 무어 알고리즘
➡️ 문자열 탐색 알고리즘.
input으로 주어진 문자열에 pattern 을 찾는 알고리즘. 오른쪽에서 왼쪽으로 탐색해 나감.
Bad_Match_Table 만들기.
글자별로 value를 만들어 줌.
value = max(1,length_of_pattern - index - 1)
- 중복되는 글자는 더 작은 값을 value로 가짐.
- 글자외에
*값을 추가해야 하는데,*는 input과 pattern이 mismatch일 때 그 글자가 BMT에 속하지 않을 때 사용하는 값으로value(*) = length_of_patern - 예를 들어 test의 BMT는
value(t) = 1(두 번째 t의 value)
value(e) = 2
value(s) = 1
value(*) = 4
input = THIS IS A TEST
pattern = TEST
- 맨 처음 test의 마지막 글자와 this의 s와 비교.
- mismatch. s는 BMT에 있음. value = 1.
- Shift right 1.
- t와 ' '비교.
- mismatch. ' '는 BMT에 없음. value = 4 (*의 value)
- Shift right 4
- 동일한 문자열이 나올때 까지 반복.
if (두 번째 글자부터 같다) {
그 위치부터 해당 value 값을 더하고;
더한 위치에 pattern의 끝이 배치되도록 한다.;
}