Song 컴퓨터공학

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

힙(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" 란 임의의 지역에서 출발하여 모든 다리를 단 한번만 건너서 처음 출발했던 지역으로 돌아올 수 있는가? 를 묻는 문제입니다. 이 문제의 정답은 "없다" 입니다. 오일러가 '어떤 한 지역에서 시작하여 모든 다리를 한 번씩만 지나서 처음 출발점으로 되돌아오려면 각 지역에 연결된 다리의 개수가 모두 짝수"이어야 한다는 것을 증명했죠. 그 때 오일러는 위 문제를 아래 그림처럼 간단히 바꿔서 증명했습니다. 이..

[C 자료구조] 큐(Queue) - 선형큐 / 원형큐 배열 구현 큐(Queue) 란? 스택의 경우, 나중에 들어온 데이터가 먼저 나가는 LIFO 구조인 반면, 큐(Queue) 는 먼저 들어온 데이터가 먼저 나가는 자료구조입니다. 이런 특성을 FIFO (First-In First-Out) 이라고 합니다. songsite123.tistory.com 지난 포스팅에서 큐에 대해 설명하고, 선형큐와 원형큐를 배열을 사용해 구현해보았습니다. 오늘은 배열이 아닌 연결 리스트를 사용하여 큐를 구현하는 법에 대해 다뤄보겠습니다. 다시 한 번 큐에 대해 간단히 복습해보면 큐는 front 에서 dequeue ( 삭제, 꺼냄 ) 연산이 진행되고 rear 에서 enqueue ( 삽입 ) 연산이 진행되는 자료구조입니다. 연결리스..

큐(Queue) 란? 스택의 경우, 나중에 들어온 데이터가 먼저 나가는 LIFO 구조인 반면, 큐(Queue) 는 먼저 들어온 데이터가 먼저 나가는 자료구조입니다. 이런 특성을 FIFO (First-In First-Out) 이라고 합니다. 스택은 아래 부분이 막히고 윗 부분이 뚫린 형태였다면 큐는 양쪽이 뚫린 통입니다. 스택이 맨 위에서만 데이터를 삽입하고 삭제했다면 큐는 삽입과 삭제가 다른 쪽에서 일어납니다. 양 끝의 이름을 일반적으로 front 와 rear 라고 부르며 데이터의 삽입이 일어나는 곳을 rear 라고 하고 데이터의 삭제가 이뤄지는 곳을 front 라고 합니다. 데이터 삽입을 스택에서는 push 라고 했지만 queue 에서는 enqueue 라고 합니다. 삭제 연산은 dequeue 라고 합니..