전체 글 썸네일형 리스트형 C++ string에 관한 놀라운 사실 vector처럼, string은 크기가 amortized linear하게 늘어난다. https://gcc.gnu.org/legacy-ml/libstdc++/2001-07/msg00085.html 더보기 Aho–Corasick algorithm Aho–Corasick 알고리즘은 특정 문자열에 패턴이 존재하는지를 확인하는 알고리즘이다. 패턴들의 길이의 합을 $m$, 확인하고 싶은 문자열을 $n$이라고 하면 $O(n+m)$의 시간에 패턴이 존재하는지 확인할 수 있다. 자세한 설명은 www.slideshare.net/ssuser81b91b/ahocorasick-algorithm를 참고하자. class AhoCorasick { private: struct node { node* child[26]{}; node* failure = nullptr; node* output = nullptr; } root; void deallocate(node* p) { for (auto q : p -> child) { if (q) { deallocate(q); } } de.. 더보기 BOJ 18826 A+B (MC) 놀랍게도 이 문제는 숏코딩이 가능하다. 제출하라는 512×256×512 크기의 Anvil 파일은 사실 16×256×16 크기의 Chunk 1024개로 이루어져 있다. 구조가 알려져 있으므로 직접 Anvil 파일을 최적화하는 방법도 있겠지만, 다행히 Anvil 파일에서 필요없는 Chunk를 날려버리는 mcaselector라는 툴이 있다. 이를 이용해서 1개의 Chunk 안에 코드를 구현하고 필요없는 1023개의 Chunk를 지워버리면 굉장히 작은 파일으로 제출할 수 있다. 먼저 에디토리얼을 읽고 오면 A and not B를 계산하는 A ? B만을 이용해서 4 bit adder를 구현해야 한다는 사실을 알 수 있다. 이때 중계기의 특성상 B가 A보다 먼저 도착해야 하지만, 괜히 시간을 다르게 해놓으면 헷갈리.. 더보기 Hopcroft–Karp bipartite matching algorithm Hopcroft–Karp 알고리즘은 이분 그래프에서 최대 매칭을 $O((V+E)\sqrt{V})$에 구하는 알고리즘이다. 아이디어는 다음과 같다. 정점의 집합 $X$, $Y$가 있고, 이분그래프 $G = (X \cup Y, E)$의 어떤 매칭 $M$이 있다고 하자. (매칭은 간선의 집합이라고 보고, 자명히 $M \subset E$ 다.) 이때 $X$에 속하면서 아직 매칭되지 않은 정점에서 출발해, $E-M$에 속한 간선과 $M$에 속한 간선을 번갈아 가면서 $Y$에 속하면서 아직 매칭되지 않은 정점으로 도착하는 단순 경로를 확장 경로(augmenting path)라고 한다. 이때 어떤 매칭인지 언급해야 할 필요가 있을 경우 M-확장 경로(augmenting path with respect to M)라고 .. 더보기 Prism으로 syntax highlighting 지원하기 티스토리 공지에서는 코드 삽입을 위해서 에디터의 코드블럭 기능을 사용하라고 한다. 하지만 코드블럭을 사용할 경우 처럼 html 코드가 더러워져서 그냥 직접 html을 수정해서 코드를 넣기로 했다. 다양한 Syntax highlighter 중에서 Prism을 사용한 이유는 여러 가지가 있다. 용량이 굉장히 작다. class를 상속받기 때문에 body에 class를 지정하는 식으로 기본 언어를 지정할 수 있다. 지원하는 언어가 많아서 티스토리 코드블럭에서 지원하지 않는 언어들도 사용할 수 있다. 정규 표현식만 안다면 새로운 언어를 만들거나, 기존 언어를 수정할 수도 있다. 플러그인을 통해 다양한 기능들을 지원한다. Prism을 적용하는 한가지 방법은 다운로드 페이지에서 직접 Prism을 다운로드 받는 방법이.. 더보기 MathJax 3으로 LaTeX 지원하기 관리 - 꾸미기 - 스킨 편집으로 들어간 후 html 편집을 누르고 위 코드를 사이 아무 곳에나 끼워넣는다. 2~8줄은 \$로 inline math를 넣을 수 있게 하는 코드다. 9줄은 옛날 브라우저들을 지원하기 위한 코드다. 10줄은 MathJax 3를 불러오는 코드다. 항상 최신 버전을 불러온다. 성공했다면 LaTeX처럼 \$로 둘러싸서 inline math를 넣을 수 있고 \$\$로 둘러싸서 display math를 넣을 수 있다. 예를 들어 $F_n = F_{n-1} + F_{n-2}$는 $F_n = F_{n-1} + F_{n-2}$로 보이고, $$C_{n+1} = \sum_{i+j=n} C_i C_j$$는 다음 수식처럼 보인다. $$C_{n+1} = \sum_{i+j=n} C_i C_j$$ 이때.. 더보기 Unity git 시작 & UnityYAMLMerge git으로 Unity 프로젝트를 관리할 때 여러 사람이 Scene이나 Prefab 등을 수정하면 골치가 아파진다. 이런 Asset들을 그냥 git 기본 설정대로 텍스트 파일처럼 merge하면 unity에서 읽을 수 없게 될 수도 있기 때문이다. 그래서 Unity에서 제공하는 UnityYAMLMerge라는 공식 merge tool을 사용해야 Scene이랑 Prefab을 제대로 merge할 수 있다. 이 과정은 각 프로젝트마다 해줘야 한다. 먼저 Unity를 킨 다음 Edit -> Project Settings... -> Editor로 들어간 후 Version Control의 Mode를 Visible Meta Files, Asset Serialization의 Mode를 Force Text로 설정한다. 이 과.. 더보기 이전 1 다음
