뭐라도 끄적이는 BLOG

그래프(Graph)는 객체 사이의 연결 관계(Connectivity)를 표현하는 자료구조이다. 그래프는 노드(Node or Vertex)와 간선(Edge)의 집합이다. 노드는 일반적으로 모델링하려는 시스템을 구성하는 객체를 나타내며, 간선은 이러한 객체 사이의 관계를 정의한다. 간선의 특성에 따른 그래프의 종류 구분 종류 설명 간선의 방향성 무방향 그래프 간선에 방향이 없는 그래프 (양방향 통행) 방향 그래프 간선에 방향이 잇는 그래프 (일방 통행) 간선의 가중치 가중 그래프 간선에 가중치가 할당된 그래프 구조적 특징 완전 그래프 연결 가능한 최대 간선 수를 가진 그래프 부분 그래프 그래프에서 일부의 노드나 간선을 제외하여 만든 그래프 다중 그래프 중복된 간선을 포함하는 그래프 무방향 그래프(Undire..

트리(Tree)는 계층구조(Hierarchical Structure)로 자료를 저장한다. 여기서 계층 구조란 트리를 구성하는 노드가 부모-자식(Parent-Child)관계라는 의미이다. 즉, 특정 부모 노드 하나에 여러 개의 자식 노드들이 연결되는 구조를 말한다. 이러한 계층구조의 대표적인 예로 컴퓨터의 폴더 구조를 들 수 있다. 트리는 하나의 부모 노드에 여러 개의 자식 노드가 연결되어 있다. 그래서 트리를 구성하는 부모-자식 노드의 관계가 일대일이 아니라는 점에서 비선형 자료구조이다. 반대로 각 노드의 부모 노드는 모두 1개라는 점은 주의하기 바란다. 트리의 개념 트리(Tree)는 노드(Node)와 간선(Edge)의 집합이다. 보통 노드는 일반적으로 모델링하려는 시스템의 객체(Object)를 나타낸다..

자료구조에서 사용되는 큐(Queue)는 줄 서기의 특징을 가지고 있다. 즉, 큐는 추가되는 자료를 차례대로 저장하여, 저장된 순서에 의해 데이터가 나오는 자료구조이다. 먼저 저장된 데이터가 나중에 저장된 데이터 보다 항상 앞서 나오기 때문에 큐는 FIFO(First-In-First-Out)이라는 특성을 가진다. 이를 '피포'라고 읽으며 다른 말로 선입선출(先入先出)이라고도 한다. 이런 FIFO의 특성은 현실세계에도 찾아볼 수 있다. 대표적으로 은행에서 발행하는 대기표를 예로 들 수 있다. Queue에서 가장 앞에 있는 고객은 가장 먼저 도착한 고객이며, 가장 뒤에 있는 고객은 가장 나중에 도착한 고객이된다. 순서가 가장 빠른 고객이 먼저 Queue를 먼저 빠져나와 업무를 처리할 수 있다. Queue에서의..

영어 단어 stack은 동사로 '쌓다'라는 뜻이 있으며, 명사로는 '무더기[더미]'를 의미한다. 자료구조에서의 Stack도 이와 마찬가지로 자료를 쌓아두는 기능을 수행한다. 즉, Stack이라는 자료구조를 통해 여러 자료를 쌓아둘 수 있게 한다. Stack의 고유한 특성을 이야기할 때 자장 대표되는 단어로 LIFO(Last-In-First-Out)를 들 수 있다. 대게 '리포'라고 읽으며 "Last-In-First-Out"이라는 단어에서 알 수 있듯이, "가장 나중에 들어간 자료가 가장 먼저 나온다."라는 뜻이다. 이를 다른 말로 후입선출(後入先出)이라고도 한다. Stack에서 자료의 추가 혹은 반환(꺼내는 것)은 스택의 끝에서만 가능하다. 여기서 말하는 Stack의 끝이란 스택의 제일 위(Top), 즉..

리스트는 자료를 순서대로 저장하는 자료구조를 말한다. 여기서 '순서'는 '한 줄로 서기'에서 '한 줄'을 말한다. 즉, 여러 개의 자료가 일직선으로 서로 연결된(Sequential) '선형 구조'를 의미한다. 여기서 C언어에서 제공하는 배열을 떠올릴 수도 있다. 실제로 배열이 리스트를 구현하는 가장 직관적이고 단순한 방법이며 이를 ArrayList라고 부른다. 그리고 포인터를 이용한 방법이 있다. 포인터를 이용한 방법은 Node라는 특별한 자료구조를 이용하여 저장할 Data와 다음 Node를 가리키는 Link를 가지며 LinkedList라고 부른다. ArrayList ArrayList는 배열로 List를 구현한 형태를 말한다. 배열에서 리스트 자료구조를 구현할 때 몇 가지 고려해야 할 사항이 있다. 예를..

배열(Array)은 같은 자료형의 데이터를 메모리상에서 연속적으로 저장하는 자료형을 말한다. 이러한 연속된 각각의 값을 배열의 원소(Element)라고 한다. 위 그림은 int 자료형 원소가 4개 연속해 이어져 있는 1차원 배열을 나타내고 있다. int 자료형이기 때문에 자료 1개당 크기는 4바이트이다. 이제 이러한 배열의 이름을 key라고 하였을 때 C소스로 정의하면 다음과 같다. int key[4]; 위 C소스는 key라는 이름을 가지며 4개의 int자료형 원소를 가지는 배열을 정의하는 소스이다. 배열의 위치 인덱스는 0부터 시작이 되며 차례대로 key[0], key[1], key[2], key[3]이 된다. 배열의 원소의 개수가 4개이면 마지막 인덱스는 3이 되어 마지막 원소가 key[3]이다. 위..

컴퓨터 프로그램은 크게 2가지 공통점이 있다. 1. 컴퓨터에 의해서 실행되는 명령어들의 집합이다. 2. 명령을 수행하기 위해 내부적으로 여러 자료(Data, 데이터)를 저장한다. 즉, 프로그램은 내부적으로 자료(데이터)를 저장하고 이를 처리하기 위한 명령어들의 집합을 가지고 있다. 자료구조 자료구조는 컴퓨터에 자료(데이터)를 효율적으로 저장하는 방식을 말한다. 효율적인 자료구조는 컴퓨터메모리를 절약(Space Complexity)할 뿐아니라, 프로그램 수행 시간을 최소화(Time Complexity) 할 수 있다. 컴퓨터 명령 자체의 효율성을 증가시키기 위한 절차를 알고리즘이라고 하는데 효율적인 알고리즘이 가능하기 위해서는 먼저 효율적인 자료구조가 선행되어야한다. 자료구조의 설계는 보통 프로그램이 어떻게..