자료구조 기초 - 배열(Array)

배열이란 무엇일까?

컴퓨터는 데이터를 저장하고 꺼내는 작업을 반복해서 처리합니다. 이때 데이터를 정리된 형태로 저장하려면 ‘자료구조’가 필요합니다. 그중에서도 가장 기초적이고 자주 사용되는 자료구조가 바로 배열(Array) 입니다.

배열의 정의

배열은 같은 종류의 데이터를 순서대로 저장하는 구조입니다. 각 데이터는 메모리상에 연속적으로 배치되어 있고, 번호(인덱스)를 통해 빠르게 접근할 수 있습니다.

예를 들어, 학생 5명의 수학 점수를 저장하고 싶다면 이렇게 배열을 사용할 수 있습니다:

scores = [82, 90, 76, 88, 95]  # 0번부터 4번까지 번호가 붙습니다.
print(scores[0])  # 결과: 82
print(scores[3])  # 결과: 88

배열의 특징

• 빠른 접근: 원하는 데이터의 위치를 번호(인덱스)로 알면, 바로 꺼낼 수 있습니다.
• 크기 고정: 일반적인 배열은 처음 만들 때 크기를 정해야 합니다. (Python의 리스트는 예외입니다)
• 같은 데이터 타입: C나 Java에서는 배열 안에 같은 타입의 데이터만 넣을 수 있습니다.

배열의 시간복잡도

시간복잡도란?

시간복잡도(Time Complexity)는 어떤 작업을 할 때, 입력의 크기(n)에 따라 수행 시간이 얼마나 증가하는지, 쉽게 말해 시간이 얼마나 걸리는지를 수학적으로 표현한 것입니다.

예를 들어:

• O(1)은 입력의 크기와 상관없이 항상 일정한 시간이 걸린다는 의미입니다. → 매우 빠른 연산입니다.
• O(n)은 입력이 많아질수록 그에 비례해서 시간이 증가한다는 의미입니다. → 느려질 수 있습니다.

간단한 예시로 이해해봅시다:

# O(1) 예시: 배열에서 한 요소를 꺼낼 때
arr = [10, 20, 30]
print(arr[1])  # 항상 한 번에 접근하므로 O(1)

# O(n) 예시: 배열에서 특정 값을 찾기
target = 30
for value in arr:
    if value == target:
        print("찾았다!")  # 앞에서부터 끝까지 비교 → 최대 n번 비교할 수 있음

작업	시간복잡도	설명
접근 (Access)	O(1)	인덱스로 바로 찾아갈 수 있어서 매우 빠릅니다.
검색 (Search)	O(n)	전체를 하나씩 비교해봐야 할 수도 있습니다.
삽입 (Insert)	O(n)	중간에 끼워 넣으면 뒤의 요소를 모두 밀어야 합니다.
삭제 (Delete)	O(n)	중간에서 지우면 빈칸을 채우기 위해 뒤 요소를 당겨야 합니다.

배열의 장점과 단점

장점

• 인덱스로 빠르게 원하는 데이터를 꺼낼 수 있습니다.
• 코드가 간단하고 사용하기 쉽습니다.

단점

• 배열의 크기를 처음에 정해야 합니다. 나중에 늘리거나 줄이기 어렵습니다.
• 중간에 데이터를 넣거나 뺄 때 느립니다. (많은 데이터를 이동해야 합니다)

실생활 예시로 생각해보기

배열은 사물함과 비슷합니다. 사물함 번호를 알면 바로 열 수 있지만, 중간에 물건을 넣으려면 나머지를 모두 옮겨야 합니다.

마무리 정리

항목	배열
데이터 접근	빠름 (O(1))
삽입/삭제	느림 (O(n))
크기 조절	어려움
사용 용도	데이터 수가 정해져 있고, 빠르게 접근해야 할 때