배열
JS의 배열에 대해서 알아보자.
배열은 같은 타입의 원소들을 효율적으로 관리할 수 있는 기본 자료형입니다. 하나의 변수 이름으로 동일한 타입의 데이터를 그룹화하여 관리할 수 있고, 인덱스라는 것으로 원하는 데이터에 임의 접근할 수 있다는 장점이 있습니다.
배열에 대해서 더 자세히 알아봅시다.
배열 선언
배열 선언은 다양한 방식을 이용해서 만들 수 있어요.
const arr = [0, 0, 0, 0, 0, 0]; // [0, 0, 0, 0, 0, 0]
const arr2 = new Array(6); // [empty × 6]
const arr3 = [...new Array(6)].map((_) => 0); // [0, 0, 0, 0, 0, 0]
const arr4 = new Array(6).fill(0); // [0, 0, 0, 0, 0, 0]
배열은 컴퓨터에서 이런 모습으로 저장되는 자료구조를 말합니다.
0부터 시작해서 3번째 데이터에 접근하려면 arr[2]로 접근하죠.
JS의 Array 객체는 배열과 같은 기능을 지원합니다. JS의 배열은 일반적인 배열과 내부 구현이 다르지만 사용 방법은 같다고 생각하면 좋아요.
JS 배열자바스크립트의 배열은 동적으로 크기를 조절할 수 있도록 구현되어 있습니다. 그래서 자바스크립트의 배열은 다른 언어의 배열 기능을 그대로 사용할 수 있으면서 배열 크기도 가변적이므로 코딩 테스트에서 고려할 사항을 조금 더 줄여줍니다. 또 슬라이싱, 삽입, 삭제, 연결 등의 연산을 제공하므로 더 편리합니다.
배열과 차원
배열은 다양한 차원이 존재하는데요. 컴퓨터의 메모리 구조는 1차원이기에 차원과는 상관없이 모두 1차원 공간에 저장됩니다. ( 메모리에 연속 할당됩니다. )
1차원 배열
1차원 배열의 모습은 메모리에 할당된 실제 배열의 모습과 같아요. 배열의 각 데이터는 메모리의 낮은 주소에서 높은 주소 방향으로 연이어 할당됩니다.
2차원 배열
2차원 배열은 1차원 배열을 확장한 것인데요. JS에서는 다음과 같이 선언합니다.
// 리터럴
const arr = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
];
// fill 메소드와 spread operator를 이용한 2차원 배열을 구현
const arr2 = [...new Array(3)].map((_, i) => new Array(3).fill(i));
// arr2: [[0, 0, 0], [1, 1, 1], [2, 2, 2]]
2차원 배열은 실제 메모리에서는 아래 사진의 오른쪽처럼 행의 순서로 데이터를 할당해서 1차원 공간에 저장합니다.
배열의 시간 복잡도
데이터에 접근
배열은 "임의 접근" 이라는 방식으로 배열의 모든 위치에 잇는 데이터에 한번에 접근할 수 있습니다.
const arr = [1, 2, 3, 4];
arr[1]; // 2
데이터의 개수와 상관없이 상수 ( O(1) ) 입니다.
데이터 추가
데이터를 추가할 때는 어떤 위치에 추가하느냐에 따라서 다릅니다. 이는 메모리와 연관이 있습니다.
맨 뒤에 삽입
맨 뒤에 데이터를 삽입할 경우 그림처럼 다른 데이터 위치에 영향을 주지 않습니다. 따라서 데이터의 개수와 상관없이 상수 ( O(1) ) 입니다.
중간에 삽입
데이터를 중간에 삽입한다면 뒤에 있는 데이터의 개수만큼 미는 연산을 해야 합니다. (ex N-a개 ( N은 데이터의 개수 a 삽입되는 위치의 앞쪽에 존재하는 기존 데이터들의 개수 )) 밀어야 하는 데이터 개수가 N개 라면 시간 복잡도는 O(N)이 됩니다.
맨 앞에 삽입
맨 앞에 데이터를 삽입할 경우 기존의 데이터를 한 칸씩 밀어야 합니다. 데이터의 개수에 비례하게 시간 복잡도가 올라가죠 ( O(N) )
결론적으로 배열은 데이터에 자주 접근하거나 읽어야 하는 경우에 사용하면 좋아요. 하지만 메모리 공간이 충분히 확보가 되어야 한다는 점을 고려해야 합니다. 보통 정수형 1차원 배열은 1000 만개, 2차원 배열은 3000 * 3000 크기를 최대로 보면 됩니다. 또한, 중간에 데이터 삽입이 많은지 확인해야 합니다. 중간이나 맨 앞에 데이터를 빈번하게 삽입하면 시간 복잡도가 높아집니다 ( O(N)의 시간복잡도)
리스트와의 차이점리스트는 크기가 변하는 자료구조이고 배열은 크기가 고정이에요. JS의 배열은 동적 배열이라서 크기가 변할 수 있으므로 리스트로도 취급될 수 있습니다.
배열 조작
데이터 추가
// 배열의 뒤에 요소를 추가
const arr1 = [1, 2, 3];
// push(추가할 요소)
arr1.push(4); // [1, 2, 3, 4]
const arr2 = [1, 2, 3];
// concat(추가할 요소)
arr2.concat([4, 5]); // [1, 2, 3, 4, 5]
// 배열의 앞에 요소를 추가
const arr3 = [1, 2, 3];
// unshift(추가할 요소)
arr3.unshift(0); // [0, 1, 2, 3]
// 배열의 앞이나 뒤에 요소를 추가
const arr4 = [1, 2, 3];
// ...은 전개 연산자로 배열을 펼쳐준다.
arr4 = [...arr4, 4]; // [1, 2, 3, 4]
// 배열의 중간에 요소를 추가
const arr5 = [1, 2, 3];
// splice(시작 인덱스, 제거할 요소 개수, 추가할 요소)
arr5.splice(1, 0, 1.5); // [1, 1.5, 2, 3]
shift, unshift의 JS 최적화JS에서는 데이터의 개수가 15,000개보다 적을 때 unshift, shift 를 통해서 배열을 조작하면 엔진에서 이를 최적화하여 다른 배열 조작보다 더 적은 시간 복잡도를 가진다고 합니다.
공식 문서에서의 대괄호공식문서에서 splice를 보면
array.splice(start[, deleteCount[, item1[, item2[, ...]]]])이런 식으로 표현되어 있는데요. 대괄호로 감싸져있는 부분은 optional 매개변수이고 대괄호로 감싸져있지 않은 부분은 필수 매개변수입니다. splice는 start가 꼭 필요한 메소드임을 알 수 있습니다. 참고로 start만 넣게 되면 start 인덱스의 뒤쪽 데이터는 반환하고 기존 배열은 start 인덱스까지의 배열만 남게 됩니다.
데이터 삭제
// 배열의 마지막 요소를 제거하려면 pop 메서드를 사용한다.
const arr1 = [1, 2, 3];
const result1 = arr1.pop(); // 마지막 요소를 제거하고 반환
console.log(arr1); // [1, 2]
// 배열의 첫 번째 요소를 제거하려면 shift 메서드를 사용한다.
// shift 역시 unshift와 같이 데이터 15,000개까지 엔진에서 최적화를 해준다.
const arr2 = [1, 2, 3];
const result2 = arr2.shift(); // 첫 번째 요소를 제거하고 반환
console.log(arr2); // [2, 3]
// 배열의 특정 위치의 요소를 제거하려면 splice 메서드를 사용한다.
const arr3 = [1, 2, 3];
const result3 = arr3.splice(1, 1); // 1번 인덱스부터 1개의 요소를 제거
console.log(arr3); // [1, 3]
특정 연산 적용 (고차함수 이용)
JS 배열에는 유용한 고차 함수들이 존재합니다. 기존 반복문, 조건문을 이용한 복잡한 로직을 대체할 수 있어요.
// 배열의 각 요소에 대해 특정 연산을 적용하는 고차함수
// map, filter, reduce
// 배열의 각 요소에 대해 특정 연산을 적용한 결과를 반환하는 고차함수
const arr1 = [1, 2, 3, 4];
// 배열의 각 요소를 제곱한 새로운 배열을 반환한다.
const squares = arr1.map((x) => x * x); // [1, 4, 9, 16]
// 배열의 요소 중 특정 조건을 만족하는 요소만으로 구성된 배열을 반환하는 고차함수
const arr2 = [1, 2, 3, 4];
// 배열의 요소 중 짝수인 요소만으로 구성된 배열을 반환한다.
const evens = arr2.filter((x) => x % 2 === 0); // [2, 4]
// 배열의 각 요소에 대해 특정 연산을 적용한 결과를 누적하는 고차함수
const arr3 = [1, 2, 3, 4];
// 초기값 0을 주지 않으면 배열의 첫 번째 요소가 초기값이 된다.
const sum = arr3.reduce((x, y) => x + y, 0); // 10
참고 문헌
https://product.kyobobook.co.kr/detail/S000213641007
SUMMARY알고리즘은 꾸준히 공부해주지 않으면 개념들이 유독 빠르게 사라지는 것 같아요. 사라지면 다시 채워넣을 수 있도록 꾸준히 공부해보겠습니다. 잘못된 지식이 있다면 댓글 부탁드려요!
읽어주셔서 감사해요.