codingfarm

일반적으로 (A+B)*(C+D) 와 같은 연산 표기법을 중위표기법 이라 한다. 이런 표기법은 사람은 읽기 쉽지만 컴퓨터는 해석이 난감하다는 단점을 가지고 있다. 컴퓨터가 해석하기에 최적인 표기법으로 후위표기법이 있다. 중위표기법을 후위표기법으로 바꾸는 알고리즘은 아래와 같다. 1. 피연산자가 나오면 출력한다. 2. 연산자가 나올경우... 스택 최상단 연산자의 우선순위가 현재 연산자의 우선순위보다 낮아질때까지 혹은 스택이 빌때 까지 pop 하면서 출력, 이후에 현재 연산자를 push 3.여는괄호일 경우 스택에 push 4. 닫는괄호일 경우 스택내에 첫번째 여는 괄호가 나올때 까지 stack을 pop 하면서 출력(괄호는 출력X) 위 알고리즘을 적용한 코드는 아래와 같다. 1 2 3 4 5 6 7 8 9 10..

github.com/tony9402/baekjoon/tree/main/graph_traversal

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 #include #include #include using namespace std; // ex) 2016-09-15 20:59:57.421 0.351s // 2016-09-15 20:59:58.299 8 void StrTok(string& org, vector& ret, const string& delims) { ret.clear(); string new_str; for (int index = 0; index

어휘력이 모자라서 충돌 이외의 적절한 말을 모르겠다. 임의의 범위를 가진 데이터들이 주어질때, 특정 데이터의 범위와 겹치치는 것들을 필터링 하는 방법에 대해서 정리해보았다. 1 : 1 1:1 대응을 검사하는 방법은 간단하다. 가령 [al, ar], [bl, br] 과 같은 범위를 가지는 데이터가 주어젔을 때, 해당 데이터가 서로 겹처지는지 확인하는 방법은 아래와 같다. $$al \leq br \; \& \& \; bl \leq ar $$ 위 조건이 만족된다면 해당 데이터는 겹처지는 것이다. 참고로 겹처지지 않을 조건은 아래와 같다 $$al > br \; || \; bl > ar $$ 1 : N 그렇다면, 하나의 데이터가 주어질때 여러 데이터들과의 충돌 여부를 판정하는 방법은 무엇일까? 하나하나 대응하면서..

[0, 1, 2, 3, 3, 3, 4, 5, 6, 7, 8, 9] 위 처럼 정렬된 데이터가 있을때, 특정 값을 기준으로 그 보다 낮거나 높은 값들의 갯수를 구하고 싶다. 가령 3보다 낮은 값은 [0, 1, 2] 3개이며, 높은 값은 [4, 5, 6, 7, 8, 9] 6개이다. 이를 구하는 방법은 아래와 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include #include #include using namespace std; int main(void) { vector vi = { 0, 1,2,3,3,3, 4,5,6,7,8,9 }; vector::iterator it; it = lower_bound(vi.begin(), vi.end(), 3); cout

다익스트라 shnoh.tistory.com/15 예제 codingfarm.tistory.com/300 codingfarm.tistory.com/301 BFS와 유사한 형태지만, BFS는 이미 지나간 노드는 새로운 진입을 철저히 막는 반면 다익스트라는 새로 들어온 진입으로의 경로가 기존의 값보다 더 낫다면 새로운 진입이 가능해진다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 #include #include #define INF 2000000000 usi..

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816..

문자열 검색에서 매우 빠른 성능을 보이는 알고리즘 여러 기업에서 난이도 있는 문제의 주제로 자주 출제되는 추세이다. 가령 to, tea, ted, ten, a, inn 6개의 단어에 대해 trie 알고리즘을 적용했을 때 트리의 구조는 아래와 같다. 트라이 노드의 내부 구조는 단순하다. 자신과 같은 타입의 노드를 자식노드라 가지며 새로운 단어를 추가하거나 초기화 하기 위해선 해당 함수를 재귀적으로 호출하면 된다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59..

배열내에 임의의 숫자들이 정렬되어 저장되있다. 또한 임의의 수가 2개 주어진다 할때 배열내에서 2개의 수 사이에 있는 성분들의 갯수는 몇개일까? 이것 문제를 해결하기 위한 이상적인 방법은 이진탐색을 이용하는 것이다. 2개의 임의의 수 중에 작은수를 기준으로 lower_bound, 큰수를 기준으로 upper_bound를 해서 나온 2개 요소의 위치를 빼주면 구간길이를 구할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 // Example program #include #include #include #include using namespace std; int main() { vector vi; for(int i=0; i

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816..

낮은 key 값 우선 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 #include using namespace std; class HeapNode { public: int..

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106#include#include using namespace std; vector tree; //tree[i] : i 번 노드가 가지는 자식들의 목록vector par; //par[node][i] : node의 2^i 번째 부모의 번호, par[node][i] = par[par[node][i-1]][i-1]vector depths; //..

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091//https://www.acmicpc.net/problem/1197 #include#include#include using namespace std; class Edge {public: int from, to, weight; Edge(int from_, int to_, int weight_) : from(from_), to(to_), weight(weight_) {} Edge() : Edge(-1,..

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include#include using namespace std; vector union_set;vector union_level; int UnionFind(int index) { if (union_set[index] != -1) { union_set[index] = UnionFind(union_set[index]); return union_set[index]; } else return index;} void UnionMerge(int a, int b) { a = UnionFind(a); b = UnionF..

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include using namespace std; class Node {public: int key, value;}; Node tmp[100]; void MergeSort(Node* arr, int start, int end) { if (start >= end) return; int mid = (end - start) / 2 + start; MergeSort(arr, start, mid); MergeSort(arr, mid + 1, end); //PartSort(arr, start, end, mid); int i = s..

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150#include using namespace std; class ListNode {public: in..

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134#include using namespace std; class ListNode {public: int value; ListNode* pPrev, * pNext; ListNode() { ..

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include using namespace std; class VectorNode {public: int value, key;}; class Vector {public: int cnt, reserved; VectorNode *nodes; void Resize() { reserved *= 2; VectorNode *tmp = new VectorNode[reserved]; for (int i = 0; i = reserved) Resize(); nodes[cnt].key = key; no..

세그먼트 트리는 배열의 구간합을 더 효율적으로 구하기 위한 알고리즘이다. 가령 임의의 배열이 주어질때 위 배열에서 길이 n만큼의 구간을 다 구하는데 걸리는 시간 복잡도는 $O(n)$ 이다. 하지만 매번 구간의 합을 구할때마다 해당길이 만큼 계속해서 반복하는것은 시간낭비이다. 더 효율적인 방법은 없을까? 임의의 배열 S가 주어질때 S[i]는 arr[0] ~ arr[i] 에 있는 모든 원소들의 합과 같다. 만약 $a \sim b$까지의 구간에 있는 원소들의 합을 구해야 한다면? S[b]-S[a-1] 을 통해 구간의 합을 $O(1)$의 상수 시간만에 구할 수 있다. 하지만 이 방법은 배열 요소의 값이 변한다면 값을 수정하기가 굉장히 번거로워진다. 가령 a[i]의 값이 변한다면 S[i] 이후의 값들을 모두 수정..