Song 컴퓨터공학

[C 자료구조] 그래프 ADT 구현 : 인접행렬 / 인접리스트 n = 0; for (row = 0; row adj_mat[row][col] = 0; } Graph 구조체 안에는 인접 행렬을 나타낼 2차원 배열과 정점의 개수를 저장할 변수를 선언합니다. 그 이후 songsite123.tistory.com 지난 포스팅에서 인접 행렬과 인접 리스트로 그래프를 구현해보았죠. 오늘은 그렇게 구현한 그래프의 탐색 연산을 구현하는 방법에 대해 알아보겠습니다. 그래프의 탐색은 가장 기본적인 연산으로 하나의 정점으로부터 시작해서 차례대로 모든 정점들을 한 번씩 방문하는 것 입니다. 그래프의 탐색 방법은..

너비 우선 탐색, BFS 이란? BFS 란 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법입니다. BFS는 큐를 사용해 구현하며 DFS와 마찬가지로 인접 행렬로 표현된 그래프와 인접 리스트로 표현된 그래프의 경우 조금 달라집니다. 오늘 포스팅에서는 BFS 의 동작을 단계별로 이해해보고 인접 행렬로 표현된 그래프에 적용할 수 있는 BFS 코드를 구현해보겠습니다. BFS 도 DFS와 마찬가지로 시간 복잡도는 인접 행렬인지 인접 그래프로 표현되었는지에 따라 달라지게 되는데 인접 행렬의 경우 O(n^2), 인접 그래프의 경우 O(n+e) 가 됩니다. BFS의 구현에 있어서 큐는 반드시 알아야 하기 때문에 큐의 개념이 헷갈리신다면 아래의 포스팅을 참고해주세요. [..

깊이 우선 탐색, DFS 이란? DFS 란 트리에서 생각해보면 트리를 탐색할 때 시작 정점에서 한 방향으로 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 매우 유사합니다. 즉 DFS는 특정 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완전히 탐색하는 방법입니다. DFS 는 스택을 사용해 구현합니다. 아래의 동작과 구현에서 확인하겠지만, 깊이 우선 탐색을 통해 그래프를 탐색하게 되면 모든 간선을 조사하므로 정점의 수가 n 이고 간선의 수가 e인 그래프인 경우, 그래프가 인접 행렬로 표시되어 있다면 O(n^2), 인접 리스트로 표현되어 있는 경우는 O(n+e) 가 됩니다. 따라서 희소 그래프인 경우는 DFS는 인접 리스트의 사..

힙(Heap) 이란? 힙(heap) 은 완전 이진 트리의 일종으로 여러 값들 중 최댓값 혹은 최솟값을 빠르게 찾아내기 위한 자료구조입니다. 이진 탐색 트리와는 다르게 힙은 중복된 값을 허용합니다. 완전 이진 트리는 지난 게시물에서 배웠었는데요 그 부분만 다시 보면 완전 이진 트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져있고, 마지막 레벨은 왼쪽에서 오른쪽 순으로 데이터가 차 있는 이진 트리를 말합니다. Heap 은 중복 키 값을 허용하고, 부모 노드와 자식 노드 간의 관계가 정해져 있는 자료구조입니다. Max heap 와 Min heap 은 위처럼 부모 노드가 자식 노드보다 키값이 더 큰지 작은지로 결정됩니다. Max heap 은 가장 큰 값을 빠르게 찾을 수 있고, Min heap 은 가장 ..

이진 탐색 트리(Binary Search Tree) [C 자료구조] 트리(Tree) 의 종류 트리(Tree) 란? 수학, 그래프 이론에서는 회로가 없는 무방향의 그래프를 트리라고 정의합니다. 이는 자료구조에서 쓰이는 트리와 기본적으로 같지만 차이가 좀 있습니다. 무슨 말인지 쉽게 알아 songsite123.tistory.com 트리와 이진트리의 개념은 위 포스팅에서 확인하시면 되겠습니다. 이진탐색트리는 빠른 탐색 및 정렬을 위해 고안된 형태의 자료구조로 어떠한 특징을 가지는 이진트리를 말합니다. 각 노드에 중복되지 않는 키(key)가 있다. 루트 노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 값을 가지고 있다. 루트 노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 값을 가지고 있다. 좌우 서브 트리..

[C 자료구조 ] 트리의 순회(Traversal of Tree) - 전위 / 중위 / 후위순회(Traversal) 란 트리의 노드들을 체계적으로 방문하는 것을 말합니다. 모든 노드들을 방문해야 하고 3가지의 기본적인 순회방법이 있습니다. 전위순회(preorder traversal, VLR), 중위 순회(inorder traversongsite123.tistory.com위 포스팅에서 재귀적으로 전위, 중위, 후위 순회를 구현해보았습니다. 오늘은 재귀함수 호출이 아닌 스택과 반복문을 사용해서 순회함수를 구현해보도록 하겠습니다. 순회의 과정이나 메커니즘은 똑같으니 위 포스팅을 먼저 보고 순회가 무엇인지 어떤 순서로 이루어지는지 먼저 이해하고 오시는 것을 추천드립니다. 스택을 이용한 트리 순회 코드위 같은 형태..

순회(Traversal) 란 트리의 노드들을 체계적으로 방문하는 것을 말합니다. 모든 노드들을 방문해야 하고 3가지의 기본적인 순회방법이 있습니다. 전위순회(preorder traversal, VLR), 중위 순회(inorder traversal, LVR), 후위순회(postorder traversal, LRV) 입니다. 가장 먼저 중위순회에 대해 자세하게 단계별로 이해하고, 전위 순회와 후위 순회와의 차이점에 대해 알아보겠습니다. 밑의 포스팅에서 L, V, R 이라는 약자가 많이 나올텐데 L은 Left 의 약자로 왼쪽 서브 트리, V 는 Visit, R은 Right의 약자로 오른쪽 서브 트리를 의미합니다. 중위 순회 (inorder traversal) 중위순회는 LVR 탐색이 이루어집니다. 왼쪽 서브 ..

트리(Tree) 란? 수학, 그래프 이론에서는 회로가 없는 무방향의 그래프를 트리라고 정의합니다. 이는 자료구조에서 쓰이는 트리와 기본적으로 같지만 차이가 좀 있습니다. 무슨 말인지 쉽게 알아봅시다. 트리는 스택이나 큐 같은 선형 자료 구조가 아닌 노드로 이루어진 비선형 자료구조입니다. 트리는 계층 간의 관계를 표현하는 자료구조입니다. 트리는 아래의 특징들을 가집니다. 1. 트리는 하나의 루트 노드를 가진다. 2. 루트 노드는 0개 이상의 자식 노드를 가진다. 3. 자식 노드 또한 0개 이상의 자식 노드를 가진다. 4. 노드와 노드들을 연결하는 간선(Edge) 들로 구성되어 있다. 5. 트리에는 사이클(cycle) 이 존재할 수 없다. 사이클이란 시작 노드에서 출발해 다시 시작 노드로 돌아올 수 있는 경..

n = 0; for (row = 0; row adj_mat[row][col] = 0; } Graph 구조체 안에는 인접 행렬을 나타낼 2차원 배열과 정점의 개수를 저장할 변수를 선언합니다. 그 이후 초기화를 진행하는데 당연히 아직은 정점을 따로 삽입하지 않았기 때문에 n = 0 으로 초기화합니다. 또한 간선도 없으니까 배열을 모두 0으로 초기화 시켜 줍니다. 정점 삽입 연산 : insert_vertex() void insert_vertex(Graph* g, int vertex) { if (((g->n) + 1) > MAX_VERTICES) { fprintf(stderr, "최대 정점 개..

그래프(Graph) 란? 그래프(graph) 란 객체 사이의 연결 관계를 표현할 수 있는 자료구조 입니다. 그래프는 오일러가 처음으로 사용했다고 알려져 있는데요, 아래 문제는 오일러의 "Konigsberg bridge problem" 이라고 불리는 문제입니다. "Konigsberg bridge problem" 란 임의의 지역에서 출발하여 모든 다리를 단 한번만 건너서 처음 출발했던 지역으로 돌아올 수 있는가? 를 묻는 문제입니다. 이 문제의 정답은 "없다" 입니다. 오일러가 '어떤 한 지역에서 시작하여 모든 다리를 한 번씩만 지나서 처음 출발점으로 되돌아오려면 각 지역에 연결된 다리의 개수가 모두 짝수"이어야 한다는 것을 증명했죠. 그 때 오일러는 위 문제를 아래 그림처럼 간단히 바꿔서 증명했습니다. 이..