원주율 외우기

• 1. Problem
• 2. My Approach
• 3. Implementation
• 4. Textbook Approach
• 5. Implementation
• 6. Analysis
• 7. Feedback

1. Problem

2. My Approach

• 주어진 문제로부터 따로 특별한 접근방법을 생각할 수 없어 모든 경우의 수를 비교하는 동적계획법을 적용하기로 했다.
• 숫자는 오직 3개, 4개, 5개 단위로만 판단할 수 있다.
• 주어진 숫자 배열들을 3개, 4개, 5개로 나눴을 때 각각의 레벨과 재귀적으로 구한 그 이후의 값들을 더해주어 비교한다.

  • getLevel() : 주어진 범위(3~4)에서 레벨을 측정한다.
  • Memoization() : getLevel을 재귀적으로 호출하여 비교한다.

• getLevel() 함수의 구현은 간단해보이지만 예외처리를 철저하게 해줘야하기 때문에 의외로 애를 많이 먹었다. 처음에 짠 코드는 string에서 특정 인덱스의 값에 접근하고, character형 변수를 int형 변수로 변환해주는 둥 연산외에도 많은 처리를 하고 있는데 심지어 정답도 뜨지 않았다. 이렇게 짜면 안된다는 것을 인지하기 위해 올려둔다.

3. Implementation

• 처음 getLevel( ) 코드

  int getLevel(string str){
    int grade = atoi(str.substr(1,1).c_str()) - atoi(str.substr(0,1).c_str());
    int second_grade = atoi(str.substr(2,1).c_str()) - atoi(str.substr(1,1).c_str());
    //  same numbers
    if(grade == 0 && grade == second_grade){
        for(int i=2;i<str.size();i++)
            if(grade != atoi(str.substr(i,1).c_str()) - atoi(str.substr(i-1,1).c_str())) return 10;
        return 1;
    }
    //  mono increment or mono decrement
    else if((grade == 1 || grade == -1) && grade == second_grade){
        for(int i=2;i<str.size();i++)
            if(grade != atoi(str.substr(i,1).c_str()) - atoi(str.substr(i-1,1).c_str())) return 10;
        return 2;
    }
    //  sequence
    else if(grade == second_grade){
        for(int i=2;i<str.size();i++)
            if(grade != atoi(str.substr(i,1).c_str()) - atoi(str.substr(i-1,1).c_str())) return 10;
        return 5;
    }
    else if(grade == -1*second_grade){
        for(int i=2;i<str.size();i++)
            if(str.substr(i,1) != str.substr(i-2,1)) return 10;
        return 4;
    }
    return 10;
  }
  

• 책을 참고하여 수정된 getLever( ) 코드

  int getLevel(string str){
    if(str == string(str.size(),str[0])) return 1;
  
    bool progressvie = true;
  
    for(int i = 0; i < str.size()-1;i++)
        if(str[i+1]-str[i] != str[1]-str[0])
            progressvie = false;
  
    //  Mono increment or decrement
    if(progressvie && abs(str[1]-str[0]) == 1)
        return 2;
    //  Sequence
    else if(progressvie) return 5;
  
    // Repetition
    bool repetition = true;
    for(int i=0;i<str.size();i++)
        if(str[i] != str[i%2])
            repetition = false;
    if(repetition) return 4;
  
    return 10;
  }
  

  • 범위가 넓은 부분부터 확인하며 점근적으로 접근하는 것을 볼 수 있다.
  • 이와 같이 여러 예외경우를 조사해야 하는 경우 위와 같은 접근 방법을 알아두자.

• Memoization( ) 코드

  int Memoization(int start){
    //base case
    if(start == input.size()) return 0;
    else if(start > input.size()-3) return 9999;
  
    int& ret = cache[start];
    if(ret != -1)
        return ret;
  
    ret = 999999;
    int q3 = getLevel(input.substr(start,3)) + Memoization(start+3);
    int q4 = getLevel(input.substr(start,4)) + Memoization(start+4);
    int q5 = getLevel(input.substr(start,5)) + Memoization(start+5);
  
    return ret = min(min(q3,q4),q5);
  }
  

  *

4. Textbook Approach

• 책 역시 ‘*’ 에 대응하는 문자의 수를 0개부터 card의 남은 문자열수만큼 하나씩 늘려주면서 체크를 해준다.
• 다만 하나의 조건문 안에 재귀함수를 호출하면서 좀 더 재귀적인 구조의 알고리즘을 구현하였다.
• memoization을 적용하여 중복되는 경우를 줄여주었다.

5. Implementation

string w, s;
int cache[101][101];
bool check(int w_idx, int s_idx) {

    int& ret = cache[w_idx][s_idx];
    if(ret != -1) return ret;

    while(w_idx < w.length() && s_idx < s.length() && (w[w_idx] == '?' || w[w_idx] == s[s_idx]))
        return ret = check(w_idx + 1, s_idx + 1);

    if(w_idx == w.length())
        return ret = (s_idx == s.length());

    if(w[w_idx] == '*')
        if(check(w_idx + 1, s_idx) || (s_idx < s.length() && check(w_idx, s_idx + 1)))
            return ret = 1;

    return ret = 0;
}

6. Analysis

• 채점서버로 돌려본 결과 본인의 코드는 8ms, 책의 코드는 4ms의 수행시간이 걸렸다.
• 본인의 코드는 while문 안에서 최악의 경우 N번의 재귀호출이 발생하고, 책의 코드 역시 N번의 재귀호출이 일어나 이 부분에 있어선 큰 차이가 없을 것으로 보인다. * 다만 책의 코드에선 memoization을 사용함으로써 중복되는 경우를 줄여주었으니 아마 이 점에서 수행시간이 줄었다고 볼 수 있다.

7. Feedback

• 본 문제는 분할 정복 구조를 사용하여 복잡해 보이는 문제를 쉽게 해결가능한 하부 문제들로 쪼개어 해결한다.
• 문제가 주어지면 가장 먼저 분할정복의 관점에서 바라봐야 할 필요성을 느낀다.
• Memoization은 채점 기준에 따라 적용을 안해도 되지만, 보통 철저한 대회의 경우 Memoization을 이용하여 중복처리를 해주지 않으면 시간초과를 발생하게 한다. 특별한 상황을 제외하고 Memoization을 처리해주는 습관을 기르자.