[자료구조와 알고리즘] 리스트(List) - Python

---

📚 리스트(List)

✅ 리스트(List): 데이터들을 잘 관리하기 위해 묶어서 관리할 수 있는 자료형.

• 여러가지 데이터들을 ,로 구분하여 []로 감싼 구조

• 저장되는 요소들이 모두 같은 자료형일 필요가 없다.

arr = [0, 1.23, '파이썬', [0, 0]]
print(f'arr: {arr}, 타입: {type(arr)}\n')

for idx, value in enumerate(arr):
    print(f'arr의 {idx + 1}번째 원소: {value},  타입: {type(value)}')

arr: [0, 1.23, '파이썬', [0, 0]], 타입: <class 'list'>

arr의 1번째 원소: 0,  타입: <class 'int'>
arr의 2번째 원소: 1.23,  타입: <class 'float'>
arr의 3번째 원소: 파이썬,  타입: <class 'str'>
arr의 4번째 원소: [0, 0],  타입: <class 'list'>

---

1. 리스트 인덱싱(Indexing)

• 리스트의 인덱스(Index)로 리스트의 원소에 접근할 수 있으며, 0부터 (리스트의 크기 - 1)까지로 구성된다.

• 이때, 인덱스로 -1을 사용할 경우 리스트의 크기와 관계없이 리스트의 마지막 원소를 가져온다.

arr = [10, 20, 30, 40, 50]

print(arr[0], arr[3], arr[4]) # 10 40 50
print(arr[-1]) # 50

---

2. 리스트 슬라이싱(Slicing)

• 리스트의 인덱스를 지정하여 원소를 불러올 때, 중간에 :를 사용하여 원하는 범위의 값을 가져올 수 있다.

arr = [10, 20, 30, 40, 50]

# 1번째 원소 ~ 3번째 원소
print(arr[1:4]) # [20, 30, 40]

# 2번째 원소 ~
print(arr[2:]) # [30, 40, 50]

# ~ 3번째 원소
print(arr[:4]) # [10, 20, 30, 40]

# 모든 원소
print(arr[:]) # [10, 20, 30, 40, 50]

---

3. 리스트 연산자(Operator)

• +, *를 사용하여 리스트를 합치거나, 반복하는 작업을 할 수 있다.

arr1 = [10, 20, 30]
arr2 = [30, 40, 50]

print(arr1 + arr2) # [10, 20, 30, 30, 40, 50]
print(arr1 * 3) # [10, 20, 30, 10, 20, 30, 10, 20, 30]

---

4. 리스트와 관련된 함수

4.1 append()

• 리스트의 맨 마지막(오른쪽)에 원소를 추가한다.
• 데이터 타입에 관계없이 추가할 수 있다.
• 시간복잡도: O(1)

arr = [10, 20, 30]

arr.append(50)
print(arr) # [10, 20, 30, 50]

arr.append('a')
print(arr) # [10, 20, 30, 50, 'a']

4.2 extend()

• 서로 다른 두 리스트를 결합한다.
• 시간복잡도: O(N) (결합되는 리스트의 크기만큼)

arr1 = [10, 20, 30]
arr2 = [40, 50, 60]

arr1.extend(arr2)
print(arr1) # [10, 20, 30, 40, 50, 60]

4.3 insert()

• insert()에 지정한 인덱스의 위치에 원소를 삽입한다.
• 시간복잡도: O(N)

arr = [10, 20, 30, 40, 50]

arr.insert(3, 100)
print(arr) # [10, 20, 30, 100, 40, 50]

4.4 pop(), pop(i)

• pop()의 경우 리스트의 맨 마지막(오른쪽)에 있는 원소를 제거하고 return한다.

• pop(i)의 경우 리스트의 i번째 인덱스의 원소를 제거하고 return한다.

• 시간복잡도
  pop(): O(1)
  pop(i): O(N)

arr = [10, 20, 30, 40, 50]

n1 = arr.pop()
print(f'arr: {arr}, n1: {n1}')
# arr: [10, 20, 30, 40], n1: 50

n2 = arr.pop(1)
print(f'arr: {arr}, n2: {n2}')
# arr: [10, 30, 40], n2: 20

4.5 remove()

• remove()에 지정된 원소를 찾아 제거한다.
• 시간복잡도: O(N)

arr = [10, 20, 30, 40, 50]

arr.remove(40)
print(arr) # [10, 20, 30, 50]

4.6 index()

• index() 에 지정된 원소의 인덱스를 반환한다.
• 시간복잡도: O(N)

arr = [10, 20, 30, 40, 50]

print(arr.index(40)) # 3

4.7 len()

• 리스트의 길이를 반환한다.
• 시간복잡도: O(1)

arr = [10, 20, 30, 40, 50]

print(len(arr)) # 5

---

5. 리스트의 정렬

5.1 sort()

• 리스트의 원소를 위 아스키 코드 기준으로 정렬한다.
• 정렬이 바로 이루어지며 값을 따로 return하지 않는다.
• reverse 인자를 사용하여 내림차순, 오름차순을 지정할 수 있으며, 기본값은 False
• key 인자를 사용하여 key에 지정된 함수를 기준으로 정렬한다.
• 시간복잡도: O(N log N)

arr = [10, 50, 80, 40, 20]

arr.sort()
print(arr)
# [10, 20, 40, 50, 80]

arr.sort(reverse=True)
print(arr)
# [80, 50, 40, 20, 10]

arr_2d = [[1, 50], [6, 30], [8, 20]]

arr_2d.sort(key=lambda x: x[1])
print(arr_2d)
# [[8, 20], [6, 30], [1, 50]]

5.2 sorted()

• 리스트의 원소를 위 아스키 코드 기준으로 정렬한다.
• 정렬된 리스트를 return한다.
• reverse 인자를 사용하여 내림차순, 오름차순을 지정할 수 있으며, 기본값은 False
• key 인자를 사용하여 key에 지정된 함수를 기준으로 정렬한다.
• 시간복잡도: O(N log N)

arr = [10, 50, 80, 40, 20]

print(sorted(arr))
# [10, 20, 40, 50, 80]

print(sorted(arr, reverse=True))
# [80, 50, 40, 20, 10]

arr_2d = [[1, 50], [6, 30], [8, 20]]

print(sorted(arr_2d, key=lambda x: x[1]))
# [[8, 20], [6, 30], [1, 50]]

---

6. 리스트의 복사

가장 간단하게 리스트를 복사하는 방법으론 = 연산자를 사용하는 것이다.

그러나 이는 리스트의 값을 수정하거나 추가/삭제하는 과정에서 문제가 발생할 수 있다.

arr1 = [10, 20, 30]
arr2 = arr1

arr2.append(50)
print(f'arr1: {arr1}, arr2: {arr2}')
# arr1: [10, 20, 30, 50], arr2: [10, 20, 30, 50]

arr2[1] = 100
print(f'arr1: {arr1}, arr2: {arr2}')
# arr1: [10, 100, 30, 50], arr2: [10, 100, 30, 50]

n = arr2.pop()
print(f'arr1: {arr1}, arr2: {arr2}')
# arr1: [10, 100, 30], arr2: [10, 100, 30]

위 코드에서 볼 수 있듯이, arr1을 arr2로 가져와 arr2에 대해서만 작업을 했는데도 arr1이 함께 변경되는 것을 볼 수 있다.

이는 =를 사용하여 리스트를 복사할 경우 arr1, arr2 모두 같은 주소를 가리키기 때문이다.

그렇다면 이와 같은 문제를 해결하기 위해 어떤 방법을 사용해야 할까?

6.1 얕은 복사(Shallow Copy)

얕은 복사의 방법으론 슬라이싱을 사용하는 방법과 copy() 함수를 사용하는 방법이 있다.

arr1 = [10, 20, 30]
arr2 = arr1[:]
arr3 = arr1.copy()

# 슬라이싱을 활용한 방법
arr2.append(500)
print(f'arr1: {arr1}, arr2: {arr2}')
# arr1: [10, 20, 30], arr2: [10, 20, 30, 500]

# copy() 함수를 사용한 방법
n = arr3.pop()
print(f'arr1: {arr1}, arr3: {arr3}')
# arr1: [10, 20, 30], arr3: [10, 20]

이처럼 슬라이싱과 copy() 함수를 사용한 경우 arr2와 arr3에 대해 작업을 해도 원본인 arr1의 원소는 변경되지 않는다는 것을 볼 수 있다.

그러나 얕은 복사에도 문제가 존재하는데, 2차원 리스트와 같이 리스트의 원소로 리스트를 가지고 있는 경우가 있다.

arr1 = [10, 20, [300, 400]]
arr2 = arr1[:]
arr3 = arr1.copy()

# 슬라이싱을 활용한 방법
arr2[2].append(1000)
print(f'arr1: {arr1}, arr2: {arr2}')
# arr1: [10, 20, [300, 400, 1000]], arr2: [10, 20, [300, 400, 1000]]

# copy() 함수를 사용한 방법
arr3[2][1] = 1
print(f'arr1: {arr1}, arr3: {arr3}')
# arr1: [10, 20, [300, 1, 1000]], arr3: [10, 20, [300, 1, 1000]]

위 코드와 같이 arr1, arr2, arr3 안의 리스트는 여전히 같은 곳을 참조하고 있기 때문에 이곳에 대해 작업을 할 경우 세 개의 리스트가 모두 동시에 변경되는 것을 볼 수 있다.

이를 해결하기 위해 깊은 복사(Deep Copy)를 사용할 수 있다.

6.2 깊은 복사(Deep Copy)

깊은 복사는 copy 모듈의 deepcopy() 함수를 사용하며 이를 사용할 경우 원본 리스트에 있는 값들을 완전히 새로운 공간에 복사하기 때문에 새로운 리스트에 대한 작업이 원본 리스트에 영향을 미치지 않는다.

import copy

arr1 = [10, 20, [300, 400]]
arr2 = copy.deepcopy(arr1)

arr2[1] = 2
print(f'arr1: {arr1}, arr2: {arr2}')
# arr1: [10, 20, [300, 400]], arr2: [10, 2, [300, 400]]

arr2[2].append(1000)
print(f'arr1: {arr1}, arr2: {arr2}')
# arr1: [10, 20, [300, 400]], arr2: [10, 2, [300, 400, 1000]]

arr2[2].pop(1)
print(f'arr1: {arr1}, arr2: {arr2}')
# arr1: [10, 20, [300, 400]], arr2: [10, 2, [300, 1000]]

그러나 deepcopy() 함수는 모든 값을 복사하고, 새로운 공간에 저장해야 하기 때문에 얕은 복사에 비해 시간과 메모리 사용이 많이 늘어나게 된다.

따라서 상황에 맞춰 얕은 복사를 사용할 때도 많고, 특히 시간 계산이 중요한 PS 분야에서는 대부분 얕은 복사를 많이 사용한다.

---