DStory

BATS & TBATS 오늘은 BATS와 TBATS에 대해 알아본다. 여러개의 계절성을 가지는 시계열이 존재한다. 아래의 이미지를 보자. 전기 수요의 경우 9시부터 18시, 평일이 주말보다 높다. 이 경우 2가지의 계절성을 가진다. 2개 이상의 계절성을 가질 때, SARIMA(Seasonal ARIMA) 모델을 사용하면 안된다. 왜냐하면 애초에 SARIMA 모델은 단일 계절 주기를 가정하기 때문이다. 이를 처리하기 위해 BATS와 TBATS를 사용한다. BATS (Box-cox, ARMA erros, Trend, Seasonal components) BATS는 지수평활법( Exponential Smoothing)을 연장한 버전이다. 구체적으로 알아보자. Box-Cox - 평균과 분산을 안정화시켜, 정상성..

Search Tree 이진검색트리 Binary Search Tree - 최대 두개의 자식노드 - 노드의 키 값은 왼쪽 자식 노드의 키 값보단 크고 오른쪽 자식의 키 값보단 작다. - 이진 검색 트리에서의 삽입은 최악의 경우에도 이진트리가 균형이 잡혀있으면 시간복잡도는 O(logn). 이진 검색 트리에서의 삭제 - 삭제하고자 하는 노드 r이 리프 노드인 경우 : 삭제 - 삭제하고자 하는 노드 r의 자식 노드 하나가 있는 경우 : r을 제거하고 r 자리에 r의 자식으로 대체 - 삭제하고자 하는 노드 r의 자식 노드 두개가 있는 경우 : r의 직후원소를 찾고 r을 데체 ​ 레드블랙트리 Red-Black Tree (RB-Tree) 1. 루트 노드는 블랙이다. 2. 노드가 레드이면 자식은 블랙이다. 3. 모든 리..

Stack & Queue Stack '접시 쌓기' (Last In First Out) - push : 스택에 자료를 한개 집어 넣는 동작 pop : 스택 안에 있는 자료를 한 개 꺼내는 동작 ​- Stack이 비어있을 때 stack.pop -> stack underflow | Stack이 가득 찼을 때 stack.push -> stack overflow 시간 복잡도 가장 위에 있는 원소에 접근하기 때문에 접근, 삽입, 삭제의 시간복잡도는 O(1) 예 - 재귀 알고리즘 - 괄호검사, 후위 연산법, 문자열 역순 - DFS(Depth First Search) Queue '줄 서기' (First In First Out) - enqueue : 큐에 자료를 한 개 집어 넣는 동작 dequeue : 큐 안에 있는 자..

Asymptotic notation 알고리즘의 수행 시간을 표기하기 위해, 필수적인 부분에 집중하고 불필요한 상세들을 무시한다. 예를 들어, f(n) = n^2 + 2n 일 때, 시간 복잡도는 n^2이라고 한다. n이 무한대로 가는 데에선 낮은 차수의 증가폭이 높은 차수의 증가폭을 넘지 못하기 때문이다. 점근법 표기법 상한 표기법 : Big- O 점근적 상한만 알고 있을 때 사용하며 기껏해야 f(n)의 비율로 증가하는 함수 e.g. 7n-2가 O(n)임을 증명하라. sol) Let. c>0 이고 n_0 >= 1 n = 7n-2를 만족하는 c, n_0가 존재하는가? ​-> c=7,n_0 = 1일때 존재한다. ​ 하한 표기법 : Big - Omega 점근적 하한만 알고 있을 때 사용하며 적어도 f(n)의 비..

Sort Algorithm 기초 정렬 알고리즘 1. 선택정렬 가장 작은 숫자를 구해 맨 왼쪽과 비교 수행시간 : (n-1) + (n-2) + ... + 2 + 1 = O(n^2) 더보기 장점 - n개의 원소에 대해서 n의 메모리를 할당하기 때문에 하나씩 정교하게 비교할 수 있다. - 역순으로 정렬할 선택 정렬이 높은 효율을 보여준다. 단점 - 이미 정렬되어 있는 자료에 한개라도 자료가 추가 된다면 처음부터 재정렬하기 때문에 최악의 시간복잡도를 보일 수 있다. 2. 버블정렬 맨 왼쪽부터 오른쪽에 있는 숫자와 하나씩 비교 수행시간 : (n-1) + (n-2) + ... + 2 + 1 = O(n^2) 더보기 장점 - n개의 원소에 대해서 n의 메모리를 할당하기 때문에 하나씩 정교하게 비교할 수 있다. 단점 -..