728x90 분류 전체보기60 자료구조 - 우선순위 큐 우선순위 큐(priority queue)는 우선순위를 가진 데이터가 먼저 나가는 형식을 뜻한다. C++에서는 앞서 구현해본 스택이나 큐를 이용해서 우선순위 큐를 구현할 수 있다. 우선순위 큐는 최소 우선 순위큐 / 최대 우선 순위큐로 구분 가능하다. 1. 앞서 배열을 이용해서 구현하는 방법, 2. 연결리스트를 이용하는 구현 방법, 3. 그리고 가장 최근에 배운 완전이진트리를 이용한 힙(heap)을 이용한 구현방법이 존재한다. 오늘은 3번째 방법으로 최대 힙, 최소 힙을 구현해보겠다. ※여기서 최대 힙이란? 부모 노드의 키값 >= 자식 노드의 키값 인 완전이진트리 // 최소힙은 그 반대 힙에서 부모노드와 자식노드의 관계 왼쪽 자식의 인덱스 = 부모의 인덱스 * 2 오른쪽 자식의 인덱스 = (부모의 인덱스 .. 2022. 12. 19. 자료구조 - 순환 순환기법이란? 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하는 기법 ex) 주로 이진탐색이나, 영역채색 ps에 많이 사용 // 팩토리얼 프로그래밍 #include int factorial(int n){ printf("factorial(%d)\n",n); if (n == 1) {return 1;} // 끝나는 부분이 있어야함 else { return n * factorial(n-1); } } // 팩토리얼 프로그래밍 반복구현 int factorialIter(int n){ int result = 1; for(int k = n; n >0; n--){ result = result * k;} return result; } // 거듭제곱 반복문 double power_Itr(dobule x, int n).. 2022. 12. 18. 자료구조 - 트리 트리 : 계층적인 구조를 나타내는 자료구조( 부모- 자식 등의 관계들이 나타남) 노드(node) : 트리의 구성요소 루트(root) : 부모가 없는 노드(가장 위의 노드) 서브트리(subtree) : 하나의 노드와 자손들로 이루어진 작은트리 단말노드(terminal) : 자식이 없는 노드 비단말노드 : 자식을 가지는 노드 간선(edge) : 노드간 연결 링크 레벨(level) : 트리의 각층의 번호 높이(height) : 트리의 최대 레벨 (부모가 레벨1) 차수(degree) : 노드의 자식 노드수 일반트리의 경우 포인터를 이용하면 너무 복잡함 그래서 이진트리(binary tree)를 사용 각 노드에는 최대 2개까지의 자식 노드가 존재 모든 노드의 차수가 2이하 서브 트리간의 순서가 존재한다 이진트리는 .. 2022. 12. 18. 자료구조 - 리스트 앞서 배열도 배우고, 연결리스트도 배워보았다. 이번에는 이를 좀더 심도있게 배워보는 시간을 가지도록 하겠다. 배열리스트 // ArrayList.h #include #define MAX_LIST_SIZE 100; class ArrayList { int data[MAX_LIST_SIZE]; int length; public: ArrayList(void) { length = 0; } void insert(int pos, int e) { if(!isFull() && 0 insertNext(n);} } Node* remove(int post){ Node* prev = getEntry(pos-1); return prev->removeNext(); } Node* find(int val){ for(Node* p=get.. 2022. 12. 18. 이전 1 ··· 10 11 12 13 14 15 다음 728x90