배열 연산의 시간 복잡도

🕰️ 시간 복잡도 먼저 이해하기

문제를 해결하는 데 걸리는 시간, 입력된 데이터를 함수로 표현해 데이터를 다루는데 걸리는 시간을 정량화해 나타낸 것을 시간 복잡도라고 한다. 어떤 목적을 달성하거나 결과물을 만들기 위해 거쳐야하는 과정을 알고리즘이라고 하는데, 이때 다양한 알고리즘이 나타날 수 있으며 그 중에서 가장 시간복잡도가 낮은 것을 선택해야한다.

☑️ 배열에서의 시간 복잡도

배열은 임의 접근이라는 방법으로 배열의 모든 위치에 있는 데이터에 단 한 번에 접근할 수 있다. 따라서 데이터에 접근하기 위한 시간 복잡도는 O(1)이다.

 맨 뒤에 데이터를 추가할 경우, arr = [1, 2, 3] -> arr = [1, 2, 3, 4] 형태로 추가한다 했을 때 arr[3]에 다른 데이터 위치에 영향을 주지않고 한번에 접근할 수 있으므로 시간 복잡도는 O(1)이다.

 만약 맨 앞에 삽입할 경우에는 기존에 인덱스에 있던 요소들을 하나씩 밀어줘야함으로 데이터 개수 N개만큼 연산이 추가적으로 들어간다. 그 때 시간 복잡도는 O(N)이 된다.

 중간에 삽입할 경우 삽입한 데이터 뒤에 있는 데이터 개수 N개 만큼 미는 연산을 해야함으로 시간 복잡도는 O(N)이 된다.

☑️ 배열 선택시 고려할 점

위에서 알게된 시간 복잡도처럼 데이터에 자주 접근할 경우 배열을 사용하면 한번에 접근함으로 좋은 성능을 낼 수 있다. 이 때 고려해야할 사항은 할당할 수 있는 메모리 크기를 확인해야하고, 중간에 데이터 삽입이 많은지를 확인해야 한다. 배열은 선형 자료구조이기 때문에 중간이나 처음에 데이터를 빈번히 삽입하면 시간 복잡도가 높아져 코딩테스트시에 시간 초과가 발생할 수 있다. 자바스크립트에서는 배열의 크기가 변할 수 있으므로 배열을 리스트처럼 활용할 수 있다.

☑️ 자주 활용하는 배열 기법

데이터 추가하기

const arr = [1, 2, 4];

// 맨 끝 데이터 추가
arr.push(4); // [1, 2, 4, 4]

// 데이터 추가
arr.concat([4, 5]) // [1, 2, 4, 4, 5]

// 스프레드 연산자 활용하려 추가
arr = [...arr, ...[4, 5]]; // [1, 2, 4, 4, 5]

// 맨 앞 데이터 추가
arr.unshift(0); // [0, 1, 2, 4]

// 위치를 지정하여 데이터 추가
arr.splice(2, 0, 3); // [1, 2, 3, 4] // 2번째 인덱스에 0개의 인수를 삭제하고 3을 추가해줘.

 

배열에서 데이터 삭제

const arr = [1, 2, 3, 4, 5];

// 기존 변수의 맨 마지막 데이터 삭제하고 반환하기 
const poppedElement = arr.pop(); // 5
console.log(arr); // [1, 2, 3, 4]

// 기존 변수의 맨 앞 데이터 삭제하고 반환하기
const shiftedElement = arr.shift(); // 1
console.log(arr); // [2, 3, 4, 5]

// 중간데이터 삭제하기
const removedElements = arr.splice(2, 2) // [3, 4] // 2번째 인덱스에 있는 데이터 2개 삭제하고 반환해줘.
console.log(arr); // [1, 2, 5]

🏷️ splice()메서드

삭제하고 추가할 데이터가 있는 경우에는 3번째 인자부터 추가할 데이터를 넣을 수 있다.

☑️ 고차함수 이용하기

map(), filter(), reduce()와 같은 고차함수를 이용하면 기존 배열 기반으로 새로운 배열을 만드는 것이 가능하다.

🏷️ reduce() 이해하기

map()과 filter()는 사용해야하는 인수가 1개지만 reduce()는 받아야하는 인수가 2개이다. 첫 번째 인자는 이전까지 합쳐진 상태를 의미하고, 현재는 순회하며 바라보고 있는 데이터를 의미한다.

array.reduce(callbackFn, initailValue);

const arr = [1, 2, 3, 4, 5];
// 전체 배열 하나로 합치기
arr.reduce((a, b)=> a + b ); // 15

🏷️ 참고링크

• 알고리즘의 시간복잡도와 Big-O표기법 이해하기
• 코딩테스트 합격자되기 JS - 5장 배열