자료구조 7주차 linked list 처럼 쓰면서 중앙을 찍을 수 있도록 하기 Binary Search Tree Contents Skip List Idea from Linked List Binary Search Tree Definition Search Algorithm, Insert Algorithm, Delete Alogrithm Proofs of Correctness and Performance Skip List Definition of Binary Search Tree 모든 곳에서 왼쪽은 전부 작고, 오른쪽은 전부 큰 구조 == Tree 지금 보는 BST는 루트에 중앙값이 오지 않아도 된다고 하자. NODE contains KEY One ROOT Node (unless empty BST) → 예외는..
자료구조
자료구조 6주차 Linked List 배열의 문제 사이즈를 늘릴 때 힘들다… 배열을 키울려면 다른 곳에다 새로 만들 수 밖에 없다. 사이즈 바꾸는 것을 해결하기 위해 사용되는 Linked List Contents Definition of Linked List(정의) Implementation(이행) Performance(성능) Sample Application(+다양한 적용 기술들) Definition of Linked List Consists of Nodes Node : Unit of storage (item) Nodes are linked with pointers ( 다음 노드를 가리키기 위한 포인터 ) Linked List는 배열처럼 연속된 주소를 가지고 있지 않고, 여기저기 흩어져 있다. 다시 한..
자료구조 5주차 Stack & Queue Stack Insert/Delete만 제공 Push/Pop이라고 부름 Last in, First out 성능 : Push : O(1), Pop: O(1) Stack sort 가장 큰 값이 중앙, 가장 작은 값이 마지막에 있으면 수행 불가 stack stackSort(stack stk) { stack tempStk; while(!stk.empty()) { // 스택에서 하나씩 pop int temp = stk.top(); stk.pop(); // tempStk이 비어있거나, tempStk의 top() 값이 temp보다 클 때까지 pop하여 tempStk에 push while(!tempStk.empty() && tempStk.top() > temp) { stk.pus..
자료구조 4주차 String matching : 문자열 일치 : 완전히 같다 수준을 이야기함 : 배열에서 문제를 품 Problem Definition Text : simple string of characters pattern : simple string of characters to do : whre in the Text the Pattern occurs 알고리즘 알고리즘 Naive (BruteForce) DFA (Deterministic Finite Automation) KMP (Knuth, Morris, Pratt) 시간 O(mn) O( E 공간 O(n) O(m+n) O(m) - 답만 계산하는 것보다 추가적으로 더 계산하는 게 편할 때가 있음 char T[100] = { 'a','b','a','b'..
Array for Search, Insert, Delete Search, Insert, Delete 자료구조의 가장 중요한 연산들 모든 자료구조에 해당하는 것은 아님 Item : 저장되는 대상을 부를 이름 정수만 가능한 것으로 생각하자…일단은 file system에 file을 넣고 빼고 하는 과정 Array 메모리에 연속되게 저장됨 How to Store Items in an Array? Packed vs Unpacked Packed : 한쪽으로 모임 Unpacked : 사용 안 하는 자리가 중간 중간 존재 배열이 항상 가득 찬 것은 아님 빈 자리를 한 쪽으로 모은다? Sorted vs Unsorted Item들이 정렬된 상태를 유지하느냐 아니냐 Item의 개수를 표시하는 변수가 따로 필요 값이 할당되어..
자료구조 2주차 수학적 귀납법 base , step 이 존재해야 함. P(1)이 참이고, P(n-1) → P(n)이 참이면 P(n)은 모든 자연수 n에 대해서 참이다. 명제 P → Q 의 의미 “p→q” vs “p→q&q→p” 100점 → chicken T → T ⇒ T T → F ⇒ F F → T ⇒ T (?) vacuous true F → F ⇒ T if n>3 then n^2>10 n=1? → vacuously true다. P(1)이 참이고(base), P(n-1)→P(n)이 참이면(step) P(n)은 모든 자연수 n에 대해서 참이다. P(n-1) False 경우는 결과는 Vacuously True이므로 이야기를 안함. True인 경우에만 할 이야기가 있음. 그래서 참일 때만 언급을 함. ( ==..
건국대학교 자료구조 강의 정리, 요약 컴퓨터에서 “바로” 할 수 있는 일과 못하는 일을 구분해야함. CPU ↔ Memory 그림 요약 컴퓨터가 계산을 수행하는 과정을 간략히 소개 변수와 계산 과정에 대한 정보가 Memory에 할당 1에서 수행한 것들은 모두 주소 정보가 존재하고 CPU와의 상호과정에서 Bus(전선)이 이 둘을 연결해주는 역할을 수행 왜 주소 정보를 가지나? == Memory에서 특정위치에 저장되어 있는 값을 가져올 수 있어야 하기 때문. 과정 1) IP에서 명령이 담겨있는 2016번지 주소를 인지 2) 2016이 Add(ress) 버스에 올라감 3) 2016로 가서 37을 Data 버스를 통해 불러옴 4) CPU가 37이 무슨 뜻인지 해석을 해서 그 작업을 실제로 진행 5) Add 버스에..
