Aif

다익스트라 알고리즘 최단 경로를 구하는 알고리즘 임의의 시작 정점에서 각각의 정점으로의 최단 경로를 구해낸다. 프림 알고리즘과 유사하다. 프림 알고리즘과 같이 그리디 알고리즘 기반이다. 전체적인 흐름은 시작 정점을 지정하고 해당 정점으로 가는 간선을 우선순위 큐에 넣는다. 이 간선은 시작을 나타내는 간선으로 가중치는 0이고 출발지는 -1로 한다. 우선순위 큐가 빌때까지 반복 { 우큐에서 하나 뺌 우큐에서 하나 삭제 해당 간선이 방문했을 경우 다음 반복 해당 간선 방문으로 표시 그래프를 모두 확인하여 시작 정점에 붙은 간선을 확인하여 거리가 현재 가중치보다 높게 저장된 간선을 현재 가중치로 계산하여 저장 후 우큐에 삽입 } 말로 보면 좀 힘들고 코드로 보는게 편할듯 하다.. int calDistance(i..

최소신장트리를 만드는 알고리즘으로 크루스칼 알고리즘이 있다. 개념자체는 단순하다. 그래프의 모든 간선을 가중치의 순서대로 이어 붙인다. 그렇다면 중복되는 간선은 어떻게 걸러내야 할지 고민하게 된다. 이 방법은 집합 개념을 도입하여 해결한다. 만약 최소 가중치의 간선을 최소신장트리에 포함하려 할 경우를 생각해 본다. 처음에는 아무도 집합을 이루지 않기에 바로 최소신장트리에 포함된다. 하지만 계속 반복되면 같은 집합 내에서 간선이 선택될 경우가 발생한다. 이는 순환을 발생시키므로 위와 같은 상황을 제외하면 최소신장트리가 완성된다. vector set; int findParent(vector set, int child) { int parent = set[child]; while (parent != child)..

프림알고리즘을 구현하려고 꽤 많은 시간을 사용했다. 그래프 구조라는 것에 대해 고민이 많았졌는데 에초에 구조라는게 그냥 데이터를 관리하기 위해 정해놓은 룰이기도하고 뭔가 자료구조에대해 굉장히 모호해지고 어려워졌다.... 어쨋든 프림 알고리즘은 그래프의 한 정점을 시작점으로 하여 가장 적은 가중치의 간선을 통해 탐색해 나가서 결국엔 최소의 가중치로 모든 정점을 그래프구조로 만들게된다. 이름은 최소신장트리 이지만 최소신장그래프도 가능한것이다. 그러면 크게 최소신장그래프를 저장하기위한 그래프를 선언하고 현재 가장 적은 가중치의 간선을 판단하기 위해 우선순위 큐를 사용한다. 그리고 전체적인 흐름은 다음과 같다. 우선순위 큐가 빌때까지 반복 { 우선순위 큐에서 간선 하나를 빼고 이미 방문한 정점이면 컨티뉴 간선의..

최소 신장 트리 란 간선에 가중치가 추가된 그래프 자료구조에서 한 정점에서 다른 정점으로 이동 경로가 가장 적은 가중치를 갖는 트리 대표적으로 프림 알고리즘, 크루스칼 알고리즘 두 개가 있다. 프림 알고리즘 - 간선이 많은 복잡한 그래프에 적합 임의의 정점을 최소신장트리에 삽입한다. -> 최소신장트리의 루트노드로 만듬 최소신장트리의 노드들을 체크하여 간선의 가중치가 최소값인 노드를 찾는다. 체크할 간선이 가르키는 노드는 최소신장트리에 있으면 안됨 찾은 노드를 최소신장트리에 추가한다. 우선순위 큐를 이용하여 탐색해야할 간선들을 관리하여 최소신장트리를 만들어갈 수 있다. 크루스칼 알고리즘 - 간선의 개수가 적은 경우 적합한 알고리즘 간선들의 가중치를 정렬한 뒤 최소신장 트리가 완성 될때 까지 간선을 작은 순..

연결 리스트와 같이 마지막 노드로 이동하여 추가하는 과정을 거치면 된다. void Graph::Vappend(int data) { VORTEX* newVortex = new VORTEX; newVortex->Data = data; newVortex->Ehead = nullptr; newVortex->next = nullptr; if (!graph->Vhead) graph->Vhead = newVortex; else { VORTEX* temp = nullptr; temp = graph->Vhead; while (temp->next) { temp = temp->next; } temp->next = newVortex; } } void Graph::Eappend(VORTEX* from, VORTEX* to) {..

그래프 오일러가 쾨니히스베르크 문제를 풀기위해 고안해냄 그래프는 정점의 모음과 이 정점을 잇는 간선의 모음의 결합이다. 정점들의 모임 + 간선들의 모임 = 그래프 구현 방법 정점들의 집합은 배열과 리스트 어느것으로 구현해도 된다. 하지만 간선들의 집합은 인접관계를 나타내야 하므로 배열로 나타내게 되면 2차원 배열 (행렬) 로 나타내야 한다. 또한 행렬로 나타내게 되면 2차원 배열 하나에 정점 두 개의 정보가 포함되므로 정점 하나가 늘어나면 배열은 제곱으로 늘어난다. 정점의 저장할 데이터의 크기도 같은 원리로 행렬에서는 제곱으로 크기가 커지게된다. 알고리즘에서 제곱은 최악의 상황으로 여겨지는듯 하다. 리스트도 단점은 있다. 리스트의 단점은 역시 집합을 탐색하는데 오래걸린다는 것이다. 하지만 n^2회랑 n회..

삭제 과정 1. 루트 노드를 삭제하고 트리의 최고 깊이 제일 오른쪽 노드를 루트노드로 옮김 2. 루트 노드보다 작은 값을 가진 자식 노드와 교환한다. 둘 다 작을 시 둘 중 작은 노드 3. 자식 노드가 더 클 때 까지 2번 반복 void Heap::mindelete() { int prevCapacity = H->Capacity - 2^(int)log2(H->Capacity); if (prevCapacity == H->UsedSize) { H->Capacity = prevCapacity; H->Tree = (NODE*)realloc(H->Tree, sizeof(NODE) * H->Capacity); } H->Tree[0].Data = H->Tree[H->UsedSize-1].Data; H->Tree[H->..

삽입 과정 1. 힙의 가장 아래 오른쪽에 노드를 추가한다. 2. 부모 노드와 비교하여 작으면 자리를 바꾼다. 3. 부모 노드가 더 작은 값이면 종료 아니면 2번을 다시 수행한다. void Heap::append(int data) { if (H->Capacity == H->UsedSize) { H->Capacity += H->Capacity * 2; H->Tree = (NODE*)realloc(H->Tree, sizeof(NODE) * H->Capacity); } NODE* newNode = new NODE; newNode->Data = data; int newdata = H->UsedSize; int temp = 0; H->Tree[H->UsedSize].Data = newNode->Data; while..

힙 이란 부모노드가 자식노드보다 작은 완전 이진 트리이다. 힙은 새로운 규칙을 따르는 완전 이진 트리인 것이다. 이진 트리는 탐색을 수행할 경우 분할 탐색이 가능한데, 힙에서는 불가능하다. 그러면 성능이 안좋아 보이는데 기존의 이진 트리에서 탐색 성능을 버리면서 얻은 것이 있다. 힙의 루트 노드는 최솟값이라는 점이다. 힙은 추가와 최솟값 삭제 기능을 수행한다. 힙을 보고 느낀점은 뭔가 이때까지 배운 자료구조들을 필요한 상황에 맞게 알고리즘을 적용해서 입맛대로 바꾸는 느낌인 것같다. 앞으로도 그런 느낌으로 진행될듯 하다.. 힙의 구현 힙은 배열형식으로 구현하면 편리하다. 기본적으로 완전 이진 트리 형식이기 때문에 부모노드와 자식노드의 위치를 배열로 나타낼 때, 일정한 규칙을 가진다. k번 인덱스에 위치한 ..

해쉬란 사전적으로는 뭉개져서 형체를 알 수 없다라는 뜻이었나. 검색해보면 잘게 썬 고기요리라고 나옴 자료구조에서 해쉬는 데이터를 전혀 유추할 수 없는 데이터로 바꾸는 과정이다. 이 때 데이터는 절대로 원래의 데이터를 알 수 없다. 이 과정은 잘게 다져지는 것과 비슷하다. 현실적으로 hash와 비슷한데 비슷하지 않은 부분도 있다. 데이터를 해쉬하면 길이가 일정하게 변한다. 데이터의 길이가 1비트건 16비트건 일정하게 변하게 된다. 요약하면 데이터를 해쉬하면 복원할 수 없는 데이터, 일정한 길이의 비트의 데이터로 변조시킨다. 이러면 어디에 쓰나 싶지만 원래의 데이터를 같은 방법(알고리즘)으로 해쉬하면 똑같이 변조된다. 쓰고보니 당연한 얘기이긴하다. 어쨋든 이 부분은 보안에 유리하다는 장점이 떠오른다. 현재 ..