[c++] 레퍼런스에 대한 고찰 (1311 할일 정하기 1)

DP 비트마스킹 문제를 메모이제이션으로 푸는데 레퍼런스 변수로 선언하지 않았을 때 시간초과가 발생했다.

왜 레퍼런스를 쓰는지에 대한 궁금증을 풀기위한 글을 적어봅니다.

 

우선, 레퍼런스란

참조형 변수 (Reference Vaiable)

참조만 한다는 것이다.

 

이게 무슨말이냐면

int &temp = dp[work];

dp[work] 에 &를 이용하여 temp 라는 별명을 붙여준 것이다.

== 이름만 같고 같은 변수

== 같은 메모리를 공유한다 !

 

같은 메모리를 공유한다는 것은 temp 의 값을 변경해도 dp[work] 의 값이 바뀐다는 것이다.

 

반대로 temp 를 레퍼런스로 선언하지 않는다면?

temp 와 dp[work] 는 다른변수이기 때문에 temp 값을 바꿔도 dp[work] 의 값이 바뀌지 않는다.

== 메모이제이션이 되지않는다. (레퍼런스를 쓰지 않았을 때 시간초과가 나는 이유)

 

결국 레퍼런스를 사용하는 이유는 매우 필수적인 것이었다.

굳이 레퍼런스를 사용하지 않는다면 그냥 변수로서 dp[work] 값을 사용하면 된다.

 

 

레퍼런스를 사용한 코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int N, D[20][20], dp[1 << 20], res;

int rec(int num, int work) {
    if (num == N) {
        return 0;
    }
    int &temp = dp[work];
    if (temp != -1) {
        return temp;
    }
    temp = 1e9;
    
    for (int i=0; i<N; i++) {
        if (!(work & (1 << i))) {
            temp = min(temp, D[num][i] + rec(num + 1, work | (1 << i)));
        }
    }
    return temp;
}

int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> N;
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            cin >> D[i][j];
        }
    }
    // fill(dp, dp + (1 << 20), -1);
    memset(dp, -1, sizeof(dp));
    res = 1e9;
    for (int i=0; i<N; i++) {
        res = min(res, D[0][i] + rec(1, 1 << i));
    }
    cout << res << "\n";
    return 0;
}

 

레퍼런스를 사용하지 않은 코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int N, D[20][20], dp[1 << 20];

int rec(int num, int work) {
    if (num == N) {
        return 0;
    }
    if (dp[work] != -1) {
        return dp[work];
    }
    dp[work] = 1e9;
    for (int i=0; i<N; i++) {
        if (!(work & (1 << i))) {
            dp[work] = min(dp[work], D[num][i] + rec(num + 1, work | (1 << i)));
        }
    }
    return dp[work];
}

int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> N;
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            cin >> D[i][j];
        }
    }
    memset(dp, -1, sizeof(dp));
    int res = 1e9;
    
    for (int i=0; i<N; i++) {
        res = min(res, D[0][i] + rec(1, 1 << i));
    }
    cout << res << "\n";
    
    return 0;
}