얕은 복사와 깊은 복사, 미묘한 속도 차이로 인한 시간 초과 발생 (feat. 백준)

프로그래밍의 값 복사는 '깊은 복사', '얕은 복사' 두 종류가 있는데, 적당히 설명하자면 주소값을 복사해가 두 변수가 한 인스턴스를 가리키게 되면 얕은 복사, 값 자체를 복사해 메모리에 주소 영역이 하나 더 생기면 깊은 복사라고 구분할 수 있다. 각각 다른 말로 '값 복사', '레퍼런스 복사' 라고 부르기도 한다. 아주 간단한 예시를 들자면 아래와 같다.

 

int a = 1;
int *b = &a;  //얕은 복사

//--//

int a = 1;
int b = a;  //깊은 복사

 

변수가 저장한 값이 리터럴일 경우 손쉽게 깊은 복사를 사용할 수 있지만, 배열 같은 자료 구조의 형태가 되는 순간 깊은 복사보다는 얕은 복사를 주로 사용하게 된다. 당장 배열 자료구조의 경우 두 변수를 '=' 기호로 잇는 것 처럼 간단하게 깊은 복사가 이루어지지 않는다.

 

int a[] = {1, 2, 3, 4, 5};

int b[] = a;  // 불가능. 컴파일 에러 발생.

//...//

int a[5] = {1, 2, 3, 4, 5};
int b[5];

memcpy(b, a, sizeof(int)*5); //가능. 올바른 깊은 복사 방법.

 

하지만 배열 처럼 여러개의 데이터를 담을 수 있는 구조체 자료구조의 경우, '=' 연산자를 통한 깊은 복사가 가능하다. 

 

struct Gujo {
    int a;
    int b;
};


int main() {
    Gujo gj1;
    gj1.a=1;
    gj1.b=2;
    
    Gujo gj2 = gj1;  //가능. 깊은 복사가 일어난다.
}

 

이 사실을 머리로는 이해하고 있었으나, 깊게 생각하지 않아 백준 문제를 풀다가 '시간 초과'가 발생했다. 내가 작성한 코드에서 문제된 부분의 구조는 대략 아래와 같았다. 

 

struct GJ {
	//..//
};

void bfs (int n, GJ gj) {    
	//...//
}

int main() {
	// 생략...
    
    GJ gj;
    // (gj 멤버 값 넣어주기)
    bfs(n, gj);               
        
	// 생략...
}

 

bfs 함수에 gj 매개변수를 깊은 복사 (값 복사)로 넘겨준 것이었다. 깊은 복사는 메모리를 새로 할당하고, 값을 하나하나 복사해서 메모리에 새로 만든다는 점에서 주소값만 달랑 복사하는 얕은 복사에 비해 실행 시간이 오래 걸릴 수 밖에 없다.

 

이 깊은 복사와 얕은 복사의 차이 때문에 나는 시간 초과가 발생했고 장장 세 시간 가량을 헤맸다. (ㅠㅠ)

 

이 문제를 눈치채고 코드를 얕은 복사(레퍼런스 복사)로 바꿔주니 무사히 정답처리 되었다.

 

struct GJ {
	//..//
};

void bfs (int n, GJ* gj) {     // .... (1)
	//...//
}

int main() {
	// 생략...
    
    GJ gj;
    // (gj 멤버 값 넣어주기)
    bfs(n, &gj);               // .... (2)
        
	// 생략...
}

 

 

END.