재귀함수 사용 시 코드 실행시간을 단축하는 방법 (C++)

재귀 문제를 풀면서 분명 같은 로직인데 실행시간이 많게는 10배이상 차이나는 것을 보았다.

 

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

14889번 문제는 N제한이 20이하이므로 순열을 사용하여 스타트팀과 링크팀으로 나눈다면 시간복잡도가 최대 20! = 2,432,902,008,176,640,000 이 되어버리기 때문에 재귀(백트래킹)를 사용하여 풀어야한다.

 

void solve(vector<int> a, vector<int> b, int idx) {
  if (idx == n + 1) {
    if (a.size() != n / 2 || b.size() != n / 2) {
      return;
    }
    if (a.size() == n / 2 && b.size() == n / 2) {
      int sum_a = 0;
      int sum_b = 0;
      for (int i = 0; i < n / 2; i++) {
        for (int j = 0; j < n / 2; j++) {
          sum_a += score[a[i]][a[j]];
          sum_b += score[b[i]][b[j]];
        }
      }
      if (abs(sum_a - sum_b) < ans)
        ans = abs(sum_a - sum_b);
      return;
    }
  }

  a.push_back(idx);
  solve(a, b, idx + 1);
  a.pop_back();
  b.push_back(idx);
  solve(a, b, idx + 1);
  b.pop_back();
}

문제의 핵심 풀이 알고리즘은 위 코드와 같다. a벡터와 b벡터에 사람을 1명씩 넣으면서 idx가 n + 1 이 되면 재귀함수를 더 이상 호출하지 않고 두 팀의 능력치를 계산하여 ans에 두 팀의 능력치 차이의 최솟값을 갱신해 준다.

 

문제가 되는 부분은 void solve(vector<int> a, vector<int> b, int idx) 여기인데, 재귀함수를 호출할 때 마다 a벡터와 b벡터를 복사하여 재귀함수로 넘겨준다. 즉, 필요 이상의 배열(벡터)복사가 발생하여 배열의 크기가 커질수록 코드의 실행시간이 점점 늘어난다.

그렇다면 어떻게 해결할 수 있을까?

 

바로 레퍼런스(&)를 사용하는 것이다.

void solve(vector<int> &a, vector<int> &b, int idx) 코드를 다음과 같이 수정하면 재귀함수 호출 시 더 이상 벡터의 복사가 일어나지 않고, 레퍼런스를 사용하여 복사본이 아닌 원본을 넘겨줄 수 있다.

위 결과가 레퍼런스를 사용한 코드, 아래 결과가 레퍼런스를 사용하지 않은 코드.

실행 시간이 약 8배 차이 나는 것을 볼 수 있다.

 

전체코드 : http://boj.kr/0ec05d56a5ca43bd898ef4943f85f91f

 

주의) 레퍼런스를 사용하여 원본 배열(벡터)이 변경되기 때문에 의도치 않은 에러가 발생할 수 있다.