Sevity Blog

런타임오류

1. 배열 크기가 너무 작게 잡혔거나

2. 다음처럼 T로 여러 테스트 케이스를 돌리는데 배열이나 변수가 그 밖에 선언되어 있는 경우 발생가능

기존에는 syntax highlighter인가 먼가를 쓰고 있었는데, 

여기에 있는 Color Scripter를 써보니까 직관적이고 결과도 깔끔하니 이쁜 것 같다.

사용 방법은 여기에서 코드를 붙여넣은 다음에 복사하기해서 가져와서 티스토리에서 HTML누른다음에 붙여넣기하면 <div>태그로 복사된다.

이를 사용한 코드 샘플은 다음과 같다.

이항계수 ${n}\choose{k}$는 $_nC_k$ 조합과 동일하다.

구하는 방법은 다음과 같다.

$$_nC_k = {n!\over{k!(n-k)!}}$$

예를 들어 바구니에 든 10개의공 중에서 순서에 상관없이 3개의 공을 꺼내는 경우의 수를 구하라고 하면 다음처럼 구하면 된다.

$$_{10}C_k = {{10}!\over{3!7!}} = {{{10}\times 9\times 7}\over{1\times 2\times 3}} = 120$$

브루트포스

    long long fact[100] = {};
    fact[0] = fact[1] = 1;
    for(int i=2;i<100;i++)fact[i] = i*fact[i-1];
    int n = 10, k = 3;
    printf("%lld\n", fact[n]/(fact[k]*fact[n-k]));

일단 중간에 들어가는 factorial자체가 다음과 같이 n이 20을 넘어가면 long long 범위를 초과해 버려서 n이 20이하일 때만 사용할 수 있는 방법이다.

fact[1]:1
fact[2]:2
fact[3]:6
fact[4]:24
fact[5]:120
fact[6]:720
fact[7]:5040
fact[8]:40320
fact[9]:362880
fact[10]:3628800
fact[11]:39916800
fact[12]:479001600
fact[13]:6227020800
fact[14]:87178291200
fact[15]:1307674368000
fact[16]:20922789888000
fact[17]:355687428096000
fact[18]:6402373705728000
fact[19]:121645100408832000
fact[20]:2432902008176640000
fact[21]:-4249290049419214848

$O(n^2)$ 파스칼의 삼각형 점화식 이용

다음처럼 dp solution을 적용하면 n이 대략 50근방일 경우 해결 가능하다.

(n이 100이 넘어서 예를 들어 $_{100}C_{50}$만 되어도 값이 100891344545564193334812497256 이렇게 커져서 long long 범위를 초과해 버린다.

이럴 경우 이 소스코드를 참고해서 bigint를 쓰면 쉽게 해결할 수도 있다)

const int MAX = 50;
long long C[MAX+1][MAX+1] = {};
int main(void)
{
    C[0][0]=1;
    for(int i=1;i<=MAX;i++){
        C[i][0]=1;
        for(int j=1;j<=MAX;j++)
            C[i][j] = C[i-1][j-1]+C[i-1][j];
    }

    printf("%lld\n", C[10][3]);
    return 0;
}

위 코드를 이해하려면 다음 관계 식을 알아야 하는데,

$$_nC_k=_{n-1}C_{k-1}+_{n-1}C_k$$

수학적으로 증명하는건 오히려 어렵지 않고, 개념적으로 이해하기는 조금 까다로울 수 있는데.. 대부분의 인터넷자료에서 설명하기로는 다음과 같다.

특별한공을 하나 마킹하고, 이공을 포함하는 경우와 포함하지 않는 경우로 나눠서 생각하면

정답은 (포함하는경우)+(포함하지 않는 경우)가 될 것이다.

포함하는 경우에는 마킹한거는 이미 공을 골라놓은 셈이니

n-1개에서 k-1개를 뽑는게 될테니까 $_{n-1}C_{k-1}$이 될 것이고,

포함하지 않은 경우에는 마킹한거를 빼놓고 k개를 골라야 하니 

n-1개에서 k개를 뽑는게 될테니까 $_{n-1}C_k$가 될 것이다.

뭐 적당히 납득할만한 설명인것 같다는 생각은 든다.

$O(n\log n)$ 페르마의 소정리

n의 범위가 더 커질 경우, 보통 modulo 연산과 함께 나오는 경우가 많다.

예를 들어 이 문제와 같이 N이 매우클때 결과값을 10,007로 나눈 나머지를 구하라는 문제가 있다고 하자.

mod연산의 경우 덧셈, 뺄셈, 곱셈에 대해서는 자유롭게 중간 중간 mod를 취해줘도 결과가 같지만 나눗셈에 대해서는 그렇지 않은데,

하필이면 이항계수 계산식에는 나눗셈이 들어가며 그 식을 한줄로 나타내 보면 다음과 같다.

$$ [n! / (k!(n-k)!)]  \% 10,007$$

그런데 만약 $(k!(n-k)!)$의 역원인 $(k!(n-k)!)^{-1}$을 구하게 되면 다음처럼 나눗셈이 곱셈으로 바뀌어서 mod연산을 취할 수 있게 된다.

$$[n! \times (k!(n-k)!)^{-1}]  \% 10,007 = [n!\%10,007 \times (k!(n-k)!)^{-1}\%10,007]  \% 10,007 $$

근데 언뜻들으면 말장난처럼 보일것이다. 왜냐하면 저 역원은 당연히 1보다 작은 분수처럼 보이기 때문이다.

하지만 실제 역원이 아닌 모듈러 연산에 대한 역원은 분수가 아닐 수 있다. 다음을 보자.

$$k!(n-k)! \times x \equiv 1(\mod 10,007)$$

위 식에서 x가 바로 k!(n-k)!의 모듈러 연산에 대한 역원이 되는데, k!(n-k)!에다가 어떤 자연수를 곱하고 모듈러 한 이후에 나온 나머지가 1이기만 하면 되는 조건이기 때문에 충분히 분수가 아니라 자연수가 될 수 있음을 간파할 수 있다.

그럼 분수가 아닌 자연수인 역원은 어떻게 구할 수 있을까?

페르마의 소정리는 다음과 같다.

p가 소수이고 a가 p가 서로소이면

$$a^{p-1} \equiv 1(\mod p)$$

이를 좀 변형하면

$$a \times a^{p-2} \equiv 1(\mod p)$$

이렇게 되고, 신기하게도 a의 모듈러 연산에 대한 역원이 바로 $a^{p-2}$가 됨을 알 수 있다.

$a^{p-2}$를 빠르게 구하는 방법은 분할정복을 쓰면 되며, 나눗셈이 들어가던 원래의 식은 다음처럼 바뀐다.

$$ [n! / (k!(n-k)!)]  \% 10,007 = [n! \times (k!(n-k)!)^{-1}]  \% 10,007 = [n! \times (k!(n-k)!)^{p-2}]\%10,007$$

식을 보면 -1승을 p-2승으로 바꿔주면 되는걸 볼 수 있다.

위의 내용을 전체적으로 반영한 코드는 다음과 같다.

#define ll long long
ll f[4000001];
ll M = 1000000007;
ll pp(ll a, ll p, ll M)
{
    if(p==1) return a;
    ll b = pp(a,p/2,M);
    if(p%2==0){
        return (b*b)%M;
    }else{
        return (((b*b)%M)*a)%M;
    }
}
int main(void)
{
    int N,K;scanf("%d %d",&N, &K);
    f[0]=f[1]=1;for(int i=2;i<4000001;i++)f[i]=(i*f[i-1])%M;
    printf("%lld\n", (f[N]*pp((f[K]*f[N-K])%M,M-2,M))%M);

    return 0;
}

약분하기

modulo가 없고 n의 값이 큰 경우에 사용할 수 있는 방법인데 이것도 재밌는 방법이다.

$$_{10}C_{3} = {{10\times9\times8}\over{1\times2\times3}}$$ 

이런식이 되는데..

10곱하고 1로 나누고 9곱하고 2로나누고 8곱하고 3으로 나누고 이런식으로 구하자는 것 ㅋ

한가지 걱정되는것은 이렇게 했을때 순간적으로라도 나눈값이 정수가 아닌 경우가 생기면 망하는건데

증명은 모르겠지만 실제로 그런경우는 없나보다.

코드는 다음처럼 심플하다.

        int n,m;scanf("%d %d",&n, &m);

        m = min(m,n-m);
        long long r = 1;
        long long div = 1;
        while(m--)
        {
            r*=n--;
            r/=div++;
        }
        printf("%lld\n", r);

n의 범위가 커도 동작하는 대신 쿼리한번에 걸리는 시간이 좀 있다보니 일반적인 경우는 n이 크지만 않다면 dp솔루션이 더 활용도가 높다.

최대공약수(gcd)를 쉽게 구할 수 있게 해주는 공식.

숫자 a와 b가 주어진다고 했을때 두수의 최대 공약수 gcd(a,b)를 구하는 문제를 생각해보자.

a>b 라고 했을 때 $a = bq+r$ 꼴로 표현할 수 있는데,

$gcd(a, b) = gcd(b, r) $

이란것이 유클리드 호제법이다.

r = a%b는 b보다 작으므로 gcd(a,b)에서 gcd(b,r)로 순서가 바뀜에 주의하자.

(사실 gcd는 순서에 무관하나 이해를 위해 a>b라는 속성을 유지하는 것)

증명은 여기를 참고하자.

계속 위처럼 하다가 r==0이 되는 순간 즉 a가 b로 나눠떨어지는 순간 b를 리턴하면 된다.

위의 내용대로 구현한 코드는 다음과 같다.

int gcd(int a, int b) 
{
    while(1)     
    {         
    	int r = a%b;         
        if(r==0) return b;         
        a=b,b=r;     
    } 
}

그런데 위의 코드는 함수 종료부분에 return 코드도 없고 while(1)인것도 좀  그래서 살짝 정리하고 나면 인터넷에 많이 퍼져있는 다음 형태가 된다.(자료형도 좀 더 사용성 좋도록 long long으로 변경)

long long gcd(long long a, long long b) {
    while (b > 0)     
    {         
    	long long t = a % b;         
        a = b, b = t;     
    }     
    return a; 
}

재귀호출 버전

여러수의 최대공약수 구하기

n개의 숫자에 대한 최대 공약수를 구할때는 단순히 루프를 돌면서 gcd를 반복하면 된다.

마치 max함수가 n개에 대해서 할때는 여러번 적용하듯이..

관련문제

http://codeup.kr/problem.php?id=4016

내 풀이

Google colab은 Jupyter ipython notebook과 같은 python code를 온라인에서 공유하면서 작성할 수 있게 해준다.

더구나 GPU도 쓸 수 있고 속도도 빠른편이며 sklearn, prophet등 ML관련 library들도 대부분 미리 설치되어 있다.

팁1: 인터넷에 있는 파일을 바로 다운받아서 데이터로 쓰기

ML을 하다보면 데이터가 생명인데, 매번 클릭해서 다운받으면 번거롭기 때문에 wget으로 바로 받으면 공유하기도 좋고 편하다.

위 파일처럼 압축된 경우에도 다음처럼 zipfile 을 import하여 풀 수 있다.

팁2: github에 있는 파일 받기

github에 올려져 있는 파일의 경우 git clone을 하지 않고 wget만으로는 받기 힘든데.. 다음처럼 raw.으로 시작하는 주소로 바꾸고 약간만 조심하면 바로 받을 수 있다.

주소를 바꾸는 규칙에 대해서는 여기를 참조하라.

요즘에는 그냥 git clone 되는거 같다.

facebook에서 나온 ML forecasting engine인것 같다.

여기가 홈페이지 이며 분석 해서 정리할 예정이다.

여기를 보면 kaggle 문제를 prophet을 이용해서 푼 kernel을 볼 수 있다.

(해설이 자세한 편이라 따라가면서 해보는 것도 좋을 듯 하다.)

구글 colab 에서는 별다른 설정없이 아래와 같이 바로 import 가능한걸 확인

가장 기본적인 저장소 개요는 여기를 참조

안드로이드 프로그래밍을 할 때 상태저장 또는 파일입출력, 파일공유 등을 위해 저장소 개념은 중요하다.

그런데 내부/외부 저장소가 있고 저장경로와 권한에 대해 신경써줘야 하는등, 데스크탑에서 하던 콘솔 프로그래밍 또는 MFC등의 application에 비해 복잡성이 좀 더 존재한다.

안드로이드에서 지원하는 저장소에는 다음 5가지가 있다.

1. SharedPreferences: 전용 원시 데이터를 [키, 값] 쌍으로 저장합니다.

2. 내부 저장소: 전용 데이터를 기기 메모리에 저장합니다.

3. 외부 저장소: 공용 데이터를 공유 외부 저장소에 저장합니다.

4. SQLite 데이터베이스: 구조적 데이터를 전용 데이터베이스에 저장합니다.

5. 네트워크 연결: 자신의 네트워크 서버를 사용하여 데이터를 웹에 저장합니다.

SharedPreferences

int, string 등에 대해서 설정값 저장하고 불러올 수 있다.

windows programming에서의 registry개념과 어느정도 유사하다.

내부 저장소

가장 기본적인 파일 입출력 형태라고 볼 수 있다.

다른앱과 공유할 필요없는 앱내부 자료 저장용으로 쓴다.

외부저장소

앱간에 공유할 정보가 있다면 이곳에 저장한다. 앱의 외부라는 측면에서 외부저장소라 부른다.

사진이 저장되는 Pictures폴더나 SD카드, USB스토리지등이 외부저장소에 해당한다.

예를들면 Pictures 폴더의 경우 아래처럼 접근해서 사용

단순히 Environment.getExternalStorageState() 라고만 했을때는, 외부SD카드 경로가 리턴될수도 있고, 내부 메모리의 일정영역이 리턴될수도 있다.

하드웨어 제조사 마음대로. 관련해서는 여기를 참조.

캐글에 실제로 도전해 보는건 처음이다.

도전하려고 하는 것은 이 문제 이며, 간단한(?) classification으로 보여서 해보려고 한다.

(나중에 알았지만 이 문제는 예측할때 여러 class를 동시에 낼 수 있는 multi-class문제여서 생각보다는 복잡했다.)

환경설정

캐글에 로그인한 다음 competition에 join하고 new kernel하면 ipython notebook 환경으로 들어갈 수가 있다.

이 글에 사용된 kernel은 여기를 눌러서 확인

데이터 둘러보기

1차원 array

indexing

a = ['a','b','c','d','e','f'] 이런 배열이 있을때, 기본 인덱싱은

a[0] 이렇게 한다 (a[0]은 0번째 element를 indexing하며 따라서 'a'가 된다.)

이때 a[-1] 이렇게 음수도 쓸 수 있으며 마지막 element부터 -1, -2로 indexing된다. (따라서 a[-1]은 'f'가 된다)

slicing

부분집합을 가져오는 slicing은 colon을 한 번 쓰거나, 두 번 쓸 수 있으며,

각각 [start:stop], [start:stop:step] 이라는 의미가 된다.

또한 colon기호는 대괄호 안에서만 쓸 수 있으나 slice() 객체를 사용하면 밖에서 할 수도 있다.

예를 들어 a[1:3] 하면 ['b', 'c']가 되는데, 

a[1:3]은 a[slice(1,3)]과 같기 때문에 

아래처럼 두줄에 나눠쓰는게 가능하다.

> col = slice(1,3)

> a[col]

slicing의 다양한 옵션은 여기를 보면 쉽게 파악할 수 있다.

2차원 array

indexing

a = [[1,2,3],[4,5,6]] 이런 배열이 있을때, 기본 인덱싱은

a[0][1] 이렇게 한다 (a[0][1]은 0번째 row, 1번째 column을 의미하며 값은 2가 된다)

근데 2차원 인덱싱의 경우는 a[0][1]대신 a[0,1]로도 할 수 있다.

slicing

다른건 쉬운데 index을 위한 comma와 slicing을 위한 colon이 같이 쓰이면 헷갈릴 수 있다.

예를 들어 위의 a배열에 대해서 a[:,0:2]라고 하면 [[1,2],[4,5]]가 되는데..

a[:,0:2]는 

a[slice(None, None, None), slice(0, 2, None)]과 같고, 3줄로 풀어쓰면 다음과 같다.

> row = slice(None, None, None)  # 모든 row를 원한다.

> col = slice(0, 2, None)  # 첫번째, 두번째 컬럼만 원한다(마지막 컬럼 배제)

> a[row,col]

여기참조해서 작성했음을 밝힙니다.

Weka란

ML하는데 있어서 기본 적인 툴, Java로 작성되어 있으며 오픈소스이다(여기서 다운로드)

다양한 종류의 ML알고리즘을 제공하며 간단하게 유명한 알고리즘들을 빠르게 돌려보고 싶을때 유용하다(앙상블 알고리즘 돌려보는데도 좋다)

단 커스터마이징이 커맨드라인 옵션 수준이라 나만의 모델을 만드는데 적합하지는 않은것 같다.

data입출력에 CSV와 유사한 ARFF포맷 사용

weka 실행 후 Explorer 누르고 Open file 누르고 설치폴더 data 안에 들어가면 기본적으로 제공되는 많은 arff 파일들을 살펴볼 수 있다.

추가적인 데이터는 여기서 살펴보면 좋다.

데이터 자체를 살펴보고 싶으면 Edit버튼을 누르고 보면 된다.

처음에 둘러보기 좋은 데이터는 iris 추천.. 꽃잎 length랑 width가 주어지고 class로 세가지 iris종류가 label되어 있는 자료이다.

Weka로 할 수 있는 것들

특정 인풋컬럼(feature)에 대해서 노말라이즈하기, 비주얼라이즈하기

Select Attributes 탭에서 feature selection 하기 (유의미한 컬럼 순으로 나열해서 필요없는 컬럼 제거하거나 할 수 있다)

Attribute Evaluator는 CorrelationAttributeEval이나 InfoGainAttributeEval 이런거 고르면 된다.

classification하기.. 

Classify탭에서 알고리즘 고르고 Start 버튼 누르면 된다. baseline performance는 ZeroR로 하면 좋다고 한다.(Zero Rule)

Zero Rule 알고리즘은 단순히 개수가 많은쪽 class로 몰빵해서 예측하는 알고리즘이라고 함

(classification이 아닌 regression의 경우는 평균값으로 예측한다고 함)

5 Top algorithms that you can use for classification include:

- Logistic Regression (functions.Logistic).

- Naive Bayes (bayes.NaiveBayes).

- k-Nearest Neighbors (lazy.IBk).

- Classification and Regression Trees (trees.REPTree).

- Support Vector Machines (functions.SMO).

regression하기..

Weka는 기본적으로 Classification에 강한 툴이지만 regression 알고리즘 및 샘플 데이터도 어느정도 제공한다.

여기서 regression용 추가 데이터 다운로드(jar파일이라 압축해제해야 arff파일들 나온다)

classfication과 마찬가지로 ZeroR로 베이스라인 성능 확인하고(Root mean squared error 등) 다음 알고리즘들 돌려보면 된다.

5 Top algorithms that you can use for regression include:

- Linear Regression (functions.LinearRegression).

- Support Vector Regression (functions.SMOReg).

- k-Nearest Neighbors (lazy.IBk).

- Classification and Regression Trees (trees.REPTree).

- Artificial Neural Network (functions.MultilayerPerceptron).

Ensemble하기..(classification, regression 둘 다 지원)

앙상블은 일종의 메타 알고리즘이라 어떤걸 sub알고리즘으로 사용할지 커맨드라인에서 지정해줘야함에 주의.. 기본적으로는 ZeroR로 세팅된 경우가 많아서 더욱 그렇다.

5 Top ensemble algorithms that you can use include:

- Bagging (meta.Bagging).

- Random Forest (trees.RandomForest).

- AdaBoost (meta.AdaBoost).

- Voting (meta.Voting).

- Stacking (meta.Stacking).