코드네임 :

야 이거 틀림!!!!!   제어(control) 해저드 해법 중 동적 branch 예측

Pipelining: instruction의 수행 갯수를 늘림으로써 성능을 향상시킴- 여러 instruction을 병렬처리로 실행 (겹치는 실행)- '각' instruction의 실행시간 latency는 그대로- 만일 4개의 세탁소를 pipeline 한다 하더라도 4배 빨라지지는 않음..- instruction set 설계는 pipeline 구현의 복잡도에 영향 [ Pipeline Hazards ]1. 구조적 해저드- 세탁기가 한번에 두곳에서 쓰이려고 한다면 불가능- 하드웨어가 필요한 명령어 조합을 지원하지 못해서  2. 데이터 해저드-  명령어를 실행하는데 필요한 데이터가 아직 준비되지 않은 경우 - 이거 앞에서 WB로 연산으로 업데이트 된 데이터를 받아야만 다음 연산에서           쓰일 수 있..

흠름름름 틀릴수도 잇더여 no. 104header length = 20total (IP datagram) length = 1500bytespayload length = 1500 - 20 = 1480 bytes no. 105header length = 20total (IP datagram) length = 548bytespayload length =  548- 20 = 528bytes  두 IP header의 어떠한 부분으로부터 fragmentation이 되었음을 알 수 있는가?>> 각각의 Flags 필드로부터 이들이 fragmentation 되었음을 알 수 있다.       즉 104번의 flag : 0x1와 105번 패킷의 flag : 0x0으로부터 알 수 있다. (0x1 : 현재 패킷이 단편화 되었고..

이진 탐색 트리 (최악의 경우 O(N)) 의 성능을 개선한AVL 트리, 레드-블랙 트리, B-트리의탐색, 삽입과 삭제 연산의 시간복잡도는 모두 O(logN) 그런데! O(logN)보다 좋은 성능을 갖는 자료구조는 없을까?>> Hash Table!  : 데이터의 값과 Hash 함수에 의해 삽입 위치가 결정되는 자료구조 : 충돌의 경우를 무시한다면 삽입, 삭제, 검색에 O(1)만 소요됨[ Hash Table의 충돌 해결법 ] 1. Chaining  2. Linear Probing 어라.. 문제점 1해결!!어라.. 문제점 23. Quadratic Probing을 통한 해결!4. Double Hashing

균형을 고려하는 AVL과는 또 다른 트리!  m차 B-트리 의 조건1. 모든 leaf 노드의 깊이가 동일  2. 노드 당 자식 수는 [m/2] ~ m개 (leaf 노드 제외) *[m/2] : 올림 함수  3. 자식 노드의 수는 데이터 수보다 1 많음 (leaf노드 제외) >> 즉, m차 B트리 에서 노드 내 데이터의 수는 최대 m-1개  4. 단일 노드 내에서 데이터는 정렬됨  5. 트리의 관점에서도 데이터는 정렬됨 B-트리에서의 데이터 탐색 과정높이에 따라 결정되므로.. 시간복잡도는 O(hN) = O(logN) [ B-트리에서의 원소 삽입 ]1. 데이터 수 제한을 넘어서지 않는 경우에서의 삽입 - 새 데이터가 들어갈 적절한 리프 노드를 선정 - 해당 리프 노드에 데이터가 추가될 여유가 있는 경우 그대로..

두개의 클래스를 고려1. Node Class : data, left, right, height 값2. AVL Class : 나머지 모든 것   # Case 1 (LL) # Case 2 (RR) # Case 3 (LR) # Case 4 (RL)    https://github.com/codenameVien/DataStructure/blob/main/AVLTree.ipynb DataStructure/AVLTree.ipynb at main · codenameVien/DataStructureContribute to codenameVien/DataStructure development by creating an account on GitHub.github.com

NIL 닐일반적으로 이진 트리의 노드는 값과 left 및 right를 가지는데, left나 right 중 하나 이상이 None 일 수 없음 - 즉 좌측 자식이 없거나, 우측 자식이 없거나, 둘다 없거나모든 None 을 NIL 로 규정 시 아래와 같은 트리를 얻을 수 있음 모든 leaf노드 is NIL값을 가지는 모든 노드는 내부 노드              Recoloring & Restructing  걍 아래는 위에꺼 손으로 해보기 전 적어놧던 개념.. Recoloring 과정>> 원소 추가시엔 Red만 추가하기 떄문에, Black의 수는 신경 쓸 필요 없고, Red 연속만 신경쓰기  그런데 중간에 삼촌 노드 땜에 만족하지 않는 경우가 생겼다! ( NIL = 검정)이땐 어떻게 해야 할까? Restruc..

이진 탐색 트리의 한계- 노드가 N개인 이진 탐색 트리에서 삽입/삭제/탐색에 드는 시간복잡도 : 최악의 경우 O(N) >> 아래와 같은 최악의 불균형 모양일 때,>> 80을 삽입하고자 하면 6개 노드를 모두 다 돌아야함.. >> O(N)BUT!!>> 균형 잡힌 트리의 경우>> 최악의 상황이더라도 연산에 드는 시간복잡도 : O(logN)>>> 높이 h만큼의 노드를 탐색해야하므로 시간복잡도는 O(hN)>>> O(hN) = O(logN) 트리에서 균형이란?임의 노드의 Balance Factor= 좌측 서브트리의 높이 - 우측 서브트리의 높이 >> 아무것도 없는 부분은 -1로 간주함 AVL 트리= 균형잡힌 이진탐색트리(조건)1. 이진탐색트리 이자2. 모든 노드의 Balance Factor의 절대값이 1 이하인 ..