GoldTree of C.E

정렬이란? 정렬은 물건을 크기 순으로 오름차순이나 내림차순으로 나열하는 것을 의미한다. 레코드, 필드, 키 보통 정렬시켜야할 될 대상은 레코드(record)라 불리며, 또 레코드는 필드(field)라는 보다 작은 단위로 구성된다. 여러 필드 중에서 특별히 레코드와 레코드를 식별해주는 역할을 하는 필드를 키라고 한다. 알고리즘의 효율성 모든 경우에 최적인 정렬 알고리즘은 없다. 즉, 각 응용 분야에 적합한 정렬 방법을 사용해야 한다. 대개 정렬 알고리즘을 평가하는 효율성의 기준으로는 정렬을 위해 필요한 비교 연산의 횟수와 이동 연산의 횟수이다. 이들 횟수를 빅오 표기법을 이용하여 근사적으로 표현한다. 정렬의 종류 정렬 알고리즘을 내부 정렬(internal sorting)과 외부정렬(external sort..

그래프 그래프의 정의는 '연결되어 있는 객체 간의 관계를 표현하는 자료구조'이다. 그예로는 전에 알아본 Tree구조도 그래프의 특수한 경우이고, 지하철노선도 또한 그래프의 일종이다. 그래프의 정의와 용어 그래프는 정점(vertex)과 간선(edge)들의 유한 집합이라 할 수 있다. 수학적으로는 G = (V, E)로 표시한다. 정점(Vertices) 여러 가지 특성을 가질 수 있는 객체 V(G) : 그래프 G의 정점들의 집합 노드(node)이다. 간선(edge) 정점들 간의 관계 E(G) : 그래프 G의 간선들의 집합 링크(link)이다. 종류 무방향 그래프(undirected graph) : 간선을 통해서 양방향으로 갈수 있다. 방향 그래프(directed graph) : 간선에 방향성이 존재하는 그래프..

트리의 개념 지금까지는 리스트, 스택, 큐 등의 선형 자료 구조(linear data structure)를 알아봤다. 이번에는 계층적인 구조(hierachiacal structure)알아보려 한다. 계층적인 구조에 대해 예를 들면 컴퓨터의 폴더를 들수있다. 폴더는 상위폴더와 하위폴더로 이루어져있는 것을 알 수 있다.하위폴더를 들어가기 위해서는 먼저 상위폴더를 들어간 후에 하위폴더로 들어갈 수 있다. 트리의 용어들 트리의 구성 요소에 해당하는 A,B,C,...,N,O를 노드(node)라 한다. 계층적인 구조에서 가장 높은 곳에 있는 노드(위 그림의 A)를 루트(root)노드라고 하며, 그 외의 노드를 서브트리(subtree)라고 한다.위 그림은 {B,F,G},{C,H,K,L,M},{D,I,N},{E,J,O..

원형 연결 리스트 원형 연결 리스트란 마지막 노드가 첫 번째 노드를 가리키는 리스트이다. 단순 연결 리스트와 원형 연결 리스트의 차이점을 알아보자. 위 그림의 단순 연결 리스트를 보면 마지막 노드는 다음 연결할 노드가 없어 NULL값을 가지고 있지만, 원형 연결 리스트의 경우 마지막 노드가 첫번째 노드를 가리키면서 순환하는 모습을 볼 수 있다. 더 구체적으로 얘기하면 단순 연결 리스트의 마지막 노드의 링크는 NULL값을 가지고 있지만, 원형 연결 리스트의 마지막 노드의 링크는 첫번째 노드를 가리키고 있다. 예시로 지하철 4호선과 2호선 순환내선을 들 수 있다. 4호선은 단순 연결 리스트이다. 오이도를 head라고 했을 때, 오이도 -> 정왕 -> 신길온천 -> ... -> 창동 ->상계 -> 당고개 으로..

이 글은 이해한 것을 적어놓은 글로, 'C언어로 쉽게 풀어쓴 자료구조'에서 가져왔다. 리스트 추상 데이터 타입 리스트의 소개 리스트에는 항목들이 차례대로 저장되어 있다. 리스트의 항목들은 순서 또는 위치를 가진다. 앞에서 살펴본 스택과 큐도 넓게 보면 리스트의 일종이다. 리스트는 집합하고는 다르다. 집합은 각 항목 간에 순서의 개념이 없다. 리스트 ADT 객체 : n개의 element형으로 구성된 순서 있는 모임 연산 : insert(list, pos, item) ::= pos 위치에 요소를 추가한다. insert_last(list, item) ::= 맨 끝에 요소를 추가한다. insert_first(list, item) ::= 맨 처음에 요소를 추가한다. delete(list, pos) ::= pos ..

스택 그림처럼 가장 최근에 들어온 변수가 가장 위에 있게 되고, 또 먼저 나가게 된다. 이런 입출력 형태를 후입선출(LIFO:Last-In-First_Out)이라고 한다.

모든 정보는 https://coding-factory.tistory.com/610에서 가져왔으며, 이해를 하기위해 적어놓은 것이다. 그래프란? 그래프는 정점과 간선으로 이루어진 자료구조이다.정확히는 정점(Vertex)간의 관계를 표현하는 조직도이다. 그런면에서 트리는 그래프의 일종인 셈입니다. 다만 트리와는 달리 그래프는 정점마다 간선이 없을수도 있고 있을수도 있으며 루트 노드, 부모와 자식이라는 개념이 존재하지 않는다. 또한 그래프는 네트워크 모델 즉, 객체와 이에 대한 관계를 나타내는 유연한 방식으로 이해할 수 있다. 실생활에서 다양한 예를 그래프로 효현할 수 있는데 대표적으로 지하철 노선도, 도심의 도로등이 있다. 이런식으로 활용할 수 있는 방법이 많기에 문제도 다양하게 출제를 할 수있다. 그래프는..