배열은 하나의 변수 이름으로 동일한 타입의 데이터를 그룹화하여 관리할 수 있고, 인덱스라는 것으로 원하는 데이터에 임의 접근할 수 있다는 장점이 있는 자료형이다.
배열 선언
배열을 선언하는 방법은 여러가지 있다.
이름이 arr이고 길이가 6인 정수형 배열을 선언하는 3가지 방법을 예제로 알아보자.
리터럴
const arr = [0, 0, 0, 0, 0, 0];
배열 생성자
const arr1 = new Array(6); // [undefined, undefined, ...]
const arr2 = [...new Array(6)].map((_, i) => i + 1); // [1, 2, 3, 4, 5, 6]
Array.fill() 함수
const arr = new Array(6).fill(0); // [0, 0, 0, 0, 0, 0]
위와 같이 선언한 배열은 컴퓨터에 이런 모습으로 저장된다.
배열의 인덱스는 0부터 시작한다. 즉, 3번째 데이터에 접근하려면 arr[2]와 같이 접근하면 된다.
자바스크립트의 Array 객체가 배열과 같은 기능을 지원한다. 엄밀히 따져서 자바스크립트 의 배열은 일반적인 배열과 내부 구현이 다르지만 사용 방법이 크게 다르지는 않다.
자바스크립트의 배열은 동적으로 크기를 조절할 수 있도록 구현되어 있어 다른 언어의 배열 기능을 그대로 사용할 수 있으면서 배열 크기도 가변적이므로 코딩 테스트에서 고려할 사항을 조금 더 줄여준다. 또 슬라이싱, 삽입, 삭제, 연결 등의 연산을 제공하므로 더 편리하다.
배열과 차원
2차원 배열, 3차원 배열과 같이 다차원 배열을 사용할 때도 많다.
하지만 컴퓨터 메모리의 구조는 1차원이므로 2차원, 3차원 배열도 실제로는 1차원 공간에 저장한다.
즉, 배열은 차원과는 무관하게 메모리에 연속 할당된다.
1차원 배열
1차원 배열의 모습은 메모리에 할당된 실제 배열의 모습과 같다.
- 왼쪽 그림이 1차원 배열의 모습이고, 오른쪽 모습이 실제 메모리에 배열이 할당된 모습이다.
- 배열의 각 데이터는 메모리의 낮은 주소에서 높은 주소 방향으로 연이어 할당된다.
2차원 배열
2차원 배열은 다음과 같이 선언할 수 있다.
// 2차원 배열을 리터럴로 표현
const arr = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
];
// arr[2][3]에 저장된 값을 출력
console.log(arr[2][3]); // 12
// arr[2][3]에 저장된 값을 15로 변경
arr[2][3] = 15;
// 변경된 값을 출력
console.log(arr[2][3]); // 15
다음과 같이 선언할 수도 있다.
// 크기가 3 * 4인 배열을 선언하는 예
const arr = [...new Array(3)].map((_, i) => new Array(4).fill(i));
// [[0, 0, 0, 0], [1, 1, 1, 1], [2, 2, 2, 2]]
2차원 배열 데이터에 접근하는 방법은 행과 열을 명시해 [] 연산자를 2개 연이어 사용한다는 점만 다르다.
const arr = [[1, 2, 3], [4, 5, 6]]; // 2행 3열 2차원 배열을 표현
- 왼쪽은 2차원 배열을 사람이 이해하기 쉽도록 2차원으로 표현한 모양이다.
- 하지만 실제로는 오른쪽처럼 0행, 1행 순서로 데이터를 할당해 1차원 공간에 저장한다.
배열 연산의 시간 복잡도
배열은 임의 접근이라는 방법으로 배열의 모든 위치에 있는 데이터에 단 한 번에 접근할 수 있다. 따라서 데이터에 접근하기 위한 시간 복잡도는 O(1)이다.
또한, 배열은 데이터를 어디에 저장하느냐에 따라 추가 연산에 대한 시간 복잡도가 달라진다.
맨 뒤에 삽입할 경우
다음과 같은 배열에서 2를 추가한다면, 맨 뒤에 삽입할 때는 arr[3]에 임의 접근을 바로 할 수 있으며 데이터를 삽입해도 다른 데이터 위치에 영향을 주지 않는다. 따라서 시간복잡도는 O(1)이다.
맨 앞에 삽입할 경우
데이터를 맨 앞에 삽입한다면 기존 데이터들을 뒤로 한 칸씩 밀어야 한다. 즉, 미는 연산이 필요하다. 데이터 개수를 N개로 일반화하면 시간 복잡도는 ○(N)이 된다.
중간에 삽입할 경우
5 앞에 데이터를 삽입한다면 5 이후의 데이터를 뒤로 한 칸씩 밀어야 한다.
즉, 현재 삽입한 데이터 뒤에 있는 데이터 개수만큼 미는 연산을 해야 한다. 밀어야 하는 데이터 개수가 N개라면 시간 복잡도는 ○(N)이 된다.
배열을 선택할 때 고려할 점
데이터에 자주 접근하거나 읽어야 하는 경우 배열을 사용하면 좋은 성능을 낼 수 있다.
예를 들어 그래프를 표현할 때 배열을 활용하면 임의 접근을 할 수 있으므로 간선 여부도 시간 복잡도 ○(1)로 판단할 수 있다. 하지만 배열은 메모리 공간을 충분히 확보해야 하는 단점도 있다.
따라서 코딩 테스트에서는 다음 사항을 고려해 배열을 선택해야 한다.
1. 할당할 수 있는 메모리 크기를 확인
- 배열로 표현하려는 데이터가 너무 많으면 런타임에서 배열 할당에 실패할 수 있다. 운영체제마다 배열을 할당할 수 있는 메모리의 한계치는 다르지만 보통은 정수형 1차원 배열은 1000만 개, 2차원 배열은 3000 * 3000 크기를 최대로 생각한다.
2. 중간에 데이터 삽입이 많은지 확인
- 배열은 선형 자료구조이기 때문에 중간이나 처음에 데이터를 빈번하게 삽입하면 시간 복잡도가 높아져 실제 시험에서 시간 초과가 발생할 수 있다.
자주 활용하는 배열 기법
자바스크립트에서 배열 자료구조가 필요할 때는 앞서 언급했듯 Array 객체를 활용한다. 코딩 테스트에서 자주 활용하는 기법을 알아보자.
배열에 데이터 추가
push()
맨 끝에 데이터를 추가하려면 push() 메서드를 이용하자.
// 배열 맨 끝에 데이터 추가
const arr = [1, 2, 3];
arr.push(4); // [1, 2, 3, 4];concat()
concat()메서드로 배열에 든 데이터를 추가할 수도 있다.
let arr = [1, 2, 3];
arr = arr.concat([4, 5]); // [1, 2, 3, 4, 5]spread 연산자
let arr = [1, 2, 3];
arr = [...arr, ...[4, 5]]; // [1, 2, 3, 4, 5]unshift()
배열의 맨 앞에 데이터를 추가하려면 unshift() 메서드를 이용하자.
const arr = [1, 2, 3];
arr.unshift(0); // [0, 1, 2, 3];- 맨 앞에 데이터를 추가하는 시간 복잡도는 ○(n)이지만 배열 내 데이터가 적으면 자바스크립트 엔진이 최적화를 하여 더 적은 시간 복잡도로 처리한다.
❓ 실험에 따르면 대략 15,000개까지는 최적화가 되지만 이후로 급격하게 느려진다고 한다.
splice()
배열 중간에 데이터를 추가하기 위해서는 splice() 메서드를 사용하자.
array.splice(start[, deleteCount[, item1[, item2[, ...]]]])- 첫 번째 매개변수 start는 배열 내 시작 지점을 의미한다.
- 두 번째 매개변수 deleteCount는 삭제할 데이터의 수를 의미하고 이후로는 추가할 데이터를 받는다. 이를 이용하여 두 번째 매개변수를 0으로 설정하면 다음과 같이 중간에 데이터를 추가할 수 있다.
const arr = [1, 2, 3, 4, 5];
arr.splice(2, 0, 9999); // [1, 2, 9999, 3, 4, 5]
배열에서 데이터 삭제
pop()
pop() 메서드는 가장 마지막 데이터를 삭제하고 반환한다.
const arr = [1, 2, 3, 4, 5];
const poppedElement = arr.pop(); //5
console.log(arr); // [1, 2, 3, 4]
shift()
shift() 메서드는 맨 앞 데이터를 삭제하고 반환한다.
const arr = [1, 2, 3, 4, 5];
const shiftedElement = arr.shift(); // 1
console.log(arr); // [2, 3, 4, 5]
- 배열 특성상 맨 앞 데이터를 삭제하면 시간 복잡도가 **○(n)**이 되지만 unshift() 메서드와 마찬가지로 배열 내 데이터가 적으면 자바스크립트 엔진이 최적화를 해준다.
splice()
splice() 메서드를 이용하여 중간 데이터를 삭제할 수 있다. 첫 번째 매개변수로 시작 지점을 정하고 두 번째 매개변수로 삭제할 데이터의 수를 정하면 된다. 데이터를 삭제할 때는 세 번째 이후 매개변수는 생략한다.
const arr = [1, 2, 3, 4, 5];
const removedElements = arr.splice(2, 2); // [3, 4]
console.log(arr); // [1, 2, 5]
고차 함수를 이용하여 데이터에 특정 연산 적용
자바스크립트는 배열에 map(), filter(), reduce()와 같은 유용한 고차 함수를 기본으로 제공한다.
이를 이용하면 기존 반복문, 조건문을 이용한 복잡한 로직을 대체할 수 있다.
배열에 제곱 연산 적용
다음과 같이 배열의 모든 데이터에 제곱 연산을 적용할 수 있다.
const numbers = [1, 2, 3, 4, 5];
const squares = numbers.map(num => num * num); // [1, 4, 9, 16, 25]
- 주목해야 하는 점은 numbers 배열의 값은 변하지 않는다. 이처럼 배열의 고차 함수는 연산을 마친 배열을 반환할 뿐, 원본 배열을 바꾸지 않는다.
짝수 필터링
filter() 메서드를 이용하면 원하는 조건에 해당하는 값만 남긴 배열을 만들 수 있다. 반환값이 참이면 남기고 거짓이라면 거릅니다.
const numbers = [1, 2, 3, 4, 5];
const evens = numbers.filter(num => num % 2 === 0); // [2, 4]
전체 합
reduce() 메서드를 이용하면 배열의 전체 데이터를 하나로 합칠 수 있다.
const numbers = [1, 2, 3, 4, 5];
const sum = numbers.reduce((a, b) => a + b); // a의 초기값은 0, b는 배열의 각 요소를 순회한다. 결과 --> 15
- 이 메서드는 익명 함수가 받아야 하는 인수가 2개이다.
- 첫 번째 인자는 이전까지 합쳐진 상태를 의미하고 두 번째 인자는 현재 순회하며 바라보고 있는 데이터를 의미한다.