아네스의 공부일지

ARIMA 모델 Autoregressive Integrated Moving Average는 개발된지 오래된 방법이지만 시계열 데이터 분석을 위해 이해해야 하는 중요한 모델링 또는 예측 기법이다. 여기 나오는 개념들을 이해하는것이 좋다. Stationary vs Non-stationary time series Seasonal vs Non-seasonal ARIMA Autoregressive - AR(p) Integrated - I(d) Moving Average - MA(q) Stationary 데이터 특성 - 연속되는 숫자들의 평균 / 분산 / 공분산이 시간에 따라서 변하지 않으면 Stationary하다고 한다. ARIMA 모델이 효과적으로 적용이 되려면 Data가 Stationary 특성을 보여야한다...

permutation을 만들 때, 섞어야하는 배열이 있다면, 그 배열의 index를 섞는다 라고 생각하면 편하다. 하나를 여러번 뽑을 순 없으므로 visited[] bool 배열로 한 index가 두번 선택되게 하지 않게끔 막는다. 출력 조건이 사전순으로 증가하는(오름차순) 순서로 출력해야 하기 때문에 permutation을 실행하기 전에 sort후 실행한다. C++ 풀이 #include using namespace std; vector v; vector permu; bool visited[9]; int M, N; void print_permu() { for (int i = 0; i M; for (int i = 1; i > temp; v.push_ba..

단순했다. N개 중에 M개를 뽑아 조합을 만드는 문제. C++은 재귀로 풀고, python은 itertools의 combinations를 제공해준다. C++ 풀이 dfs의 for문은 그림과 같은 방식 #include using namespace std; vector v; vector comb; vector res; int M, N; void print_comb() { for (int i = 0; i < comb.size(); i++) { cout M; //1부터 시작. dfs(1); } Python 풀이 python 개사기.. import sys from itertools import combinations input = sys.stdin.readline N, M = list(map(int,input()..

1. SImple Moving Average Rolling mean 시켜서 하는거랑 다를바 없음 2. Weighted Moving Average window가 길어지면 그만큼 앞의 missing data도 많아지고, Trend도 늦게 반영한다. Moving Average라서 극단값을 쫓아가지 못한다. 샘플에다가 Weight를 주는데, 최근것에다가 크게 준다. 오래된 데이터일수록 사라져가게끔. 3. Simple Exponential Smoothing F는 Forcast의 F, A는 Actual의 A 예측 Residual이 다들 크다. Trend와 Seasonality 반영도 안됨 보완하는 방법으로 홀츠 Exponential Smoothing = 트랜드, Seasonality 반영 window size만큼 ..

아이디어 다익스트라 알고리즘을 사용하는데, Priority_queue를 이용해서 풀어야했다. 내가 자꾸 틀렸던건 if(visited[nn] ==false && dist[nn] > dist[node]+nw) { dist[nn] = dist[node] +nw; //값을 갱신한다. pq.push({-(dist[node] +nw),nn}); // 이렇게 하면 맞습니다. //pq.push({-nw, nn}); //이렇게 하면 틀리고 } 이부분인데 왜 누적합을 보내야하는지 의문이였다. 그런데, 찾고찾다가 아래와같은 반례를 볼 수 있었다. (좌) : priority_queue에 간선 비용순으로 push했을 때 (우) : priority_queue에 간선 누적합 순으로 push했을 때 C++ 풀이 #include us..

아.. 결국 혼자서 못풀고, 다른사람들의 풀이법을 보고 풀었다. 아이디어 얻고나서 무릎을 탁! 쳐버렸ㄷ. 아이디어 대충 아래와같은 트리가 있고, 임의의 노드(여기서 1번 노드)에서 출발해서 가장 길이가 긴 노드를 찾는다. (5번 노드) 그럼 5번 노드부터 가장 길이가 긴 트리길이를 찾으면 그것이 트리의 지름이 된다. C++ 풀이 #include using namespace std; vector v[100001]; bool visited[100001]; int maxidx = 0; int maxvalue = 0; void dfs(int node, int sum) { if( maxvalue < sum) // 가장 먼 node찾기. { maxvalue = sum; maxidx = node; } for(int ..

시계열 데이터 특성 : Level + Trend + Seasonality + Noise (Error) - Level은 Decomposition이 불가능해서 Noise에 속한다. Trends Seasonality : 반복되는 트렌드 Cyclical : 일정하지 않은 기간의 트렌드 +Noise ETS모델 : 데이터의 패턴을 더 잘 파악하기 위해서 또는 예측을 수행하기 위해 Smoothing을 한다. Smoothing을 위해서 Error, Trend, Seasonality 요소들을 활용하는데, 각각을 더하거나 곱하여 Smoothing을 한다. 이것들을 가지고 시계열 데이터를 모델링 할 수 있다. ETS Decomposition : ETS 컴포넌트들을 시각화 하는 것은 데이터의 흐름을 이해하는데 큰 도움이 된다..

코드보면 dp가 참 짧은 라인 수인데,, 생각해 내기가 너무 힘들더라. 맨처음엔 그리디인 것 같아서 풀었는데, 반례가 있어서 납득했다. 예를들어 극단적으로 2 1 10 100 1 100 200 이런 경우만 따져봐도 1번 집에서 Greedy하게 비용 1을 선택하면 2번 집에서 101, 201을 가지게 되는 반면 1번 집에서 10을 선택하면 2번집에서 1을 선택해서 11의 비용을 가질 수 있다. 그러므로 그리디는 이러한 경우때문에 성립이 불가하다. 아래 코드에서는 dp배열을 ary와 동일한 사이즈로 만들어두고 채워나간다. 그림으로 따지면 이렇다. i번째 집에 칠할 수 있는 비용은 이전까지 칠해온 비용 + 현재 집에서 칠하는 비용(Ri, Gi, Bi)인데, R-R , G-G, B-B를 연속으로 칠하는 것은 불..

아이디어 vector에 3개의 값을 유지한다. v(입력값, 기존 index, 정렬후 index). 1. 입력을 다 받고 입력값 기준으로 sort를 실시 한 뒤 2. 각 entry들이 몇번째 숫자인지 순서를 매긴 후 (정렬 후index) 3. 기존 index를 기준으로 원상 복구 시켜서 정렬 후 index를 출력한다. C++ 풀이 #include using namespace std; vector v; bool compare(pair& a, pair& b) { return a.second.first > N; for(int i = 0 ; i< N;..

예제 1번에서 이런 모습이 된다. 사실 bfs를 써도 되고 , dfs를 써도 상관없다. C++풀이 #include using namespace std; vector v[1001]; queue q; bool visited[1001]; int cnt = 0; void bfs(){ while(!q.empty()) { int node = q.front(); q.pop(); for(int i = 0; i> N >> M; for(int i = 0 ; i> s >> e; v[s].push_back(e); v[e].push_back(s); } for(int i = 1 ; i