-
Data Forecast
Data Forecast contents What is Data Forecast? Basic Concepts what is STL Decomposition? Data Forecast methods conclusion What is Data Forecast? Data Forecast 란 무엇인가? 데이터 예측은 많은 경우에 필요하고 그 중요성 또한 크다고 할 수 있다. 만약 돌에 걸려 넘어지게 되었을 때, 그 결과를 예측해보면 쉽게 ‘다칠 것이다’라고 말할 수 있다. 하지만 자율주행 자동차를 제작한다고 생각해보자 자동차가 빠른속도로 다가오는 트럭을 상대로 미래를 예측해야 하는 상황이 생길 것이다. 관측 가능한 모든 데이터를 고려해보자 자동차의 현재...
-
On Factoring Given Any Bits
서론 이번에 Belluminar 라고 하는 대회에 참가했습니다. 해당 대회는 각 팀마다 문제를 두 개 씩 출제하고, 대회 시간 동안 문제를 풀면서 점수를 겨루는 방식으로 구성되어 있습니다. 저는 이번에 공부했던 테크닉을 문제로 내기로 결심해서 작성을 했는데, 생각보다 만족스러운 퀄리티로 문제가 나오지 않아 아쉬웠습니다. 본래라면 공부한 내용을 포스트로 바로 쓰겠지만, 제 이름이나 아이디를 검색해 그대로 솔버에 사용하는 것을 원치 않았기 때문에 이러한 소셜 해킹을 방지하기 위해서 이제서야 포스팅을 하게 되었습니다. 이번 포스트는 제가 냈던 문제의 근간이 되는...
-
2D Segment Tree
안녕하세요, 이번 글에서는 2D Segment Tree 에 대해 알아보도록 하겠습니다. Segment Tree에 관한 기초 지식 2D Segment Tree를 이해하기 위해서는 Persistent Segment Tree 포스팅 때와 비슷하게 Segment Tree에 대한 이해가 선행되어야 합니다. Segment Tree가 무엇인지, 혹은 Dynamic Segment Tree가 무엇인지 모르고 있다면 먼저 링크를 타고 그 부분을 공부한 후에 오시는 것을 추천드립니다. Bottom-Up 방식의 Segment Tree Segment Tree를 구현하는 방법으로는 Top-Down 방식과 Bottom-Up 방식이 있습니다. 이전 글에서는 Top-Down 방식만을 설명했으나 2D Segment Tree에서는 Bottom-Up 방식을...
-
알고리즘 문제 풀이7
알고리즘 문제 풀이 7 최근에 푼 재미있는 문제들을 포스팅 해보겠습니다. [BOJ 9208 링월드] 이 문제는 원형으로 나열되어 있는 $M$개의 도시가 있고, 연속된 도시들로 이루어진 $N$개의 구간이 있을 때, $N$개의 구간에서 겹치지 않게 도시를 하나씩 고를 수 있는가를 답해야 하는 문제입니다. 우선, M개의 도시가 원형이 아니라 선형으로 나열되어 있다면 어떨까요? 이 문제는 매우 간단한 그리디로 풀 수 있습니다. 왼쪽 도시에서부터 쭉 보면서 현재 도시를 고를 수 있는 구간들 중 오른쪽 끝 도시가 가장 왼쪽에 있는 구간에게...
-
동적 계획법을 최적화하는 9가지 방법 (Chapter 1)
동적 계획법을 최적화하는 9가지 방법 (Chapter 1) 동적 계획법(DP) 알고리즘의 시간 복잡도를 줄이는 기법에 대해서는 다양한 프로그래밍 대회에서 많이 출제된 바가 있다. 이러한 알고리즘은 굉장히 아름다운 방법으로 시간 복잡도를 줄이기 때문에 다양한 대회에서 인기가 많으나, 실제로 표준적인 알고리즘 교과서나 입문서에서 배우기는 힘든 내용이라 초심자가 시작하기 힘든 것이 단점이다. 현재 동적 계획법 최적화에 대해서 배울 수 있는 인터넷 자료들은 대부분 최신 자료가 아니기 때문에, 내가 알고 있는 동적 계획법 최적화 기법을 모두 소개함으로써 이 분야의 지식...