프로그래밍 언어/C

[자료구조] 그래프 탐색 (DFS, BFS)

[ 그래프의 탐색 ] 더보기 - 그래프의 탐색 └ 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한번씩 방문하여 탐색하는 것 많은 문제들이 단순 그래프의 노드(정점)를 탐색하느 것으로 해결 가능함 - 탐색 방법 └ 깊이 우선 탐색 ( DFS : Depth First Search ) 너비 우선 탐색 ( BFS : Breath First Search ) [ 깊이 우선 탐색 (DFS) ] 더보기 - 깊이 우선 탐색 (DFS) └ 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 탐색 방법이다. 주로 스택을 사용하여 구현, 단순 탐색 속도 자체는 너비 우선 탐색 (BFS)에 비해 느림. 탐색이 아닌 순회를 할 경우 자주 사용한다 ① 갈림..

[자료구조] 그래프

[ 그래프 ] 더보기 - 그래프 (Graph) └ 그래프는 정점(Vertex)과 정점들을 연결하는 간선(Edge)으로 구성되어 있는 자료구조 이론적으로 행렬과 리스트 두개의 형태로 구현이 가능하나 최적의 형태는 두 구조의 조합된 형태를 띄고 있음 [ 가중 그래프 ] 더보기 - 가중 그래프 (Weight Graph) └ 정점과 정점 사이를 잇는 간선에 가중치가 주어진 그래프를 말한다. 가중 그래프 중 유향 그래프를 네트워크(Network)라고도 한다. 각 정점들을 도시, 간선들을 도로라고 가정한다면 가중치는 각 도로를 지나기 위한 비용이나 도시 사이의 거리등의 값으로 계산 가능 [ 부분 그래프 / 유도 부분 그래프 ] 더보기 - 부분 그래프 (Subgraph) └ 어떠한 그래프의 정점과 간선 가운데 일부로..

[자료구조] 트리 (2)

《 트리 》 [ 이진트리의 순회 ] 더보기 - 전위순회(Preorder) └ 순회 순서 : 루트 → 왼쪽 서브 트리 → 오른쪽 서브트리 순서로 순회 (VLR) // C code // 전위 순회 void preorder(TreeNode* root) { if (root != NULL) { printf("[%2d] ", root->data); preorder(root->left); preorder(root->right); } } - 중위순회(Inorder) └ 순회 순서 : 왼쪽 서브트리 → 루트 → 오른쪽 서브트리 순서로 순회 (LVR) // C code // 중위 순회 void inorder(TreeNode* root) { if (root != NULL) { inorder(root->left); print..

[자료구조] 트리 (1)

《 트리(Tree) 》 [ 트리의 개념 ] - 리스트, 스택, 큐 등과 같은 자료구조는 데이터가 순차적으로 나열된 선형 구조임 - 트리는 데이터가 계층적으로 구성되어 있는 비선형 구조로 구성되어 있음 - 부모와 자식 관계의 노드들로 구성되어 있음 - 인공지능 학습에서 사용되는 결정트리(decision tree), PC의 폴더 구조 등과 같이 계층적인 조직을 표현할 때 주로 사용 [ 트리의 용어 ] 노드 : 트리의 구성 요소 단말 노드 / 리프 노드(terminal node / leaf node) : 자식이 없는 노드 비단말노드(internal node) : 적어도 하나 이상의 자식을 가지는 노드 루트 노드(root node) : 트리의 최상위 노드로써 부모 노드 x 서브 트리(sub tree) : 하나의..

[자료구조] 연결리스트 (2)

《 원형 연결리스트 》 - 마지막 노드의 링크가 첫 번째 노드를 가리키는 연결 리스트 - 삭제나 삽입시 항상 선행 노드를 가리키는 포인터가 필요함 - 보통 헤드 포인터가 마지막 노드를 가리키게끔 구성함 - 리스트의 처음이나 마지막에 노드를 삽입하는 연산이 단순 연결리스트에 비해 용이 [ insert_first() 함수 ] // C code // 해당 노드의 앞에 노드를 삽입하는 함수 ListNode* insert_first(ListNode* head, element value) { ListNode* node = (ListNode*)malloc(sizeof(ListNode)); node->data = value; if (head == NULL) { head = node; node->link = head; ..