해나의 컴공생존기

1. vector Vector: Variable-Size Array(사이즈가 늘어나고 줄어들 수 있는 배열) Sorted Search: O(log n), Insert: S+ O(n) , Delete: S+ O(n) Unsorted Search: O(n), Insert: S + O(1), Delete: S + O(1) 2. Dummy Nodes Standarad Linked List에 대부분 포함되는 구조. 처음에 만들때 노드를 두개 만들고 하나는 마이너스 무한대 하나는 플러스 무한대 값을 집어넣는다. 이 두 값은 실제로 사용하는 값은 아니고, 미리 경계를 정해놓는 것이다. 이렇게 해놓으면 못찾았을때 (실패했을 때), P와 L이 NULL인 경우가 없어지게 된다. 3. Circular List Circula..

Linked List 연속적인 노드 Node : unit of storage (item) Nodes are linked with pointers Linked list는 배열과 다르게 메모리 아무데나 있을 수 있다. 대산 한 노드에 가면(=한 노드의 주소를 알아서 그곳의 내용을 읽으면) 다음에 갈 노드의 주소가 적혀있다. 즉 노드들이 포인터들도 연결이 되어 있는 것이다. Linked List의 노드의 구조를 살펴보면 다음과 같다. Whole List 이런식으로 구성이 되어있다. (화살표 등은 사람이 보기 쉽게 표현한것이다.) 마지막 노드에는 더이상 갈 곳이 없으므로 null값을 넣는다. 첫번째 노드로 갈때는 어쩔수 없이 그 노드가리키는 포인터를 가지고 있어야 한다. Code for List class No..

Equivalence Relation 정의 관계의 정의 Given a set A, a Relation on A is any subset of AxA Ex) A = {1, 2, 3, 4}, R = {(1,3), (3,4), (1,1), (2,2)} We write 1R3 to mean (1,3) ∈ R An extreme example Relation '

Queue Insert/Delete만 제공 First in, First out( 먼저 들어오는게, 먼저 나가는 것) 성능: Insert O(1) , Delete O(1) Queue 구현 Stack과 다르게 Queue는 Head와 Tail 두개가 필요하다. 앞서 다룬 stack보다 좀더 생각할 거리가 늘어나게 된다. 만약 새 값이 insert 될때 Tail과 Head는 어떻게 될까? head는 그대로 있고 Tail은 위로 한칸 움직일 것이다. 반대로 값이 delete 되면 Head가 위로 한칸 올라갈것이다. 그렇다면 다음과 같은 상황에서 Tail에 새 값이 새로 insert가 되면 어떻게 될까? 간단하다 제일 밑의 빈공간에 Tail이 가리키게 된다. 아래의 그림과 같이 말이다. 그러면 이 상황에서 좀 더 ..

Stack Insert/Delete만 제공 Push/Pop이라고 부름 Last in, First out(나중에 들어오는게, 먼저 나가는 것) 성능: Push: O(1), Pop: O(1)(넣는것을 push, 빼는것을 pop) Stack 구현 Stack Pointer는 값이 다음에 들어올 자리를 뜻한다. Stack Code int Stack[N]; int SP; int init() {SP = 0} int isEmpty() {return SP == 0;} int Push() { Stack[SP] = x; SP++; } int Pop() { SP--; return Stack[SP]; }​ # 미로찾기 이런 미로 문제를 해결하는 알고리즘 중에 DFS 와 BFS가 있다. 오늘은 DFS로 미로를 찾는 과정을 알아볼..

Problem Defintion Text : 간단한 문자열 Pattern: 간단한 문자열 To Do : 패턴을 발생하는 곳 찾기 Text : abababcabcabcdabccbaabdabcabcdabcd 다음과 같은 text에서 abcabcd 를 찾는 문제라고 생각해보자. 사람이라면 한글자 한글자 보겠지만 굉장히 느린방법이고 사람중심적인 방법이다. 1) Naive 알고리즘 Naive 알고리즘은 아까 위에서 설명한 사람이 한 것과 같은 방식의 알고리즘이다. 사람이 할때는 패턴을 하나씩 옮겼지만 컴퓨터로 이를 구현할때 어떻게 표현해야 할까? 코드로 표현하면 다음과 같다. // n 은 문자열의 길이 // m은 패턴의 길이, output은 결과 int naivematch ( char T[], int n, cha..

대부분의 자료구조는 Search, Insert, Delete가 중요하다. 오늘은 배열의 Search, Insert, Delete 를 보려고한다. 배열 상태에 따라 방법이 달라진다 Packed vs Unpacked : 빈자리가 있나 없나 Sorted vs Unsorted : 정렬이 되어있나 없나 총 4가지 경우를 보려고 한다. Case 1 ) Packed, Unsorted 가장 간단한 방법 Item의 개수를 표시하는 변수가 따로 필요 하다. => 위 배열을 보면 item이 5개 있으니 어딘가에 5라고 저장 해놓으면 해결된다. Search : n개의 배열에서 어떤 값 x가 있는지 없는지 확인, O(n) Insert : [Search, O(n)], O(1)(상수시간) Delete : [Search, O(n)]..

우선 Merge Sort에 대해 알아 보기 전에 Merge에 대해 알아보자. Merge 와 Merge Sort 는 서로 같은 뜻 같지만 실제로는 둘이 조금 다르다. Merge 알고리즘은 soring 된 배열 두개를 합쳐서 새로운 배열을 만드는 알고리즘이다. 두 배열을 앞에서부터 비교해 나가면서 작은것들을 복사해서 한 배열에 넣는 알고리즘이다. 이러한 알고리즘을 이용하는 것이 Merge Sort 이다. 어떤 배열을 나눈다음에 서로 2그룹씩 합치면서 점점 올라오면서 정렬하는 것이 Merge Sort의 기본적인 로직이다. int sort(int a[], int n) { int h; int b[n]; h = n / 2; // copy a[] to b[] sort(b,h); // 반 나눈거의 앞부분 sort(b+..

Selection Sort의 알고리즘 로직은 다음과 같다. 배열이 있으면, 전체에서 제일 작은 값을 앞으로 옮긴다. 그 다음 나머지 부분에서 제일 작은 값을 앞으로 옮긴다. 그렇게 반복해서 결과적으로 정렬된 배열을 만들어 내는 것이다. int sort (int a[], int n) // n 은 배열의 크기 { //m 최소값 인덱스, t 는 교환할때 활용 int i, j, m, t; for (i = 0; i a[j] ) m = j; t= a[i]; a[i] = a[m]; a[m]=t; // 두 값의 교환 } return; } 먼저 코드를 보자면 첫번째 루프에서 0부터 n 까지 돌아가는데 거기서 최소값을 찾아서 m에 저장한다. 그리고 그 안에서 한번 더 루프가 돌아가는데 j 는 i 부터 n 까지 가장 작은 ..

Array ( 배열 ) 정의 : 연속된 주소, 동일한 Type 장점 : n개 중 k번째 access(Read&Write)가 상수 시간에 가능, Search(어떤 x가 배열안에 있느냐?)가 빠름 단점 : 크기 변화 비용이 크다. Insert, Delete가 느릴수 있다. 사용 : 변화가 없거나 드문 자료 배열에서 가장 흔히 쓰이는 search 방법은 linear search 이다. 이는 하나하나 다 읽어보며 찾는 방법이고 모두 다 읽어봐야해서 크게 효율적이지 않다. 또 다른 방법은 Binary Search 이다. 이 방법은 sorting 되어있는 상태에서만 사용가능하다. 기본적인 로직은 절반을 확인하고 그의 절반..절반.. 을 확인하는 방법이다. 코드로 나타내면 int search(int a[], int ..