알고리즘 스터디

부분합(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;
    }

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

알고리즘 스터디

조합탐색(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만을 해결하기 위해 고안된 프로그램들 정수계획법, 선형계획법 등을 사용함.

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

알고리즘 스터디

탐욕법

10.1 도입

탐욕법(greed method)은 가장 직관적인 알고리즘 설계 패러다임 중 하나

• 탐욕법은 각 단계마다 지금 당장 가장 좋은 방법만을 선택한다.
• 탐욕적 알고리즘은 많은 경우 최적해를 찾지 못한다.
• 따라서 탐욕적 알고리즘이 사용되는 경우는 크게 다음 두 가지 로 제한된다. 
  
  1. 탐욕법을 사용해도 할살 최적해를 구할 수 있는 문제를 만난 경우, 탐욕법은 동적계획법보다 수행 시간이 훨씬 빠르기 때문에 유용하다.
  2. 시간이나 공간적 제약으로 인해 다른 방법으로 최적해를 찾기 너무 어렵다면 최적해를 적당히 괜찮은 답(근사해)을 찾는 것으로 타협할 수 있다.

예제 : 회의실 예약

• 회사에 회의실이 하나 밖에 없는데, n(<=100)개의 팀이 각각 회의하고 싶은 시간을 그림 10.1과 같이 제출했다고 할때, 이 중 서로 겹치지 않는 회의들만을 골라서 진행해야 한다. 최대 몇개나 선택할 수 있을까?

무식하게 풀 수 있을까?

• 이 문제를 무식하게 푸는 방법은 모든 부분 집합을 하나하나 만들어 보며 그중 회의들이 겹치지 않는 답들을 걸러내고 그중 가장 큰 부분 집합을 찾아낸다.
• 그러나 집합의 크기가 n일 때 부분 집합의 수는 2^n이기 때문에 n이 30만 되어도 시간 안에 문제를 풀기는 힘들다.

탐욕적 알고리즘의 구상

• 이 문제를 해결하는 탐욕적인 방법은 길이와 상관 없이 가장 먼저 끝나는 회의부터 선택하는 것이다. 
  
  1. 목록 S에 남은 회의 중 가장 일찍 끝나는 회의 S(min)을 선택한다.
  2. S(min)과 겹치는 회의를 S에서 모두 지운다.
  3. S가 텅 빌 때까지 반복한다.

정당성의 증명 1 : 탐욕적 선택 속성

• 탐욕적 알고리즘의 정당성 증명은 많은 경우 일정한 패턴을 가진다.
• 우리가 처음으로 증명해야할 속성은 동적 계획 법처럼 답의 모든 부분을 고려하지 않고 탐욕적으로만 선택하더라도 최적해를 구할 수 있다는 것이다. -> 탐욕적 선택속성(greed choice property)
• 앞서 제한 한 알고리즘의 경우, 탐욕적 선택 속성이 성립한다는 말은 다음 조건이 성립한다는 의미이다.

가장 종료 시간이 빠른 회의 S(min)를 포함하는 최적해가 만드시 존재한다.

정당성의 증명 2 : 최적 부분 구조

• 항상 최적의 선택만을 내려서 전체 문제의 최적해를 얻을 수 있을음 보여야 한다.
• 부분 문제의 최적해에서 전체 문제의 최적해를 만들 수 있음을 보여야한다.

구현

• 전체 시간 복잡도 O(n^2)

코드 10.1 회의실 예약 문제를 해결하는 탐욕적 알고리즘

// 각 회의는 [begin, end] 구간 동안 회의실을 사용한다.
int n;
int begin[100], end[100];
int schedule(){
    // 일찍 끝나는 순서대로 정렬한다.
    vector<pair<int,int>> order;
    for(int i=0; i<n; ++i)
        order.push_back(make_pair(end[i], begin[i]));
    sort(order.begin(), order.end());
    //earliest : 다음 회의가 시작할 수 있는 가장 빠른 시간.
    //selected : 지금까지 선택한 회의의 수
    int earliest = 0, selected = 0;
    for(int i=0; i<order.size()l ++i){
        int meetingBegin = order[i].second, meetingEnd = order[i].first;
        if(earlist <= meetingBegin){
            //earlist 를 마지막 회의가 끝난 시간 이후로 갱신한다.
            elarlist = meetingEnd;
            ++selected;
        }
    }
    return selected;
}

• 위 알고리즘은 O(nlogn) 시간이 걸리는 정렬 후에 선형 시간만이 걸리는 선택 과정을 통해 최적해를 찾아낸다.

난 동적 계획법으로 풀었는데?

schedule(idx) = meeting[idx] 혹은 그 이전에 끝나는 회의들 중 선택할 수 있는 최대 회의 수

• schedule()은 매 단계에서 meeting[idx] 를 선택할지 여부를 결정한다. idx번 회의가 시작하기 전에 끝나는 회의들 중 마지막 회의의 번호를 before[idx] 에 저장했다고 하면 선택하지 않은 경우의 최적해는 schedule(idx-1)로, 선택할 경우의 답은 1+schedule(before[idx])로 재귀적으로 표현할 수 있다.
• before[]를 만드는 데 O(nlogn)의 시간이 걸리고, schedule()의 수행에는 2O(n)의 시간이 걸리니 사실 탐욕법과 다를 것이 없다.
• 많은 경우 동적 계획법이 아니라 탐욕법을 사용하는 이유는 동적 계획법이 필요한 메모리나 시간이 과도하게 크기 때문이다.

예제 : 출전 순서 정하기

- 어느순서대로 선수들을 내보내야 승수를 최대화 할 수 있을까?

무식하게 풀 수 있을까?

• 이 문제에는 n!개의 답이 있어서 n이 조금만 커져도 답의 개수가 너무 많아서 시간안에 다 셀 수 없다.

그렇다면 동적 계획법은 어떨까?

order(taken) = 각 한국 팀 선수를 이미 순서에 추가 했는지 여부가 taken에 주어질 때, 남은 선수들의 적절히 배치해서 얻을 수 있는 최대 승수

• 시간복잡도 O(n^2) -> 그래도 느리다.

탐욕적 알고리즘의 구상

• 맨 앞 경기부터 한 명씩 출전할 한국 선수를 정한다. 상대방 선수를 이길 수 있는(레이팅이 같거나 높은) 한국 선수가 있는 경우 그중 레이팅이 가장 낮은 선수를 상대방 선수와 경기시킨다. 만약 상대방 선수가 한국팀의 모든 선수보다 레이팅이 높다면 남은 선수 중 가장 레이팅이 낮은 선수와 경기시킨다.

탐욕적 선택 속성 증명

항상 우리가 하는 선택을 포함하는 최적해가 존재한다는 걸 증명한다.

1) 질 수 밖에 없는 경기 (A: 가장 레이팅이 낮은 선수)

-> A,B 를 바꿔도 승수가 줄어드는 일이 없다,

2) 이길 수 밖에 없는 경기(A:가장 레이팅이 낮은 선수)

-> A, B를 바꿔서 승리할 경우 원래 순서 또한 최적해임

두 경우 모두 우리의 선택은 최다 승을 보장함

최적 부분 구조 증명

• 첫 번째 경기에 나갈 선수를 선택하고 나면 남은 선수들의 경기에 배정하는 부분 문제를 얻을 수 있다. 이때 남은 경기에서도 당연히 최다승을 얻는 것이 좋으니 최적 부분 구조도 자명하게 성립한다.

구현

코드 10.2 출전 순서 정하기 문제를 해결하는 탐욕적 알고리즘

int order(const vector<int>& russion,
          const vector<int> &korean){
    int n = russion.size(), wins = 0;
    // 아직 남아 있는 선수들의 레이팅
    multiset<int> ratings(korean.begin(), korean.end());
    for(int rus=0;rus<n;rus++){
        // 가장 레이팅이 높은 한국 선수가 이길 수 없는 경우
        // 가장 레이팅이 낮은 선수와 경기 시킨다.
        if(*ratings.rbegin() < russian[rus])
            ratings.erase(ratings.begin());
        else{
            ratings.erase(ratings.lower_bound(russian[rus]));
            ++wins;
        }
    }
return wins;
}   

탐욕적 알고리즘 레시피

1. 문제의 답을 만드는 과정을 여러 조각으로 나눈다.
2. 각 조각마다 어떤 우선순위로 선택을 내려야 할지 결정한다. 이에 대한 직관을 얻기 위해서는 예제 입력이나 그 외의 작은 입력을 몇 개 손으로 풀어보는 것이 효율적이다.
3. 어떤 방식이 동작할 것 같으면 두 가지의 속성을 증명해본다. 
   a. 탐욕적 선택 속성 
   b. 최적 부분 구조

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

알고리즘 스터디

동적계획법(dynamic programming)

8.1 도입

프로그래밍 대회문제에서 가장 자주 출현하는 디자인 패러다임 중 하나

• 동적계획 법이라는 말은 최적화 문제를 연구하는 수학 이론에서 왔으며, 우리가 전산학 전반에서 일반적으로 사용하는 동적(dynamic), 혹은 프로그래밍 (programming)이라는 단어와는 아무런 관련이 없음.
• dynamic programming의 적절한 번역은 동적 계획법임

중복되는 부분문제

• 동적 계획법 접근 방법 : 큰 의미에서 분할 정목과 같은 방식을 의미함.
• 분할정복과 동적계획법 차이 : 
  
  1. 문제를 나누는 방식.
  2. 계산 결과 재활용 - 동적계획법에서 어떤 부분 문제는 두 개 이상의 문제를 푸는 데 사용 -> 속도 향상
• 캐시 : 이미 계산한 값을 저장해 두는 메모리 저장소
• 중복되는 부분 문제(overlapping subproblems) 두 번 이상 계산되는 부분 문제
• 조합폭발(combinatorial explosion) 중복문제가 분할의 깊이가 깊어질수록 지수적으로 증가하는 것.
• 동적계획법의 목적 : 조합폭발 문제를 해결하기 위해 고안된 알고리즘 설계 기법

예 ) 가장 유명한 동적계획법 이항 계수

이항 계수 점화식

( n, r ) = ( n-1, r-1 ) + ( n-1, r )

코드 8.1 재귀 호출을 이용한 이항 계수의 계산

int bino(int n, int r){
    // 기저 사례 : n=r (모든 원소를 다 고르는 경우) 혹은 r = 0 (고를 원소가 없는 경우)
    // if( n == r || r == 0 ) return 1;
    return bino( n-1, r-1) + bino( n-1, r);
}

코드 8.1의 시간복잡도

• bino내에 반복문도 없음
• bino(n,r)의 수행시간은 재귀 호출이 몇번이나 이루어지는지를 계산하면 파악할 수 있음.
• 이때 주목할 점은 이항 계수의 특성상 같은 값을 두 번 이상 계산할 일이 빈번 하다는 점임

표, 이항 계수 (n, n/2)를 계산 할 때 필요한 함수 호출의 수

메모이제이션 (memoization)

• 한번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법

코드 8.2 메모이제이션을 이용항 이상 계수의 계산

// -1로 초기화 해준다.
int cache[30][30];
int bino2(int n, int r){
    // 기저 사례
    if( r==0 || n == r ) return 1;
    // -1이 아니라면 한 번 계산했던 값이니 곧장 반환
    if( cache[n][r] != -1)
        return cache[n][r];
    return cache[n][r] = bino2(n-1, r-1) + bino2(n-1, r);
}

• 메모이제이션을 사용하면 모든 부분 문제가 한 번씩만 계산된다고 보장할 수 있기 떄문에 함수 호출 횟수가 엄청나게 감소라리라 예상할 수 있음. (위의 표 참고)

메모이제이션을 적용 할 수 있는 경우

• 참조적 투명성 (referential transparency) 
  함수의 반환 값이 그 입력 값만으로 결정되는지의 여부.
• 당연히 메모이제이션은 참조적 투명할수에 만 적용 할 수 있음.

코드 8.3 메모이제이션의 사용 예

// 전부 -1로 초기화해둔다.
int cache[2500][2500];
// a와 b는 각각 [0, 2500] 구간 안의 정수
int someObscureFunction(int a, int b){
    // 기저 사례를 처음에 처리한다.
    if(...) return ...;
    // (a,b)에 대한 답을 구한 적이 있으면 곧장 반환
    int& ret = cache[a][b];
    if(ret != -1) return ret;
    // 여기에서 답을 계산 한다.
    ...
    return ret;
}
int main(){
    // memset()을 이용해 cache 배열을 초기화 한다.
    memset(cache, -1, sizeof(cache));
}

메모이제이션의 시간 복잡도 분석

• 주먹구구 방식

  (존재하는 부분 문제의 수) * (한 부분 문제를 출 때 필요한 반복문의 수행 횟수)

• 물론 이 식은 수행시간 상한을 간단히 계산할 수 있는 방법일 뿐이며, 항상 정확하지는 않음.

분할 정복 (Divide and Conquer)

7.1 도입

분할 정복은 가장 유명한 알고리즘 디자인 패터다임

• 각개 격파라는 말로 간단히 설명 할 수 있음

분할 정복과 재귀 호출의 다른 점

• 재귀 호출 : 한 조각과 나머지 전체로 나눔
• 분할 정복 : 거의 같은 부분 문제로 나눔

분할 정복 알고리즘의 세가지 구성요소

• 문제를 더 작은 문제로 분할하는 과정(divide)
• 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge)
• 더 이상 답을 분할 하지 않고 곧장 풀 수 있는 매우 작은 문제(base case)

예제 : 수열의 빠른 합과 행렬의 빠른 제곱

• 1부터 n까지의 합을 n개의 조각으로 나눈 뒤, 
  이들을 반으로 뚝 잘라 n/2개의 조각들로 만들어진 부분 문제 두 개를 만듬

• faseSum() 
  = 1+2+…+n 
  = ( 1+2+…+n/2 ) + ((n/2+1)+…+n)

코드 7.1

// 필수조건 : n은 자연수  
// 1+2+...+n 을 반환한다.   
int fastSum(int n){  
  // 기저 사례  
  if(n == 1) return 1;  
  if(n%2 == 1) return fastSum(n-1) + n;  
  return 2*fastSum(n/2) + (n/2) * (n/2);  
}

시간 복잡도 분석

• O(lgn)

행렬의 거듭 제곱

• n*n 크기의 행렬 A 가 주어질 때, A의 거듭제공(power) A^m은 A를 연속해서 m번 곱한 것

코드 7.2 행렬의 거듭 제곱을 구하는 분할 정복 알고리즘

// 정방 행렬을 표현하는 SquareMatrix 클래스가 있다고 가정하자.
Class SquareMatrix;
// n*n 크기의 항등 행렬(identity matrix)을 반환하는 함수
SquareMatrix identity(int n);
// A^m을 반환한다.
SquareMatrix pow(const SquareMatrix& A, int m){  
    // 기저 사례 : A^0=I
    if(m == 0) return identity(A.size());
    if(m % 2 > 0) return pow(A, m-1) * A;
    SquareMatrix half = pow(A, m /2 );
return half * half;

시간 복잡도

• 곧이곧대로 m-1번 곱셈을 통해 A^m을 구하면 O(n^3m)번의 연산이 필요함.
• 분할 정복을 사용할 경우은 문제라도 어떻게 분할하느냐에 따라 시간 복잡도 차이가 커짐.
• 그림 7.2 참고, a는 m-1번 곱한것과 다를게 없음. b는 O(lgm)
• 분할정복이 큰 효율 저하는 불러오는 이유는 바로 여러번 중복되어 계산되면서 시간을 소모하는 부분이 있기 때문

예제 : 병합 정렬과 퀵정렬

• 병합정렬 
  주어진 수열을 가운데에서 쪼개 비슷한 크기의 수열 두 개로 만든 뒤 이들을 재귀호출을 이용해 각가 정렬함. 그 후 정렬된 배열을 하나로 합침으로써 정렬된 전체 수열을 얻음.

• 퀵정렬 
  배열에 포함된 수가 다른 쪽 배열의 수보다 항상 작도록 배열을 분한 함. 
  이를 위해 퀼 정렬은 파티션(partition)이라고 부르는 단계를 도입하는데, 
  이는 배열에 있는 수 중 임의의 ‘기준수(pivot)’를 지정한 후 기준보다 작거나 같은 숫자를 왼쪽 더 큰 숫자를 오른 쪽으로 보내는 과정임

• 두 정렬 알고리즘은 같은 아이디어로 정렬을 수행하지만 시간이 많이 걸리는 작업을 분할 단계에서 하느냐 병합 단계에서 하느냐가 다름.

시간복잡도 분석

• 병합정렬 
  병합에 필요한 시간 * 단계별로 필요한 시간 
  O(n) * O(lgn) = O(nlgn)

• 퀵정렬 
  시간복잡도를 구하기 까다로움 - 분할된 두 부분 문제가 비슷한 크기로 나눠진다는 보장을 할 수 없음. 
  최악의 경우 O(n^2) 
  평균 O(nlgn)

예제 : 카라츠바의 빠른 곱셈 알고리즘

시간 복잡도 분석

• 단순한 알고리즘 O(n^2)
• 빠른 곱셈 알고리즘 O(n^lg3)