UpWrite

인접행렬을 이용한 그래프 구현(1) 방향성 가중치 단순 그래프 # 인접행렬을 이용해서 표현할 수 있는 단순한 형태의 그래프. # 배열 안의 값은 간선의 가중치를 나타낸다. # 가중치가 없는 다중 그래프라면 배열의 값이 간선의 갯수가 된다. 다만 이러면 간선을 하나씩 추가할 수 있도록 코드가 수정될 필요가 있다. # 아직 그래프 순회나 검색 등의 내용을 넣진 않았다 MatrixGraph.h #pragma once #include struct edge { bool exist; int weight; }; class MatrixGraph { int vertexCount; int** matrix; public: bool AddEdge(int StartVertex, int EndVertex, int weight);..

인접행렬을 이용한 그래프의 구현 소개 # 그래프를 정점 수 만큼의 행과 열을 갖는 정방행렬로 표현하는 방법이다. # 그래프 G = (V,E)가 n개의 정점으로 구성되었다고 가정하면, 인접행렬A는 n*n의 2차원 배열로 표현한다. 즉, A = (i,j) # 단순 그래프의 2차원 배열 A(i,j)의 원소는 간선(Vi,Vj)이 간선의 집합 E(G)에 속하면 A(i,j) = 1로 표시하고, 그렇지 않으면 A(i,j) = 0으로 표현한다. # 다중 그래프의 2차원 배열 A(i,j)의 원소는 간선(Vi,Vj)이 간선의 집합 E(G)에 속하면 A(i,j) = n(간선의 개수)로 표시한다. # 가중치 그래프라면 2차원 배열 A(i,j)의 원소에 가중치를 함께 표현할 수도 있다. 아래의 그림은 다중 가중치 방향성 그래프..

그래프의 정의 # 그래프G는 각각 공집합이 아닌 정점의 집합V와 간선의 집합E의 집합이다. 그래프G=(V,E)로 표시한다. # 정점이란 데이터가 저장되는 노드를 의미한다. 그래프G의 정점들의 집합V는 V(G) = {A,B,C,...}로 표현한다. # 간선이란 두 정점을 이은 선으로 데이터와 데이터간의 연결을 의미한다. 그래프G의 간선들의 집합E는 E(G) = {(A,B),(A,C),(B,C)...}로 표시한다. 그래프의 분류 1. 방향성 유무에 따른 분류 # 비방향성 그래프(undirected graph) : 간선에 방향이 표시되지 않은 그래프. 간선(A,B)와 간선(B,A)가 서로 같은 간선을 가리킨다. # 방향성 그래프(directed graph 또는 digraph) : 간선에 방향이 표시된 그래프...

우선순위큐와 힙 # 힙을 우선순위큐를 염두에 두고 구현했기 때문에 아래의 코드는 힙에서 달라진게 함수명밖에 없다. # 그래서 우선순위큐를 구현하는 것을 힙을 구현하는 것과 동일시하기도 한다. C++로 구현한 힙 기반의 우선순위 큐 #pragma once class PQ_Heap { int* capacity; int iSize; int iCount; int* tRet; private: int ParentIndex(int index); // 지정한 노드의 부모 노드의 인덱스를 반환 int LeftIndex(int index); // 지정한 노드의 왼쪽 노드의 인덱스를 반환 int RightIndex(int index); // 지정한 노드의 오른쪽 노드의 인덱스를 반환 public: bool Add(int d..

우선순위 큐 # 큐가 들어온 시간에 따라 우선순위를 정한 것이고, 스택이 들어온 시간의 역순으로 우선순위를 정해 우선순위가 높은 것을 먼저 내보내는 자료구조라면 우선순위 큐는 데이터에 따라 다르게 정해지는 우선순위에 따라 먼저 내보낼 자료구조를 정하는 자료구조이다. # 우선순위 큐는 들어온 순서에 상관없이 우선순위가 높은 것을 가장 먼저 내보낸다는 것만 지켜지면 되는 추상적인 자료구조이다. # 우선순위 큐는 데이터의 값을 대소비교해서 우선순위를 정할 수도 있고, 우선순위를 따로 표시하는 태그를 가질수도 있다. # 우선순위 큐의 ADT Add : 우선순위 큐에 데이터 삽입하기. Remove : 가장 우선순위가 높은 데이터 삭제하기. (혹은 내보내기) Retrieve : 가장 우선순위가 높은 데이터 확인하기..

힙 # 힙이란 부모노드에 저장된 값이 자식노드의 값(혹은 우선순위)보다 항상 큰 (혹은 항상 작은) 완전이진트리이다. # 즉 힙은 다음의 세가지 조건을 만족하는 자료구조이다. 1) 항상 완전이진트리의 형태이다. 2) 부모 노드의 키값이 자식 노드의 각각의 키값보다 항상 크다. (혹은 항상 작다.) 3) 자식 노드의 키값은 자식 노드의 자식 노드보다 항상 크다. (혹은 항상 작다.) 즉 재귀적인 구조를 갖는다. # 힙에서 형제 노드끼리의 값은 비교하지 않는다. # 루트노드의 값이 항상 가장 큰 힙을 최대 힙 (Max Heap)이라 하고, 항상 가장 작은 힙을 최소 힙(Min Heap)이라 한다. # 힙과 이진탐색트리의 삽입, 삭제, 탐색시의 시간 복잡도를 비교해보면 이진탐색트리는 평균적인 경우 삽입 : L..

이진탐색트리(Binary Search Tree) # 이진 탐색 트리란 이진 트리 중 탐색을 위해서 고안된 것으로 다음과 같은 조건을 갖는다. 1) 노드N에 대해서 N의 왼쪽 하위트리에 있는 노드는 N보다 작고, N의 오른쪽 하위트리에 있는 노드는 N보다 크다. 2) 노드N에 대해서 N의 왼쪽 서브트리도, 오른쪽 서브트리도 이진 탐색트리이다. # 이진탐색트리는 정렬 기준에 대해 약하게 정렬되어 있다고 할 수 있다. # 이를 이용해 완전히 정렬된 상태를 얻고 싶다면 이진탐색트리를 중위순회하면 된다. # 이진탐색트리는 최악의 경우 탐색, 삽입, 삭제 작업에 대해서 N의 효율을 보인다. # 이는 이진탐색트리의 최악의 경우는 데이터가 한쪽 방향으로만 쏠려 연결리스트와 같은 모습이 되기 떄문이다. # 하지만 평균적..

수식 트리 # 이진트리의 활용법 중 하나인 수식트리 # 문자열로 수식을 입력받아 그 결과를 리턴해준다. # 큐와 스택은 앞에서 만든걸 활용했다. C++로 구현한 수식트리 #pragma once #include "Queue_list.h" #include "stack_list.h" #include #include #if defined(UNICODE) || defined(_UNICODE) #define tcout std::wcout #define tcin std::wcin #else #define tcout std::cout #define tcin std::cin #endif struct node { TCHAR data; node* left; node* right; }; node* MakeNode(TCHAR ..

스레이드 이진 트리 # 스레이드 이진 트리라는 말보다는 스레드 이진 트리라는 표현이 더 많이 쓰이는 것 같지만, 왠지 운영체제의 스레드와 혼동이 되므로 스레이드라 썼다. # 스레이드 이진 트리는 이진트리의 순회를 재귀함수로 구현하면 시스템 스택을 사용하므로 비효율적이기 때문에 이를 영링크를 활용하여 비재귀적으로 바꾼 트리이다. # ... 라는데 아래의 구현이 더 효율적일지는 잘 모르겠고, 일단 순회에 있어서 재귀호출을 사용하지 않게 하는데만 집중했다. # 아무리 생각해도 구현의 난이도가 쓸데없이 높아서 사용이 많이 될지는 모르겠다. # 저번 포스트의 전위, 중위, 후위 순회 부분만 비재귀로 바꿨다. 구현 코드 #pragma once template struct node { T data; node* pre..

이진트리 # 최소한의 기능만 가진 이진트리 (라지만 꼭 있어야 하는 기능들이 아직 없는듯한...) # 아무래도 미완성 느낌이 강하긴 하지만 추후에 내용을 추가하기로 결정. # 현재로서는 트리에 노드를 추가하려면 수작업으로 노드를 찾아가서 노드를 추가하는 식으로 작업하도록 되어있다. # 순회의 목적에 따라 함수포인터를 전달하도록 되어있기 때문에 이를 사용한 메인 함수도 함께 첨부했다. # 다음 포스트는 '스레이드 이진트리'와 '수식 트리'까지 다루고, 바로 '우선순위 큐와 힙', '그래프'로 넘어간 뒤, # 알고리즘 부분으로 넘어가서 탐색과 정렬에 관련된 자료구조를 다뤄야 할 듯 하다. C++로 구현한 포인터 기반 이진트리 BinaryTree.h #pragma once template struct node..