part 1

차이를 확인하는 데이터 요약

더치페이와 N빵

평균

• 어떤 변수의 합계가 고정되어 있을 때 모든 관측치가 똑같이 나눠 가질 수 있는 값을 평균(Mean) 이라고 합니다.

• x위에 "모두 같다"라는 의미로 바(-)를 얹어 표현합니다.
• 우리에게 너무나 익숙한 평균속에는 모든 사람이 평등하거나 모든 사람들에게 공평하다는 개념이 들어 있습니다.
• 그러나 평균을 계산하는 순간 역설적이게도 불공평한 현실을 깨닫게 됩니다.
• 키가 170cm인 남자는 대한민국 성인 남성의 평균 키가 174cm라는 것을 아는 순간 시무룩해집니다.
• 시험에서 60점을 받아서 눈물이 나다가도 평균 점수가 30점이라는 것을 알게 되면 입가에 미소가 번지겠죠?
• 이처럼 평균을 계싼하는 순간, 데이터 속에 있던 차이가 보입니다.

분산

• 분산은 관측치들이 평균에서 평균적으로 얼마나 떨어져 있는지를 계산합니다.

• 1단계 각각의 관측치에서 평균을 뺍니다. 평균으로부터 얼마나 차이가 나는지를 계산합니다.

• 2단계 1단계에서 계산한 값을 제곱합니다.

• 3단계 2단계까지는 i번째 관측치 하나에 대한 계산이였는데 3단계에서는 모든 n개 관측치에 대해서 똑같은 계산을 하고, 그 결과를 모두 더합니다. 분산이 한 변수의 특징을 설명하는 것이 아니라 모든 변수의 특징을 설명하는 것이니 모든 관측치를 다 활용하는 것이죠.

• 4단계 3단계에서 구한 합계를 n-1로 나눕니다. 깐깐한 통계한자들이 n이 아니라 n-1로 나누는게 더 좋다는 것을 밝혀버려서 n-1로 나누게 됐지만, 관측치가 많으면 n으로 나누는 것과 큰 차이가 없습니다.

• 물론 어려운 제곱 말고 절댓값을 쓸 수도 있습니다.

• 부호를 없애는 데는 절대값이 제일 간단하지만 이론적으로는 '미분이 가능한' 분산을 더 선호합니다.

• 물론 현실적인 이유도 있습니다. 평균에서 100명이 100원씩 차이를 보이는 것과 2명이 5,000원의 차이를 보이는 것 모두 절댓값으로는 10,000원이라는 같은 차이를 보입니다.

100 * 100원 = 2 * 5,000원 = 10,000원

• 그렇지만 두 번째의 경우가 좀 더 불평등하지 않나요? 분산에 사용된 제곱합을 계산하면 다른 결과가 나옵니다.

100*(100원)제곱 = 1,000,000원 제곱 < 2 * (5,000)제곱 = 50,000,000원 제곱

표준편차

• 그러나 분산은 치명적인 단점이 있습니다. 바로 단위(unit)입니다.
• 평균이 만원이라는 것은 쉽게 이해되지만 5,875,000(원제곱)이라는 큰 숫자의 분산은 납득이 어렵습니다.
• 큰 숫자도 문제지만 더 큰 문제는 원제곱입니다. 우리가 사는 세상 어디서도 원제곱을 쓰는 곳은 없습니다.
• 통계학자가 차이를 설명하기 위해서 만든어 낸 단위죠.
• 어쩔 수 없이 그대로 써야 할까요? 아니 제곱근으로 해결할 수 있습니다.

5,875,000(원제곱)의 제곱근 = 2,424원

• 마법처럼 단위가 원제곱에서 원으로 돌아오고 엄청나게 크던 숫자도 뭔가 납득한 만한 수준으로 줄어들었습니다.
• 분산에 제곱근을 씌워서 단위 문제를 해결한 이 숫자를 표준편차(Standard deviation) 라고합니다.
• 표준편차가 클수록 관측치들이 평균으로부터 더 멀리 떨어져 있다는 뜻이죠.
• 두 값의 의미는 크게 다르지 않지만, 표준편차가 훨씬 덜 부담스럽습니다.

part 1

차이를 확인하는 데이터 요약

순서대로 한줄서기

정렬과 순서 통계량

• 크기에 따라 순서대로 줄 세우는 과정을 정렬이라고 합니다.
• 오름차순으로 정렬된 값을 통계학에서는 순서통계량(order statistics) 이라고 부릅니다.
• 그리고 그중에서 가장 먼저 나오는 값, 즉 가장 작은 값을 최솟값(Minimum), 가장 나중에 나오는 값, 즉 가장 큰 값을 최대값(Maxsimun) 이라고 특별한 이름을 지어줬습니다.

분위수

• 경쟁에서는 점수가 중요한 것이 아니라 위치가 중요합니다.
• 내 점수를 기준으로 나보다 점수가 낮은 사람들과 높은 사람들로 나뉘는 데요. 이렇게 기준이 되는 특정한 점수들을 분위수(Quantile) 라고 합니다.
• 가장 대표적인 분위수가 100등분 기준, 기호 %를 사용하는 백분위수(Percentile) 입니다.
• 최솟값은 0% 지점이 되고, 최대값은 모든 관측치가 최대값보다 작으니 100% 지점이 됩니다.

사분위수와 다섯 숫자 요약

• 분위수를 데이터 분석에 어떻게 활용해야 할까요?
• 50% 지점에 있는 값을 기준으로 관측치들이 정확히 반반으로 나뉘기 떄문에 중앙값(Median) 이라는 이름을 붙여줍니다.
• 0%, 25%, 50%, 75%, 100% 로 총 5개의 지점을 만듭니다. 이 5개의 지점은 데이터를 정확히 4등분 합니다.
• 그래서 사분위수(Quartile)라는 특별한 이름을 지어줬습니다.
• 이처럼 하나의 연속형 변수로 최솟값, Q1, 중앙값, Q3, 최대값이라는 숫자 다섯 개를 계산하고 의미를 찾는 과정을 다섯 숫자 요약(Five number summary) 이라고 합니다.

상자그림

• 구간의 갈이가 모두 똑같지 않습니다. 똑같이 25명씩 들어가 있지만 길이가 긴 구간이 있고 상대적으로 짧은 구간도 있습니다.
• 구간이 널찎하면 관측치가 드문드문 퍼져 있다는 뜻이고 구간이 좁으면 관측치가 빽빽하게 들어 있따는 뜻이죠.
• 관측치가 빽빽하다, -> 경쟁이 치열하다.

히스토그램

• 히스토그램은 상자그림과 달리 먼저 구간을 적절히 나눕니다. 그리고 각 구간에 포함되는 관측치가 몇 개나 있는지 개수를 세어 도수분포표(Frequency distribution table)를 만들고, 이 표를 그림으로 표현합니다.
• 가령 75~85점의 중상위권에 연습생들이 많이 몰려 있고 85점 이상의 고득점 연습생 수가 적다는 걸 알 수 있습니다.

Part 1

|이름|성별|몸무게|
|김철수|여|48|
|이영희|남|80|

치킨 뜯고 공부하자 100일 프로젝트 대망의 첫날

이포스팅은 루비출판사에서 진행하는 공부하고 치킨 먹는 프로젝트의 후원을 받습니다.^^ http://m.post.naver.com/viewer/postView.nhn?volumeNo=12359301&memberNo=38315694&vType=VERTICAL

머릿말

part1

머릿말. 데이터 분석을 배우기 위해서 우리는 어디서부터 시작해야 할까요?

• 아무리 복장합 데이터 분석도 목적과 과정을 살펴보면 어떤 차이를 확인하고 설명하려 합니다.
• 통계학은 차이를 수학이라는 도구로 풀어냅니다.

프롤로그

1. 문법보다 회화
2. 차이를 이하해기 위한 통계
   • 진짜 목표는 데이터 속에 있는 차이는 확인하고 설명하는 것.
3. 불확실성을 설명하는 통계
4. 과거와 현재, 미래가 소통하는 언어

목차

PART 1 차이를 확인하는 데이터 요약

1. 줌아웃
2. 날줄과 씨줄
   • 데이터의 구성, 데이터와 데이터 공간
   • 알파벳을 활용한 예제 데이터의 표현, 기술 통계량과 변수 요약
3. 순서대로 한줄서기
   • 정렬과 순서 통계량, 분위수, 사분위수와 다섯 숫자 요약, 상자그림, 히스토그램
4. 더치페이와 N빵
   • 평균, 분산, 표준편차
5. 물수능과 불수능
   • 표준화, 표준화 예제
6. 먹고 싶은거 먹어, 난짜장
   • 동전던지기, 파이차트와 막대 그래프
7. 0.000012%의 꿈, 로또
   • 확률, 확률을 활용한 당첨 번호 예측, 데이터 분석과 확률

PART 2 차이를 설명하는 통계 개념

1. 범인은 이 안에 있다.
2. 부전자전, 유전 연결고리
   • 산점도, 상관관계, 상관계수
3. 40% 니가 하면 나도한다.
   • 교차표, 행, 백분율과 열 백분율, 열지도, 독립
4. 최저가, 알고 보니 옵션가
   • 조건부 확룰과 심슨의 역설
5. 아낌없이 주는 의사결정 나무
   • 모자이크 그림, 의사결정나무 모형
6. 점심 뭐 먹지?
   • ABCDEF 테스트, 분산과 분산분석

PART 3 차이를 예측하는 통계 모형

1. 우연과 운명 사이
2. 지구는 우주의 티끌
   • 표본과 모집단 통계량과 분포, 자연스러운 확률
3. 웬만해선 이길 수 없다.
   • 유의수준, 필요학과 같은 분포, 키의 히스토그램 정규분포
4. 남자평균 174.9cm, 여자평균 162.3cm
   • 표본평균의 표준편차, 표본평균의 표준편차 계산, t-값과 t-분포
   • t-분포, p-값과 t-테스트
5. 관계 검증을 위한 테스트
   • t-검정을 활용, 카이제곱분포를 활용한 독립성검정
   • F-분포를 활용한 분산분석
6. 아빠 키유전 확률, 25%
   • 다시 한번 상관계수, 선형회귀모형, 부모 맘 같지 않은 자식

PART 4 데이터 분석 도구, R

1. 그것이 R고싶다.
2. R 시작하기
   • R설치, R Studio 설치, R Studio 실행
3. 순서대로 살펴보는 BR31
4. R로 분석 다시 보기
   • 하나의 연속형 변수를 요약하기, 하나의 변주형 변수를 요약하기
   • 두 개의 범주형 변수의 관계 찾기, 두개의 연속형 변수의 관계 찾기
   • 차이를 설명하는 간단한 통계 모형 살펴보기
5. 대학만 가면 끝일 줄 알았는데

알고리즘 스터디

부분합(partial sum)

17.1 도입

• N 명의 시험 성적을 내림차순 으로 정렬해준 배열 scores[]가 있을 때 평균 average(a, b)를 구한다고 하자. 일반적인 방법은scores[a]~scores[b] 를 더한 뒤 이것을 b-a+1로 나누는 것이다. 이렇게 하면 반복문의 수행 횟수를 최대 O(N)이 된다.
• 평균 점수를 한 번 계산할 거라면 이걸로 충분하지만 여러 번 호출하게 될 거라면 이것을 좀 더 최적화 할 수 없나 생각하게 된다.
• 이럴때 유용하게 사용되는 것이 부분합(partial sum) 이다.

부분합은은 다음 처럼 정의 할 수 있다.

psum[i] = ∑(j=0,i)scores[j]

다음 표는 한 예제 배열 scores[]의 각 원소와 해당 배열의 부분합을 보여준다.

psum을 미리 계산해 두면 scores[]의 특정 구간의 합을 O(1)에 구할 수 있다. scores[a]부터 scores[b]까지의 합을 다음과 같이 얻으면 된다.

psum(b) - psum(a-1)

• 단순한 아이디어지만 부분 합은 종종 아주 유용하게 이용된다.

부분합 계산하기

• 구간합을 빠르게 계산하기 위해 구간 합을 미리 계산해 둔다.
• 아래 코드 17.1의 partialSum()은 구간합을 미리 구하는 예제이다.
• 반복문을 통해 구간 합을 구하기 위해 최대 O(N)의 시간이 걸린다는 점을 돌이켜 보면, 구간합을 두 번 이상 구할 때는 대부분의 경우 부분합을 사용하는 편이 이득임을 알 수 있다.

부분 합 계산하기

코드 17.1 부분합을 계산하는 함수와 이를 이용해 구간을 계산하는 함수의 구현

vector<int> partialSum(const vector<int>& a){
    vector<int> ret(a.size());
    ret[0] = a[0];
    for(int i = 1; i < a.size(); ++i)
        ret[i] = ret[i-1] + a[i];
    return ret; 

int rangeSum(const vector<int>&psum, int a, int b){
    if(a==0) return psum[b];
    return psum[b]-psum[a-1];
}

부분 합으로 평균 계산하기

• 코드 17.1 의 rangeSum()은 특정 구간은 O(1)로 계산한다. rangeSum()의 결과를 b-a+1로 나누면 해당 구간의 평균을 쉽게 구할 수 있다.

1/(b-a+1) * rangeSum(psum, a,b)

부분 합으로 분산(variance) 계산하기

• 배열 A[]의 구간 A[a … b] 의 분산은 다음과 같은 식으로 정의된다.

v = 1 / (b-a+1) * ∑ (i=a,b) (A[i] - m(a,b))^2

• m(a,b)는 해당구간의 평균이다.
• 이것만으로 분산을 계산하기는 힘들다. 그러나 이 식을 다음과 같이 정리해보자

v = 1/(b-a+1) * ∑ (i=a,b) (A[i] - m(a,b))^2 
= 1/(b-a+1) * ∑ (i=a,b) (A[i]^2 - 2A[i] *m(a,b) + m(a,b)^2) 
= 1/(b-a+1) * ( ∑ (i=a,b)A[i]^2 - 2m(a,b)* ∑ (i=a,b)A[i] + (b-a+1)m(a,b)^2)

• 이때 괄호안의 세계의 항 중, 가운데 항과 오른쪽 항은 psum을 이용해 쉽게 계산 할 수 있다. 문제가 되는 것은 A[i]^2의 합인데, 이것 또한 A[]의 각 제곱의 부분합을 저장하는 배열을 미리 만들어 두면 O(1)에 계산 할 수 있다.

코드 17.2 배열의 부분합과 제곱의 부분합을 입력받고 특정 구간의 분산을 계산하는 함수의 구현

    // A[]의 제공의 부분 합 벡터 sqpsum, A[]의 부분 합 벡터 psum이 주어질 때
    // A[a..b]의 분산을 반환한다.
    double variance(const vector<int>& sqpsum,
            const vector<int>& psum, int a,int b){
        // 우선 해당 구간의 평균을 구한다.
        double mean = rangeSum(psum, a, b) 
                / double(b-a+1)
        double ret = rangeSum(sqpsum, a, b) 
                - 2 * mean * rangeSum(psum, a, b) 
                + (b-a+1) * mean * mean;
        return ret / (b-a+1)

2차원으로의 확장

• 2차원 배열 A[][]이 주어질 때, A[y1,x1] 에서 A[y2,x2]까지의 직사각형 합은 다음과 같이 부분합 배열을 사용해 빠르게 구할 수 있다.

psum[y,x] = ∑(i=0,y)∑(j=0,x)A[i,j]

• 다시 말해 psum[y,x]는 (0,0)을 위쪽 위칸, (y,x)를 오른쪽 아래 칸으로 갖는 직사각형 구간에 포함된 원소들의 합이다.
• psum[][]을 미리 계산해 두면 2차원 배열 에서도 우리가 원하는 구간의 합을 아래 식과 같이 쉽게 구할 수 있다.

sum(y1, x1, y2, x2) = psum[y2,x1-1] - psum[y1-1,x2] - psum[y2,x1-1] + psum[y1-1,x1-1]

코드 17.3 부분 합을 이용해 2차원 배열의 구간 합을 구하는 함수의 구현

    // 어떤 2차원 배열 A[][]의 부분합 psum[][]이 주어질 때,
    // A[y1,x1]과 A[y2,x2]를 양 끝으로 갖는 부분 배열의 합을 반환한다.
    int gridSum(const vector<vector<int>>& psum, int y1, int x1, int y2, int x2){
        int ret = psum[y2][x2];
        if(y1>0) ret -= psum[y1-1][x2];
        if(x1>0) ret -= psum[y2][x1-1];
        if(y1>0 && x1>0 ) ret += psum[y1-1][x1-1];
        return ret;
    }

예제 : 합의 0에 가장 가까운 구간

• 양수와 음수가 모두 포함된 배열 A[]가 있을 때, 그 합이 가장 가까운 구간을 찾는 문제를 풀어 보자.

• 0에 가장 가까운 구간은 A[2]~A[5]로 그 합은 1이다.
• 이런 구간을 찾는 한 가지 방법은 A의 모든 구간을 순회하면서 각각의 합을 계산하는 것이다.
• 이렇게 하면 배열 길이 N에 대해 O(N^2)의 시간이 걸린다.
• 부분합 을 사용하면 이 분제를 아주 쉽게 풀 수 있다.
• A[i] ~ A[j]의 구간의 합을 다음과 같이 표현 할 수 있다.

∑(k=i, j)A[k] = psum[j] - psum[i-1]

• 이 값이 0에 가깝다는 말은 psum[]의 두 값의 차이가 가장 적다는 뜻이다.
• 주어진 배열에서 가장 가까운 두 값을 찾기 위한 간단한 방법은 이 배열을 정렬한 뒤 인접한 원소들을 확인하는 것이다.
• 정렬은 O(NlgN)시간에 수행할 수 있다.
• i-j의 구간 합 계산은 O(NlgN)시간에 수행할 수 있다.
• 부분합을 구하는 것과 인접한 원소들을 확인하는 것 모두 O(N)에 할 수 있으니 이 알고리즘 수행시간은 O(NlgN) 이 된다.

코드 17.4 합이 0에 가장 가까운 구간을 찾는 코드

    # python으로 구현됨
    # 부분합 배열 구함
    psum = partialSum(list)

    # 구간합 구하기
    sum = rangeSum(psum, 0, list.__len__()-1)

    len =  list.__len__() - 1
    rangelist = []

    for i in range( len ):
        for j in range( len )[i+1:]:
            rsum = rangeSum(psum, i, j)
            # 구간 최소 값과 인덱스 저장
            rangelist.append([abs(rsum),i,j])

    rangelist.sort()

    # 구간 최소값과 인덱스 출력
    print(rangelist[0])

출저 : 알고리즘 문제 해결 전략

알고리즘 스터디

정수론(number theory)

14.1 도입

• 정수론 : 정수의 성질을 연구대상으로 하는 수학의 한 분야

14.2 소수

• 소수(Prime number) 는 정수론의 가장 중요한 연구 대상 중 하나로, 양의 약수가 1과 자기 자신 두개 뿐인 자연수를 의미한다. 
  예) 7
• 합성수(composite number) 소수의 반대발로, 세 개 이상의 양의 약수를 갖는 자연수를 의미한다. 
  예) 9
• 1은 소수도 아니고 합성수도 아니다. (주의!)

소수 판별

• 소수에 관한 가장 기초적인 문제
• 이 문제를 풀기 위한 많은 연구가 진행되어 있지만, 대부분 효율적인 방법들은 너무 복잡한 관계로 프로그래밍 대회에는 출제되지 않음.
• 따라서 여기서는 단순한 방법을 사용함
• 합성수 n이 p * q 로 표현 될 때 한 수는 항상 sqrt(n) 이하 ,다른 한 수는 항상 sqrt(n) 이상이라는 점을 이용하면 n-1까지 순회하지 않고 sqrt(n) 까지만 순회하도록 최적화 할 수 있다.
• 2를 예외로 처리하는 이유는 2가 유일한 짝수 소수이기 때문에 2만 예외 처리하면 그 외의 모든 짝수를 합성수 라고 판단 할 수 있기 때문이다.

코드 14.1 O(sqrt(n)) 시간에 동작하는 소수 판별 알고리즘

    // 주어진 자연수 n이 소수인지 확인한다.
    bool isPrime(int n){
        // 예외 처리 : 1과 2는 예외로 처리한다.
        if( n <= 1) return false;
        if( n == 2) return true;
        // 2를 제외한 모든 짝수는 소수가 아니다.
        if( n % 2 == 0) return false;
        // 2를 제외했으니 3이상의 모든 홀수로 나누어보자.
        int sqrtn = int(sqrt(n))
        for(int div = 3;div <= sqrtn; div +=2)
            if(n % div == 0 )
                return false;
            return true;

• isPrime()을 최적화할 수 있는 방법에는 여러 가지가 있다.
• 2와 3을 제외한 모든 소수는 6k +-1의 형태를 띈다는 사실을 이용할 수도 있다.

소인수 분해

• 소인수 분해 : 한 합성수를 소수의 곱으로 표현하는 방법.

코드 14.2 간단한 소인수 분해 알고리즘

 vector<int> facterSimple(int n){
     vector<int> ret;
     int sqrtn = (int)sqrt(n);  
     for(int div = 2; div <= sqrtn; ++div)
         while( n % div == 0){
             n /= div;
             ret.push_back(n)
        }
    if( n>1 ) ret.push_back(n);
    return ret; 

에라토스테네스

• 에라토스테네스 (BC 276년 ~ BC 194년) 
  
• 에라토스테네스는 고대 그리스의 수학자이자 천문학자
• 지구의 크기를 처음으로 계산해 냈으며, 또 소수를 걸러내는 에라토스테네스의 체를 고안함
• 엘리트지만 2인자로 유명함. 그리스 계의 수학계의 콩라인. 당시 별명 베타.

에라토스테네스의 체

• 주어진 수를 N이라 할때, 2~N 목록에서 지워지지 않은 수들을 순회하며 이 수의 배수를 지우기를 반복한다.

  시작	2	3	4	5	6	7	8	9	…
  2의 배수 지우기	2	3	X	5	X	7	X	9	…
  3의 배수 지우기	2	3	X	5	X	7	X	X	…

• 각 수 m이 소수인지 찬단하기 위해 sqrt(n)까지의 모든 수를 나눠보는 대신, 소수를 찾을 때마다 그 배수들을 지우는 형태로 동작하기 때문에 훨씬 빠르게 수행된다.

최적화 방안 
- 지워지지 않은 수를 찾을 때 n이 아니라 sqrt(n) 까지만 찾는다. 
- i의 배수들을 지울 때 2 * i 에서 시작하는 것이 아니라 i * i 에서 시작한다. 2 * i에서 2의 배수 들은 모두 지워졌을 것이고 3 * i 는 3의 배수를 지울 때 이미 지워졌을 테니까.

코드 14.3 에라토스테네스의 체

    int n;
    bool isPrime[MAX_N+1];
    // 가장 단순한 형태의 에라토스테네스의 체의 구현
    // 종료한 뒤 isPrime[i]=i가 소수인가?
    void eratosthenes(){
        memset(isPrime, ture, sizeof(isPrime));
        // 1은 항상 예외 처리
        isPrime[0]=isPrime[1]=false;
        int sqrt=int(sqrt(n))
        for(int i=2; i<sqrtn;++i)
            // 이 수가 아직 채워지지 않았다면
            if(isPrime[i])
                //i의 배수 j들에 대해 isPrime[j]=false로 둔다.
                // i*i 미만의 배수는 이미 지워졌으므로 신경 쓰지 않는다.
                for(int j=i*i; j<=n; j+= i)
                    isPrime[j]=false;   
    }

예제 에라토스테네스의 체를 이용한 빠른 소인수 분해

• 에라스토테네스의 체를 응용해 훨씬 빠르게 소인수 분해를 수행 할 수 있다.
• 최적화의 비결은 체에서 각 숫자가 소수인지 합성수 인지만을 기록하는 것이 아니라, 각 숫자의 가장 작은 소인수를 같이 기록해 두 는 것이다.

코드 14.4 에라토스테네스의 체를 이용한 빠른 소인수 분해

    // minFactor[i]=i 의 가장 작은 소인수(i가 소수인 경우 자기 자신)
    int minFactor[MAX_N]
    // 에라토스테네스의 체를 수행하면서 소인수분해를 위한 정보도 저장한다.
    void eratosthenes2(){
        // 1은 항상 예외 처리
        minFactor[0]=minFactor[1]=-1;
        // 모든 숫자를 처음에는 소수로 표시해 둔다.
        for(int i=2; i<=n; ++i)
            minFactor[i]=i;
        // 에라토스테네스의 채를 수행한다.
        int sqrtn = int(sqrt(n))
        for(int i =2; i<sqrtn; ++i){
            if(minFactor[i]==i){
                for(int j=i*i; j<=n; j+=i)
                // 아직까지 본 적 없는 숫자인 경우 i를 써둔다.
                if(minFactor[j]=j)
                    minFactor[j]=i
            }
        }
    }
    // 2 이상의 자연수 n을 소인수 분해하는 결과를 반복한다.
    vector<int> fector(int n){
        vector<int> ret;
        // n이 1이 될 때까지 가장 작은 소인수로 나누기를 반복한다.
        while(n>1){
            ret.push_back(minFactor[n]);
            n /= minFactor[n]
        }
        return ret;
    }

출저 : 알고리즘 문제 해결 전략

평가

머신러닝을 이용하여 모델 구현 후 결과가 좋은 모델인지 평가 하기 위해 각 모형이 얼마나 좋은 지 말해주는 점수가 필요하다.

대표적으로는 프리시즌(Precision)과 리콜(recall)이 있다.

프리시즌(Precision) - 정밀도

• 정의 : Positive라 예측한 사례 중 TruePostive 비율

• 점수 구하는 공식 : TruePositive / ( TruePositive + FalsePsitive )

리콜(Recall) - 재현율

• 정의 : True라 예측한 사례 중 TruePositive 비율 

• 점수 구하는 공식 : TruePositive / ( TruePositive + TrueNegative )

에러

• ErrorType1 : 실제로는 False인데 Positive로 예측한 사례

• ErrorType2 : 실제로는 True인데 Negative로 예측한 사례

• 경우에 따라 ErrorType 1, 2 중 더 치명적인 Error가 다를 수 있음

예)

• ErrorType1이 더 치명 적인 경우 : 중고 자동차를 구입 할때 좋은 자동차라 예측하고 구매하였지만 좋지 않은 자동차였을 경우. (좋은 중고 자동차를 나쁘다 판단하여 안사면 손해는 없지만 나쁜 중고자동차를 좋다고 판단하여 구매하면 손해가 크다)

• ErrorType2가 더 치면 적인 경우 : 암 진단시 건강한 사람이라고 예측 하였는데 암 환자인경우

• 예시에서 볼 수 있듯이 경우에 따라 적절한 평가 지표를 사용해야 한다.

• 프리시즌과 리콜 외에도 Accuracy, Kappa 등의 지표가 있다.

1. 협업 필터링

- 도메인 지식 필요없음

- 제품 종류가 많아 추천이 잘된다.

2. 컨텐츠 기반

- 도메인 지식 필요 

- 다양한 메타데이타 (구성하기 어려울 수 있음)

3. 협업필터링 + 컨텐츠기반

4. 차원 축소

5. 평가 방식

- 정확도 (평점 예측)

- 만족도 (클릭율, 구매율)

결론 : 일반적인 이야기

알고리즘 스터디

조합탐색(combinatorial search)

11.1 도입

조합탐색

• 완전탐색을 포함해 유한한 크기의 탐색 공간을 뒤지면서 답을 찾아 내는 알고리즘
• 탐색 공간(search space) 부분답과 완성된 답의 집합
• 목표 : 기본적으로 모두 최적해가 될 가능성이 없는 답들을 탐색하는 것을 방지하여 만들어 봐야 할 답의 수를 줄이는 것을 목표로 함.

조합탐색 최적화 기법

• 가지치기(pruning) : 탐색 과정에서 최적해로 연결될 가능성이 없는 부분을 잘라낸다. 
  예) 외판원 문제를 추는데, 길이가 10인 경로를 이미 찾아냈다고 하면, 더이상 탐색하지 않고 탐색을 중단하는 것

• 탐색의 순서를 바꾸거나, 탐색 시작 전에 탐용법을 이용해 적당히 좋은 답을 우선 찾아낸다.

11.2 조합 탐색 기법들

여행하는 외판원 문제(TSP)를 푸는 완전탐색 알고리즘에 기법들을 적용하면서 변화하는 수행 속도를 관찰해본다.

• 입력파일 
  소행, 중형, 대형, 초대형 네가지 입력. 
  각각 n=12, n=16, n=20, n=24 크기의 입력 20개씩을 가지고 있으며 각 입력은 2차원 평면세 n개의 점을 임의로 배치하고 이들 사이의 거리를 재서 만듬

목표는 이 동적 계획법 알고리즘 보다는 더 빨리 답을 얻는 것

- 입력이 커질수록 수행시간이 급격히 증가하는 것을 볼 수 있다. 
- 만약 컴퓨터의 메모리가 모자랐다면 결국 가상 메모리를 사용 해야 했을 테고, 결과적으로 상상할 수 없을 정도로 느려졌을 것이다.

조합 탐색 뼈대의 구현

코드 11.1 TSP를 해결하는 완전 탐색의 구현

const double INF = le200;
const int MAX = 30;
int n; // 도시의 수
double dist[MAX][MAX]; // 두 도시간의 거리를 저장하는 배열
// 지금까지 찾은 최적의 해
doubel best;
void search(Vector<int>& path, vector<bool>& visited, double currentLength){
    int here = path.back();
    // 기저 사례 : 전체 도시를 모두 순회했을 경우 종료
    if(path.size() == n){
        best=min(best, currentLength+dist[here][0]);
        return;
    }
    for(int next = 0; next < n; ++next){
        if(visited[next]==true) continue;
        push.push_back(next);
        visited[next]=true;
        search(path, visited, currentLnegth + dist[here][next]);
        visited[next]=false;
        path.push_back(next);
    }
}
void solve(){
    best = INF;
    vector<int> path = vector(1,0);
    Vector<bool> visited = vector(n, false);
    visited[0]=true;
    search(path, visited,0);
    return best;
}

• 이와 같은 단순한 알고리즘의 수행 속도는 어떨까? search가 만드는 경로의 수는 (n-1)!개.
• 11!는 약 4천만 정도되므로 소형 입력은 그럭저럭 풀수 있다.
• 중형 입력 경로는 12*13*14*15 ~ 30,000 배 는다. -> 풀기 불가능

최적해보다 나빠지면 그만두기

간단한 가지치기 : 지금까지 찾은 가장 좋은 답 이상일 경우 중단 
if(best <= currentLength) return;

간단한 휴리스틱을 이용한 가지치기

• 휴리스틱(heuristic) : 경험에 의거한 문제 풀이 기법. 사람이 어림짐작으로 문제를 푸는 과정을 알고리즘으로 옮긴 것이 휴리스틱이라고 생각하면 얼추 비슷하다.

• 과소평가(underestimate)하는 휴리스틱, 난관적인 휴리스틱(optimistic heuristic) 낙관적인 휴리스닉

휴리스틱 함수 작성하기

• 남은 도시를 모두 방문할 필요 없이, 가장 멀리 있는 도시 하나만 방문했다가 시작적으로 돌아가도 된다.
• 남은 도시들을 방문하는 방법이 꼭 일렬로 연결된 형태가 아니어도 된다.

단순한 휴리스틱 함수 구현

코드 11.2 단순한 휴리스틱을 이용한 가지치기의 구현

가까운 도시부터 방문하기

코드 11.3 가까운 정점부터 방문하는 최적화의 구현

지나온 경로를 이용한 가지치기

코드 11.4 지나온 경로를 이용하는 두 가지 가지치기 전략의 구현

MST 휴리스틱을 이용한 가지치기의 구현

코드 11.5 MST 휴리스틱의 구현

마지막 단계 메모이제이션하기

코드 11.6 부분적으로 메모이제이션을 사용하는 최적화의 구현

// 남은 도시의 수가 CACHED_DEPTH 이하면 동적 계획법으로 바꾼다.
const int CACHED_DEPTH = 5;
// dp(here, visited)=cache[here][남은 도시의 수][visited]
map<int,double> cache[MAX][CACHED_DEPTH+1]
/// here : 현재 위치
// visited : 각 도시의 방문 여부 
// 일 때, 나머지 도시를 모두 방문하고 시작점으로 돌아가는 최단 경로의 길이를 반환한다.
double dp(int here, int visited){
    // 기저사례 : 더 방문할 도시가 없으면 시작점으로 돌아간다.
    if(visited == (1<<n)-1) return dist[here][0];

    // 메모이제이션
    int remaining = n - __builtin_popcount(visited);
    double& ret = cache[here][remaining][visited];
    if(ret > 0) return ret;
    ret = INF;

    // 다음 도시를 하나씩 시도한다.
    for(int next = 0; next < n; ++next){
        if(visited & (1<<next)) continue;
        ret = min(ret, dp(next, visited + (1<<next)) + dist[here][next]);
    }
    return ret;
}

void search(vector<int>& path, int visited, double currentLength) {
// 생략
// 기저 사례 : 남은 도시 수가 CACHED_DEPTH 이하면 동적 계획법으로 바꾼다.
    if(path.size() + CACHED_DEPTH >= n){
        best = min(best, currentLength + dp(path.back(), visited));
        return;
    }
    // 생략
}
double solve(){
    // 생략
    // cache 초기화
    for(int i = 0; i < MAX; ++i)
        for(int j = 0; j <= CACHED_DEPTH; ++j)
            cache[i][j].clear();
    // 생략
}

전문적 TSP 해결 기법들

• 여기서 소개한 알고리즘은 TSP를 해결하기 위한 방법과는 거리가 멈
• 실제로는 TSP만을 해결하기 위해 고안된 프로그램들 정수계획법, 선형계획법 등을 사용함.

출저 : 알고리즘 문제 해결 전략