-
효율적인 긴 문자열 연산을 위한 Rope 자료구조
로프와 쿼리 최근 백준 온라인 저지에 로프와 쿼리라는 이름의 베타 문제가 올라왔습니다. 그런데 문제 본문의 어디를 보아도 로프라는 단어는 쓰이지 않고, 줄과 관련되어 보이는 부분도 없습니다. 그저 문자열의 일부를 잘라서 앞이나 뒤로 옮기는 쿼리를 수행하는 문제일 뿐입니다. 그러면 이 문제의 이름은 왜 로프와 쿼리인 걸까요? 일반적인 문자열 자료구조로는? 우선 이 문제를 단순한 std::string 객체로 해결을 시도해 봅시다. #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); string s; cin >> s; int q; cin...
-
OpenAI Gym 사용하기
서론 OpenAI Gym은 강화학습을 도와주고, 좀 더 일반적인 상황에서 강화학습을 할 수 있게 해주는 라이브러리 입니다. 이 게시글에서는 OpenAI Gym을 사용하는 법을 알아보고, 샘플 프로젝트인 CartPole-v1에서 동작하는 신경망을 만들어봅니다. OpenAI Gym의 설치 OpenAI Gym은 python3.5 이상에서 작동합니다. gym은 간단하게 pip로 설치할 수 있습니다. 그리고 이 샘플 프로젝트를 도와주는 numpy와 keras를 설치해야합니다. 기본적으로 이는 Python에 추가적인 지원을 해주는 Anaconda가 해줄 수 있으며, gym설치 및 numpy 업그레이드를 진행해야합니다. pip install gym pip install numpy --upgrade CartPole-v1 우리가...
-
meet in the middle
Meet in the middle meet in the middle 은 절반 크기의 비슷한 문제를 두 번 해결한 결과를 통해 본 문제를 해결함으로서 문제 해결에 소요되는 시간 복잡도의 향상을 꾀하는 방법입니다. 저 말만 들으면 어떠한 장점이 있는지 감이 오지 않지만, 문제를 푸는 시간 복잡도가 exponential 한 경우라면 아래와 같이 개선이 된다는 것을 느낄수 있을 것입니다. $2^n > 2 * 2^{n/2}$ 구체적인 예제를 통해 설명해 보도록 하겠습니다. BOJ 1208 부분집합의 합2 이 문제는 $N(N\leq 40)$개의 수로 이루어진 집합이...
-
코딩테스트 대비 특강
이 포스트는 3월 1일과 2일에 걸쳐 진행한 코딩테스트 특강의 내용을 기술한 포스트입니다. BFS/DFS, 백트래킹, 시뮬레이션 개념을 알고 있고 기출 문제에 손을 댈 수는 있는데 100% 푼다는 확신은 없어서 개념을 다시 정리하고 모의고사를 쳐보고 싶은 분이 이 포스트를 보신다면 많은 도움이 될 것입니다. 특강의 슬라이드는 여기에서 확인할 수 있습니다. 이 특강은 개인이 준비한 특강이고, 특히 특정 기업의 채용절차와 아무런 관련이 없습니다. 무엇보다 먼저 기초 지식과 자주 실수하는 점을 짚고 넘어가겠습니다. 함수의 인자로 구조체/pair/tuple/vector를 넘길 때 어떤...
-
빠르게 수렴하는 MCMC 만들기
저번 포스트에서 Markov Chain Monte Carlo(MCMC)에 대해서 간략히 알아보고 MCMC를 구현하는 대표적 알고리즘인 Metropolis-Hastings 알고리즘을 이해해보았습니다. 이번에는 이어서 MCMC의 수렴속도에 대해 논의해봅시다. MCMC가 만드는 샘플들은 target distribution에 점점 수렴하는 특징이 있습니다. 다르게 말하면 MCMC가 만들어내는 샘플을 사용하기 위해서는 샘플들이 target distribution에 수렴할 때 까지 기다려야 합니다. 적절히 수렴한 상태를 mix 되었다고 하고 이때까지 걸리는 시간을 mixing time이라고 합니다. 저번에 MCMC가 다른 샘플링 기법들에 비해 빠른 수렴속도를 가진다고 했는데, 사실 절대적인 수렴속도는 일반적으로 빠르지 못합니다. 때문에...