LittleDeveloper

방향그래프? 1. 방향 비사이클 그래프(DAG) 2. 방향 사이클 => 위상순서 x 위상정렬? 위상 정렬(topological sort): DAG로부터 위상순서를 얻는 절차 방향그래프의 위상순서(topological order) : 모든 i 더이상 나가는 간선이 없는 정점부터 번호 매김 2. 각 정점의 진입차수 이용 =>들어오는 간선이 없는 정점부터 번호 매김 -아래의 위상 정렬 알고리즘은, 두 번째 알고리즘이며, 1)인접정점리스트에서 새로 입력되는 간선에 대한 노드가 리스트의 '맨 앞에' 삽입됨 (*단순연결리스트 addFirst() ) 2)최초로 진입간선의 개수가 0인 정점을 찾을 때, '정점 번호 순..

필요 //큐 템플릿 #define SIZE 10 typedef struct{ char elem[SIZE]; int front, rear; }QueueType; void initQueue(QueueType* Q){ Q->front = Q->rear = 0; } int isEmpty(QueueType* Q){ return Q->rear == Q->front; } int isFull(QueueType* Q){ return (Q->rear + 1) % SIZE == Q->front; } void enqueue(QueueType* Q, char vName){ if (isFull(Q)){ printf("FULL\n"); return; } Q->rear = (Q->rear + 1) % SIZE; Q->elem[Q->..

그래프 순회란? 순회: '모든 정점과 간선'을 그래프를 탐험하는 체계적인 절차 ex)웹 검색엔진의 데이터 수집 부문: 웹의 하이퍼텍스트 문서(정점), 문서 내 링크(간선)를 검사하여 탐색 1. DFS(깊이우선탐색) -이진트리에 대한 선위순회와 유사함. Alg DFS(G) input graph G output labeling of the edges of G as 트리 간선 & 후향 간선 {The algorithm uses a mechanism for setting and getting ''labels'' of vertices and edges} 1. 정점 u의 라벨 = Fresh 2. 간선 e의 라벨 = Fresh 3. if (출발 정점 v의 라벨 = Fresh) --> rDFS(G, v) Alg rDFS..

1. 간선 구조체 만들기 typedef struct Edge { int weight; char v1, v2; struct Edge* next; }Edge; 2. 인접정점 구조체 만들기 typedef struct IncidentEdge { char adjVertex; Edge* e; struct IncidentEdge* next; }IncidentEdge; //정점이 관리, 인접리스트는 간선 만들고 생성 3. 정점 구조체 만들기 typedef struct Vertex { char vName; IncidentEdge* iHead; struct Vertex* next; }Vertex; 4. 그래프 구조체 만들기 typedef struct { Vertex* vHead; Edge* eHead; }Graph; 5...

2. 개방주소법으로 정리하기 [HOW? by pseudo code] Alg findElement(k) input bucket array A[0,..,M-1], hash function h, key k output element with key k 1. v

[ 다람쥐의 창고 정리를 도와주세요!! ] 귀여운 다람쥐 친구가 겨울맞이 식량 창고를 정리하고 있어요. 창고 A에 서랍은 13개가 있고, 무작위로 넣지 않고 해시 함수 값에 따라 먹이를 저장할거래요. (먹이들은 원래 며칠에 획득했는지 날짜로 라벨링되어 있었대요. 예를 들어 13일에 주운 사과, 28일에 선물받은 도토리 등...) 다람쥐는 먹이들에 00, 01, 02, ,....,..,12 이런 식으로 번호 라벨을 붙여놓고, 해시 함수 값에 따라 각각 0번째 서랍, 1번째 서랍, 2번째 서랍,..., 12번째 서랍에 각각 넣기로 했어요! 그런데 문제가 있어요. 어느 날 15일에 얻은 먹이(해시 함수 값=2)를 2번째 서랍에 넣으려고 하니까, 이미 서랍에 다른 먹이가 있는거예요.. 어떻게 하면 좋을까요? 먹..

와! 벌써 그래프까지 왔네요. 여기까지 온 당신 정말 대단해! 이번 시간에는 그래프의 개념과 종류를 알아봅시다. 1. 그래프 ADT -그래프(graph): (V, E) 쌍 --> V: 정점(vertex)이라 불리는 노드의 집합 --> E: 간선(edge)이라 불리는 정점쌍들의 집합 *정점과 간선은 원소(정보)를 저장해요. ex) 그림 첨부 2. 간선에 따른 그래프 유형 -방향간선(directed edge): 정점들의 순서쌍(u, v) (u는 시점, v는 종점) -방향그래프(directed graph): 모든 간선이 방향 간선인 그래프 -무방향간선: 정점들의 무순쌍 (u, v) -무방향그래프: 무방향간선으로 이루어진 그래프 -간선의 끝점(end vertex) -정점의 부착(incident) 간선 -정점의 ..

해시테이블(hash table): 키-주소 매핑에 의해 구현된 사전 ADT 해시테이블 = 버켓 배열 + 해시함수 -항목들의 키를 주소(인덱스 i)로 매핑함으로서 1차원 배열에 사전 항목들을 저장 성능: 탐색, 삽입, 삭제- O(n) 최악시간, 그러나 O(1) 기대시간 버켓 배열: 해시테이블을 위한 버켓 배열은 크기 M의 배열 A로서, A의 각 셀은 버켓(키-원소 쌍) = 슬롯 -정수 M: 배열의 용량 -키 k를 가진 원소 e는 버켓 A[k]에 삽입 -사전에 존재하지 않는 키에 속하는 버켓 셀들- NoSuchKey 라는 특별한 개체를 담는 것 - 버켓 배열 분석 -키가 유일한 정수며 [0, M-1] 범위에 잘 분포되어 있다면, 해시테이블에서의 탐색, 삽입, 삭제에 O(1) 최악의 시간 소요 -2가지 중요한..

1. 우선순위 큐란? *자료구조까지 학습한 분이라면 '큐(Queue)'의 개념은 아실 거예요. 큐는 '선입선출', 즉 먼저 들어간 데이터가 먼저 나가는 자료구조를 말하죠. 그런데 왜 '우선순위'라는 말이 붙는건지?? '우선순위 큐'는 우선순위가 높은 데이터부터 나가는 구조입니다! 그러니까 들어온 순서랑은 무관하다는 이야기죠. *우선순위 큐 ADT -우선순위 큐 ADT는 각 데이터를 (키, 원소)로 저장한답니다. 이 ADT 메소드에는 무엇이 있는지 한번 살펴볼까요? 주요 메소드 insertItem(k,e): 키 k인 원소 e를 큐에 삽입 element removeMin() : 큐에서 최소 키를 가진 원소를 삭제하여 반환 일반 메소드 integer size(): 큐의 데이터 수 반환 boolean isEmp..

1. 이중연결리스트를 이용한 영문자 리스트 ADT -add(L, r, e): list의 순위 r에 원소 e 추가 -delete(L, r): list의 순위 r에 위치한 원소 삭제 -get(L, r): list의 순위 r에 있는 원소 반환 -print(L): list의 모든 원소를 출력 *순위 정보가 유효하지 않으면 "invalid position" 출력, 해당 연산 무시 ->연산 이름은 각각 A, D, G, P 로 주어짐. STEP1 [자료구조 선언] - 일단 "구조체"가 필요해요! 이 구조체를 왜 만드냐구요? '노드 하나가 담을 원소(영문자)', '이전 노드를 가리키는 링크', '다음 노드를 가리키는 링크' 이 3가지 정보를 포함할 노드의 구조로 구조체가 가장 적절해보이네요~ 혹시 typedef 가 뭐..