CS(76)
-
[CS] Red-Black Tree
BST의 일종 BST의 문제점을 해결하기 위해 탄생 BST의 문제점이란? BST는 부모 노드의 왼쪽 자식 노드는 부모보다 작아야 하고 오른쪽 자식 노드는 부모보다 커야 한다. 이 조건을 만족하는 BST 중 다음을 생각해보자. 부모 노드보다 작은 자식만 생기게 되는 경우. 이 경우 왼쪽으로만 쭉 길어지게 된다. 탐색에 걸리는 시간 복잡도 또한 O(n)이 되고 만다. 삭제와 삽입 또한 마찬가지다. 이러한 상황을 불균형이라고 하는데 불균형을 해결하기 위해 red-black tree가 나오게 되었다. Red-Black tree는 어떻게 해결했는가? red-black tree를 활용하게 되면 worst case에서도 탐색, 삽입, 삭제를 모두 O(logn)에 할 수 있게 된다. 그 이유는 불균형이 발생하게 되면 ..
2023.08.17 -
[CS] 최대최소힙
최대최소힙은 엘리베이터와 같다. 삽입할 때는 아래에서부터 위까지 올라가고 삭제하면 위에서부터 아래로 내려간다.
2023.08.12 -
[CS] Array와 Linked List의 차이
여러 개의 목판으로 이루어진 흔들다리를 생각해보자. Array는 목판마다 번호를 적어 놓았다. Linked List는 목판을 이어 붙이기만 했다. [탐색] 이번에는 다리에서 목판을 찾아야 한다고 생각해보자. Array의 경우 목판 별로 숫자를 적어놨다. 그러니 바로 찾을 수 있다. O(1) Linked List의 경우 숫자를 적지 않고 이어 붙여놓기만 했다. 그러니 처음부터 찾아야 한다. O(n) [삭제] 흔들 다리 앞이 낡아서 목판 하나를 끊어내야 한다고 생각해보자. Array의 경우는 처음을 끊어내고 한쪽 다리의 목판을 하나하나씩 떼고 옮겨 새로 붙이고 번호도 새로 적는다. O(n) Linked List는 그냥 끊어내면 된다. O(1) [삽입] 이번에는 흔들다리 앞에 목판 하나를 추가해야 한다고 생각..
2023.08.11 -
[CS] 논리적 공간과 물리적 공간
논리적 공간은 컴퓨터가 인식하는 공간(가상메모리) 물리적 공간은 실제 데이터가 메모리에 존재하는 공간(실제메모리)
2023.08.11