컴퓨터 이론66 30. 그래프 표현 방법 C언어에서는 다양한 방법으로 그래프를 표현한다. 우선 그래프를 표현할 때 주의해야 할 부분은 표현하려는 그래프가 가중치 그래프인지, 비 가중치 그래프인지를 확인해야 한다. 그리고 방향그래프인지, 무방향 그래프 인지를 확인해야 한다. 그래프를 표현하는 방법에는 2차원 배열을 이용하는 방법과 연결 리스트를 이용하는 방법이 존재한다. 2차원 배열을 이용한 표현 방법이다. #include #define GRAPH_VERTEX_CNT 5 int Graph[GRAPH_VERTEX_CNT][GRAPH_VERTEX_CNT] = {0,}; void Add_Graph(int v1, int v2){ Graph[v1][v2] = 1; Graph[v2][v1] = 1; } void Graph_Print(){ int i, j; .. 2023. 5. 3. 29. 그래프 그래프란? 우리는 그래프라고 하면 수학에서 사용하는 차트를 제일 먼저 생각하게 된다. 이번에 이야기하는 그래프는 차트와는 다르다. 그래프는 정점과 간선으로 이루어진 자료구조이다. 정점은 그래프에서 노드를 의미하고, 간선은 정점과 정점을 연결하는 선을 의미한다. 정점과 간선은 우리가 이전에 들어본 적이 있을 것이다. 이전에 배운 자료구조인 트리도 정점과 간선으로 이루어져 있다. 미리 이야기 하지만 트리는 그래프의 일종이다. 그래프는 다양한 분야에서 사용된다. 예를 들어 지도, 인터넷 등 다양한 분야에서 활용된다. 그래프는 노드 간의 연결 관계를 나타내므로, 연결된 객체 간의 관계를 모델링하는데 적합하다. 그래프의 종류 그래프는 다양한 종류가 존재한다. 무방향 그래프 : 간선이 양방향으로 이어진 그래프이다... 2023. 5. 3. 28. 승자트리와 패자트리 이진트리를 처음 접했을 때 가장 먼저 생각난 것은 토너먼트 대진표이다. 사람들의 생각이 비슷하다고 느낀 것은 이진트리를 활용한 토너먼트와 관련된 알고리즘과 자료구조가 존재한다. 토너먼트 알고리즘 토너먼트 알고리즘은 N개의 항목이 존재할 때, 이들을 두 개씩 짝지어 경기를 시키고, 이긴 항목을끼리 다시 경기를 시켜 이긴 항목을 또 다시 경기시키는 과정을 반복하여 마지막에 승자를 결정하는 알고리즘이다. 이 알고리즘에서 승자트리와 패지트리는 토너먼트 경기에서 승자와 패자를 효율적으로 추적하기 위해 사용되는 자료구조이다. 승자 트리 각 경기의 승자들을 이진 트리 형태로 구성하여 저장한다. 이진 트리의 각 노드는 해당 경기에서 승리한 항목을 나타내며, 상위 레벨의 노드에서는 하위 레벨에서의 승자들 중 가장 우수한.. 2023. 5. 2. 27. Union Find Union-Find 알고리즘이란? 집합을 표현하는 데 사용되며 서로소 집합을 구현하는 데 사용한다. 원소 간의 관계를 유지하면서 Union과 Find 연산을 효율적으로 수행하는 알고리즘이다. 그럼 C언어에서 집합을 어떻게 표현하게 될까? 어쩌면 집합보다는 트리의 표현이라고 생각된다. 표현 방법은 인덱스 번호를 값이라고 할 때 배열에 해당 인덱스에 저장된 값에 따라 달라진다. 만약 저장된 값이 -1이라고 하면 해당 집합은 루트 집합이다. 저장된 값이 -1이 아니라면 해당 인덱스를 부모로 하고 있는 자식 집합이다. 즉, -1이 루트, 아니라면 자식 집합이라는 뜻이다 (이런 표현 때문에 트리의 표현이라고 생각된다.) 예를 들어 a[5] = {-1, -1, -1, -1, -1}이라면 {0}, {1}, {2}, .. 2023. 4. 13. 26. Heap Heap 이란? 힙은 완전 이진트리의 일종으로, 각 노드의 값이 해당 노드의 자식 노드의 값보다 우선순위가 높은 자료구조이다. 위와 같은 조건을 Max Heap, 자식 노드의 값보다 우선순위가 낮은 경우 Min Heap이라고 부른다. 힙은 주로 우선순위 큐를 구현하는 데 사용된다. 우선순위 큐는 데이터가 들어온 순서가 아닌 우선순위에 따라 데이터를 처리하는 자료구조이다. 예를 들어, 작업 스케쥴링에서 우선순위가 높은 작업을 먼저 처리하는 등의 용도로 사용된다. 트리의 배열 구현 우리는 지금까지 트리를 구현하기 위해 노드 구조체를 선언하고 포인터를 이용하여 자식을 연결하는 방식으로 트리를 구현해 왔다. 하지만 이번에는 배열을 이용하여 구현해 볼 것이다. 배열로 구현한다고 해서 무엇인가 있어보이지만 그런 거.. 2023. 4. 12. 25. 스레드 이진트리 (Threaded Binary Tree) 스레드 이진트리란? 이진 트리에 삽입, 삭제 등의 연산을 보다 빠르고 간단하게 수행하기 위해 추가된 자료구조이다. 스레드 이진트리는 각 노드에 스레드라는 추가적인 링크를 추가하여 구현된다. 스레드 링크는 이진트리의 노드에서 왼쪽이나 오른쪽 자식이 NULL 일 때, 해당 방향으로 직접 다음 순서의 노드를 가리키는 포인터이다. 이렇게 스레드 링크를 추가함으로써, 이진 트리에서 전위, 중위, 후위 순회를 수행할 때 재귀 호출 없이 스레드 링크로 순회가 가능해진다. 스레드 이진 트리 구조체 leftThread, rightThread가 1이라면 해당 링크는 스레드 링크이고, 0이면 자식의 포인터를 저장한다. typedef struct Node *Nodepointer; typedef struct Node{ int .. 2023. 4. 7. 이전 1 ··· 4 5 6 7 8 9 10 11 다음