그래프
그래프의 이해와 종류 쾨니히스베르크의 다리 문제 모든 다리를 한번씩만 건너서 처음 출발한 장소로 돌아올 수 있는가? 정점 별로 연결된 간선의 수가 모두 짝수여야, 간선을 한번씩만 지나서 처음 출발했던 정점으로 돌아올 수 있다. 무방향 그래프 : 방향성 x 방향 그래프 : 방향성 o 완전 그래프 : 각각의 정점에서 다른 모든 정점을 연결한 그래프 가중치 그래프 : 간선에 가중치 정보를 두어서 그래프를 구성(이동시간) 부분 그래프 : 원 그래프의 일부 정점 및 간선으로 이뤄진 그래프를 뜻한다. 그래프의 집합 표현 그래프 G의 정점 집합 : V(G)={A,B,C,D} 그래프 G의 간선 집합 무방향 E(G)={(A,B),(A,C),(A,D)} 방향 E(g)={,,} 그래프를 구현하는 두 가지 방법 인접 행렬 기..
빠른 탐색을 보이는 해쉬 테이블 AVL 트리는 탐색과 관련하여 매우 만족스러운 성능을 보였다. 하지만 탐색 키의 비교 과정을 거치면서 찾는 대상에 가까워지는 방식이기 때문에, 원하는 바를 단번에 찾아내는 방식이라고 말하기는 어렵다. 이럴 때 도입을 검토할 수 있는 자료구조가 바로 테이블이다. AVL 트리의 탐색 연산 : O(log2 n)의 시간복잡도 테이블의 시간 복잡도 : O(1) 해쉬 함수 : 넓은 범위의 키를 좁은 범위의 키로 변경하는 역할 충돌 : 서론 다른 두 개의 키가 해쉬 함수를 통과하였는데 그 결과가 같은 경우 좋은 해쉬 함수의 조건 : 데이터가 전체 영역에 고루 분포되어 있는 경우 ex) Person.h #ifndef __PERSON_H__ #define __PERSON_H__ #defi..
이진 탐색 트리의 문제점 : 이진 탐색 트리의 연산은 O(log2 n)의 시간 복잡도를 가진다. 그런데 균형이 맞지 않을수록 O(n)에 가까운 시간 복잡도를 보인다. 이러한 이진 탐색 트리의 단점을 해결한 트리를 가리켜 균형 잡힌 이진 트리라 하며, 그 종류 중 AVL 트리를 선택한다. 균형인수 = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이 LL회전 : LL상태 : 균형 인수 +2가 연출된 상태. RR회전 : RR상태 : 균형 인수 -2가 연출된 상태. LR회전 : LR상태 : 자식 노드가 왼쪽으로 하나, 그리고 이어서 오른쪽으로 하나 달린 상태. RR회전을 통해 LL상태로 RL회전 : RL상태 : 자식 노드가 오른족으로 하나, 그리고 이어서 왼족으로 하나 달린 상태. LL회전을 통해 RR상태로
탐색은 알고리즘보다 자료구조에 더 가까운 주제이다. 왜냐하면 효율적인 탐색을 위해서는 어떻게 찾을까만 고민해서는 안 되고 효율적인 탐색을 위한 저장방법이 무엇일까를 고민해야되기 때문이다. 보간탐색 이론적으로 보간 탐색과 이진 탐색의 유일한 차이점은 탐색의 대상을 선정하는 방법이다. InterpolSearch.c #include int ISearch(int ar[], int first, int last, int target) { int mid; //if(first > last) //return -1; // -1의 반환은 탐색의 실패를 의미 if(ar[first]>target || ar[last]
우선순위 큐 : 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다. 우선순위 큐의 구현 방법 1. 배열 기반 2. 연결 리스트 기반 3. 힙(heap) 이용 힙이라는 자료구조를 이용해서 구현하는 것이 일반적 힙 : 완전 이진 트리이다. 그리고 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다. 즉, 루트 노드에 저장된 값이 가장 커야 한다.(값은 말 그대로 값이 될수도 있고 우선순위가 될 수도 있다.) heap : 무엇인가를 차곡차곡 쌓아올린 더미 최대 힙(max healp) : 루트 노드로 올라갈수록 저장된 값이 커지는 완전 이진 트리 최소 힙(min heap) : 루트 노드로 올라갈수록 저장된 값이 작아지는 완전 이진 트리 힙은 우선순위 큐의 구현에 어울리는, 완전 이..
트리(Tree)
트리는 계층적 관계를 표현하는 자료구조이다. 노드(node) : 트리의 구성요소에 해당하는 요소(A, B, C, D) 간선(edge) : 노드와 노드를 연결하는 연결선 루트 노드(root node) : 트리 구조에서 최상위에 존재하는 A와 같은 노드 단말 노드(terminal node) : 아래로 또 다른 노드가 연결되어 있지 않은 노드(E, F) 내부 노드(internal node) : 단말 노드를 제외한 모든 노드 서브 트리 : 큰 트리에 속하는 작은 트리 이진 트리(Binary Tree) 1. 루트 노드를 중심으로 두 개의 서브트리로 나뉘어야 한다. 2. 나뉘어진 두 서브 트리도 모두 이진 트리이어야 한다. (노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면, 공집합 노드가 존재하는 것으로 간주..
큐 : 선입선출 배열에서 할 때 dequeue를 하면 f를 뒤로 이동시킨다. => 배열 크기 10인데 앞에꺼가 비어있으면 넣을 수가 없어 => 원형 큐 => F, R의 위치만으로는 꽉 찬 경우와 빈 경우를 구분X => 배열의 길이가 N이라면 데이터가 N-1개 채워졌을 때, 이를 꽉 찬 것으로 간주 ex) 원형 큐 CircularQueue.h #ifndef __C_QUEUE_H__ #define __C_QUEUE_H__ #define TRUE1 #define FALSE0 #define QUE_LEN100 typedef int Data; typedef struct _cQueue { int front; int rear; Data queArr[QUE_LEN]; } CQueue; typedef CQueue Que..