CEO

컴퓨터에서 괄호가 포함된 연산을 쉽게 처리하기 위해서는, 중위 표현식(Infix)보다 후위 표현식(Postfix)을 통해 계산하면 쉽게 처리할 수 있다. 이는 Stack을 통해 쉽게 구현할 수 있으며, 변환한 식을 계산하는 것은 어렵지 않다. Stack을 사용하여 구현 후위 표현식 변환 int priority(char c) { if (c == '(') return 0; else if (c == '+' || c == '-') return 1; // *, / 인 경우 return 2; } string changePostfix(string target) { stack s; string prefix; for (int i = 0; target[i]; i++) { if (target[i] == '(') s.push..

c++에서 문자열을 다루는 경우는 크게 부분문자열을 만드는 경우와 특정 구분문자(delimiter)를 기준으로 문자열을 나누는 경우이다. 어렵진 않지만, 모르면 삽질해야하니 정리해두고자 한다. substr #include #include using namespace std; string getSubStr(string s, int len) { string subStr; vector subStr; // 자를 길이 for (register int end = 1; end < len; end++) { // 자를 위치 for (register int start = 0; start < len; start++) { subStr.push_back(s.substr(start, end)); } } return subStr;..

Trie를 개념만 알고, 생각해보니 직접 구현해본 적이 없었다. 알고리즘 문제 풀이를 할 때, 요긴하게 사용하기 위한 목적으로 정리해보고자 한다. 다른 곳에서 검색할 수 있는 것과 같이 동적으로 할당하는 것이 아닌, 문제의 조건에 맞게 정적으로 Trie를 할당해두고, 사용하는 방식을 다루고자 한다. Trie? 트라이 (컴퓨팅) - 위키백과, 우리 모두의 백과사전 "A", "to", "tea", "ted", "ten", "i", "in", "inn"를 키로 둔 트라이. 이 예제에는 모든 자식 노드가 알파벳 순으로 왼쪽에서 오른쪽으로 정렬되어 있지는 않다. (루트 노드와 't' 노드) 트라이(trie)는 컴퓨터 ko.wikipedia.org Trie란 root를 기준으로 문자열을 저장할때, 각 노드에 어떤 ..

코딩 테스트 문제를 풀면서 PQ(Priority Queue)를 직접 구현하여야 할 경우가 있었다. 단순히 Parent, Left Child, Right Child의 인덱스만 아는 것이 아니고, push, pop, updaet, erase 모든 기능에 대해 어떤 식으로 동작하는지 간략히 정리해보고자 한다. PQ에 삽입할 데이터 struct Info { int idx; int score; } PQ에 삽입할 데이터는 일반 변수가 아닌, 사용자 지정 변수를 기반으로 정렬이 가능한 경우를 다루고자 한다. 위 구조체 처럼 score를 기준으로 정렬될 수 도 있고, 경우에 따라 다양한 우선순위에 따라 정렬시킬 수 있다. `idx`의 경우, PQ에 push, pop을 할 때는 필요하지 않지만, PQ에 update, e..