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를 포함하..

람다 표현식(lambda expression) 이란? 람다 표현식(lambda expression)은 C++11 부터 지원하는 문법으로, 익명의 함수를 호출할 수 있는 기능을 지원한다. 알아둔다면 매우 편리한 기능이다. 람다 표현식의 기본형태 람다식은 위 그림과 같이 캡쳐, 인자, 반환 타입, 람다 본문 이렇게 네가지로 구성된다. [ ] ( ) -> typename { } 와 같은 형식이다. #inclㅕde #include using namespace std; void abssort(int* x, unsigned n) { sort(x, x + n, // 람다 시작 [](int a, int b) { return (abs(a) < abs(b)); } // 람다 끝 ); } 위의 코드와 같이 사용될 수 있다...

선택트리는 승자트리(Winner Tree)와 패자트리(Loser Tree)로 구분된다. 승자트리 (Winner Tree) n개의 외부 노드(external node)와 n-1개의 내부 노드(internal node)를 가지는 완전 이진 트리(Complete Binary Tree) 이다. 외부 노드는 토너먼트의 플레이어라고 생각하면되고 내부 노드는 플레어이 간의 경기라고 생각하면 된다. 가장 작은 수가 우승한다. 이 트리의 루트는 최종 승자이다. 승자트리를 이용한 정렬 n개의 수를 정렬하려고 할때, Winner Tree를 가장 작은 수가 우승하는 트리라고 정하면, n개의 수를 트리의 외부 노드레 넣고 승자를 찾는다. 정렬된 숫자들을 넣은 배열을 sortedArr이라 한다면, 승자는 가장 작은수 이므로 승자..

이진탐색트리(Binary Search Tree) 란? 이진탐색트리의 정의는 다음과 같다. 이진트리(Binary Tree)이다. 각 노드는 (key, value)쌍을 가지고 있다. 임의의 노드 x에 대해서 x의 왼쪽 서브트리에 있는 노드들의 key는 모두 x보다 작고 오른쪽 서브트리에 있는 노드들의 key는 모두 x보다 크다. 이진탐색트리의 연산 이진탐색트리는 탐색, 삽입, 수정, 삭제의 연산을 가진다. IsEmpty() Get(key) -> 탐색 Insert(key, value) -> 삽입, 수정 Delete(key) -> 삭제 Get : 탐색 시간복잡도: O(n) (n은 Tree의 원소수) T Get(T item) { TreeNode ptr; ptr = root; while(ptr != null) { ..