배열(Array)
배열은 동일한 데이터 유형을 가진 여러 개의 요소들을 하나의 변수에 저장하기 위한 자료 구조입니다. 각 요소는 인덱스를 사용하여 접근할 수 있습니다.
1. 배열이란?
배열은 동일한 데이터 유형을 가진 여러 개의 요소들을 하나의 변수에 저장하기 위한 자료 구조입니다. 각 요소는 고유한 인덱스를 가지고 있으며, 이 인덱스를 사용하여 요소에 빠르게 접근할 수 있습니다.
2. 배열의 구성 요소
- 요소(Element): 배열에 저장된 개별 데이터 항목을 의미합니다.
- 인덱스(Index): 각 요소의 위치를 가리키는 숫자 값으로, 0부터 시작하여 순차적으로 증가합니다.
3. 배열의 특징
- 동일한 데이터 타입: 배열은 동일한 데이터 타입의 요소들로 이루어져야 합니다.
- 고정된 크기: 배열은 생성 시 크기가 결정되며, 크기를 동적으로 변경할 수 없습니다.
- 연속적인 메모리 할당: 배열의 요소들은 연속된 메모리 공간에 할당되어 있어 빠른 접근이 가능합니다.
장단점:
장점:
- 빠른 접근: 인덱스를 사용하여 요소에 빠르게 접근할 수 있으며, 시간 복잡도가 O(1)입니다.
- 메모리 효율: 연속된 메모리 할당으로 메모리 사용이 효율적입니다.
- 단순한 구조: 간단한 인덱스 계산만으로 요소에 접근할 수 있어 구현이 간단합니다.
단점:
- 고정된 크기: 배열의 크기는 생성 시에 결정되며, 크기를 변경하기 어렵습니다.
- 메모리 낭비: 배열의 크기보다 작은 데이터도 모두 할당되어 메모리 낭비가 발생할 수 있습니다.
- 중간 삽입/삭제의 비효율성: 중간에 요소를 추가하거나 삭제할 경우, 이후의 요소들을 이동시켜야 하므로 비효율적입니다.
주의할 점:
- 인덱스 범위 확인: 배열의 인덱스는 0부터 시작하며, 유효한 범위 내에서만 접근해야 합니다.
- 메모리 오버플로우 방지: 배열 요소에 접근할 때 메모리 오버플로우를 방지하기 위해 주의가 필요합니다.
- 동일한 데이터 타입 유지: 배열은 동일한 데이터 타입으로 구성되어야 합니다.
4. 접근, 검색, 추가, 삭제와 시간복잡도
배열은 다양한 연산을 수행할 수 있는데, 대표적으로 접근(access), 검색(search), 추가(add), 삭제(remove) 연산이 있습니다. 이 연산들의 시간 복잡도는 배열의 특성에 따라 달라집니다.
접근 (Access):
배열의 특정 위치에 저장된 요소에 접근하는 연산입니다. 인덱스를 사용하여 직접 요소에 접근하므로 매우 빠른 시간에 수행됩니다. 시간 복잡도는 O(1)입니다.
검색 (Search):
특정 요소의 값을 찾는 연산입니다. 배열에서 요소를 검색할 때 최악의 경우 배열 전체를 순회해야 할 수 있으므로, 선형 검색(Linear Search)을 사용할 경우 최악의 시간 복잡도는 O(n)입니다. 하지만 정렬된 배열에서 이진 검색(Binary Search)을 사용하면 시간 복잡도를 O(log n)으로 줄일 수 있습니다.
추가 (Add):
새로운 요소를 배열에 추가하는 연산입니다. 배열의 끝에 요소를 추가할 경우에는 비교적 간단하게 수행됩니다. 하지만 중간에 요소를 추가하려면 추가한 위치 이후의 요소들을 모두 이동시켜야 하므로, 시간 복잡도는 최악의 경우 O(n)이 될 수 있습니다.
삭제 (Remove):
배열에서 요소를 삭제하는 연산입니다. 삭제된 요소 이후의 요소들을 앞으로 이동시켜 빈 공간을 메꿔야 하므로, 중간에 요소를 삭제할 경우 시간 복잡도는 최악의 경우 O(n)이 될 수 있습니다. 하지만 끝에 있는 요소를 삭제할 경우에는 O(1)의 시간 복잡도를 가질 수 있습니다.
5. 배열 활용문제 풀어보기
문제 1
- C 언어에서 배열 선언하는 방법은 무엇인가요?
문제 2
int nums[] = {18, 5, 12, 9, 27, 8};
int length = sizeof(nums) / sizeof(nums[0]);
int max = nums[0];
for (int i = 1; i < length; i++) {
if (nums[i] > max) {
max = nums[i];
}
}- 위 코드는 무엇 구하는 코드인가요?
문제 3
int data[] = {5, 8, 12, 6, 10};
int index = 2;
printf("값: %d\n", data[index]);- 위 코드는 어떤 값을 출력하나요?
문제 4
int n = 10;
for (int i = 0; i < n; i++) {
printf("%d\n", i);
}- 구현된 for문의 시간 복잡도는 무엇인가요?
