johyeongseob 님의 블로그

교재: C언어로 쉽게 풀어쓴 자료구조 개정 3판 (2019, 천인국 외) 12.1 정렬이란? 정렬(sorting)은 물건을 크기순으로 오름차순(ascending order)이나 내림차순(descending order)으로 나열하는 것을 의미한다. 정렬은 컴퓨터 공학에서 가장 기본적이고 중요한 알고리즘 중의 하나로 자료 탐색에 있어서 필수적이다. 정렬시켜야 할 대상은 레코드(record)라고 부른다. 레코드는 다시 필드(field)라고 하는 단위로 나누어진다. 여러 필드 중에서 특별히 레코드와 레코드를 식별해 주는 역할을 하는 필드를 키(key)라고 한다. 정렬이란 결국 레코드들을 키값의 순서로 재배열하는 것이다. 모든 경우에 있어서 최상의 성능을 보여주는 최적 알고리즘은 존재하지 않는다. 따라서 이들 중..

교재: C언어로 쉽게 풀어쓴 자료구조 개정 3판 (2019, 천인국 외) 11.1 최소 비용 신장 트리신장 트리 신장 트리(spanning tree)란 그래프 내의 모든 정점들이 연결되어 있으며 사이클을 포함하지 않는 트리이다. 신장 트리는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결하게 된다. 신장 트리는 그래프의 최소 연결 부분 그래프가 된다. 최소의 의미는 간선의 수가 가장 적다는 의미히다. 최소 비용 신장 트리 최소 비용 신장 트리(MST: minimum spanning tree)는 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 신장 트리를 말한다. 이를 구하는 방법으로는 Kruskal과 Prim이 제안한 알고리즘이 대표적으로 사용되고 있다. 11.2 Kruskal의 M..

교재: C언어로 쉽게 풀어쓴 자료구조 개정 3판 (2019, 천인국 외) 10.1 그래프란?그래프의 소개 그래프(graph)는 객체 사이의 연결 관계를 표현할 수 있는 자료 구조다. 그래프 이론(graph theory)은 컴퓨터 학문 분야의 활발한 연구 주제이며 문제 해결을 위한 도구로서 많은 이론과 응용이 존재한다. 우리는 여기서 그래프의 기본적인 알고리즘에 대해서 학습한다. 10.2 그래프의 정의와 용어그래프의 정의 그래프는 정점(vertex)과 간선(edge)들의 유한 집합이라 할 수 있다. 수학적으로는 G = (V, E)와 같이 표현한다. 여기서, V(G)는 그래프 G의 정점들의 집합을, E(G)는 그래프 G의 간선들의 집합을 의미한다. 정점은 여러 가지 특성을 가질 수 있는 객체를 의미하고, 간..

교재: C언어로 쉽게 풀어쓴 자료구조 개정 3판 (2019, 천인국 외) 9.1 우선순위 큐 추상 데이터 타입우선순위 큐의 소개 우선순위 큐는 우선순위의 개념을 큐에 도입한 자료구조이다. 보통의 큐는 선입 선출(FIFO)의 원칙에 의하여 먼저 들어온 데이터가 먼저 나가게 된다. 그러나 우선순위 큐(priority queue)에서는 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나가게 된다. 히프(heap)구조가 우선순위 큐를 가장 효율적으로 구현할 수 있다. 우선순위 큐는 2가지로 구분할 수 있는데, 최소 우선순위 큐는 가장 우선순위가 낮은 요소를 먼저 삭제한다. 최대 우선순위 큐는 반대로 가장 우선순위가 높은 요소가 먼저 삭제된다. 9.2 우선순위 큐의 구현 방법히프를 사용하는 방법 ..

8.1 트리의 개념 만약 자료가 계층적인 구조(hierarchical structure)를 가지고 있다면 리스트, 스택, 큐 등의 선형 자료 구조(linear data structure)는 더 이상 적합하지 않다. 트리(tree)는 이러한 계층적인 자료를 표현하는데 적합한 자료구조이다. 트리는 인공 지능 문제에서도 사용된다. 대표적인 것이 결정 트리(decision tree)이다. 결정 트리는 인간의 의사 결정 구조를 표현하는 한 가지 방법이다. 이러한 구조를 트리라고 부르는 이유는 마치 실제 트리를 거꾸로 엎어놓은 것 같은 모양을 하고 있기 때문이다. 트리의 용어들 트리의 구성 요소를 노드(node)라 한다. 트리는 한 개 이상의 노드로 이루어진 유한 집합이다. 이들 중 하나의 노드는 루트(root) ..

교재: C언어로 쉽게 풀어쓴 자료구조 개정 3판 (2019, 천인국 외) 7.1 원형 연결 리스트 원형 연결 리스트란 마지막 노드가 첫 번째 노드를 가리키는 리스트이다. 즉 마지막 노드의 링크 필드가 NULL이 아니라 첫 번째 노드 주소가 되는 리스트이다. 원형 연결 리스트가 특히 유용한 경우는 리스트의 끝에 노드를 삽입하는 연산이 단순 연결 리스트보다 효율적일 수 있다는 것이다. 원형 연결 리스트에서 헤드 포인터가 마지막 노드를 가리키고, 첫 번째 노드는 head->link가 가리키고 있으므로, 리스트의 처음과 끝에 노드를 삽입할 수 있다. 원형 리스트의 처음에 삽입ListNode* insert_first(ListNode* head, element data){ ListNode* node = (ListN..

교재: C언어로 쉽게 풀어쓴 자료구조 개정 3판 (2019, 천인국 외) 6.1 리스트 추상 데이터 타입리스트의 소개 리스트(list)는 우리들이 자료를 정리하는 방법 중의 하나이다. 리스트에는 항목들이 차례대로 저장되어 있다. 리스트의 항목들은 순서 또는 위치를 가진다. 리스트는 집합하고는 다르다. 집합은 각 항목 간에 순서의 개념이 없다.L = [item(0), item(1), item(2), ... , item(n-1)]리스트는 다음과 같은 기본적인 연산들을 생각할 수 있다.리스트에 새로운 항목을 추가한다(삽입 연산).리스트에서 항목을 삭제한다.(삭제 연산).리스트에서 특정한 항목을 찾는다(탐색 연산). 6.3 연결 리스트 이번 절에서 연결된 표현(linked representation)에 대하여 ..

교재: C언어로 쉽게 풀어쓴 자료구조 개정 3판 (2019, 천인국 외) 5.1 큐 추상 데이터 타입 큐(queue)는 먼저 들어온 데이터가 먼저 나가는 다시 말해, 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조로 이러한 특성을 선입선출(FIFO: First-In First-Out)이라고 한다. 큐에서 삽입이 일어나는 곳을 후단(rear)라고 하고 삭제가 일어나는 곳을 전단(front)라고 한다. 큐에서 가장 중요한 연산은 삽입과 삭제 연산인 enqueue와 dequeue이다. enqueue 연산은 큐에 요소를 추가하는 연산으로서 큐의 맨 뒤에 새로운 요소를 추가한다. dequeue 연산은 큐의 맨 앞에 있는 요소를 꺼내서 외부로 반환한다. 큐의 응용으로 예를 달면 운영 체제에는 ..

교재: C언어로 쉽게 풀어쓴 자료구조 개정 3판 (2019, 천인국 외) 4.1 스택이란?  스택이란 '(건초, 밀집 따위를 쌓아놓은) 더미, 낟가리'를 의미한다. 식당에 쌓여있는 접시 더미, 책상에 쌓여있는 책, 창고에 쌓여있는 상자 등이 스택의 전형적인 예이다. 스택에서 가장 최근에 들어온 것이 가장 위에 있게 되고, 또 먼저 나가게 된다. 이런 입출력 형태를 후입선출(LIFO: Last-In First-Out0이라고 한다. 스택에서의 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삭제할 수 없다. 스택에서 입출력이 이루어지는 부분을 스택 상단(Stack top)이라 하고 반대쪽인 바닥 부분을 스택 하단(stack bottom)이라고 한다. 스택에 저장되는 것을 요소(element)라 부른..

교재: C언어로 쉽게 풀어쓴 자료구조 개정 3판 (2019, 천인국 외) 3.1 배열  배열은 동일한 타입의 데이터를 한 번에 여러 개 만들 때 사용된다. 대량의 데이터를 저장하기 위하여 배열을 사용하면 "연속적인 메모리 공간"이 할당되고 인덱스(index) 번호를 사용하여 쉽게 접근이 가능하기 때문에 반복 루프를 이용하여 여러 가지 작업을 손쉽게 할 수 있다. 배열 ADT  배열은 의 쌍의로 이루어진 집합으로 정의할 수 있다. 즉 인덱스(index)가 주어지면 해당하는 값(value)이 대응되는 자료 구조이다. 수학적으로 배열은 인덱스에서 값의로의 사상(mapping)에 해당된다.3.2 구조체구조체의 개념 복잡한 객체어는 다양한 타입의 데이터들이 한데 묶여져서 있다. 배열이 타입이 같은 데이터의 모임이..