Do you believe in you?

문자열 문제에서 유용하게 쓸 정규표현식을 공부해보자. (http://sweeper.egloos.com/2999049 사이트를 참고해서 적었습니다.) · 헤더파일: · 관련 함수: 1) regex_match: 정규식이 전체 대상 문자열과 일치하는지 여부를 반환(bool) 2) regex_search: 문자열이 정규식과 매치되는 sub string을 포함하고 있는지 여부를 반환(bool) 3) regex_replace: 정규식 표현식을 replace 문자열로 교체한다. 교체된 전체 문자열을 반환한다.(string) 4) swap: 두 basic_regex 또는 match_results 개체를 교환 합니다.(string) · 상세 설명 1) std::regex_match 는 전체 문자열이 특정 규칙(패턴)을 ..

2차원 행열을 2차원 벡터를 활용해서 표현해보고, 그 값을 초기화해보자. vector visited_map(4, vector(3, false)); 뜻은 2차원 행열과 같은 역할을 하는 4 X 3 짜리 2차원 벡터를 생성과 동시에 false로 초기화한다는 말이다. 그럼 아래와 같은 데이터 공간이 만들어지게찌~ false false false false false false false false false false false false 참고로 1차원 벡터의 생성과 초기화는 다음 구문으로 표현할 수 있다. vector v(4,0); 뜻은 4열짜리 벡터를 만들고 0으로 초기화 해준다는 말~ 0 0 0 0 #2차원 벡터 동적할당 및 해제 방법! #include int main(){ //동적할당 생성 vector..

▶ 다익스트라(Dijkstra) 알고리즘이란? 다이나믹 프로그래밍(DP)를 활용한 최단 경로(Shortest Path) 탐색 알고리즘. 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 구현은 Greedy 알고리즘이나 DP 알고리즘을 사용하는데, Greedy 알고리즘을 사용할 수 있는 이유는 인접한 노드들 중 가장 작은 비용을 갖고 있는 노드를 선택하여 탐색을 진행하기 때문이다. DP 알고리즘을 활용할 수 있는 이유는 "최단 거리는 여러 개의 최단 거리들"로 이루어져있기 때문이다. (최단 거리 = 최단 거리 정보들의 합) 위의 그림은 a(1)와 b(5)사이의 최단 경로를 찾는 다익스트라 알고리즘의 흐름을 보여준다. 가장 낮은 값을 가진 방문하지 않은 꼭짓점을 선택하고, 방문하지 않은 각 인..

=> map과 unordered_map의 차이는 구현방식이다. map은 균형 이진트리(Red-black tree)로 구현되고, unordered_map(hash_map)은 hash 방식(hash table)으로 구현된다. 즉, map에 들어가는 element 들은 key에 따라 정렬되어 저장되고, unordered_map은 key의 hash값에 따라서 저장된다. => 데이터가 적은 경우는 map > unordered_map, 데이터가 많은 경우는 map < unordered_map 성능이 더 좋다. map의 데이터들은 정렬되어 저장되므로 O(logN)의 탐색 속도를 보장하고, key값으로 탐색하는 unordered_map의 경우 O(1)의 탐색속도를 갖기 때문이다. 참고로 map의 경우 데이터 추가, 삭..

* C++ sort함수란? : C++STL에서 제공하는 sort 알고리즘 - 헤더파일: - 구문: sort(start, end); //start부터 end개를 오름차순(default)로 정렬한다. - 내부는 Quick sort(퀵 정렬)로 구현되어 있다. 따라서 평균 시간 복잡도는 O(NlogN)을 가진다. 1) 함수 원형 template void sort(T start, T end); template void sort(T start, T end, Compare comp); : 3번째 인자 값(Compare comp)을 넣으면 오름차순, 내림차순 등으로 정렬할 수 있다. compare 함수는 true 인 경우를 기준으로 정렬한다. 2) 배열(array) 사용할 때 예시 sort(arr, arr+n); /..

▷ C++ Template이란? : int, double, long 등의 자료형에 구애받지 않고 공통된 함수를 만들어 놓고 사용하기 위해 정의해두는 것 ▷ C++ Document에서의 정의 #include template const T& min (const T& a, const T& b) ▷ 사용법 #include #include using namespace std; template T sum(T a, T b){ return a + b; } int main(){ cout