동적배열에 대한 자세한 설명은 해당 포스트를 참고해주시기 바랍니다. [자료구조] 배열, 연결리스트 선형 자료구조란? 선형 자료구조란, 자료를 순차적으로 나열한 형태의 자료구조를 말한다. 대표적으로 배열, 연결 리스트(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..

STL(Standard Template Library) 이란? STL이란 표준 템플릿 라이브러리(Standard Template Library)의 약자로써, C++에서 프로그래밍에 필요한 자료구조와 알고리즘을 Template의 형태로 제공하는 C++ 라이브러리이다. STL의 장단점 장점 일반화를 지원한다. 컴파일 타임 매커니즘을 이용하므로 실행 시 효율 저하가 적다. 사용자의 알고리즘을 적용시키는 등의 확장성이 우수하다. 소스코드의 길이가 대폭 감소된다. 단점 템플릿 기반이므로 함수, 클래스가 매번 구체화되어 코드가 비대해진다. 디버깅이 어렵다. STL의 구성 1. 컨테이너(Container) 자료를 저장하는 객체, 자료구조를 모아둔 집합이다. 순차 컨테이너 (Sequence Container) 자료를 ..

🔻그래프 탐색 알고리즘 이번에는 그래프를 탐색하는 알고리즘에 대하여 다루어 볼 것이다. 그래프 탐색 알고리즘이란 한 정점에서 시작하여 차례대로 그래프에 있는 모든 정점들은 한번씩 방문하는 알고리즘을 뜻한다. 많은 그래프에 대한 문제를 해결하기 위해서 그래프 탐색 알고리즘을 알아야하는데 예를들어 다음과 같은 상황에서 탐색이 필요하다. 한 정점과 다른 정점의 경로를 구할 때 그래프가 연결되어 있는지 확인할 때 신장 트리(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를 포함하..