자료구조

1. 연결리스트와 배열의 차이점 연결리스트와 배열의 차이점에 대해 알기 전에 먼저 자료구조가 무엇인지부터 우리가 알아야 합니다. C언어나 C++같은 C언어 계열 언어를 접할 때, 빠질 수 없는게 자료구조입니다. 자료구조는 어떠한 방대한 데이터를 다룰 때 데이터를 정렬

1. 양방향 연결리스트

연결리스트에서 단방향과 양방향 2개를 배웠습니다. 원형은 이 둘과는 종류가 다르지만, 원형 역시 탐색을 좀 더 수월하게 하기위해서 사용하는 자료구조입니다. 원형은 말 그대로 Node의 Head와 Tail을 이어서 원처럼 만든 것입니다. 위 그림처럼 단순 연결리스트에서

지금까지는 연결리스트와 배열과 같은 구조만 배웠습니다. 이제 이것을 응용한 여러가지 자료구조들을 소개해볼까 합니다. 먼저 자료구조에는 크게 선형 자료구조와 비선형 자료구조가 있습니다. 선형 자료구조에는 Stack, Queue등이 있고, 비선형 자료구조에는 Tree, G

Stack을 배열로 구현했을 때의 장점과 연결리스트로 구현했을 때의 장점은 배열과 연결리스트의 장점과 매우 유사합니다. 따라서 진짜 데이터에 따라 자유롭게 구현하시면 됩니다.먼저 헤더파일부터 바로 보겠습니다.LinkedListStack.h연결리스트의 종류는 단방향, 양

Stack은 활용도가 많은 편은 아닙니다. 하지만 Stack이라는 자료구조로 만들 수 있는것은 엄청나게 많습니다. 그 중 사칙 연산 계산기를 만들어볼까 합니다. 공학용 계산기같은 계산은 못합니다.사칙 연산 계산기를 만들기 전에 먼저 수식표기법에 대해 알아야 합니다. 수

Queue라는 자료구조는 Stack과 비슷한 구조를 이루는 자료구조입니다. Stack이 LIFO(Last In First Out, 후입선출)이었다면, Queue는 FIFO(First In First Out, 선입선출)입니다. Queue는 터널같은 모양으로 생각하면 쉽습

Queue는 연결리스트로 구현하기가 아주 용이합니다. 배열로 구현했을 때 보다 장점이 되게 많습니다. Enqueue와 Dequeue가 배열 못지않게 빠릅니다. 거기다가 메모리도 배열보다 효율적으로 사용합니다. 따라서 많은 사람들은 Queue를 연결리스트로 구현하는 것을

트리는 대표적인 비선형구조입니다. 구현했을 때, 가장 적합한 모습이 나무 모양이라서, 이름이 트리입니다. 트리에는 각 노드마다 역할과 이름이 있습니다. 지금부터 간단하게 그 이름만 짚고 넘어가겠습니다.부모노드와 자식노드는 서로가 있어야 생기는 관계입니다. 부모노드는 자

Binary Tree 보통 이진트리라고 부르는 이 트리는 자식노드를 최대 2개까지만 가질 수 있는 트리입니다. 예를 들어, n개의 노드를 가진 이진트리는 n-1의 간선을 가집니다. 높이가 h인 이진트리는 최소 h(높이)개의 노드를 가지며, 최대 2의 h승 -1개의 노드

이진트리로 만들 수 있는 대표적인 것중에 하나가 수식트리입니다. 수식트리는 우리가 앞에서 했던 Stack을 이용해 사칙연산을 계산했던 것과 같이 트리를 이용해 사칙연산을 계산하는 것입니다. 단말노드가 모두 숫자로 이루어져있고, 단말노드를 제외한 노드들은 전부 수식으로

분리 집합은 서로소 집합이라고도 합니다. 용어의 의미처럼 분리 집합은 다음과 같은 특징을 가집니다. 전체집합 U에 대해, U의 분리 집합 A, B는 다음 조건을 만족합니다.A, B는 U의 부분집합입니다.A, B는 공통 원소를 가지지 않습니다.A, B의 합집합이 곧 전체