[C++] Call by reference vs Call by Value 시간복잡도

 

Call by reference는 참조 방식으로, 함수의 매개변수에 변수의 주소를 넘겨준다. 따라서 함수 내에서 입력받은 매개변수를 수정할 때, 원본 변수도 바뀌게 된다.

 

반면 Call by Value는 값 방식으로, 함수의 매개변수에 변수의 값을 전달한다. int a를 매개변수로 받아도 int a가 가진 "값"을 받는다.

가령 int a = 10일때, dfs(a) 라면 a가 아니라!! a가 가진 10이 전달된다. 때문에 함수 내에서 int a를 지지고 볶고 해도 원본과 독립적이며 원본 변수를 바꿀 수 없다.

 

---

 

 

어느때와 다름 없이 코테 문제를 풀다가, 똑같은 코드라도 함수 인자 전달 방식에 따라 성공과 실패가 갈라져 글을 작성하게 되었다

 

우선 내가 푼 문제는 백준의 '키 순서' 이다

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

 

학생들의 수 N이 최대 500이라 데이터셋은 크지 않지만 시간 제한은 1초, 그리고 메모리 제한은 128MB로 자칫 생각없이 풀면 시간 초과로 입구컷을 당할 수 있는 문제다

 

입구컷을 당할 수 있다 << 이건 내 얘기다... 내가 그랬으니까!!

 

 

틀렸던 나의 코드를 다시 보자

 

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

int N, M, cnt;
vector<vector<int>> tall(505);
vector<vector<int>> small(505);

void dfs(vector<vector<int>> v, int arr[], int start)
{
    arr[start] = true;
    for(int next : v[start])
        if (arr[next] == false)
        {
            cnt++;
            dfs(v, arr, next);
        }
}

int main()
{
    cin >> N >> M;
    for(int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        tall[b].push_back(a);
        small[a].push_back(b);
    }

    int answer = 0;
    for(int i = 1; i <= N; i++)
    {
        cnt = 0;
        int visited[505] = {};
        dfs(tall, visited, i);
        visited[505] = {};
        dfs(small, visited, i);
        
        if (N-1-cnt == 0) answer++;

    }

    cout << answer;
    return 0;
}

 

N이 크지 않아 깊이 우선 탐색으로 풀수 있으리라 생각했는데, 시간 초과가 나서 어딜 고쳐야 할지 감이 안와 지피띠니 쌤에게 여쭈어보았다.

 

dfs 함수를 보면, 나는 인자를 이렇게 받아주고 있었다

 

void dfs(vector<vector<int>> v, int arr[], int start)

 

그러니 dfs 함수가 재귀적으로 실행될 때마다 2차원 벡터 배열을 새로 복사해서 만들어주고 있었던 것이다..ㅋㅋㅋ 인자수가 최대 500이니, 수백만번 스택에 새로 복사해주고 있었다

 

따라서 2차원 벡터 배열을 새로 만들지 않고 그대로 참조해서 쓰면 이렇게 바뀐다

 

void dfs(const vector<vector<int>>& v, int arr[], int start)

 

const =  바꿀 수 없는 변수, 수정 금지

& = 원본 가리키기

const & = 원본+수정 금지

 

라는 뜻이다.

 

여지껏 함수 실행시 값을 새로 할당하는(배열을 계속 새로 만듦) Call by Value 방식만 쓰다가, 원본 값을 가리키는 Call by Reference 방식을 사용하니 문제가 풀려 이 개념을 더욱 잊지 않을것 같다!

 

앞으로도 시간 초과가 나는 문제가 있으면 이 방식을 사용할 것이다

 

 

 

마지막으로 두 방식의 시간복잡도를 찾아보니 다음과 같았다

int dfs(vector<int> arr, int start)
return dfs(arr, start)

dfs 함수가 계속해서 arr 배열을 복사함.
배열의 크기를 n이라 하고, k번 호출 시 O(n*k) 걸림

 

 

int dfs(vector<int>& arr, int start)
return dfs(arr, start)

dfs 함수가 계속해서 arr 원본 배열을 참조함. 주소만 넘겨주므로 O(1) 걸림

 

 

그래서 나처럼 참조 방식으로 변경해서 푼 사람들도 많은 것 같다

 

 

https://www.acmicpc.net/board/view/98239

 

함수 인자(parameter) 전달 방식 속도 : call by value VS call by reference

 

 

참고 사이트:

Does pass by reference and pass by value cause a change in time complexity of a program in C++?