여행 짐 싸기

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

1. Problem

2. My Approach

• 잘 알려진 0-1배낭 문제(0-1 Knapsack Problem)과 거의 같기때문에 같은 방법으로 접근했다.
• 가방의 무게가 허용하는 선에서 절박도를 최대화하기 위해 맨 처음 무게 조건을 확인하고 특정 짐을 넣었을 경우와 넣지 않았을 경우를 비교한다.

• 동적계획법(Dynamic Programming)을 사용하는 대표적인 문제로서, 추가로 중복 연산을 없애기 위해 메모이제이션(Memoization)을 사용했다.

• 문제는 그렇게 넣은 짐들에 대한 정보를 따로 어떻게 저장할 지다

  • 최대 절박도를 구하는 packing()은 재귀함수이므로, 내부에서 호출되는 packing()과 인과관계에 있어 반환되는 값들이 연결되어 있다고 볼 수 있다.
  • 따라서 우리는 최대 절박도인 int형 변수 뿐만 아니라 넣은 짐에 대한 정보인 string 타입의 변수도 함께 넘겨줘야 하므로 반환형을 pair<int, string>으로 선언해주었다.

3. Implementation

• 메모이제이션의 구현은 재귀함수와 직접적으로 연결되어있다.

  • 재귀함수 진입시 해당 재귀함수 인덱스에 따른 메모리에 값이 있는 지 체크한다.
  • 여기서 재귀함수 고유의 인덱스로 parameter를 들 수 있다.
  • 따라서 계산한 값을 저장하는 배열 cache의 row 또는 column등의 요소는 재귀함수가 받는 parameter와 일대일 대응한다.

pair<int,string> cache[1001][100];

pair<int, string> packing(int rest, int idx){
    if(idx == N) return make_pair(0, "");

    pair<int,string>& ret = cache[rest][idx];
    if(ret.first != -1) return ret;

    if(weight[idx] <= rest){
        ret.second += name[idx] + "\n" + packing(rest-weight[idx], idx+1).second;
        ret.first = need[idx] + packing(rest-weight[idx], idx+1).first;
    }

    if(ret > packing(rest, idx+1))
        return ret;
    else{
        return ret = packing(rest, idx+1);
    }
}

• 다만 재귀함수의 반환형과 저장소 cache의 타입이 일반적인 Primitive type이 아닌 pair<int, string>이기 때문에 초기화하는 함수를 따로 구현했다.

  void init(){
    for(int i=0;i<1001;i++)
        for(int j=0;j<100;j++){
            cache[i][j].first = -1;
            cache[i][j].second = "";
        }
  }
  

• 최종적으로 구한 pair 객체에서 짐의 개수를 구하기 위해서 string 타입 변수에 기록된 '\n' 문자를 카운팅한다.

  int count(string str){
    if(str.find("\n") != string::npos)
        return 1 + count(str.substr(str.find("\n")+1));
    else
        return 0;
  }
  

4. Textbook Approach

• 최대 절박도를 구하는 알고리즘은 내가 생각한 것과 크게 다르지 않다.
• 다만 넣은 짐을 역추적하는 방법은 매우 기발하다.

  만약 해당 인덱스의 짐을 넣지 않았다면 이 때 최대절박도와 그 다음 인덱스의 최대절박도는 동일하다.

5. Implementation

void reconstruct(int rest, int idx, vecotr<string>& picked){
  //  Base case : Checked out all items
  if(idx == N) return;
  if(packing(rest,idx) == packing(rest,idx+1)){
    reconstruct(rest,idx+1,picked);
  }
  else{
    picked.push_back(name[item]);
    reconstruct(rest-weight[idx],idx+1,picked);
  }
}

6. Analysis

• 채점서버 결과 본인이 짠 코드는 상당히 긴 수행시간(868ms)이 걸렸는데, 메모리 초기화가 치명적이었던 것으로 여겨진다.
• 재추적 알고리즘 reconstruct은 기존에 만들어진 memoization으로 인해 비교연산 외에 추가적인 시간소요가 없다.
• 책에서 소개된 재추적 알고리즘 외에 cache와 같은 사이즈의 memory를 만들어서 물건을 넣을 때마다 체크를 해준 뒤 재추적 하는 방법도 있다.

  • packing() 함수 내에서 물건을 넣는 if문 안에 추가로 선언해준다.

    check[rest][idx] = 1;
    

  • 역추적 함수 trace()

    void trace() {
     int vol = max_v;
     for(int i = 0; i < num; i++) {
         if (check[i][vol]) {
                 carry.push_back(name[i]);
                 vol -= v[i];
         }
     }
    }
    

7. Feedback

• 연쇄반응처럼 일어나는 재귀함수 연산의 정확한 동작 원리를 이해할 수 있어야 그 안에서 변수들의 변화와 의미를 구할 수 있다.
• 상황에 따라 접근하는 방법을 배열의 begin( )이 아닌 end( )에서부터 시작하면, 조건 검사를 줄여 좀 더 쉬운 코드를 구현할 수 있음을 알아두자.