목록전체 글 (134)

observe_db

[자료구조] 정렬(Sorting)

용어레코드(record): 여러 개의 field로 객체(object, 정보) 표현리스트(list): 레코드의 집합(set)키(key): 레코드를 구분하기 위한 필드순차 탐색(Sequential Search or Linear Search): 레코드 리스트를 순차적으로 검사하는 것안정성(Stability): 정렬의 각 pass를 수행할 때 key값에 대해 상대적으로 순서를 그대로 유지한다면 알고리즘은 stable하다고 함.- 여러 개의 키를 우선순위를 정해서 정렬하는 경우 알고리즘 선택에 중요한 관건이 됨.(다른 말로 단일 키엔 그닥 의미 없음) 순차 탐색seqSearch(element a[], int k, int n){/* a[1:n]탐색; a[i].key = k를 만족하는 최소의 i를 반환. 없으면 0을..
학교 공부/자구(2-1) 2025. 1. 19. 19:33
[자료구조] 그래프(Graph)

그래프의 추상 타입(The Graph Abstract Data Type)시초는 오일러의 쾨인스버그 다리 문제래프의 추상 타입(The Graph Abstract Data Type) 시초는 오일러의 쾨인스버그 다리 문제임의의 지역에서 출발하여 모든 다리를 단 한번씩만 지나 처음 출발한 지역으로 되돌아 올 수 있는가?- 각 정점(vertex)의 차수가 짝수이면 가능.차수(degree): 정점에 연결된 간선 수오일러 행로(Eulerian walk) 정의(definition)그래프 G: 2개의 집합 V와 E로 구성- V: 공집합이 아닌 정점(vertex)의 유한집합- E: 간선(Edges), E ⊆{{x, y} | (x, y) ∈ V^2 ∧ x!=y}- 표기: G=(V,E) 무방향 그래프(undirected gr..
학교 공부/자구(2-1) 2025. 1. 14. 08:16
[자료구조] 힙(Heaps)

if P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C. 우선순위 큐(Priority Queue)- 우선 순위가 가장 높은/낮은 원소를 먼저 삭제- 임의의 우선순위를 가진 원소 삽입 가능- 추상 데이터 타입 MaxPriorityQueue 무순서(unordered): 선형 리스트로 구현(가장 간단)- IsEmpty() : O(1) // linked list가 null인지 검사- push(): O(1) //임의의 위치에 노드 삽입- top(): Θ(n) //list 전체 검사..
학교 공부/자구(2-1) 2025. 1. 6. 17:26
[자료구조] 트리(Trees)

트리: 정보의 항목들이 가지(branch)로 연결되는 데이터 구조: 하나 이상의 노드로 이루어진 유한 집합.루트(root) 노드 1개나머지는 n개의 분리 집합 T1,T2,...Tn으로 분할.(Ti는 서브트리) - 노드: 데이터(정보) 아이템+ 다른 노드로 뻗은 가지(branch)- 차수(degree): 노드의 서브트리 수(= link 수 = branch 수)- 단말(leaf) 노드: 차수 = 0 => 자식(child) 비존재- 비단말 노드: 차수 !=0  => 자식(child) 존재- 자식: 노드 X의 서브트리의 루트(부모)- 형제(sibling): 부모가 같은 자식들- 트리의 차수 = max{노드의 차수}- 조상: 루트까지의 경로상에 있는 모든 노드- 노드 레벨: 루트=레벨1, 자식레벨 = 부모레벨+1..
학교 공부/자구(2-1) 2025. 1. 3. 16:26
이전 Prev 1 2 3 4 5 ··· 34 Next 다음