참조형 데이터 타입을 다루다 보면 접하게 되는 깊은 복사와 얕은 복사에 대해 기본개념, 예시, 활용법까지 모두 다 정리해보자.
1. 기본 개념
깊은 복사(Deep Copy)
데이터 자체를 통째로 복사 한다.
데이터 자체를 통째로 복사 했기에, 새로운 주소를 가진다. 즉, 복사된 두 개의 객체는 서로 독립적인 메모리를 가지게 된다.
기본형 데이터의 경우 깊은 복사가 되지만, 참조형은 일반적으로 그렇지 않다.
얕은 복사(Shallow Copy)
데이터의 주소값만 복사한다.
즉, 복사된 두 개의 객체는 서로 같은 메모리를 가르키고 있다.
2. 예시
위 개념을 통해, 일반적으로는 기본형 타입의 데이터의 경우 깊은 복사가, 참조형 데이터의 경우 얕은 복사가 일어남을 알 수 있었다.
이를 실제 예시를 통해 확실히 하자.
1. 기본형 데이터 타입 - 깊은 복사
자, 먼저 기본형 데이터 타입이다. 우리가 일반적으로 자주 보기 때문에 너무 당연하게 느껴 질 수 있다.
b는 a를 복사 한 후, 새로운 값을 재할당 하였다.
하지만 이는 당연하게도 b만을 변화시키고 a를 변화시키지는 않는다.
이는 a를 복사하여 b를 생성할 때 깊은 복사가 일어났기 때문이다.
2. 참조형 데이터 타입 - 얕은 복사
위에서 기본형 데이터 타입을 복사한 방식으로 배열을 복사해보자.
arr을 복사하여, brr을 만든 후, brr의 1번째 index값을 재할당 하였다.
어라! arr[1]도 바뀌어 버렸다. 왜 이런 일이 일어났을까?
이는 arr을 복사하여 brr을 만들 때 얕은 복사만 일어났기 때문이다.
따라서, brr과 arr은 같은 주소(메모리)를 바라보고 있게 되는데, 그 주소에 있는 1번째 index의 값을 재 할당하였으니,
당연히 주소를 공유하는 arr, brr 모두 값이 변경되게 되는 것이다.
그렇다면 어떻게 배열을 깊은 복사 할 수 있을까? 대표적으로는 brr = arr.slice() 형시긍로 구현 할 수 있다.
3. 활용 - 배열로 행렬 만들기
그래, 개념은 알겠다. 근데 실제로 저런 개념이 언제 등장하고 언제, 어떻게 사용해야 할까?
1. 배열로 행렬을 만들때
알고리즘을 풀다보면 배열로 행렬을 만들어야 할 경우가 종종 생긴다.
이때 나는 처음, 아래와 같은 방식으로 접근 하였다.
let arr = new Array(5).fill(new Array(5).fill(0))
직관적이지만 완전히 잘못된 방식이다. fill() 메소드는 배열의 시작 인덱스 부터 마지막 인덱스까지 정적인 하나의 값으로 채운다.( 링크 )
그렇기 때문에, 아래와 같은 현상이 일어나게 된다. 그리고 이는 절대로 우리가 원하는 방식이 아니다.
그렇다면 어떻게 배열로 행렬을 만들 수 있을까? (개인적으로 1번이 간단한 것 같다.)
//1번
let length = 5;
let arr = Array.from({length}, () => new Array(5).fill(0))
//1번
let arr = new Array(5);
for(let i =0; i < arr.length; i++){
arr[i] = new Array(5).fill(0);
}
//2번
const memo = [];
for (let i = 0; i < M ; i++) memo.push(Array(N ).fill(-1));
위의 방식을 통해 아래처럼 우리가 원하던 결과를 얻을 수 있다.
2. 재귀 함수를 만들 때
아니 갑자기 재귀함수가 왜 나오는데?
우리는 DP같은 문제를 풀기 위해 재귀를 쓰는 경우가 꽤 자주 있다.
예를 들어, dfs로 완전 탐색을 해야 하는 경우가 있다고 생각해보자.
dfs를 진행할 때에는 해당 노드를 방문했는지 여부를 체크 해야 한다.
이를 체크 하기 위해 visited: [] 같은 변수를 선언하여 인자로 넘겨주는 경우가 생기는데,
만약 인자로 넘겨주는 배열을 깊은 복사 해서 넘겨주지 않는다면, 각각의 케이스는 독립적이지 않게 된다.
아래 코드를 보면서 이해해 보자. 아래 코드는 programmers 양과 늑대라는 문제의 답 일부이다. ( 문제가 궁금하다면 링크 로 가보자)
function bfs(currentNode, sheep, wolf, queue) {
console.log("currentNode", currentNode, "queue", queue);
const position = queue.indexOf(currentNode);
//queue 깊은 복사
queue = queue.slice();
if (info[currentNode]) {
wolf += 1;
} else {
sheep += 1;
}
if (wolf === sheep) return;
maxSheep = Math.max(sheep, maxSheep);
//1. 현재 위치 노드와 연결된 자식 노드들을 queue에 넣어준다.
if (connectedNode.length) {
queue.push(...connectedNode[currentNode]);
}
queue.splice(position, 1);
for (let node of queue) {
bfs(node, sheep, wolf, queue);
}
}
for (let i = 0; i < edges.length; i++) {
const [from, to] = edges[i];
if (connectedNode[from]) {
connectedNode[from].push(to);
} else {
connectedNode[from] = [to];
}
}
bfs(0, 0, 0, [0]);
해당 문제에서는 bfs로 완전탐색을 진행하고 있다. 이때, queue에는 아직 방문하지 않은 자식 노드들이 들어가 있게 되는데,
만약 queue를 queue = queue.slice() 형식으로 깊은 복사 해주지 않는다면, 각각의 케이스가 독립적이지 않게 되기 때문에, 완전탐색이 불가하게 된다.
'JavaScript' 카테고리의 다른 글
json [object Object] 출력 (0) | 2022.04.13 |
---|---|
new Set으로 배열 중복값 제거(with 퍼포먼스 테스트) (0) | 2022.04.11 |
[ES6] Map vs Set (0) | 2022.04.11 |
정규표현식 (0) | 2022.04.11 |
날짜 편리하게 계산하기(feat. dayjs) (0) | 2022.04.11 |