Samsung Software Membership

shjgkwo

December 15, 2019

Flow with demands

목차 1. 개요 2. Demands(수요)가 대체 뭐야? 3. Flow with demands 해결법 4. 응용 5. 문제풀이 6. 마무리 7. 참고자료 개요 이번에 소개할 알고리즘은 Flow with demands 입니다. 보통의 간선에 흐를 수 있는 유량에 상한이 있는 최대 유량 문제와 다르게 하한이 있는 최대 유량 문제를 효과적으로 해결하는 알고리즘 이며, 2016년도 한국 ACM-ICPC 예선 H번에서 이 알고리즘을 사용하게 됩니다. 기본적인 아이디어와 작동원리 등을 설명하고 실제로 문제풀이에 어디에 쓰이는지 보이고자 합니다. 일단 기본적으로 최대 유량에 대한 기본...

algorithm maximum-flow

shjgkwo

October 21, 2019

Judger와 Express를 이용한 채점 서버 구현 후기

목차 1. 개요 2. Judger 3. Express 서버 구현 4. 테스트 5. 후기 개요 채점 서버는 OJ(Online Judge)를 만들때 제일 핵심적인 기능입니다. 학교 졸업 프로젝트의 일환으로, 프로그래밍 학원 선생님한테 유용하게 쓰일법한 웹 어플리케이션을 구상하는 과정에서 OJ의 채점 기능이 반드시 필요하게 되었습니다. 이번에 구현한 채점 서버는 Node.JS의 Express 기반 채점 서버입니다. 클라이언트로부터 소스코드를 받을 때, 시스템 콜 혹은 메모리 오버플로, 버퍼 오버플로등의 문제에서 발생할 수 있는 보안적 이슈를 해결하기 위하여 칭다오 대학에서 만든 OJ에서 SECCOMP기반의 Judger를...

C Node.js Express Docker

shjgkwo

September 18, 2019

Codeforces Virtual을 통한 스터디와 문제풀이

목차 1. 개요 2. Codeforces 3. 문제풀이 4. 마무리 개요 문제풀이를 하는 사람들 중에 코드포스는 본인의 실력을 가늠하기에 매우 훌륭한 지표입니다. 특히나 코드포스 블루(expert) 등급에 해당하는 사람들은 웬만한 회사의 코딩테스트는 쉽게 통과한다라는 말이 있을 정도로 본인의 실력의 지표로서는 매우 유용한 가치가 있습니다. 하지만 그런 지표뿐만이 아니라 본인의 실력을 늘리는데에도 코드포스 만큼 좋은 사이트는 몇 없습니다. 백준을 제외하고서라도 콘테스트 형식, 즉 제한된 시간에 빠른 알고리즘을 구상해내야하는 코딩테스트와 비슷한(물론, ACM-ICPC의 형태와 조금 더 가깝습니다.) 환경으로서 본인의 제한된...

algorithm Codeforces study

shjgkwo

August 19, 2019

Suffix Automaton 구현과 그 응용

목차 1. 개요 2. 구현 3. 응용 4. 문제풀이 5. 마무리 6. 참고자료 개요 이 포스트를 쓰며 이번 포스트에서 살짝 양심고백을 한다면, 원리를 100% 이해하지 못하고 그 구현과 구현체만을 응용하는 것을 다루는 것을 리뷰하려고 합니다. Suffix Automaton의 구현과 동작이 모두 $O(N)$에 이루어지기 때문에 그 효율성 때문에 사용만 가능하다면 매우 유용할 것 입니다. Suffix Automaton의 원리를 전부 이해하고 구현한다면 참 좋겠지만, 아직 몇가지 소정리에 대해서 더 공부해야 이해가 제대로 될 것 같아서 구현방법만 집중적으로 설명하고, 응용에...

algorithm string automata

shjgkwo

July 22, 2019

Treap

목차 1. 개요 2. 개념 3. 구현 4. 응용 5. 문제풀이 6. 마무리 7. 참고자료 개요 이 포스트를 쓰며 언제 한번, Treap의 활용성에 대해서 적고 싶었다. 물론 여기서 내가 여러분에게 소개하고자 하는 것은 Treap을 BST로서 다루는 것이 아닌, 배열을 자유롭게 붙이고 떼고 뒤집는 것에 설명하기 위함이다. Treap은 기본적으로 BST로서 사용할 수 있지만, Splay Tree 처럼 배열을 다루는 데 사용할 수 있다. Splay Tree 처럼 여러가지의 method 들을 활용하여 amortized 시간을 내는것은 아니고, 확률에 의존하는 경향이...

algorithm BST data-structure

shjgkwo

June 17, 2019

Prime Number

목차 1. 개요 2. 개념 3. 구현 4. 문제풀이 5. 마무리 6. 참고자료 개요 이 포스트를 쓰며 학교 고급 알고리즘 시간에 Miller–Rabin Algorithm 에 대해서 공부하게 되었다. 매우 흥미로운 내용이 많았으며, 다른 사람들과 공유하면 좋겠다고 생각하여 소인수 분해 알고리즘 등의 다양한 알고리즘을 알게 된것을 포함하여 공유하고 싶어졌다. 이번 포스트에서는 그 알고리즘들의 구현과 실제 문제에 대해 어떻게 사용되는지 소개하고자 한다. 기본 지식 일단 최소한 Modulo Operation, 즉, 나머지 연산에 대해서 조금 설명할 필요가 있다. Mod 연산은...

algorithm number-theory

shjgkwo

May 17, 2019

Palindromic Tree

목차 1. 개요 2. 개념 3. 구현 4. 문제풀이 5. 마무리 6. 참고자료 개요 이 포스트를 쓰며 두달 전에 Manacher’s Algorithm 에 대해 소개했다. 이번에는 그것의 연장선상이며, 조금 지엽적이면서도 활용도가 높은 Palindromic Tree에 대해서 소개하고자 이 포스트를 쓰게 되었다. 이 포스트를 이해 하기 위해서는 간단한 오토마타에 대한 지식을 요구한다. 또한 KMP Algorithm에 대해 알고 있으면 이해하기 훨씬 수월하다. 또한 Manacher’s Algorithm 에 대한 지식이 없다면 Manacher’s Algorithm 에 대한 포스트를 한번 읽어보길 바란다. 또한 Trie에...

algorithm string

shjgkwo

April 10, 2019

Graph, SCC and BCC

목차 1. 개요 2. 개념 3. 구현 4. 문제풀이 5. 마무리 6. 참고자료 개요 이 포스트를 쓰며 DFS Numbering에 대한 많은 재미있는 사실들이 있다. 최근에 고급 알고리즘이라는 과목을 들으면서 DFS에서 Numbering을 할때 가지는 자체적인 성질과 그에 관련된 알고리즘들을 공부하게 되었다. SCC와 BCC가 그런것들이다. 이들은 PS에서 매우 유용하게 쓰일 수 있으며, 다양한 상황에 적용할 수 있고, 알아두는 것만으로 풀 수 있는 문제영역이 넓어진다. 또한 DFS Numbering 자체가 구현 자체가 쉬우므로 보통 Dynamic Programming 이나, 2-SAT등 다양한...

algorithm graph-theory

shjgkwo

March 10, 2019

Manacher's Algorithm

목차 1. 개요 2. 기본 3. 구현 4. 문제풀이 5. 마무리 6. 참고자료 개요 이 포스트를 쓰며 학기가 시작되어 모든 알고리즘들을 한번씩 보면서 넘어가던 도중 사람들이 잘 관심 가지지 않지만, 알아두면 재미있을법한 알고리즘인 Manacher’s Algorithm 을 소개해보고자 한다. Manacher’s Algorithm은 String 내에 존재하는 모든 Palindrome을 $O(N)$에 구하는 강력한 알고리즘이다. 물론 이 알고리즘이 실전에 출제되는 경우는 매우 드물지만 원리 자체가 재미있고 시간복잡도가 $O(N)$이 되는 원리가 재미있는 알고리즘이므로 자세하게 설명해보고자 한다. 팰린드롬 팰린드롬을 모르는 사람을 위해 간단히...

algorithm palindrome

shjgkwo

February 10, 2019

Tree DP 문제 해결

목차 1. 개요 2. 기본 3. 구현 4. 문제풀이 5. 마무리 6. 참고자료 개요 이 포스트를 쓰며 알고리즘 공부를 하면서 오랫동안 다이나믹 프로그래밍을 그것도 트리에서 해결하는 문제를 꽤 안풀었음을 알았다. 그래서 오랜만에 다이나믹 프로그래밍 연습도 할겸 트리에서 해결하는 다이나믹 프로그래밍 문제를 몇가지 공유하고 같이 풀어보고자 한다. 이번 포스트를 통해 트리에서의 다이나믹 프로그래밍에 대한 문제를 재미있게 봐주었으면 한다. 간단한 원리 기본적으로 Top-down 방식으로 해결하며, 보통 leaf node 부터 값을 알아낸다. Top-down 방식의 DP에 익숙한 사람들은 문제를...

algorithm

shjgkwo

January 11, 2019

Delaunay Triangulation 구현

목차 1. 개요 2. 원리 3. 구현 4. 마무리 5. 참고자료 개요 이 포스트를 작성하게 된 계기 이 글을 쓰게 된 계기는 학부 과정에 수학과 과목을 몰래 훔쳐 들으려고 하던 중, 계산 기하학에 대해 공부하는 과목을 알게 되었다. 바로 혹해서 들었다가 후반부에 너무 어렵고 추상적인 수학 파트가 나와서 좌절했다가, 초반부의 Deluanay Triangulation 만큼은 흥미롭고 응용 분야가 넓어서 공유하면 좋겠다 싶어서 가져오게 되었다. 간단한 설명 Deluanay Triangulation, 한국어로 들로네 삼각분할은 간단히 말하면 2차원 평면에 분포하는 점들을...

Delaunay-triangulation