알고리즘 스터디

탐욕법

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)

 카디날리티 집계(Cardinality Aggregation)?

엘라스틱서치 에서 제공하는 approximation aggregation으로 필드에서 고유한 값의 대략적인 개수를 계산한다.

HyperLogLog++(HLL) algorithm (확률적 자료구조 기반 알고리즘)

엘라스텍서치의 cardinality 는 HLL 알고리즘을 기반한다.

(wiki : https://en.wikipedia.org/wiki/HyperLogLog)

HLL 알고리즘의 특징 : 

• 정확도(precision) 설정 가능
  단, 정확도를 올릴 수록, 메모리 사용량이 증가
• cardinality가 낮은 집합일 수록 정확도가 높아진다.
• 메모리 사용량이 고정적
• 메모리 사용량은 정확도에 비례
• 
  

정확도 설정

• precision_threshold (0 ~ 40,000)
• 일반적으로 cardinality가 precision 보다 적다면 거의 항상 100% 정확
• 메모시 사용률 =  precision_threshold * 8 bytes
  
  

 그래프.1 threshold 에 따른 에러율 

성능 향상을 위한 방안

• cardinality 대상 필드를 hash 로 정의한다.
• 단 cardinality 가 크거나 string 인 경우만 효과적이다.
  
  

좀 더 자세히 

• https://www.elastic.co/guide/en/elasticsearch/reference/1.6/search-aggregations-metrics-cardinality-aggregation.html

집계(aggregation) 

• 검색 결과에 다양한 연산 적용
• RDBMS 의 groupby 와 유사
• 집계 종류에는 매트릭(metric), 버킷(bucket), 파이프라인(pipeline) 등이 있다.

0. 참고

1. 종류

1) 매트릭 (metric)

• 도큐먼트를 계산해서 처리된 값을 구한다.
• 타입 리스트
• Avg Aggregation
• Cardinality Aggregation
• Extended Stats Aggregation
• Geo Bounds Aggregation
• Geo Centroid Aggregation
• Max Aggregation
• Min Aggregation
• Percentiles Aggregation
• Percentile Ranks Aggregation
• Scripted Metric Aggregation
• Stats Aggregation
• Sum Aggregation
• Top hits Aggregation
• Value Count Aggregation

2) 버킷 (bucket)

• 조건에 해당하는 도큐먼트를 버킷이라는 저장소 단위로 구분해 담아 새로운 집합을 생성한다.
• 타입 리스트

• Children Aggregation
• Date Histogram Aggregation
• Date Range Aggregation
• Filter Aggregation
• Filters Aggregation
• Geo Distance Aggregation
• GeoHash grid Aggregation
• Global Aggregation
• Histogram Aggregation
• IPv4 Range Aggregation
• Missing Aggregation
• Nested Aggregation
• Range Aggregation
• Reverse nested Aggregation
• Sampler Aggregation
• Significant Terms Aggregation
• Terms Aggregation

3) 파이프라인 (pipeline)

• 집계의 결과를 다른 집계에 활용한다.
• 레벨에 따라 부모/자식 집계로 나뉜다.
• buckets_path 지정 필수
• 타입 리스트

• Avg Bucket Aggregation

• Derivative Aggregation

• Max Bucket Aggregation

• Min Bucket Aggregation

• Sum Bucket Aggregation

• Stats Bucket Aggregation

• Extended Stats Bucket Aggregation

• Percentiles Bucket Aggregation

• Moving Average Aggregation

• Cumulative Sum Aggregation

• Bucket Script Aggregation

• Bucket Selector Aggregation

• Serial Differencing Aggregation
  

2. 매트릭 집계 구조

GET /{index_name}/_search?pretty

!!) 매트릭 집계중 카디날리티 집계(Cardinality Aggregation)은 근사 집계로 정확한 값이 대신 유사값을 구한다.

(카디날리티 집계(Cardinality Aggregation) 포스트 참고 )

3. 버킷 집계 구조

GET /{index_name}/_search?pretty

4. 파이프라인 집계 구조

GET /hotels/_search?pretty