C++

[C++] 범위 (Scope)

블록 범위 (Block Scope) 객체의 잠재적인 범위는 블록내 선언 된 지점에서 시작하여 블록의 끝에서 끝난다. 중첩된 블럭내 상위 블럭에서 선언 된 것과 동일한 이름으로 선언하는 경우 상위에서 선언 된 것은 무시되고 블럭내 선언 된 것이 사용된다. 이런 방법은 지양해야 하며 다른 이름을 사용한다. int main() { int a = 0; // scope of the first 'a' begins ++a; // the name 'a' is in scope and refers to the first 'a' { int a = 1; // scope of the second 'a' begins // scope of the first 'a' is interrupted a = 42; // 'a' is in s..

[LeetCode] Length of Last Word

매커니즘은 간단하다, 빈 공간을 찾아 위치를 갱신 해주기만 하면 된다. int lengthOfLastWord(string s) { auto start = s.begin(), end = s.end(); string tmp; for (; start != end; start++) { if (*start == ' ') { bool flag = false; for (auto sPos = start; sPos != s.end(); sPos++) { flag = (*sPos == ' '); if (!flag) { tmp = ""; start = sPos; break; } } } if (*start != ' ') tmp += *start; } return tmp.length(); }

[C++] string 타입 문자열을 Split (분할)하기

Java에서는 문자열을 특정 구분자를 이용하여 여러 부분으로 나누는 함수 split을 제공한다. 또한 C의 경우 strtok라는 함수를 이용하여 char배열 형태의 문자열을 구분자를 기준으로 나눌 수 있다. 그러나 strtok의 경우 string타입의 문자열은 지원하지 않는다. C++에서는 istringstream이라는 문자열에서 작동하는 스트림 클래스가 있다. 이는 sstream이라는 C++ 표준 라이브러리를 추가해주어야 사용가능하다. istringstream는 istream을 상속받기 때문에 getline함수를 사용할 수 있다. getline 함수 : istream& getline(istream& is, string& str, char delim); getline함수를 이용하여 구분자별로 잘라서 ve..

[C++] Radix Sort (기수 정렬)

기수정렬은 정말 신기하게도 비교를 하지 않고 정렬을 하는 방법이기에 시간 복잡도가 O(n)이다. 구체적인 정렬 법을 알기 전에 이름인 '기수'가 뭔지 부터 알아보자. 여기서 '기수'라는 것은 '자릿수'를 의미한다. 자릿수로 뭘 어떻게 하는 것일까?? 방법은 다음과 같다. 1. 1의 자릿수를 보면서 각각의 버킷에 알맞게 담아준다. 버킷에서 순차적으로 뺀다면 1의 자릿수에 맞게 정렬이된다. 2. 1)에 의해서 정렬된 배열에서, 10의 자릿수를 비교해서 버킷에 담고 순차적으로 빼준다. 3. 2)에 의해서 정렬된 배열에서, 100의 자릿수를 비교해서 버킷에 담고 순차적으로 빼준다. 4. 최대 자릿수까지 계속해서 반복한다.. 구체적인 과정을 알아보자. 먼저 최대자릿수 까지 위의 과정을 반복해야 하므로 우리는 최대..

[C++] Trie (트라이) 소스코드

trie.h #ifndef TRIE_H #define TRIE_H #include #include #include #include #include #include #include #include #include namespace trie { struct SetCounter { }; namespace detail { template struct TrieNode : public PrefixHolderT { private: typedef TrieNode self_type; typedef self_type * self_pointer; self_pointer * data = nullptr; uint32_t size = 0; /* Will still be 64 bit due to alignment */ public..

[C++] Trie (트라이) 개념과 구현방법

트라이는 "문자열을 빠르게 탐색하게 해주는 자료구조" 이다. 즉, '문자열'을 관리하는 방법 중의 하나다 작동 원리 트라이는 주어진 문자열을 이루고 있는 문자를 앞에서 부터 하나씩 노드를 생성해가면서 만들어 진다. 이 과정에서 반복된 재귀 호출이 이루어지는데, 말로는 무슨 말인지 모르겠으니, 이 과정을 구체적으로 알아보자. 먼저, 문자열을 트라이로 생성하는 과정부터 알아보자. 간단하게 순서를 붙여보자면 다음과 같이 진행된다. ( 지금부터 '루트(Root)' 라는 말이 나올 수 있는데, 이는 가장 초기 노드라 생각하면 된다. 즉, 연결되어 있는 어떠한 노드도 없는 초기 노드이다. ) 1. 주어진 문자열에서 현재 문자를 가져온다. 2. 현재 문자로 이루어진 노드가 존재한다면, 그 노드로 그 다음 문자열을 탐..

[실1] 3019 - 테트리스

#include #include #include #include #include #include #include using namespace std; using ll = long long; #pragma region 상하좌우 / 위치 const pair dir[] { { 1, 0 }, { -1, 0 }, { 0, -1 }, { 0, 1 }, }; #define _y first #define _x second #pragma endregion #pragma region 빠른 입출력 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion const map blocks { ..

[C++] const map 객체에 [key] 접근시 에러

map 클래스의 객체 a가 있고 이 객체가 const 화 되고 b라는 변수로 reference 됐다고 해보자. b에 대한 value 를 접근함에 있어 b["key"] 이런식으로 접근하면 에러가 난다. 내용은 error : passing '~' as 'this' argument discards qualifiers 이하 생략. 이유는 const 화 된 map 객체에 ["key"]로 접근하면 그 값을 수정할 여지가 발생하기 때문이다. value를 접근하는 다른 방법이 있다. 바로 .at를 쓰면 된다 b.at("key") 이렇게 접근하면 에러 없이 const화 된 map 객체의 value에 접근 가능하게된다. #include #include #include #include using namespace std; ..

[C++] vector resize 시 주의할 점

기존보다 더 작게 할당하게 될 경우 만약 1 라는 값을 5 개 가진 벡터를 3 의 크기로 resizing 하며 2 로 채운다면 #include #include using namespace std; void Print_Vec(const vector vec) { for (auto const &it : vec) { cout

[LeetCode] 17 - Letter Combinations of a Phone Number

class Solution { map digitComb { {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"} }; vector res; string digits; public: void DFS(int i = 0, string curStr = "") { if (curStr.size() == digits.size()) { res.push_back(curStr); return; } for (auto& c : digitComb[digits[i]]) DFS(i + 1, curStr + c); } vector letterCombinations(string digit..