파이썬 Python | 알고리즘 | ⭐⭐⭐⭐ ArrayList

 

⭕ 파이썬 Python | 알고리즘 | ⭐⭐⭐⭐ ArrayList

➡️ ArrayList

ArrayList는 배열과 유사한 자료 구조입니다. 배열은 데이터가 연속적으로 저장된다는 점에서 ArrayList와 차이가 있지만, 이해를 돕기 위해 배열과 유사하다고 생각할 수 있습니다. 알고리즘 문제에서는 배열의 삽입과 삭제가 빈번히 일어나므로 시간 복잡도와의 싸움이 자주 발생합니다. 따라서 삽입이나 삭제를 시간 복잡도를 고려하지 않고 무작위로 수행하면 문제를 해결하지 못할 수 있습니다.

---

ArrayList의 특징

1. 연속된 메모리 공간: ArrayList는 연속된 메모리 공간에 데이터를 저장합니다.
2. 원하는 위치의 값 얻기: 특정 위치의 요소에 접근할 때 O(1)의 시간 복잡도를 가집니다.
3. 삽입 및 삭제: 중간에 요소를 삽입하거나 삭제할 때 O(n)의 시간 복잡도를 가집니다.

 

➡️ 원하는 위치의 값 얻기

ArrayList는 원하는 위치의 값을 O(1)의 시간 복잡도로 얻을 수 있는 자료 구조입니다. 예를 들어, 배열의 2번째 위치에 접근하면 10이 있고, 4번째 위치에 접근하면 30이 들어 있습니다.

arr = [70, 40, 10, 60, 30, 50]
print(arr[2])  # 출력: 10
print(arr[4])  # 출력: 30

 

➡️ 삽입

ArrayList의 3번째 위치에 25를 삽입한다고 가정해 보겠습니다. 삽입할 위치만큼 공간을 확보하여 기존의 원소들을 뒤로 이동해야 합니다. ArrayList에서 원하는 값을 추가할 때, 배열의 크기가 n일 때 최대 n번의 이동을 통해 자리를 만들어 주어야 합니다. 따라서 시간 복잡도는 O(n)이 됩니다.

arr = [70, 40, 10, 60, 30, 50]
arr.insert(3, 24)  # 3번째 위치에 25 삽입
print(arr)  # 출력: [70, 40, 10, 25, 60, 30, 50]

삽입 과정

1. 3번째 위치에 공간을 확보합니다.
2. 3번째 위치부터 끝까지의 원소들을 한 칸씩 뒤로 이동시킵니다.
3. 3번째 위치에 25를 삽입합니다.

 

➡️ 삭제

ArrayList의 3번째 위치의 원소를 삭제한다고 가정해 보겠습니다. 먼저 원하는 위치의 원소를 빈 값으로 바꾸고, 그 후 삭제한 위치 이후의 있는 값들을 왼쪽으로 이동합니다. ArrayList에서 원하는 값을 삭제할 때, 배열의 크기가 n일 때 최대 n번의 이동이 필요합니다. 따라서 시간 복잡도는 O(n)이 됩니다.

arr = [70, 40, 10, 25, 60, 30, 50]
del arr[3]  # 3번째 위치의 원소 삭제
print(arr)  # 출력: [70, 40, 10, 60, 30, 50]

삭제 과정

1. 3번째 위치의 원소를 빈 값으로 바꿉니다.
2. 3번째 위치 이후의 원소들을 한 칸씩 왼쪽으로 이동시킵니다.
3. 마지막 위치의 원소는 제거됩니다.

 

---

주의사항

삽입과 삭제 후 위치를 변경하지 않으면 배열의 순서가 보장되지 않으므로 원치 않는 값을 지울 수 있습니다. 따라서 삽입과 삭제 후에는 반드시 위치를 변경해 주어야 합니다.

 

➡️ 파이썬에서 ArrayList 사용

파이썬에서는 리스트를 사용하여 ArrayList와 같은 기능을 구현할 수 있습니다. 리스트는 동적 배열로 구현되어 있으며, ArrayList와 동일한 기능을 제공합니다.

# 첫 번째 방법
arr = []

# 두 번째 방법
arr = list()

---

요소 추가

arr.append(40)  # 리스트의 끝에 40 추가
print(arr)  # 출력: [5, 10, 15, 20, 30, 40]

 

요소 찾기

index = arr.index(20)  # 값이 20인 요소의 인덱스를 찾음
print(index)  # 출력: 3

 

요소 존재 여부 확인

exists = 15 in arr  # 15가 리스트에 있는지 확인
print(exists)  # 출력: True