[Python] 자료구조(Data Structure) / 1. 배열(Array)

선형구조

---

1. 배열(array)

같은 타입의 데이터를 일정한 순서로 저장하는 자료구조이다.

인덱스(index)로 접근할 수 있으며, 인덱스는 0부터 시작

---

✅ 배열의 구조

# 예시 (Python)
arr = [10, 20, 30, 40]
print(arr[0])  # 10
print(arr[2])  # 30

인덱스(Index)	0	1	2	3
값(Value)	10	20	30	40

• 고정된 크기를 가지며, C나 Java의 기본 배열은 초기화할 때 크기를 지정해야 한다.
• Python의 리스트는 유사 배열이지만 동적으로 크기가 변한다.

 

✅ 배열의 특징

• 배열에서는 임의접근(random access)이 가능하다. 즉 내가 원하는 원소에 바로 접근하는 것이 쉽다.
• 하지만 정렬되어 있는 데이터의 n번째 데이터를 삭제하는 경우 그 뒤에 있던 데이터들이 모두 한 칸씩 앞으로 이동을 하게 된다. 즉 원소 하나를 추가하거나 삭제하기 위해서 데이터 이동 횟수가 많아지게 되는 오버헤드(overhead)가 발생할 수 있다.

장점	단점
- 각 인덱스로 빠르게 접근 가능 (O(1)) - 데이터가 연속적으로 저장되어 캐시 효율이 높음	- 삽입/삭제 시 비효율적 (O(n)) - 고정 크기(일반 배열은 크기 변경 불가)

 

 

✅ 배열의 시간 복잡도

연산	설명	시간 복잡도
접근	arr[i]	O(1)
검색	값을 찾을 때 (arr[i] == x)	O(n)
삽입	중간에 넣으면 뒤 각 요소들 이동 필요	O(n)
삭제	중간 요소 삭제 시 이동 발생	O(n)

 

 

✅ 언어별 배열 예시

• Python

arr = [1, 2, 3]
arr.append(4)  # [1, 2, 3, 4]
arr.pop()      # [1, 2, 3]

• C++

#include <vector>
vector<int> arr = {1, 2, 3};
arr.push_back(4); // [1, 2, 3, 4]

 

 

✅ 배열 관련 문제 예시 (Python)

예제: 평균 구하기

arr = [1, 2, 3, 4, 5]
avg = sum(arr) / len(arr)
print(avg)  # 3.0

 

예제: 최대값 찾기

arr = [10, 20, 5, 3]
max_val = max(arr)
print(max_val)  # 20

 

 

✅ 배열을 배워야 하는 이유

• 배열은 모든 자료구조의 기초로 리스트, 큐, 스택, 해시 테이블, 힙, 트리 같은 자료구조들이 배열을 기반으로 구현되기도 한다.
• 또한 알고리즘 문제 풀이 시 배열을 자주 다루게 된다. (ex. 정렬, 탐색, 슬라이딩 윈도우, 투 포인터 등)

 

 

 

 

 

 

---

자료구조(Data Structure) / 연결 리스트(Linked List) 내용

https://genie0000.tistory.com/18

[Python] 자료구조(Data Structure) / 2. 연결 리스트(Linked List)

 

 

 

 

---

📌 아직 배우는 중이라 부족한 부분이 있을 수 있습니다.
혹시 잘못된 내용이나 더 나은 방법이 있다면 알려주세요 🙏
감사합니다! 😄