프로그래밍을 하다보면 복사가 예상한 대로 되지 않을 때가 있습니다. 예를 들어, 아래 파이썬Python 코드처럼 배열을 복사했다고 해봅시다.

original = [[1, 2], [3, 4]]
copy = original[:]

그러면 원본을 건드렸을 때 복사본도 함께 바뀝니다.

original[0][0] = 5 # change original
copy[0][0] == 5 # True (also changed)

이는 파이썬 뿐만 아니라 일반적으로 다른 언어에서도 나타나는데요. 또 다른 예시인 자바스크립트JavaScript도 아래 처럼 노드Node.js에서 같은 현상을 보입니다.

const original = [[1, 2], [3, 4]];
const copy = [...original];

original[0][0] = 5; // change original
copy[0][0] === 5; // true (also changed)

이런 경우를 얕은 복사shallow copy라고 부릅니다. 그런데 이것이 원하는 결과가 아닐 때가 있는데요. 그래서 이와 달리 다른 쪽이 바뀌지 않게끔 복사하는 경우가 있습니다. 이를 깊은 복사deep copy라고 부릅니다.

이런 얕은 복사가 일어나는 이유는 보통 주소값을 복사하기 때문이라고 설명합니다. 그런데 복사를 수행하는 컴퓨터 입장에서는 그 값이 숫자든 주소값이든 가리지 않고 그저 값을 복사했을 뿐입니다. 정말로 문제를 일으키는 것은 그런 주소값으로 참조되는 값을 바꾸는 것입니다.

얕은 복사와 깊은 복사는 다양한 프로그래밍 언어에서 공통적으로 나타나는 컨셉입니다. 그런 복사를 어떻게 구현하는 지는 언어마다 다를 수 있습니다. 하지만 언어가 인터프리터로 구현되어 있든 컴파일러로 구현되어 있든, 그 밑에서는 저수준low-level 메모리 작업이 필요할 수밖에 없는데요. 이 메모리 상에서 무슨 일이 일어나는지 보면, 어떤 언어에서든 사실상 비슷한 일이 일어난다는 것을 알 수 있습니다.

이 글에서는 가상의 프로그래밍 언어에서 복사 연산을 직접 구현해볼 것입니다. 여기서는 포인터pointer를 사용하는 저수준 언어인 C 언어로 진행합니다. 포인터란 메모리 주소를 값으로 가지는 타입입니다.

얕은 복사 구현하기

앞서 예를 든 것처럼, 프로그래밍 언어는 배열을 복사하는 인터페이스를 프로그래머에게 제공합니다. 그러면 거꾸로 그런 언어를 만든다면, 복사는 어떻게 구현할 수 있을까요?

예를 들어, 숫자 배열 [1, 2, 3]을 복사해야 한다고 해봅시다. 배열이란 연속된 메모리 할당contiguous memory allocation이고, 따라서 할 일은 원본을 다른 연속된 공간에 복사하는 것입니다. 그러면 다음과 같이 구현할 수 있습니다.

void copyArray(int* source, int* dest, int size) {
  for (int i = 0; i < size; ++i) {
    dest[i] = source[i];
  }
}

여기서 배열 또한 포인터로 취급할 수 있다는 점을 이용했습니다.

한편 중첩된 배열, 즉 [[1, 2], [3, 4]] 같은 배열을 복사해야 한다고 해봅시다. 즉 배열의 배열인데요. 비슷하게 복사 함수를 만들 수 있습니다.

void copyNestedArray(int** source, int** dest, int size) {
  for (int i = 0; i < size; ++i) {
    dest[i] = source[i];
  }
}

이처럼 기존의 copyArray() 함수를 거의 바꾸지 않고 만들 수 있습니다. 다시 말해 데이터 타입만 다를 뿐, 똑같은 로직을 그대로 갖다 썼는데요. 이렇게 복사 함수들은 어떤 타입이든지 상관 없이 같은 일을 수행하게 만들 수 있습니다.

복사본 만들기

위에서 만든 함수로 복사본을 만들 수 있는데요. 먼저, 다음과 같이 숫자 배열 original을 copy로 복사할 수 있습니다.

// original = [1, 2, 3]

copyArray(original, copy, 3);
// copy     = [1, 2, 3]

여기서 원본을 바꾸더라도 복사본은 바뀌지 않고 남아있습니다.

original[0] = 4;
// original = [4, 2, 3]
// copy     = [1, 2, 3]

이번에는 중첩된 배열을 봅시다.

// original = [[1, 2], [3, 4]]

copyNestedArray(original, copy, 2);
// copy     = [[1, 2], [3, 4]]

그러면 한쪽 변경이 다른 쪽도 똑같이 바꾸게 됩니다.

original[0][0] = 5;
// original = [[5, 2], [3, 4]]
// copy     = [[5, 2], [3, 4]]

왜 그럴까요? 이는 배열에 접근하는 방식에서 원인을 찾아볼 수 있습니다.

주소 값으로서의 배열

배열이란 포인터와 다를 바 없는 주소값으로 다룰 수 있습니다. C 언어에서는 배열이 연속된 메모리 공간의 시작 주소를 갖는데요.

예를 들어 어떤 배열 arr이 메모리 상 0x10 번지에서 시작한다고 해봅시다. 그러면 arr은 0x10을 값으로 갖게 됩니다.

이제 C 언어에서 arr[2]의 값을 평가evaluate할 때, 먼저 그 시작 주소에서 두 칸을 더한 주소를 계산합니다. 이 ‘두 칸’이란 8 바이트를 의미하게 됩니다. 배열이 int 타입이고, 이 타입이 4 바이트를 차지한다면요.

즉 배열 변수 arr 옆에 붙는 [2]와 같은 접근 연산은 사실상 주소 값의 덧셈 연산이 됩니다. 이는 시간 복잡도가 $O(1)$ 이기 때문에, 이렇게 임의 접근random access을 구현할 수 있게 됩니다. 따라서 arr[2]의 최종 주소는 0x18이 되고, 여기에 있는 값이 곧 arr[2]의 평가 값이 됩니다.

한편 배열에 접근할 때, 우리는 배열이 갖고 있는 주소값, 즉 0x18 같은 걸 가져오길 기대하는게 아니라, 그 주소에 들어있는 값을 가져오길 바라는데요. 이런 경우 배열을 역참조dereferencing한다고 부릅니다. 즉 임의 접근은 내부적으로 이런 역참조를 활용합니다.

정리하면 C 언어에서 배열 접근 연산 arr[2]는 *(arr+2)와 같은 포인터 연산과 같게 됩니다. 여기서 +2가 주소 값 덧셈 연산을, *가 역참조를 수행하게 됩니다.

복사본 다시보기

위에서 만들었던 복사 함수는 임의 접근을 통해 값을 복사할 뿐입니다. 숫자 배열 [1, 2, 3]을 복사할 때, 각 값은 대응되는 메모리 공간에 담깁니다.

중첩된 배열 [[1, 2], [3, 4]] 또한 이와 다르지 않습니다. 앞서 언급한 대로, 배열은 연속된 메모리 공간의 시작 주소일 뿐이므로, [1, 2]와 [3, 4] 또한 어떤 주소 값에 불과합니다. 즉 배열의 배열이란 주소 값의 배열이고, 원본이나 복사본이나 그렇습니다.

복사하는 로직이 똑같았기 때문에 어떻게 보면 당연한 결과입니다. 즉 복사하려는 값이 1인지 0x30인지 신경쓰지 않고 그대로 복사만 수행했습니다.

그런데 앞서 예시를 통해 원본을 건드렸을 때 복사본 또한 함께 바뀌는 것을 보았습니다. 이는 사실 원본 배열을 바꾼 것이 아니라, 역참조한 값을 바꾼 것입니다.

여기서 원본을 통해 [1, 2] 였던 배열의 첫 번째 엘리먼트를 5로 고쳤다고 해봅시다. 즉 0x30 위치의 값을 바꾼 것입니다. 복사본을 통해 이 위치의 엘리먼트를 가져오면, 원본 때 역참조 했던 값을 똑같이 가져옵니다. 그래서 복사본 또한 함께 바뀐 것으로 보이게 됩니다.

깊은 복사 만들어보기

그렇다면 깊은 복사는 어떻게 구현할 수 있을까요? 배열의 배열을 간단한 예시로 들어봅시다. 그러면 주소 값을 복사하는게 아니라, 새 배열을 만들어내야 하는데요. 다시 말해, 다른 쪽이 영향을 받지 않게 하기 위해, 서로 다른 주소 값을 갖도록 만들어야 합니다.

void deepCopyNestedArray(int** source, int** dest, int size, int nestedSize) {
  for (int i = 0; i < size; ++i) {
    int* copy = createArray(nestedSize); // assign a different address

    for (int j = 0; j < nestedSize; ++j) {
      copy[j] = source[i][j];
    }

    dest[i] = copy;
  }
}

설명을 간단히 하기 위해 보조 함수 createArray()는 원하는 사이즈를 받아 배열을 만들어낸다고 합시다. 그러면 이 복사 함수는 주소 값을 그대로 복사하는 것이 아니라, 매번 새 배열을 만들어냅니다.

더 깊은 복사

이제 배열의 배열은 깊은 복사를 해냈습니다. 그러면 배열의 배열의 배열은 어떻게 할까요? 아니면, 엘리먼트들이 꼭 같은 중첩 레벨의 배열이 아니면 어떨까요? ([1, [2, 3]] 처럼요.)

이 질문에서 데이터 타입data type의 구분이 필요하게 됩니다. 얕은 복사는 그런 구분이 필요 없었는데요. 깊은 복사는 복사 대상이 배열인지 아닌지 구분해야 하기 때문입니다. 만약 배열이라면, 앞서 구현한 것처럼 새 배열을 만들어서 다른 주소값을 갖도록 만들어야 합니다.

그렇다면 배열을 단순히 사용할 수는 없습니다. C 언어는 런타임에 데이터 타입을 알아낼 수 있는 그런 기능은 내장되어 있지 않으니까요. 그래서 데이터 타입이 배열임을 알 수 있는 어떤 구조체를 구현할 필요성이 생깁니다. 여기선 그것까지는 하지 않을 것입니다.

한편 런타임에 데이터 타입을 알 수 있도록 언어를 만들었다고 칩시다. 어떤 중첩 레벨이든지 재귀적recursive인 호출을 통해 깊은 복사를 구현할 수 있게 됩니다. 다음 파이썬 코드처럼요.

def deepcopy(original):
    copy = []

    for element in original:
        if type(element) is list:
            copy.append(deepcopy(element))
        else:
            copy.append(element)

    return copy

레퍼런스 타입

다른 고수준high-level 프로그래밍 언어는 C 언어의 저수준 메모리 작업을 지원하지 않는 경우가 있습니다. 일단 그런 직접적인 메모리 주소를 조작하는 작업이 에러를 쉽게 유발하는error-prone 작업입니다. 메모리에 제대로 된 주소를 넣어두는 것을 까먹거나, 아니면 OS로부터 빌려온 메모리를 다시 반환하는 일을 까먹거나, 역참조를 한번만 해야 할 것을 두 번 해버리거나… 이런 식으로 사람은 저수준에서 생각하기 힘든데요.

그래서 이런 직접적인 메모리 조작 대신, 언어 자체에서 알아서 역참조를 활용해 값을 가져오도록 만들고, 그 인터페이스를 데이터 타입으로서 마련하는 경우가 있습니다. 보통 레퍼런스 타입reference type이라는 이름 하에 이를 제공하곤 합니다. 물론 그 타입을 어떻게 구현하는 지는 언어마다 다를 수 있습니다. 예를 들어 어떤 언어에서는 메모리 주소를 읽는 것까지는 허용하는 반면, 또 다른 언어에서는 그것까지 숨길 수도 있습니다.

이런 식으로 저수준 메모리 조작은 내부적으로 숨겨두고, 여기에 가비지 컬렉션garbage collection을 더해 메모리 관리를 프로그래밍 언어에 맡겨버리는 경우가 있습니다. 자바Java, 자바스크립트, 파이썬을 비롯한 많은 언어가 그렇게 하고 있습니다. 물론 이 또한 언어마다 다르게 구현될 수 있습니다.

마치며

여기까지 얕은 복사와 깊은 복사를 알아보았습니다. 여기서는 간단히 C 언어로 구현했지만, 사실 언어마다 그 구현이 다를 수 있습니다. 하지만 프로그래밍에서 복사는 메모리를 빼놓고 얘기할 수 없었는데요. 단순히 메모리 주소 값을 복사해 얕은 복사를, 새로운 메모리를 할당해 깊은 복사를 구현할 수 있었습니다.

메모리는 컴퓨터 구조 상 사용되는 하드웨어인데요. C 언어는 메모리 주소 값을 포인터라는 데이터 타입으로서 지원합니다. 그리고 배열 또한 포인터와 같기 때문에, 포인터를 통해 배열도 함께 이해할 수 있었습니다. 참고자료가 필요하다면 메모리는 컴퓨터 구조를 다루는 자료에서, 포인터는 C 언어를 다루는 자료에서 쉽게 찾아볼 수 있습니다.

여기까지 작성한 코드는 생략했던 구현을 포함해 지스트Gist에서 확인할 수 있습니다.