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..

programmers.co.kr/learn/courses/30/lessons/42577# 위 문제를 잘못 이해하고 풀었다. 특정 문자열이 주어질때, 앞자리가 같은 문자열이 존재하면 false 없으면 true를 반환해야한다. 가령 123456 123789 위 2개의 숫자는 앞자리 123이 일치하므로 false를 반환해야한다. 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 ..

배열내에 임의의 숫자들이 정렬되어 저장되있다. 또한 임의의 수가 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

www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주�� www.acmicpc.net 상하좌우 이동을 통해 각 칸으로 이동하면 해당 칸에 배정된 점수를 얻게된다. 이때 오른쪽 아래까지 이동하는동안 얻을 수 있는 최소 점수를 찾는 문제이다. 풀이 노드와 간선이 안주어젔을뿐 전형적인 다익스트라 문제이다. 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..

www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어� www.acmicpc.net 풀이자체는 복잡한것이 없으리라 생각했다. 각 마을에서 목적지 까지 가는거리와 오는거리의 최소 길이를 구해야 하므로 다익스트라를 갈때, 올때 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 26 27 28 29 30 31 32 3..

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..