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

동적배열에 대한 자세한 설명은 해당 포스트를 참고해주시기 바랍니다. [자료구조] 배열, 연결리스트 선형 자료구조란? 선형 자료구조란, 자료를 순차적으로 나열한 형태의 자료구조를 말한다. 대표적으로 배열, 연결 리스트(Linked List), 스택, 큐등이 있으며 하나의 자료가 있으면 그 뒤에 다른 하 currygamedev.tistory.com stl에서 제공하는 동적배열 자료구조인 vector의 기능 중 조회, 삽입/삭제, 맨뒤에 삽입, 초기화를 구현해 보았다. 🔻전체코드 template class Vector { public: Vector() { } ~Vector() { if (_data) delete[] _data; } void insert(int pos, const T& data) { if (_s..

선형 자료구조란? 선형 자료구조란, 자료를 순차적으로 나열한 형태의 자료구조를 말한다. 대표적으로 배열, 연결 리스트(Linked List), 스택, 큐등이 있으며 하나의 자료가 있으면 그 뒤에 다른 하나의 자료가 존재하는 구조이다. 이에 반대되는 개념으로 비선형자료구조가 있는데, 비선형자료구조란 말그래도 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태라고 볼수 있다. 이에 대한 예시로는 트리, 그래프가 대표적이다. 이번 글에서는 선형자료 중, 배열과 연결 리스트에 대해서 알아보도록 하겠다. 정적 배열 (Static array) 맨 처음 선언 시, 해당 배열의 크기를 지정하고, 한번 지정된 크기는 절대 변경할 수 없다 배열에 저장된 자료들은 메모리 상에서 연속적으로 위치한다. 임의 접근(Random A..

🔻그래프 탐색 알고리즘 이번에는 그래프를 탐색하는 알고리즘에 대하여 다루어 볼 것이다. 그래프 탐색 알고리즘이란 한 정점에서 시작하여 차례대로 그래프에 있는 모든 정점들은 한번씩 방문하는 알고리즘을 뜻한다. 많은 그래프에 대한 문제를 해결하기 위해서 그래프 탐색 알고리즘을 알아야하는데 예를들어 다음과 같은 상황에서 탐색이 필요하다. 한 정점과 다른 정점의 경로를 구할 때 그래프가 연결되어 있는지 확인할 때 신장 트리(Spanning Tree)를 찾을 때 그래프를 탐색하는 알고리즘은 굉장히 중요한 알고리즘이라고 들었다. 알고리즘 사이트인 프로그래머스에서 보았을 때도 그래프 탐색이 출제 빈도수도 높고 정답률이 낮게 나온다. 대표적으로 깊이 우선 탐색(Depth-First Search)과 너비 우선 탐색(Br..

신장 트리(Spanning Tree) 한 그래프의 부분 그래프이며, 그래프에서 모든 정점을 포함한다. 정점 간 서로 연결이 되어있어야 한다. 사이클이 존재하지 않는다. 그래프에서 신장트리는 1개가 아닌 다수일 수 있다. 신장트리는 트리이다. 원래 그래프에서 n개의 정점을 가지고 있었다면, 신장 트리는 n개의 정점과 n-1개의 간선을 가진다. 그래프 자료구조에 대한 자세한 설명은 아래 링크에 기술되어 있다. 그래프(Graph) 그래프(Graph)란? 그래프란 정점(Vertex)과 그 사이를 잇는 간선(Edge)로 이루어져 있다. 즉 정점들 사이의 관계를 나타내는 자료구조이다. G = (V,E)의 형식으로 정의하는데 여기서 V는 정점, E는 간선을 currygamedev.tistory.com 최소 비용 신장..

서로소 집합(Disjoint Set) 서로 중복 포함된 원소가 없는 집합(= 교집합이 없는 집합)들을 표현하는 자료구조이다. Union(합집합), Find(집합 탐색) 연산이 가능하다. 집합에 속한 하나의 특정 원소를 대표자라고 하며 이를 통하여 집합들을 구분할 수 있다. 이 자료구조를 Array혹은 List로 구현했을 경우 최선의 시간복잡도가 O(n + u*log(u) + f)이다. (u와 f는 각각 Union과 Find연산이 실행된 횟수이다.) 하지만 이를 Tree로 구현할 경우 시간복잡도는 O(n + f)에 근접해진다. {2, 4, 5, 9, 11, 13, 30}의 원소를 가지는 집합을 트리로 표현한다면 위와 같이 다양한 모양으로 나올 수 있다. Find 연산 Find(i)를 하게 되면 i를 포함하..