Song 컴퓨터공학

순회(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 라고 합니..

연결리스트(Linked list) 란? 구조체를 활용한 연결 리스트(Linked list using structure) 연결 리스트에 대해 알아보기 전에 이것을 왜 사용하는지 부터 알아보도록 하겠습니다. 이전에 정적 메모리... blog.naver.com 연결 리스트를 왜 배우는가에 대한 내용은 위 포스팅을 참조해주시면 됩니다. 연결 리스트(Linked List) 란 노드가 연결되어 있는 구조로 각 노드는 데이터와 포인터를 가집니다. 즉 각 노드가 데이터와 포인터를 가지고 연결되어 있는 방식으로 데이터를 저장하는 자료구조 를 연결 리스트 라고 합니다. 맨 처음의 노드는 head 포인터가 가리키고 있으며, 다음 노드를 가리키는 포인터는 다음 노드의 데이터의 주소를 값으로 가집니다. 단순 연결리스트 (Sin..

스택(Stack)이란? 스택(Stack)은 자료구조의 한 종류입니다. 두 개의 포인터로 많은 양의 데이터를 관리하는 이론? 구조? 이죠. 자료구조 중에서 '선형구조'에 해당하는 자료구조인데요, 어려울 거 없이 프링글스를 생각하시면 됩니다. 자료 구조 설명하는데 왜 뜬금없는 과자가 나오나 싶지만, 이 구조가 스택 구조와 매우 유사합니다. 우리가 프링글스를 먹을 때 맨 아래 프링글스나 중간 프링글스를 먼저 먹을 수 있나요? 아니죠. 위에서 순서대로 먹어야만 합니다. 그리고 아래에는 구멍이 안 뚫려있고, 위에만 구멍이 뚫려 있는 구조입니다. 위에는 뚫려있고, 위에서 부터 가져올 수 있으며 반대로는 뺄수없는 형태를 스택구조 라고 합니다. 이를 FILO(First In Last Out), 혹은 LIFO(Last ..

STL(Standard Template Library) 는 C++ 에서 가장 자주 사용되는 라이브러리 중 하나입니다. PS (Problem Solving)을 공부하기 전에 필수적으로 익혀야 하는 라이브러리입니다. 문제를 푸는데 필요한 알고리즘들을 빠르게 구현할 수 있기 때문입니다. 자료구조에서 배우는 스택, 큐, 트리, 등등을 일일히 구현하고 문제를 푸는 것도 중요하지만 매번 그럴 수가 없기 때문에 STL을 활용해서 문제를 해결하는 것도 중요한 것이죠. STL은 크게 4가지 ( container, iterator, algorithm, functor ) 로 나뉩니다. PS에서 중점적으로 볼 부분은 자료구조라고 할 수 있는 컨테이너(container) 와 각 컨테이너를 다룰 수 있는 여러 함수들이 구현되어 ..

C++ 이 가지는 특징 중 하나로 일반화 프로그래밍(Generic programming) 을 들 수 있습니다. 일반화 프로그래밍이란 쉽게 말하자면 일반적인, 다양한 상황에서도 같은 코드로 적용할 수 있는 것을 말합니다. C++ 에서 일반화 프로그래밍을 할 수 있는 대표적인 기능 중 하나가 바로 템플릿(Template) 입니다. 말로는 무슨 소리인지 이해가 잘 안가죠. 간단한 예를 들어보겠습니다. #include #include int max(int a, int b) { if (a > b) return (a); else return(b); } float max(float a, float b) { if (a > b) return (a); else return(b); } int main(void) { int ..