2-3 TreeDefinitionEach Node has 2 or 3 Children, Not allowed to have a single child모든 노드는 2개 혹은 3개의 자식 노드를 가진다. 한개의 자식 노드를 허용하지 않음All leaves at the same level 모든 leaf는 같은 레벨을 가짐. 즉, 루트에서부터 leaf까지의 거리가 항상 같음N개의 key가 있다면, O(log N)이다 ex) 만약, 다 자식 노드가 2개씩 있다면, 높이가 3일때 \(2^3 -1\)개       자식노드가 3개씩 있다면 최대 \(\frac{3^3-1}{3-1}\)2 트리일 때는 안됐던 (AVL) 모든 트리의 높이가 똑같이 유지할 수 있도록 할 수 있음2 트리일 때는 1차이까지는 허용하여 주어야 하는..

BST : 최악의 경우는 여전히 좋지 않음 -> AVL Tree로 이를 해결하고자 함같은 데이터를 가지고 있어도 다른 모양의 트리가 나올 수 있음오른쪽 경우가 생기는 것을 막아보자AVL Tree IdeaRoot가 어떤 수인지에 따라서, 왼쪽과 오른쪽의 균형이 맞지 않을 수 있음 양쪽의 노드의 개수가 비슷한 것을 선호 : 균형잡힌 트리→ :  균형 잡힌 트리를 만들기 위해 root의 숫자를 바꿔주고, 트리의 모양을 바꿔줌Root 뿐만 아니라 서브 트리의 root에서도 보정이 일어날 수 있음 AVL Tree Definition기본 BST 정의에 추가되는 것 Each Node has Two Labels : L & R - 각각의 서브트리의 높이Condition : |L - R| → 모든 노드에서 양쪽 서브트리..

Direct Execution응용프로그램이 실행할 때 모든 권한을 다 주는 것문제점 : 프로세스가 여러개가 돌면 불가능함OSProgram[프로그램이 실행되기 위한 기본 환경 세팅]Create entry for process list - entry = PCB프로세스를 제어하기 위해 PCB를 생성한 후 process list에 넣기Allocate memory for program프로세스가 사용할 메모리 영역 할당 Load program into memory 실행을 위한 instructions 로딩( 메모리 적재)complie 한 exe 파일은 storage에 저장되어 있기 때문임Set up stack with argc/argv 응용 프로그램이 실행되기 위한 user stack만들기 (argc/argv를 넣어..

Program vs ProcessProgram : 기계어 instructions + 디스크의 static data의 집합컴파일된 exe파일기계어 instruction : cpu가 이해하는 언어 static data : 컴파일 될 때 해당 메모리 영역이 유지되며, 변경된 값이 유지되고, 어디서든 접근 가능 ex) global, staticexe파일이 여러번 실행 >> process 여러개 생성  Process : 실행되고 있는 프로그램메모리 : instructions (메모리에 적재 - code) & data (프로그램 실행에 따라 변경됨)레지스터 : program counter (cpu가 실행해야하는 인스트럭션 위치를 가리키는 레지스터 ) & stack pointer 등오픈한 파일의 list와 상태정보 ..

[지금까지 한 것]배열 - 단점 : size의 제한Linked List - 단점 : search가 느림 (자료가 조금만 커져도)>> size도 바꿀 수 있고 search도 빠른 자료 구조가 없을까? search를 빠르게 하는 것 : binary search→ Linked List와 비슷한데, binary search가 되도록 하고 싶음  Skip Listnode를 건너뛸 수 있는 Linked ListLinked List의 단점을 그대로 가지고 있음 Binary Search Tree ( 이진 탐색 트리 )다양한 버전이 존재함Linked List : 다음 것이 있음 ↔ Binary Search Tree : 왼쪽, 오른쪽이 존재함 (포인터가 두 개 존재함)중간 값이 계속 존재하는 것이 이상적임 → 이번 경우에..

1. 2차원 배열 (n x n)  O(\(n^2\)) >> O(nm)compact한 입력이 아닐 때 #include #include int n, m;int MAP[1000][1000];int Stack[10000];int SP;void Push(int x){ Stack[SP++] = x; return;}int Pop(){ return Stack[--SP];}int isEmpty(){ return (SP == 0);}// x에서 y로 갈 수 있다고 표시void setLink(int x, int y){ MAP[x][y] = 1; return;}int LastForward[1000] = {0}; //노드마다 가지고 있는것int NextFoward(int x){//node 번호 ..

Definition of Linked ListConsists of NodesNode: unit of storage (item)Nodes are linked with pointers(link) - 포인터가 옆에 붙어있다 (what does that mean?)메모리 아무 곳에나 흩어져있음논리적으로는 1차원pointer to next node : 단순히 주소가 저장되어 있는 것Q. 화살표는 코드에서 무슨 뜻일까? A. 다음 노드의 주소가 값으로 적혀있다화살표를 따라가면 다음 노드가 어디에 있는지 알 수 있다 프로그램의 head는 변수로 가지고 있어야한다 - head는 노드가 아니다Code of nodeclass Node { int a; Node *n;};Q. node 옆에 *이 없다면 어떻게 될까A. 노드가..

미로찾기 : 알고리즘이 달라도 성능 차이가 나지 않음 Definition of Equivalence Relation (Equivalence Relation의 정의)Definition of Relation의미가 있는 관계 순전히 집합으로만 정의된 관계 ex) Given a Set A a Relation on A is any subset of A \(\times\) AA = {1, 2, 3, 4} R = {(1,3) (3,4),(1,1),(2,2)} (A\(\times\)A인 수많은 집합의 부분집합)We write 1R3 to mean (1,3) ∈ R extreme example)  관계가 성립한다는 것을 Relation 2  Equivalence Relation (동치 관계인 Relation)같다는 관계..

StackPush(Insert) / Pop(Delete)만 제공함Last in, First outQ. Stack을 가지고 sorting 할 수 있는가? A. 안되는 경우 : 3, 8, 2와 같이 중간수, 큰 수, 작은 수의 순서가 전체에 한번이라도 등장하면 sorting 할 수 없음 Q. 함수 호출 시 스택A. a함수가 b함수를 , b함수가 c함수를 실행시킨다면, c, b, a 순으로 리턴됨 스택의 구조와 같다.성능 Push : O(1)Pop : O(1)구현Stack Pointer : 빈 자리를 가리키는 ( 개인 취향 ) 배열 인덱스 (보통 빈 자리를 가리킴) - 배열의 크기(가용)을 나타내기도 함 //Stack 구현int Stack[100]; //Stackint SP; //stack pointerint..

Problem definition (문제 정의)text : simple string of characters (문자열을 찾을 텍스트)pattern : simple string of characters (찾을 텍스트 - 패턴)to do : find where in the text the patter occurs 패턴이 나타나는 텍스트 찾기AlgorithmAlgorithm시간공간naive \(O(mn)\) \(O(n)\) or \(O(1)\)DFA (Deterministic Finite Automaton) \(O(\sum m + n)\) - 테이블 제작 + 텍스트 읽기 \(O(\sum m\) - 테이블 메모리KMP (Knuth Morris Pratt) \(O(m+n)\) \(O(m)\)* n : 텍스트의 길..