이누의 개발성장기

최단 경로 알고리즘 가장 짧은 경로를 찾는 알고리즘 대표적으로 3가지 케이스가 존재한다. 한 지점에서 다른 한 지점까지 도달할 수 있는 최단경로 / 한 지점에서 다른 모든 지점까지 도달할 수 있는 최단경로 / 모든 지점에서 다른 모든 지점까지 도달할 수 있는 최단경로 그래프를 통해 지점과 연결거리를 표현한다는 특징이 있다. 다익스트라 최단거리 알고리즘 개념 특정노드에서 다른 모든 노드로 가는 최단 경로를 계산한다. 음의 거리가 없어야한다는 조건이 존재한다 다익스트라 알고리즘은 그리디 알고리즘의 일종이라고 할 수도 있다. (매 상황에서 가장 비용이 적은 노드를 선택하는 과정을 반복하기 때문) 동작과정 출발노드 설정 최단 거리 테이블 초기화 (주어진 정보 외엔 모두 무한(최대값)으로, 자기자신은 0으로 임의..

본 게시글은 대학생이 수업을 듣고 내용을 정리한 것입니다. 따라서 완벽하지 않은 부분이 있을 수 있습니다. 아울러 본 게시글에 포함된 코드들은 대략적인 개념 이해만을 위해 작성된 것으로 완전하지 않은 코드임을 알려드립니다. Huffman Coding 등장 빈도에 따라 압축한다. 등장빈도가 큰 것은 짧게, 등장빈도가 작은 것은 길게 표현한다. 노드들을 리프 위치에 등장빈도 순으로 일렬로 정렬하고, 등장빈도가 작은 것부터 둘 씩 묶는다. 묶인 것은 합을 표현한다. 그렇게 트리가 완성되면 왼쪽은 0, 오른쪽은 1로 엣지에 표기한다. root부터 각 노드에 도달할 때까지의 엣지 코드가 최종 허프만 코드가 된다. 이는 랜덤한 경우에 더 유용하다. 연속된 문자가 많을 경우 각각을 8a와 같은 식으로 압축하는 것이 ..

본 게시글은 대학생이 수업을 듣고 내용을 정리한 것입니다. 따라서 완벽하지 않은 부분이 있을 수 있습니다. 아울러 본 게시글에 포함된 코드들은 대략적인 개념 이해만을 위해 작성된 것으로 완전하지 않은 코드임을 알려드립니다. Minimum Sparsing Tree 주어진 그래프에서 엣지들의 subset을 찾고 그 결과로 엣지 cost의 합이 최소인 '연결된' 그래프를 찾아라. 해당 그래프는 자연스럽게 트리가 된다. 이는 사이클이 없다. 싸이클이 있다고 가정하면 '엣지 cost 합 최소' 조건이 성립이 안되기 대문이다. 엣지는 '노드개수 - 1'일 것이다. 해당 질문에 대한 답은 그래프 형태에 따라 여러개일 수 있다. (유일하다는 것을 증명하기 위해서는 edge w..

본 게시글은 대학생이 수업을 듣고 내용을 정리한 것입니다. 따라서 완벽하지 않은 부분이 있을 수 있습니다. 아울러 본 게시글에 포함된 코드들은 대략적인 개념 이해만을 위해 작성된 것으로 완전하지 않은 코드임을 알려드립니다. Traversal Traversal : 모든 노드를 특정 순서로 방문하는 것 여기서 '방문'이란 단순히 거치는 것을 넘어서 해당 노드에서 특정한 작업을 수행하는 것이다. Traverse (Node *D) { if (D==Null) return; // Visit(D); => Preorder traversal Traverse(D->Left); // Visit(D); => Inorder traversal Traverse(D->Right); // Visit(D); => Post..

본 게시글은 대학생이 수업을 듣고 내용을 정리한 것입니다. 따라서 완벽하지 않은 부분이 있을 수 있습니다. 아울러 본 게시글에 포함된 코드들은 대략적인 개념 이해만을 위해 작성된 것으로 완전하지 않은 코드임을 알려드립니다. Priority Queue 내부 item들이 우선순위를 가진다. 보통 우선순위는 여러 기준이 있지만 최대한 Simple하게 설정해놓는 것이 학습에 용이하다. Queue에서 가장 우선순위가 높은 것이 나온다. (우선순위 변동은 없다.) 우선순위에 의해 정렬되어 있으면 : Del는 빠르지만, Insert는 느리다. 우선순위에 의해 정렬되어 있지 않으면 : Del은 느리지만, Insert는 빠르다. 어떤 자료구조를 활용해 구현할까 기본 BST를 제외한 AVL, 2-3, 2-3-4, Red-..

본 게시글은 대학생이 수업을 듣고 내용을 정리한 것입니다. 따라서 완벽하지 않은 부분이 있을 수 있습니다. 아울러 본 게시글에 포함된 코드들은 대략적인 개념 이해만을 위해 작성된 것으로 완전하지 않은 코드임을 알려드립니다. 2-3-4 Tree 2-3 트리의 확장판이다. Node key 값의 공간이 커진다. 모든 leaf가 같은 거리에 있다. 2-3-4 트리에 N개의 key가 있을 때 Height는 O(logN)이다. 해당 트리는 2-3 트리와 달리 새로운 key값이 들어오지 않아도 key 값이 3개인 상태에서 split이 가능하다. 트리에서는 새로운 키 값이 추가될 때 [노드내부 작업 - 링크 따라가기 - 새로운 노드 및 링크 생성]의 과정이 필요했다. 이 때 각 작업의 비용은 현재 작업이 어디에서 진행..

본 게시글은 대학생이 수업을 듣고 내용을 정리한 것입니다. 따라서 완벽하지 않은 부분이 있을 수 있습니다. 아울러 본 게시글에 포함된 코드들은 대략적인 개념 이해만을 위해 작성된 것으로 완전하지 않은 코드임을 알려드립니다. tree에 대한 Lemma 한 서브트리의 모든 값들은 전체를 sorting 해놓은 리스트에서 연속적이다. 수학적 귀납법으로 증명 가능 Base : 루트에서는 무조건 성립한다. Step : 특정 노드 X에서 성립한다고 가정하면, 해당 서브트리인 L과 R은 각각 왼쪽과 오른쪽으로 갈린다. 따라서 무조건 성립하게 된다. AVL Tree 균형잡힌 Tree라고 할 수 있다. 전체를 lotation 처리한 결과이다. 각 노드의 Lable에 L/R을 추가한다. L : Height of Left s..

본 게시글은 대학생이 수업을 듣고 내용을 정리한 것입니다. 따라서 완벽하지 않은 부분이 있을 수 있습니다. 아울러 본 게시글에 포함된 코드들은 대략적인 개념 이해만을 위해 작성된 것으로 완전하지 않은 코드임을 알려드립니다. Skip List 링크드 리스트에서 중간으로 향하는 포인터를 두고 이를 활용해 이진탐색처럼 활용할 수 있도록 구성한 리스트 하지만 insert, delete 등의 기능을 사용하면서도 이러한 조건을 유지하기란 쉽지 않다. 데이터가 바뀌지 않을 때만 한정적으로 사용하기에도 적절치 않다. 배열이 더 효율적이다. 더 좋은 자료구조가 없을까? Binary Search Tree (BST) class Node { int k; // key값 Node *l, *r; // child 노드 정보 트리의 ..

본 게시글은 대학생이 수업을 듣고 내용을 정리한 것입니다. 따라서 완벽하지 않은 부분이 있을 수 있습니다. 아울러 본 게시글에 포함된 코드들은 대략적인 개념 이해만을 위해 작성된 것으로 완전하지 않은 코드임을 알려드립니다. 링크드 리스트의 개념 링크드 리스트는 데이터를 순서대로 저장해준다. 계속해서 새로운 요소를 추가할 수 있다. 배열과는 다르게 각 요소는 사실상 독립적인 레퍼런스에 위치해있다. 각 요소를 노드라고 하고, data 속성과 next 속성을 보유한다. next에는 다음 노드에 대한 레퍼런스가 들어있다. 따라서 실제 메모리에 각 노드들이 여기저기에 흩어져있어도 next속성을 통해 이어진 것처럼 활용할 수 있다. 링크드 리스트의 구현 class Node { int a; Node *n; } 노드는..

본 게시글은 대학생이 수업을 듣고 내용을 정리한 것입니다. 따라서 완벽하지 않은 부분이 있을 수 있습니다. 아울러 본 게시글에 포함된 코드들은 대략적인 개념 이해만을 위해 작성된 것으로 완전하지 않은 코드임을 알려드립니다. Stack Insert/Delete만 제공 Push/Pop이라고 부름 Last in, First Out 성능 : Push O(1), Pop O(1) Stack Pointer(SP) : 스택의 최상위 부분. 주로 다음 저장될 위치, 즉 빈 공간을 지칭한다. Stack의 구현 int Stack[N]; int SP; int init() { SP = 0; } int isEmpty() { return SP == 0; } int Push(int x) { Stack[SP] = x; SP++; } ..