2-1. 자료구조: 배열

1. 배열의 기본 개념

자료구조는 데이터를 효율적으로 관리하고 사용하기 위한 조직적인 방식입니다. 이 중 배열(Array)은 가장 기본적인 자료구조 중 하나이며, 여러 개의 데이터를 연속된 메모리 공간에 저장하는 구조를 가집니다. 마치 사물함처럼, 각 데이터는 고유한 인덱스(index)를 통해 접근할 수 있습니다. 인덱스는 배열 내 데이터의 위치를 나타내는 정수 값으로, 보통 0부터 시작합니다.

1) 배열의 특징

배열은 다음과 같은 특징을 가집니다.

• 고정된 크기: 일반적으로 배열은 생성될 때 크기가 정해지며, 이 크기를 동적으로 변경하는 것은 쉽지 않습니다. (물론, 동적 배열이라는 개념도 존재합니다.)
• 연속된 메모리 공간: 배열의 각 요소는 메모리 상에서 연속적으로 위치합니다.
• 빠른 접근: 인덱스를 사용하여 O(1) 시간에 특정 요소에 접근할 수 있습니다.

2) 배열의 비유: 사물함

배열을 이해하기 쉽게 비유하자면, 여러 개의 사물함이 일렬로 늘어선 모습과 같습니다. 각 사물함에는 특정 물건(데이터)이 들어있고, 각 사물함에는 고유한 번호(인덱스)가 매겨져 있습니다.

• 사물함 번호(인덱스)를 알면, 해당 사물함(배열 요소)에 바로 접근하여 물건(데이터)을 꺼낼 수 있습니다.
• 사물함의 크기(배열의 크기)가 정해져 있다면, 더 많은 물건을 보관하기 위해 새로운 사물함을 추가하기는 어렵습니다.

2. 배열의 연산

배열은 데이터를 저장하고 관리하는 데 사용되는 기본적인 자료구조이므로, 데이터를 조작하기 위한 기본적인 연산들이 필요합니다. 가장 기본적인 연산은 삽입(Insertion), 삭제(Deletion), 탐색(Search)입니다.

1) 삽입 (Insertion)

배열에 새로운 요소를 삽입하는 것은 배열의 특성상 간단하지 않을 수 있습니다. 배열의 크기가 고정되어 있기 때문에, 삽입 시 배열의 크기를 초과하지 않도록 주의해야 합니다.

• 맨 뒤 삽입: 배열의 마지막 위치에 새로운 요소를 추가하는 것은 비교적 간단하며, O(1)의 시간 복잡도를 가집니다.
• 중간 삽입: 중간에 요소를 삽입하려면, 삽입 위치 이후의 모든 요소들을 한 칸씩 뒤로 밀어야 합니다. 이는 O(n)의 시간 복잡도를 가집니다. (n은 배열의 크기)

2) 삭제 (Deletion)

배열에서 요소를 삭제하는 것도 삽입과 유사한 어려움을 가집니다.

• 맨 뒤 삭제: 배열의 마지막 요소를 삭제하는 것은 O(1)의 시간 복잡도를 가집니다.
• 중간 삭제: 중간 요소를 삭제하려면, 삭제된 요소 이후의 모든 요소들을 한 칸씩 앞으로 당겨야 합니다. 이 연산은 O(n)의 시간 복잡도를 가집니다.

3) 탐색 (Search)

배열에서 특정 요소를 찾는 것은 인덱스를 알고 있다면 O(1)의 시간 복잡도로 매우 빠르게 수행됩니다. 하지만, 찾고자 하는 값의 인덱스를 모르는 경우, 배열의 처음부터 끝까지 모든 요소를 확인해야 하므로 O(n)의 시간 복잡도를 가집니다.

4) 연산의 시간 복잡도 요약

3. 배열의 활용

배열은 다양한 상황에서 활용될 수 있습니다. 특히, 데이터의 순서를 유지하고, 각 요소에 빠르게 접근해야 하는 경우에 유용합니다.

1) 정렬되지 않은 데이터 저장

데이터의 순서가 중요하지 않거나, 빠르게 접근할 필요가 없는 데이터를 저장하는 데 사용할 수 있습니다.

2) 인덱스를 이용한 데이터 접근

인덱스를 사용하여 특정 위치의 데이터를 빠르게 접근해야 하는 경우에 유용합니다. 예를 들어, 게임 맵의 정보를 저장하거나, 이미지 픽셀 데이터를 저장하는 데 사용할 수 있습니다.

3) 2차원 배열 (행렬)

2차원 배열은 행과 열로 구성된 데이터를 표현하는 데 사용됩니다. 이미지 처리, 행렬 연산 등 다양한 분야에서 활용됩니다.

4) 문자열 (Strings)

문자열은 문자의 배열로 표현될 수 있습니다. 각 문자는 배열의 요소가 되고, 문자열의 길이는 배열의 크기가 됩니다.

5) 동적 배열 (Dynamic Arrays)

배열의 크기를 동적으로 조절할 수 있도록 구현된 자료구조입니다. 삽입, 삭제 연산 시 배열의 크기를 자동으로 조절하여 메모리 사용을 효율적으로 관리할 수 있습니다. ArrayList (Java), vector (C++) 등이 대표적인 예시입니다. 동적 배열은 내부적으로 배열을 사용하며, 배열이 가득 차면 더 큰 크기의 새 배열을 할당하고 기존 데이터를 복사하는 방식으로 작동합니다.

4. 배열 사용 시 주의사항

배열을 사용할 때는 다음과 같은 사항에 주의해야 합니다.

1) 메모리 할당 및 해제

C/C++과 같은 언어에서는 배열의 메모리 할당과 해제를 직접 관리해야 합니다. 메모리 누수(memory leak)가 발생하지 않도록 주의해야 하며, 동적 할당된 배열을 사용한 후에는 반드시 free() 또는 delete[] 연산을 통해 메모리를 해제해야 합니다.

2) 인덱스 범위 오류 (Index Out of Bounds)

배열의 유효한 인덱스 범위를 벗어난 접근은 프로그램 오류를 발생시킬 수 있습니다. 배열의 크기를 초과하는 인덱스에 접근하지 않도록 주의해야 합니다.

3) 배열 크기 결정

배열의 크기를 적절하게 결정하는 것은 메모리 사용 효율성과 프로그램 성능에 영향을 미칩니다. 너무 큰 크기의 배열은 메모리 낭비를 초래하고, 너무 작은 크기의 배열은 데이터를 저장할 공간이 부족하여 문제를 발생시킬 수 있습니다.

4) 동적 배열의 오버헤드

동적 배열은 배열의 크기를 자동으로 조절하는 기능을 제공하지만, 배열의 크기를 변경하는 과정에서 추가적인 연산(메모리 할당, 데이터 복사)이 발생하여 성능 저하를 일으킬 수 있습니다. 따라서, 배열의 크기가 자주 변경되는 경우에는 다른 자료구조를 고려하는 것이 좋습니다.

5. 결론

배열은 단순하면서도 강력한 자료구조로, 다양한 상황에서 데이터를 효율적으로 관리하는 데 사용됩니다. 배열의 기본적인 개념, 특징, 연산 및 활용 방법을 이해하고, 배열 사용 시 주의사항을 숙지하여 효율적이고 안정적인 코드를 작성할 수 있도록 해야 합니다. 특히, 배열의 장점과 단점을 정확히 파악하고, 문제 해결에 가장 적합한 자료구조를 선택하는 것이 중요합니다.