배열 (Array)

아마도 코딩 테스트 문제에서 가장 많이 등장하는 자료구조는 배열(array)일 것입니다. 입력 값이 배열의 형태로 주어지는 경우도 굉장히 많은데요.

이번 글에서는 너무 흔해서 오히려 소홀히 공부하기 쉬운 자료구조인 배열에 대해서 코딩 테스트의 관점에서 살펴보도록 하겠습니다.

순서있게 값을 저장

배열의 가장 중요한 특징인 값을 인덱스(index)를 사용하여 순서있게 저장한다는 것입니다. 그래서 이 인덱스(index)를 통해서 특정 위치에 저장되어 있는 값을 상수 시간(O(1))에 읽고 쓸 수 있죠.

예를 들어, 다음과 같은 형태로 값이 저장되어 있는 배열 arr가 있을 때,

index: 0 1 2 3 4 5 6 7 8 9
value: A B C D E F G H I J

인덱스 3에 있는 값을 D에서 K로 변경해보겠습니다.

print(arr[3]) # 'D'
arr[3] = 'K' # 인덱스 3에 있는 값을 'D'에서 'K'로 변경
print(arr[3]) # 'K'

이와 깉이 대부분 프로그래밍 언어에서는 배열이 가리키고 있는 변수명 뒤에 대괄호를 붙여서 arr[i] 형태의 문법으로 배열에 저장되어 있는 값에 접근하거나 갱신할 수 있습니다.

단, 배열의 크기를 초과하는 인덱스를 사용할 경우 예외가 발생하오니 주의 바랍니다.

arr[10] # Index Error

배열에는 동일한 값을 여러 번 저장할 수 있습니다. 값이 동일하더라도 인덱스가 틀리기 때문에 데이터의 중복이 전혀 문제되지 않습니다.

예를 들어, 다음 배열에는 A가 1개, B가 2개, C가 3개, D가 4개 저장되어 있습니다.

index: 0 1 2 3 4 5 6 7 8 9
value: A B B C C C D D D D

만약에 배열에서 중복되는 값을 제거해야 한다면 집합(Set) 자료구조를 사용해야 합니다.

배열에 저장된 모든 값에 접근하기 위해서는 루프를 돌아야하는데요.

전통적으로는 for 문을 사용하여 인덱스 i를 통해서 값에 접근하는 코딩 패턴이 많이 사용됩니다.

예를 들어, 자바스크립트에서 arr 배열에 저장된 모든 값을 콘솔에 출력하는 코드는 다음과 같이 작성할 수 있습니다.

for (let i = 0; i < arr.length; i++) {
  console.log(arr[i]);
}

최근에는 함수형 프로그래밍이 보편화되면서 forEach()와 같은 함수를 이용하는 경우도 어렵지 않게 볼 수 있습니다.

예를 들어, 자바스크립트의 배열에서 제공하는 forEach() 함수를 사용하여 위 코드를 재작성해 보겠습니다.

arr.forEach(console.log);

일반적으로 배열은 메모리에서 특정 부분을 선점하기 때문에 배열에 저장할 수 있는 값의 개수는 고정되게 됩니다.

예를 들어, 자바에서 빈 배열을 생성할 때는 Array() 생성자에 배열의 크기를 인자로 넘깁니다.

char[] array = new char[10];

따라서 배열은 저장해야 할 값의 개수를 미리 알수 없을 때는 매우 비효율적인 자료구조가 될 수 있습니다. 왜냐하면 배열의 크기를 초과하는 개수의 값을 저장하기 위해서는 새로운 배열을 만들어서 기존 배열에 있던 모든 값을 복사해줘야 때문입니다.

char[] newArray = new char[array.length * 2];

for (char i = 0; i < array.length; i++) {
    newArray[i] = array[i];
}

newArray[10] = 'K';

파이썬이나 자바스크립트처럼 이 부분에 대해서 덜 엄격한 프로그래밍 언어에서는 배열의 크기가 동적으로 늘어나기도 합니다.

값을 맨 뒤가 아니라 중간에 삽입하거나 삭제해야 한다면 배열은 자료구조로서 최악의 선택이 될 수 있습니다. 왜냐하면 기존에 저장되어 있는 많은 값들을 모두 한 킨씩 밀어줘야하는 shift 작업이 수반되는데 매우 비효율적이기 때문입니다.

예를 들어서, 다음과 같이 10개의 알파벳이 저장되어 있는 배열이 있다고 가정해봅시다.

const arr = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J"];

이 중 인덱스 3에 있는 D를 삭제해야 한다면 어떻게 해야 할까요? 삭제 후에 F부터 J까지의 모든 알피벳을 왼쪽으로 한 칸씩 이동시켜줘야겠죠?

delete arr[3]; // `D` 삭제

for (let i = 4; i < arr.length; i++) {
  arr[i - 1] = arr[i]; // 한 칸씩 왼쪽으로 이동
}

arr.pop(); // 마지막 값 버림

이렇게 값을 중간에서 삭제하거나 삽입해야 할 일이 많다면 링크드 리스트(Linked List)가 좋은 대안이 될 것입니다.

배열은 값을 순서있게 저장하는 자료구조로써 인덱스를 통해 매우 빠르게 값에 접근하거나 갱신할 수 있습니다. 하지만 값을 맨 끝이 아닌 중간에서 삭제하거나 삽입해야 할 때는 적합하지 않은 자료구조입니다.