외부 정렬 정렬하려는 리스트 전체가 컴퓨터의 메인 메모리에 모두 올라갈 수 없다면 내부 정렬 사용 불가 블록 - 한 번에 디스크로부터 읽거나 디스크에 쓸 수 있는 데이터 단위, 여러 개의 레코드들로 구성 판독/기록 시간에 영향을 미치는 요소 탐구 시간: 판독/기록 헤드가 디스크 상의 원하는 실린더로 이동하는데 걸리는 시간, 헤드가 가로질러야 하는 실린더 수에 따라 결정됨 회전지연 시간: 트랙의 해당 섹터가 판독/기록 헤드 밑으로 회전해 올 때까지 걸리는 시간 전송 시간: 디스크로 오는 디스크로부터 데이터 블록을 전송하는 데 걸리는 시간 합병 정렬 입력 리스트의 여러 세그먼트들을 좋은 내부 정렬 방법으로 정렬 런(run) - 정렬된 세그먼트들 런이 생성되면 외부 저장 장치에 기록됨 1에서 만들어진 런들은 ..

정렬 리스트를 오름차순, 내림차순 혹은 어떤 조건에 대해 순서대로 배열한 것 정렬에 필요성 빠른 탐색을 위해 사용 리스트의 엔트리를 비교하는 방법으로 사용 정렬 방법 내부 방법 - 정렬할 리스트가 작아서 전체적인 정렬이 메인 메모리 상에서 실행될 수 있을 때 사용 외부 방법 - 큰 리스트에 사용 삽입 정렬 template void Insert(const T &e, T *a, int i) { // e를 정렬된 리스트 a[1:i]에 삽입 // 리스트 a[1:i+1]도 정렬되게 함 // 배열 a는 적어도 i+2 원소를 포함할 공간 필요 a[0] = e; while (e < a[i]) { // 리스트의 맨 뒤부터 e가 삽입될 위치인지 탐색하며, a[i + 1] = a[i]; // 배열 a의 원소를 한칸씩 위로 ..

탐색 리스트: 하나 이상의 필드로 된 레코드의 집합 키(key): 레코드를 구분하기 위해서 사용되는 필드 순차 탐색 template int SeqSearch(E *a, const int n, const K &k) { // a[1:n]을 왼쪽에서 오른쪽으로 탐색 // a[i]의 키 값이 k와 같은 가장 작은 i를 반환, 없으면 0 반환 int i; for (i = 1; i n) return 0; // i값을 찾지 못한 경우 return i; // i값을 찾은 경우 } 시간복잡도 - O(n) 순차 탐색의 성능 향상(정렬된 리스트의 경우) SepSearch의 for 조건 부분을 i n을 i > n || a[i] != k로 변경 탐색이 실패할 때 성능 향상 이원 탐색(Binary Search) int Binar..

신장 트리(spanning tree) G의 간선들로만 구성되고 G의 모든 정점들이 포함된 트리 신장트리는 G의 최소 부분 그래프(간선의 수가 가장 적은 부분 그래프) G'로서 V(G') = V(G)이고 G'는 연결되어 있음 신장트리는 n-1개의 간선 가짐 최소 비용 신장 트리 최저의 비용을 갖는 신장트리 Kruskal, Prim, Sollin 알고리즘 사용 신장 트리의 제한 조건 그래프 내에 있는 간선들만을 사용 정확하게 n-1개의 간선만을 사용 사이클을 생성하는 간선을 사용 금지 Kruskal 알고리즘 한 번에 하니씩 T에 간선을 추가해 가면서 최소비용 신장트리 T를 구축 T에 포함될 간선을 비용의 크기 순으로 선택 이미 T에 포함된 간선들과 함께 사이클을 형성하지 않는 간선만을 T에 추가 G는 연결되..

그래프 정의 그래프 G: 2개의 집합 V, E로 구성 V: 공집합이 아닌 정점(vertex)의 유한집합 E: 간선(edges)이라고 하는 정점 쌍들의 집합 표기: G = (V, E) 그래프의 제약 사항 자기 간선 또는 자기 루프 없음 동일 간선의 중복 없음 무방향 그래프 간선을 나타내는 정점의 쌍에 순서 없음 (u, v) = (v, u) 방향 그래프 방향을 가지는 정점의 쌍 로 표시 ≠ 완전 그래프 n개의 정점과 n(n-1)/2개의 간선을 가진 그래프 그래프 G의 부분그래프(subgraph) v(G') ⊆ V(G) 이고 E(G') ⊆ E(G)인 그래프 G' (u, v)가 E(G)의 한 간선이라면 u와 v는 인접 간선 (u, v)는 정점 u와 v에 부속 정점 u로부터 정점 v까지의 경로 그래프 G에서 \(..

우선순위 큐 우선순위가 가장 높은(낮은) 원소르 먼저 삭제 임의의 우선순위를 가진 원소 삽입 가능 최대 우선순위 큐 template class MaxPQ { public: virtual ~MaxPQ() {} // 가상 소멸자 virtual bool IsEmpty() const = 0; // 우선순위 큐가 공백이면 true를 반환 virtual const T &Top() const = 0; // 최대 원소에 대한 참조를 반환 virtual void Push(const T &) = 0; // 우선순위 큐에 원소를 삽입 virtual void Pop() = 0; // 최대 우선순위를 가진 원소를 삭제 }; 표현 방법 - 최대 히프 최대 히프 최대(최소) 트리: 각 노드의 키 값이 그 자식의 키 값보다 작지(크..

트리 하나 이상의 노드로 이루어진 유한 집합 - 하나의 루트 노드 - 나머지 노드들은 n(≥0) 개의 분리 집합 \(T_{1}, T_{2},..., T_{n}\)으로 분할 - \(T_{i}\): 루트의 서브트리 노드 한 정보 아이템 + 다른 노드로 뻗어진 가지 노드의 차수(degree) 노드의 서브트리 수 단말(리프) 노드 차수 = 0 비단말 노드 차수 ≠ 0 자식 노드 X의 서브트리의 루트 형제 부모가 같은 자식들 트리의 차수 노드의 차수의 최댓값 조상 루트까지의 경로상에 있는 모든 노드 레벨 루트 == 레벨1, 자식 레벨 == 부모 레벨 + 1 높이(깊이) 노드 레벨의 최댓값 트리의 리스트 표현 (A(B(E(K,L),F),C(G),D(H(M),I,J))) - 차수가 k인 트리에 대한 노드 구조 트리 ..

연결 스택과 큐 연결 스택 top에서 노드 삽입, 삭제 용이 top: 스택의 톱 노드를 가리키는 전용 데이터 멤버 초기엔 top = 0 template void LinkedStack::Push(const T &e) { top = new ChainNode(e, top); } template void LinkedStack::Pop() { // 스택의 첫 번째 노드를 삭제 if (IsEmpty()) throw "Stack is empty. Cannot delete."; ChainNode *delNode = top; top = top->link; // top노드를 삭제 delete delNode; // 메모리 할당 해제 } 연결 큐 rear에서 노드 삽입 용이 front에서 노드 삽입, 삭제 용이 rear: 큐..

원형리스트 원형 리스트(circular list) - 체인에서 마지막 노드의 link 필드가 첫 번째 노드를 가리킴 - 포인터 current가 마지막 노드를 가리키는지 검사할 때, current->link == 0이 아니라 current->link == first로 검사 - 삽입, 삭제 함수에서 마지막 노드의 link 필드가 첫 번째 노드를 가리키는지 연산이 끝난 후 확인 원형 리스트 예시 ↙ ← ← ← ← ← ← ← ← ↖ first → [data | link] → [data | link] → [data | link] 리스트 앞에 새 노드 삽입 - 마지막 노드의 link를 변경해야 하므로 접근 포인터가 마지막 노드를 가리키는 편이 편리 template void CircularList::InsertFro..

반복자(iterator) 반복자의 필요성 컨테이너 클래스의 종류에 따라 최대값을 찾는 구현 코드가 다름 - ex) 배열과 체인에 대해 최대값을 찾는 코드가 다르다 내부 구조의 이해 없이 컨테이너에 저장된 객체를 이용할 수 있는 반복자 필요 C++ 반복자 - 객체의 원소에 대한 포인터 - 객체의 원소를 하나씩 지나가도록 지원 C++ STL 반복자의 부류 입력 출력 전방 양방 임의접근 반복자 지원 연산 참조 연산자 * 동등 연산자 ==, != 반복자 전진 ++, 감소 -- 포인터 산술 연산, 임의의 양 점프 +=, -= Chain에 대한 전방 반복자 Chain을 위한 전방 반복자 클래스 class ChainIterator { private: ChainNode *current; public: // C++ 데..