전체 글
[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..
Debug - Release 차이
보통 C++로 코드 작성 후 결과물을 실행 파일로 만들기 위해서는 빌드 작업을 해야만 한다. 이때 Visual Studio와 같은 IDE에서는 Debug 또는 Release 빌드 모드를 선택할 수 있다. 이는 사실 C/C++ 컴파일러의 최적화 옵션의 차이인데, Visual Studio에서는 편의를 위해 빌드 모드를 분리해놓은 것이다. 현업에 종사하거나 숙련된 개발자는 당연히 이 차이를 알고 있겠지만, 주로 C/C++ 개발을 처음 접하는 분들, 특히 학생들은 Visual Studio 기본값인 'Debug'로 빌드해서 배포를 하는 경우가 종종 있다. 잘못된 빌드 모드로 배포할 경우 성능 저하가 발생하거나 프로그램 실행 불가 등의 문제로 상당히 고생할 수 있으므로 각 빌드별 특징을 잘 알고있어야 한다. 차이점..
[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..
Brute Force (브루트 포스) 알고리즘
개념 브루트 포스를 사전적 의미로 찾아본다면 아래와 같다. 브루트(Brute) : 무식한 + 포스(Force) : 힘 즉, 발생할 수 있는 모든 경우를 무식하게 탐색한다는 뜻이다. 전체를 탐색한다는 의미에서 전체 탐색, 완전 탐색이라고도 한다. 브루트 포스 알고리즘을 설계할 때는 해가 하나 이상 존재한다는 가정을 세우고 모든 범위를 탐색하기 때문에 무조건 정답을 찾을 수 있다. 장단점 장점) 알고리즘을 설계하고 구현하기 매우 쉽다. 복잡한 알고리즘 없이 빠르게 구현할 수 있다. 단점) 알고리즘의 실행 시간이 매우 오래 걸린다. 메모리 효율면에서 매우 비효율적이다. 종류 선형 구조) 순차 탐색 비선형 구조) 백트래킹, dfs, bfs 예시 만약 10자리 비밀번호 자물쇠가 있다고 가정해보자. 이 자물쇠를 풀..
[골4] 14500 - 테트로미노
#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 #define MAX 501 vector vis; vector ma..
[C++] 개인적인 (MST 알고리즘) 크루스칼 & 프림 구현
사용할 데이터는 다음과 같다. 결과) 17 1 2 2 2 6 7 3 2 3 3 6 8 4 3 5 4 2 3 4 1 1 5 1 4 5 4 9 공통으로 쓰여짐 // 간선 개수 const int edge = 9; struct sNode { public: int from = 0, to = 0, weight = 0; /*sNode() = default; sNode(int from, int to, int weight) : from(from), to(to), weight(weight) { }*/ bool operator(const sNode& ref) const { return weight > ref.weight; } bool operator==(const sNode& ref) const { return from =..