학부_대학원/자료구조 (11) 썸네일형 리스트형 Binary Search Tree - BST 보호되어 있는 글입니다. Graph - BFS 넓이 우선 탐색 큐를 이용해서 구현 http://richong.tistory.com/115에 존재하는 그래프를 넓이 우선탐색 알고리즘을 했을 경우이다. 1. 첫 방문 정점을 큐에 넣음 2. 큐에서 빼면서, 방문하고, 인접 점 방문하지 않았으면 을 큐에 넣는다. 3. 반복한다. #include "stdio.h" #include "stdlib.h" #include "string.h" #define MAX 30 #define FALSE 0 #define TRUE 1 typedef struct Graph_Node { char vertex; struct Graph_Node *link; }Node, *PNODE; typedef struct Qeue{ char vertex; struct Qeue *link; }Qeu.. Sort [정렬] 보호되어 있는 글입니다. Graph - DFS Depth First Search [DFS] 깊이 우선 탐색이다. 1. 시작인 정점을 정한다. 2. 방문한 정점은 visited 했다고 설정 해준다. 방문한 정점은 stack에 push한다. 3. 방문한 정점의 인접한 Vertex를 확인한다. 4.. [인접한 Vertex가 없을 경우] stack에서 pop해서 이전 정점으로 돌아간다. 다른 인접 정점이 있는지 확인한다. 5. [인접한 Vertex가 있을 경우] 2번으로 돌아간다. 이를 구현 할 때는 stack을 사용해서 구현하며 동작은 "처음 시작했던 정점"으로 돌아오게 되면 그만한다. stack이니까 당연한 이야기이다. [그래프] 위와 같은 그래프의 깊이 우선 탐색을 알아보기 위한 소스코드이다. 12345678910111213141516171819202.. 연결리스트 - Graph 연결 리스트를 이용해서 그래프를 표현 배열로 포현하면 복잡도가 O(n^2)이 되는데, 연결 리스트로 표현하면 O(n)이 되서 효율적 [그래프] 위의 [그래프]를 각 Vertex 마다 Adjacent한 Vertex를 연결리스트로 표현한 그림은 밑에 그림이다. 간단하게 각 Vertex마다 Head Node를 만들고 연결 리스트로 Adjacent 한 Node를 연결하면 된다. [Adjacent Vertex를 연결 리스트로 표현] 설계없이 그냥 막 짜서 더럽다. #include "stdio.h" #include "stdlib.h" #include "string.h" #define MAX 30 //A-B-C 인접 연결 Node typedef struct Graph_Node { //현재 Vertex char Ver.. 자료구조 - 원형 연결 리스트 페에지 교체 정책을 공부하다보면 사용가능한 알고리즘이 나오는데 원형 연결 리스트를 이용해서 구현 할 수 있을 것같다. Circular Linked List 단순 연결 리스트에서 마지막 노드가 리스트의 첫 번째 노드를 가리키게 하여 리스트의 구조를 원형으로 만든 연결 리스트 --> 단순 연결 리스트의 마지막 노드의 링크 필드에 첫 번째 노드의 주소를 저장하여 구성 --> 링크를 따라 계속 순회하면 이전 노드에 접근 가능 #include "stdio.h" #include "stdlib.h" typedef struct Data_Node { int data; struct Data_Node* link; }Node; // 연결 리스트의 시작점을 저장 Node* Head = NULL; void Insert_Node(.. 연결 자료구조[단순 연결 리스트] 등장 배경? 순차 자료구조의 문제점의 해결 1. 삽입, 삭제 연산시 순서에 맞는 물리 주소를 유지하기 위한 이동에 대한 OverHead가 발생 2. 배열을 이용한 구현시, 메모리 사용의 비효율 --> 사용하지 않는 공간도 순서를 위해서 할당 시켜야함. --> 이러한 문제점을 해결하기 위해서 연결 자료구조가 등장 연결 자료구조 자료의 논리적인 순서와 물리적인 순서가 일치하지 않는 자료구조 각 원소에 저장되어 있는 다음 원소의 주소에 의해 순서가 연결되는 방식 --> 물리적이 주소를 맞추기 위한 OverHead가 발생하지 않음. 여러 개의 작은 공간을 연결하여 하나의 전체 자료구조 표현 --> 종합하면 필요 하지 않은 것은 할당하지 않아도 되고, 꼭 연속적일 필요도 없고 조각 조각난 메모리로도 자료구조를 표.. 다익스트라 알고리즘[Dijkstra Algorithm] Shortest Path Problem 문제를 해결하기 위한 알고리즘 각 edge에 가중치를 두는 weighted Graph에서 사용 Connected Graph에서 사용 가중치가 음수가 없어야함. 어떤 vertex를 시작점으로 하여 다음 vertex를 연결하는 edge의 가중치를 계산하여서 가장 작은 가중치를 가지는 경로를 탐색 가중치란 평균치(平均値:평균값)를 산출할 때 각 개별치(個別値)에 부여되는 중요도. 그런데 상황마다 다를것이다. 예를 들어 가난한 사람과 부자인 사람을 생각해보자 부자인 사람은 시간이 더 가치있다고 생각 하기때문에 edge를 통과하는데 걸리는 시간이 작은것에 더 높은 가중치를 둘것이다. 하지만 가난한 대학생의 경우 시간은 많지만 돈이 없기때문에 edge를 통과하는데 소비되는 돈.. 이전 1 2 다음
