🔻이진 트리(Binary Tree) 먼저 힙에 대해 알아보기전에 이진트리에 대해서 간단히 알아보도록 하겠다. 왜냐하면 힙이 이진 트리로 구현되는 자료구조이기 때문이다. 이진 트리란 한 노드가 최대 두개의 노드를 자식으로 가질 수 있는 트리이다. 그 중에서도, 마지막 레벨을 제외한 모든 레벨에는 노드들이 가득차있고, 마지막 레벨의 노드들도 좌측부터 순서로 들어가있는 형태의 이진 트리를 완전 이진 트리 라고한다. 이 완전이진트리는 이러한 구조적 특징때문에 노드의 개수를 알면 트리의 구조를 특정할 수 있다는 성질이 있다. 또 이러한 성질 때문에 아래와 같은 성질을 가지고 있다. 현재 노드 번호를 i라 할때, ◾ 현재 노드의 perent node의 번호 = (i - 1) / 2 ◾ 현재 노드의 left chil..

🔻트리(Tree) 트리(Tree)는 스택이나 큐와는 달리 비선형 자료구조이다. 노드들의 계층적 관계를 표현한다. 또한 트리안에 서브트리가 있고, 그 서브트리 안에또 서브트리가 있는 재귀적 자료구조이다. 넓게 살펴보면 그래프의 한 종류라고 할 수 있다. 위 그림처럼 노드들이 마치 나무 가지처럼 연결되어 있어서 트리라는 이름이 붙혀진 것 같다. 트리는 활용되는 범위가 무궁무진하다. 추후에 포스팅할 힙(Heap)도 트리를 이용한 자료구조이고, 용도에 맞게 트리에서 파생된 자료구조나 알고리즘이 많다. 기본적인 트리만 보면 굉장히 간단한 자료구조지만 깊게 파고들면 들수록 어려운 자료구조인 것 같다. 따라서 트리의 기본적인 요소들을 정리해보는 시간을 가지면 이후에 나올 자료구조나 알고리즘을 쉽게 익힐 수 있을 것이..

🔻다익스트라 알고리즘(Dijikstra's Algorithm) 다익스트라 알고리즘이란 가중치 그래프에서 한 정점으로부터 모든 정점의 최단거리를 구하는 알고리즘이다. 다익스트라의 경우 가중치에 음수가 존재하면 안된다는 제약사항이 존재한다. 🔶다익스트라 알고리즘의 원리 다익스트라 알고리즘의 기본적인 원리는 굉장히 간단하다. 두가지 작업을 모든 정점을 모두 방문할 때까지 반복하는 것이다. 1. 방문하지 않은 정점 중 가장 cost가 작은 정점을 방문한다. 2. 해당 정점과 연결된 정정들 중에서 거리가 이전에 기록한 값보다 작다면 값을 갱신한다 이 두작업을 무한 반복하는 것인데, 글로만 보면 무슨 말인지 이해하기 힘들 수 있으니 그림을 통해 알아보자. 6개의 정점이 있고 각 정점사이의 cost가 그림과 같은 그..

🔻그래프(Graph)란? 그래프는 정점(Vertex)과 그 사이를 잇는 간선(Edge)로 이루어져 있다. 즉 정점들 사이의 관계를 나타내는 자료구조이다. G = (V,E)의 형식으로 정의하는데 여기서 V는 정점, E는 간선을 의미한다. 그래프의 대표적인 예시는 지하철 노선도를 들 수 있을 것 이다. 지하철 역과 그 사이의 노선을 표현하는 지하철 노선도는 대표적인 그래프의 예시라고 할 수 있다. 🔸그래프의 종류 무방향 그래프(Undirected graph) 간선에 방향성이 포함되어 있지 않은 그래프이다. 그림에서 A와 B를 연결하는 간선을 (A, B)라고 하면, (A,B)와 (B,A)는 서로 같은 간선이다. 정점이 n개라할때 무방향 그래프가 가질 수 있는 최대의 간선 개수는 n(n-1)/2개 이다. 방향 ..

이번 글에서는 선형적 자료구조 중 스택(Stack)과 큐(Queue)에 대해서 살펴보도록 하겠다. 스택과 큐의 특징에 대해 알아보고, 직접 구현까지 해보도록 하겠다. 🔻스택(Stack) 스택(Stack)은 LIFO(Last-In-First-Out, 후입선출)의 특징을 가진 자료구조이다. LIFO란, 가장 먼저들어온 것이 가장 늦게나가는 방식이다. 위와 같이, 1,2,3순서대로 들어갔지만, 나올때는 3,2,1순서로 나오는 것을 LIFO방식이라고하고, 스택은 이러한 LIFO방식을 사용하는 자료구조이다. 즉, 스택에 가장 나중에 들어온 자료가 가장 먼저 삭제된다. 그러면 이러한 자료구조는 어디에 활용될 수 있을까? 우리가 에디터를 사용하여 글을 쓰다보면 잘못 썻을 때, Ctrl + Z를 사용해서 다시 이전으로..

연결리스트에 대한 자세한 설명은 해당 포스트를 참고해주시기 바랍니다. [자료구조] 배열, 연결리스트 선형 자료구조란? 선형 자료구조란, 자료를 순차적으로 나열한 형태의 자료구조를 말한다. 대표적으로 배열, 연결 리스트(Linked List), 스택, 큐등이 있으며 하나의 자료가 있으면 그 뒤에 다른 하 currygamedev.tistory.com STL에서 제공하는 연결리스트 자료구조인 list의 기능 중 push_back, pop_back을 구현하면서 연결리스트를 간단히 구현해보도록 하겠다. 여기서 노드를 삭제하거나, 삽입하는 기능을 추가하려면 연결리스트는 임의접근이 불가능하므로 iterator를 구현해야하는데 iterator까지 구현하면 볼륨이 너무 커질 것 같아서 생략하였다. 연결리스트는 노드를 다..