Domain/자료구조 (9) 썸네일형 리스트형 1. 연결리스트 연결리스트 다음 연결에 대한 참조만을 갖는 기본적인 연결리스트. 첫 항목부터 순차적으로 접근하기 때문에 O(n)의 시간 복잡도를 갖는다. 기본적인 자료구조로 사용되는 배열의 경우 물리적으로 인접하여 접근 시간 단축 및 캐싱에 유리하지만, 연결리스트는 그렇지 않다. 하지만 배열에 비해 삽입이 간단하며 배열에 비해 사이즈 변경에 신경 쓸 일이 없다는 점에서 유리하다. 결론적으로 삽입은 연결리스트, 조회는 배열이 유리하다. class Node{ friend class linkedList; private: int value; Node* link; public: Node(int v, Node* l):value(v),link(l) {} }; class linkedList{ private: Node* head; pu.. 2. 큐, 스택 1. 큐 삽입, 삭제 : O(1) FIFO(First In First Out)의 형태인 자료구조로 첫 노드와 마지막 노드를 가리키는 front, rear 변수가 존재한다. class queue{ private: Node *front; Node *rear; public: queue(){front=rear=0;} void insert(int x){ //맨 마지막에 삽입 됨 if(!front) front=rear=new Node(x); else rear=rear->link=new Node(x,0); } void remove(){ //제일 처음에 들어온 노드가 삭제 if(!front){ return; } if(!front->next){ //1개만 남은 경우 rear가 남은 것을 참조하는 것을 방지 front =.. 3. 이진 트리 이진 트리 모든 노드의 차수가 2이하인 트리. 완전 이진 트리 노드 수가 n개일 때 트리의 인덱스가 각각의 노드 인덱스와 일치 하는 트리. 쉽게 말하면 앞에서부터 순서대로 잘 채워진 이진 트리이다. 완전 이진 트리의 특성 - 부모의 인덱스 : i/2 - 좌측 자식의 인덱스 : 2*i, 우측 자식의 인덱스 2*i +1 - 1차원 배열로 표현 - 링크의 형태로 표현 순회 트리의 모든 노드를 방문하는 알고리즘 1. 전위 순회 root, left subtree, right subtree 순으로 탐색하는 알고리즘 2. 중위 순회 left subtree, root, right subtree 순으로 탐색하는 알고리즘 3. 후위 순회 left subtree, right subtree, root 순으로 탐색하는 알고.. 4. 히프 트리(Heap Tree) 히프 트리 삽입은 일반적인 큐와 같이 맨 마지막에 삽입이 되고 삭제의 경우 우선순위 큐의 형태로 삭제되는 트리이다. 중요한 점은 부모는 항상 자식보다 크면 최대 힙, 자식보다 작으면 최 소힙이다. 히프트리는 완전 이진 트리로 배열로 구현한다. 최대히프의 삽입 먼저 가장 트리의 마지막 위치에 삽입한 뒤, 부모와 비교하며 올라간다. 최대히프의 삭제 우선순위가 가장 높은 루트를 삭제하고 가장 마지막 노드를 임시적으로 루트에 배치하여 좌우 자식과 비교하며 노드를 내린다. class heap{ private: int[] tree; int capacity; int size; public: heap(){ capacity=100; size=1; tree=new int[capacity]; } //최대 히프 트리의 삽입 .. 5. 이진 탐색 트리(BST, Binary Searching Tree) 이진 탐색 트리 이진 탐색 트리는 아래의 조건을 만족해야 한다. ①각 노드에서 왼쪽 자식은 부모의 값보다 작고, 오른쪽 자식은 부모의 값보다 크다. ②각 노드는 모두 고유한 값을 갖는다. 연결리스트로 구현된 이진 탐색 트리 코드 class BST; class Node{ friend BST; private: int key; Node *left; Node *right; public: Node(int k=0, Node *l=0, Node *r=0){ key = k; left = l; right = r; } }; class BST{ private: Node *root; public: BST(){root=0;} void insert(int x){} void remove(int x){} }; 이진 탐색 트리에서의 .. 6. 그래프 1. 그래프 표현법 - 무방향, 비가중치 인접행렬 희소그래프가 아닌 경우에 주로 사용된다. (희소 그래프일 경우 탐색에 불필요한 자원이 낭비된다.) 정점이 서로 연결된 경우 1로 표시하고 그렇지 않은 경우 0으로 표시한다. 장점으로는 구현이 간단하고 연결을 확인하는데에 O(1)의 시간복잡도만 필요하다. (1과 2의 연결확인은 length[1][2]의 값을 확인하면 됨.) 단점으로는 특정 노드에 연결된 모든 노드 n개를 방문하기 위해서 O(n)의 시간 복잡도가 필요하다. 그렇기에 위에서 말한 희소그래프가 아닌 경우에 주로 사용된다. 예를들어 노드가 1억개이고 간선이 두개 뿐인 희소그래프를 고려해보면, 특정 노드에 연결된 노드가 무엇인지 찾기 위해 1억번의 탐색이 필요하다. class Graph{ priva.. 7. 탐색 1. 순차탐색 시간복잡도 : O(n) 특정 값을 순서대로 탐색하여 찾는 탐색 알고리즘. Template int SeqSearch(T*a, const int n, const T& k) // a[0:n-1]을 왼쪽에서 오른쪽으로 탐색한다. // a[i]의 키 값이 k 와 같은 가장 작은 i를 반환한다. // 그런 i가 없으면 -1을 반환한다 { int i; for (i=0; i= n) return -1; return i; } 프로그램 분석: 최선의 경우: 1, 최악의 경우: n, 평균의 경우: (n+1)/2 시간복잡도: O(n) 2. 이진 탐색 시간복잡도 : O(log n) 특정 값을 기준으로 두고 값을 찾는다. 중요한 점은 배열이 정렬되어 있어야 한다는 점이다. template int BinarySearc.. 8. 정렬(Sort) 1. 삽입 정렬 시간복잡도 : O(n²) template void Insert(const T& e, T *a, int i) {// e를 정렬된 리스트 a[1:i]에 삽입하여 결과 // 리스트 a[1: i+1]도 정렬되게 한다. // 배열 a는 적어도 i+2 원소를 포함할 공간을 가지고 있어야 한다. // a[0] = -∞; 가 저장되어 있음. while(e 이전 1 2 다음
