[Python] 알고리즘 개념3 - 배열과 리스트

---

 

🚀 1. 배열과 리스트란?

배열(Array)과 리스트(List)는 데이터를 저장하는 자료구조입니다. 이 두 개념은 비슷하지만, 동작 방식과 메모리 구조에서 차이가 있습니다.

 

✅ 배열 (Array)

배열은 같은 데이터 타입의 요소를 연속된 메모리 공간에 저장하는 자료구조입니다. 배열은 크기가 고정되며, 각 요소는 인덱스를 사용해 O(1)의 속도로 접근할 수 있습니다.

# 배열을 사용하려면 array 모듈 필요
import array
arr = array.array('i', [1, 2, 3, 4, 5])
print(arr[2])  # 3

 

💡 배열의 특징:

• 같은 데이터 타입만 저장 가능
• 크기가 고정됨 (동적으로 변경 불가)
• 빠른 인덱스 접근 가능 (O(1))
• 중간 삽입/삭제 시 O(n) 시간이 소요됨

 

 

✅ 리스트 (List)

리스트는 다양한 데이터 타입을 저장할 수 있는 동적 자료구조입니다. Python의 리스트는 내부적으로 동적 배열(Dynamic Array) 구조를 사용합니다.

# 리스트 선언 및 사용
arr = [1, 2, 3, 4, 5]  # 정수 리스트
mixed_list = [1, "hello", 3.5, True]  # 다양한 타입 포함 가능

# 요소 접근
print(arr[0])  # O(1)
print(arr[-1])  # O(1)

 

💡 리스트의 특징:

• 서로 다른 타입의 데이터 저장 가능
• 크기가 동적으로 변함
• 인덱스 접근 속도는 빠름 (O(1))
• 중간 삽입/삭제 시 O(n) 시간이 소요됨

➡ 배열은 고정된 크기를 가진 반면, 리스트는 크기가 유동적이며 다양한 데이터 타입을 포함할 수 있습니다.

---

 

 

🚀 2. 배열과 리스트의 차이

비교 항목 배열(Array) 리스트(List)

메모리 구조	연속된 메모리 할당	동적 메모리 할당
데이터 타입	같은 타입만 저장 가능	여러 타입 저장 가능
크기 조정	변경 불가 (고정 크기)	동적 크기 조절 가능
접근 속도	빠름 (O(1))	빠름 (O(1))
삽입/삭제 속도	느림 (O(n))	빠름 (O(1) ~ O(n))

➡ 배열은 빠른 접근 속도를 가지지만 크기 조정이 어렵고, 리스트는 유연하지만 메모리 오버헤드가 발생할 수 있습니다.

---

 

 

🚀 3. 배열과 리스트의 시간복잡도

연산 배열 (Array) 리스트 (List)

접근 (indexing)	O(1)	O(1)
삽입 (append)	X	O(1)
삽입 (중간에 추가)	X	O(n)
삭제 (remove)	X	O(n)
크기 변경	불가능	O(n) (재할당 발생)

➡ Python 리스트의 삽입/삭제 연산은 시간복잡도가 O(n)이므로, 리스트 중간에 요소를 삽입하거나 삭제하면 성능이 저하될 수 있습니다.

---

 

 

🚀 4. 효율적인 리스트 사용법

 

✅ 리스트 크기를 미리 할당하기

리스트의 크기가 변경될 때마다 새로운 메모리를 할당하고 기존 데이터를 복사하는 오버헤드가 발생합니다. 따라서 크기를 미리 설정하면 성능을 최적화할 수 있습니다.

arr = [0] * 1000000  # 크기가 100만인 리스트 생성

 

✅ deque 사용하여 빠른 삽입/삭제 수행

리스트의 중간 삽입/삭제가 많다면, collections.deque를 사용하면 성능이 개선됩니다.

from collections import deque

dq = deque([1, 2, 3, 4])
dq.append(5)  # O(1)
dq.appendleft(0)  # O(1)
dq.pop()  # O(1)
dq.popleft()  # O(1)

💡 deque는 양방향 연결 리스트 구조로 구현되어 있어, 리스트보다 삽입/삭제 연산이 훨씬 빠름(O(1))

➡ 리스트의 삽입/삭제가 많다면 deque를 고려하는 것이 성능 면에서 유리합니다.

---

 

 

✅ 마무리 정리

• 배열은 고정된 크기이며 연속된 메모리를 사용해 빠른 접근이 가능하지만, 크기 변경이 어렵다.
• 리스트는 동적 크기 조절이 가능하고 다양한 데이터 타입을 저장할 수 있지만, 메모리 오버헤드가 있다.
• Python에서는 리스트를 기본적으로 사용하며, 삽입/삭제가 빈번한 경우 deque를 고려한다.