Elevation

볼록 껍질을 이용한 최적화, 혹은 컨벡스 헐 트릭(CHT)은 위 그림처럼 여러 직선이 주어져 있을 때, 직선이 이루는 볼록 껍질을 구하여 x에 따른 최솟값을 구하는 최적화 기법이다. 따라서 평소라면 $O(n)$이 걸릴 최솟값 문제를, x가 속한 구간만 이분 탐색으로 찾으면 되므로 $O(\log n)$에 해결할 수 있게 된다. cht는 dp가 아니어도 충분히 사용될 수 있지만 dp의 최적화 기법으로도 자주 사용되기에 dp 카테고리에 작성하였다. cht를 적용하려면 다음과 같은 조건이 필요하다. 일차 함수 관계이거나, 일차 함수 형태로 변형 가능한 문제여야 한다.직선들이 볼록 껍질을 구성해야 하므로, 그 기울기가 단조 증가 혹은 감소해야 한다. (ex. 양수로 구성된 배열의 누적합) 컨베이어 벨트 (BOJ ..

기하에 관하여 다루는 알고리즘은 문제의 답을 직접 구할 때와 원리는 비슷하나 구현에서 상당히 다른 측면이 있다. 부동소수점 오차를 최소화하고 예외(ex. 기울기가 0 혹은 무한대) 처리의 상황을 가급적 방지하고자 하기 때문이다. 때문에 대체로 선형대수학적 접근을 통해 구현한다. 이번에는 알고리즘에서 직선을 다루는 방식에 대해 정리하였다. atan2를 이용한 직선의 표현직선의 표현에 관한 직관적인 접근은 일차함수 $y=ax+b$, 즉 기울기와 절편으로 표현하는 것이다. 그러나 기울기가 무한대가 되는 예외 상황이 발생할 수 있어 좋지 않다. 따라서 두 점 p1, p2로 표현하는 것이 좀 더 적합하다. 정렬 등을 위해 기울기가 필요할 때는, 대신 두 점이 이루는 벡터의 부호 있는 각도를 사용할 수 있다. 벡..

단순회귀분석에 이어 중회귀분석에 대해 알아본다. 중회귀분석(multiple regression)은 두 개 이상의 설명변수를 이용하는 회귀분석이다. 중회귀선형모형은 다음과 같이 식으로 표현할 수 있다. 단순회귀분석과 마찬가지로 선형성, 등분산성, 독립성, 정규성을 만족시키는 오차를 가정한다. $$ Y = \beta_0 + \beta_1 x_1 + \cdots + \beta_k x_k + e$$$$ \hat{y} = E(Y) = \beta_0 + \beta_1 x_1 + \cdots + \beta_k x_k $$ 중회귀분석에서 각 계수는, 다른 설명변수들을 모두 고정시킨 상황에서 해당 설명변수가 1단위 증가했을 때, $\triangle E(Y)$를 의미한다. 중회귀분석의 평가중회귀분석의 평가 방법 역시 크..

Class 4를 푼지 반년이나 지났는데, 이제야 Class 5 문제들을 다 풀었다. 마찬가지로 기억에 남는 문제들을 정리해 보았다. 문제의 난이도는 골드 중상위부터 플5까지이다. 본격적으로 다양한 알고리즘이 등장하는 난이도인 만큼 dp, 그리디, 분할 정복, 그래프, 자료구조, 문자열까지 골고루 연습해볼 수 있었다. 그래프는 동작 원리만 잘 알고 있다면 대부분의 문제를 수월하게 풀 수 있었으나, dp 문제는 어느 정도의 응용을 요구하여 초기 세팅에 대해 꽤 고민해야 했다. 또한 읽고 나서도 어떤 알고리즘을 써야 할지 감이 잘 잡히지 않는 문제들도 있었는데, 이러한 문제들 역시 적절한 알고리즘 및 자료 구조를 이용해야 시간 제한을 통과할 수 있는 경우가 있어 꽤 까다로웠다. 골드 상위 문제들의 위력을 잘..

두 변수 간의 관계를 살펴보고 싶은 경우, 상관분석이나 회귀분석을 수행한다. 상관분석(correlation analysis)은 두 변수 사이에 관계가 있는지, 있다면 어느 정도 강도로 존재하는지를 모상관계수를 추론함으로써 확인한다. 회귀분석(regression analysis)은 두 변수 사이의 함수 관계를 확인하는 것으로, 회귀분석을 통해 한 변수의 값으로부터 다른 변수의 값을 예측할 수 있다. 검정에 비해 비교적 잘 알려진 통계적 분석 방법이니만큼 가볍게 정리하고 넘어간다. 상관분석모상관계수 $\rho$는 공분산을 각 표준편차의 곱으로 나눈 값이다. 표본 크기가 $n$일 때 표본분산은 모분산의 $1/n$배, 표본표준편차는 모표준편차의 $1/\sqrt{n}$배임을 감안하면, 표본상관계수 $r$의 식은..

이어서 pandas의 주요 기능들에 대해 알아본다. 데이터 요약ML 프로젝트의 데이터는 종종 큰 용량을 갖기 때문에, 데이터의 편집에 앞서 데이터 전체의 흐름을 읽고 분석하는 작업도 필요하다. df.info(), df.describe()로 데이터에 대한 요약을 확인해 볼 수 있다. info()는 column별로 결측치가 아닌 값의 개수 및 자료형을 알려 주고, describe()는 숫자 자료형인 column들에 대해 평균, 표준편차, 최대 및 최소, 사분위수 등을 알려준다. describe에서 제시하는 각각의 통계량들은 대부분 df.mean(), df.std(), df.median(), df.max() 등 개별적으로도 확인할 수 있다. 한편 DataFrame 전체의 크기를 알고 싶을 때는 df.shap..

파이썬 라이브러리 pandas는 패널 데이터(Panel Data)에서 이름을 따온 것으로, 엑셀처럼 표 형식의 데이터에 대해 다양한 작업을 수행할 수 있게 해준다. 대량의 데이터가 표 형식으로 주어지는 경우가 많은 ML 프로젝트에서 pandas의 능숙한 활용은 필수적이라고 볼 수 있다. pandas의 핵심 기능들에 대해 간단히 알아보자. 자료구조: DataFrame과 Series pandas에서는 표 형식의 데이터를 담기 위해 DataFrame이라는 자료형을 이용한다. dict, ndarray, Series 등을 DataFrame으로 만드는 것이 가능하다. import pandas as pdimport numpy as npdf = pd.DataFrame({'column1':[1,2], 'column2'..