1. map1-1. map 기본 개념key와 value 쌍으로 이루어져 있으며, key를 통해 value값에 O(1)에 접근할 수 있는 자료구조검색, 삽입, 삭제가 평균적으로 O(logN)의 복잡도를 가진다.내부 구현은 레드-블랙 트리로 되어있다.1-2. 레드 블랙 트리레드 블랙 트리는 이진 탐색 트리의 일종인데, 치우치는 값이 들어온 경우(편향된 경우) 를 방지하기 위해 트리의 높이를 logN으로 유지해주는 개선된 이진 탐색 트리이다. 편향된 트리의 경우 탐색 시간이 길어져, O(logN) 복잡도가 불가능해진다.왜냐하면, 이진 탐색 트리가 기본적으로 선택한 노드를 기반으로 왼쪽은 작은 값 오른쪽은 큰 값으로 이루어져 있어서 값을 반씩 쪼개면서 찾기 때문에 빠른 탐색 O(logN) 을 할 수 있는데편향된..

코딩테스트를 풀다가 unordered_map을 key로 순환하는 방법을 생각하다가 새로운 방식을 알게 되어서 정리하게 되었다. 1. range-based for 사용for (const pair& pair : um){ cout  2. iterator 사용for (unordered_map::iterator it = um.begin(); it != um.end(); ++it){ cout first second  3. C++17 이후 range-based for새롭게 알게된 방식(visual studio에서는 C++언어 표준을 C++17 로 해야 사용할 수 있었다.)//c++17for (auto& [key, value] : um){ cout

코딩테스트 문제를 풀다가 해당 알고리즘들이 떠올라서, 정리해보기로 하였다.1. 허프만 코딩허프만 코딩이란데이터 압축 알고리즘 중 하나인데, 문자의 등장 빈도를 기준으로 인코딩 하는 기술이다.간단히 과정을 설명하자면, 우선순위 큐를 이용하여 문자를 빈도에 따라 정렬하고최소 빈도의 두 노드를 합쳐 새로운 노드를 구성하는 방식을 반복하게 된다.가장 이해하기 쉬운 그림을 가져오면, 아래와 유사하다아래 그림에서 각 숫자는 빈도수를 뜻한다.빈도수대로 정렬한 후, 최소 빈도의 수를 더하는 과정을 반복하는 모습을 볼 수 있다.간단한 예시 문제를 풀어보자 (백준 1715 https://www.acmicpc.net/problem/1715)이 문제의 알고리즘 분류가 우선순위큐와 그리디 알고리즘이다. 즉 허프만 코딩이 우선순..

문제 풀다가 접하게 된 string 처리 관련 함수를 정리해 보았다.참고한 자료는https://modoocode.com/275 C++ 레퍼런스 - transform 함수모두의 코드 C++ 레퍼런스 - transform 함수 작성일 : 2019-04-19 이 글은 21195 번 읽혔습니다. std::transform 은 범위 내 (first 부터 last 전 까지) 원소들 각각에 대해 인자로 전달한 함수를 실행 한 후, 그 결modoocode.comhttps://en.cppreference.com/w/ cppreference.comNull-terminated strings:    byte  −   multibyte  −   wideen.cppreference.com그리고 chat gpt이다. 1. tolo..

수업을 듣던 도중 substr 함수를 접하게 되어서, 이번 기회에 잘 기억해 보고자 다시 정리를 해보았다.아래의 자료를 참고해서 정리해 보았다.https://en.cppreference.com/w/cpp/string/basic_string/substr::substr - cppreference.com" data-og-description="(1) basic_string substr( size_type pos = 0, size_type count = npos ) const; (until C++23) (constexpr since C++20) constexpr basic_string     substr( size_type pos = 0, size_type count = npos ) const&; (since ..

https://school.programmers.co.kr/learn/courses/30/lessons/148653 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr이 문제를 보고 어떻게 풀어야 좋을지를 생각하던 도중, 관련된 다른 문제들이 생각나서 정리를 해보게 되었다.1. BFS bfs문제는 대부분 2차원 격차에서 길을 찾는 문제를 풀 때 많이 사용했을 것이다.그러나 다음과 같은 문제에서도 사용할 수 있다. (백준 1697 숨바꼭질: https://www.acmicpc.net/problem/1697) 해당 문제에 대해 해설을 해보자면,board라는 배열은 현재 자리(배열에 index에 해당하는) 에 올..

1. std::vector1. 2차원 벡터 선언방식vector> vec;vector> vec(10);vector vec[10];첫번째 방식첫번째 방식은 가장 기본적인 방식으로 push_back() 연산을 통해서만 가능처음에 빈 vector에 값을 대입하는 경우에 [ ] 연산자를 통해 대입이 불가능하다. (vector out of range)예시 코드#include #include using namespace std;int main(){ vector> vec; vector temp1 = { 1,2,3,4,5,6,7,8,9,10 }; vector temp2 = { 1,1,1,1,1,1,1,1,1,1 }; //vec[0] = temp1; 불가능 vec.push_back(temp1); vec.push_back..