리스트 (List)
리스트는 순서를 가지고 원소들을 저장하는 자료구조로, mutable, iterable, sequence 객체입니다.
Array List와 Linked List 2가지 방식으로 구현이 가능한데, python에서 사용하는 리스트는 Array List로 구현되었습니다.
동적 배열 dynamic array
배열(array)은 정적 배열(static array)과 동적 배열(dynamic array)로 구분됩니다. 선언 이후에 크기를 변경할 수 없는 정적배열과 다르게 동적배열은 크기를 늘릴 수 있습니다. 파이썬의 리스트는 내부적으로 동적배열(dynamic array)로 구현되어 있습니다.
List 사용법 - 기본
선언할 때에 배열의 크기를 정하지 않아도 되는 장점 덕분에 코딩테스트에서 동적 배열을 자주 사용하게 됩니다.⁽¹⁾ Python에서는 리스트 자료형을 통해 쉽게 사용할 수 있습니다.
# int형을 담은 list
[1, 3, 2, 4, 5]
# 다양한 자료형을 담은 list
[1, (2, 8), 'c', [1, 9, 8], 4.1, "asd"]
리스트는 서로 다른 자료형의 객체를 한꺼번에 담을 수 있고, 다른 크기의 데이터를 하나의 요소로 접근할 수 있다는 점에서 매우 자유롭습니다. 따라서 파이썬 문제에서 배열을 사용해야 하는 경우에는 리스트를 선언해서 사용하면 됩니다.
이제 파이썬에서 리스트가 어떻게 선언되고 연산이 어떻게 이루어지는지 알아보도록 합시다.
리스트의 선언⁽²⁾
a = list()
a = [1, 2, 3]
리스트 컴프리헨션
리스트 컴프리헨션(list comprehension)은 코드 간결화에 크게 기여하는 기능입니다. 특히 이중 리스트를 선언할 때 자주 사용하는 방법입니다.
# 1 ~ 10을 담는 리스트 만들기
a = [i for i in range(1, 11)]
# 리스트 컴프리헨션으로 이중 리스트 만들기
m = 5
n = 6
b = [[0 for _ in range(m)] for _ in range(n)]
# 조건문과 리스트 컴프리헨션 활용해서 원하는 리스트 만들기
c = [n for n in range(35) if (n % 3 == 0)]
- 결과
리스트 접근하기
- n번째 원소 접근하기
- a[n]
- 0번째 원소 업데이트하기
- a[0] = 3
- 마지막 원소 접근하기
- # len 사용 방식 a[len(a)-1] # 음수 index 사용 방식 a[-1]
음수 index 사용하기 : -1은 마지막 요소를 가리킵니다. -n은 끝에서 n번째 요소라고 생각하면 됩니다.
리스트의 원소 추가
리스트의 원소 추가 같은 경우, 마지막에 원소를 삽입하는 것과 중간에 원소를 삽입하는 것으로 나눌 수 있습니다.
- 마지막에 원소 추가
a.append(1) - 리스트의 마지막에 원소를 삽입하는 경우 맨 뒤에 원소를 추가하기만 하면 되어서 $O(1)$의 시간복잡도를 갖습니다.
- 중간에 원소 추가
⇒ 2번째 index에 10을 추가한다a.insert(2,10) - 하지만 리스트의 중간에 원소를 삽입하는 경우, 원소를 삽입한 후 뒤의 원소들을 한 칸씩 미루어야 하기에 $O(n)$의 시간복잡도를 갖습니다.
리스트 원소 삭제
리스트의 원소 삭제 역시, 마지막 원소를 삭제하는 것과 중간 원소를 삭제하는 것으로 나눌 수 있습니다.
- 마지막 원소 삭제
a.pop() - 리스트의 마지막 원소를 삭제하는 경우, 맨 뒤 원소를 삭제하기만 되기에 $O(1)$의 시간복잡도를 갖습니다.
- 중간 원소 삭제
⇒ 2번째 index에 있는 값을 삭제합니다.⇒ a에서 제일 앞에 있는 값 2를 찾은 후 삭제합니다.a.pop(2) - ⇒ 만약에 a에 2가 없으면, error가 발생합니다.
- a.remove(2)
- 하지만 리스트의 중간 원소를 삭제하는 경우, 원소를 삭제한 후 뒤의 원소들을 한 칸씩 당겨야기에 $O(n)$의 시간복잡도를 갖습니다.
(주의)리스트 순회하며 수정하기
리스트를 순회하는 도중에 리스트의 원소 개수가 변경되어서는 안 됩니다. 문자열의 리스트에서 문자열의 길이가 3인 문자열만 제거하고 싶다고 해봅시다.
strs = ["one", "two", "three", "four", "five"]
for s in strs:
if (len(s) == 3):
strs.remove(s)
print(strs)
- 결과
- ['two', 'three', 'four', 'five']
기대했던 결과는 "one" , "two"가 삭제된 ["three", "four", "five"]일 것입니다. 하지만 실제 결과는 다르게 나오게 됩니다. 순회 중인 리스트에 접근하면서 해당 리스트에서 append, remove, pop 등의 연산을 시도하면, 의도치 않은 결과를 얻게 됩니다.
따라서 이런 경우에는 원본을 직접 수정하는 것이 아니라 새로운 리스트를 만들어 수정의 결과를 저장하면 됩니다. 기존 데이터에 대한 접근과 수정을 모두 올바르게 수행하여 기대하는 결과에 잘 도달하게 될 것입니다. 아래 코드는 위의 상황을 해결하는 코드입니다.
strs = ["one", "two", "three", "four", "five"]
temp = []
for s in strs:
if (len(s) != 3):
temp.append(s)
strs = temp
print(strs)
- 결과
List 사용법 - 심화 (슬라이싱)
<aside> 💡 슬라이싱(Slicing)이란? 리스트, 튜플, 문자열과 같이 연속적으로 데이터가 나열된 객체에서 특정 범위를 선택해 새로운 객체를 만드는 행위입니다.
</aside>
리스트의 활용법 중에서도 슬라이싱은 원하는 데이터에 대한 처리를 손쉽게 할 수 있도록 해주는 강력한 기능을 제공합니다. 슬라이싱의 구조는 다음과 같습니다.
li = [m:n:s]
# m : 시작 인덱스
# n : 종료 인덱스
# s : 인덱스간 간격
유의점 1 : 슬라이싱된 객체의 마지막 요소는 n-1번 인덱스로 접근한 데이터입니다.
유의점 2 : 인덱스 간 간격은 부호에 따라 데이터 나열 순서가 달라집니다.
유의점 3 : 시작 인덱스가 반드시 종료 인덱스보다 작을 필요는 없습니다.
다음 간단한 리스트 예시를 사용해서 슬라이싱에 대해 알아봅시다.
# 예시
a = [1, 2, 3, 4, 5, 6, 7, 8, 9]
- 기본 슬라이싱
# m번 index ~ n-1번 index에 해당하는 리스트 반환하기
# (시작 index) < (마지막 index) -> 원하는 부분에 대한 리스트 반환
# (시작 index) >= (마지막 index) -> 비어있는 리스트 반환
a[m:n]
a[1:5]
- 결과
다음 간단한 리스트 예시를 사용해서 슬라이싱에 대해 알아봅시다.
# 예시
a = [1, 2, 3, 4, 5, 6, 7, 8, 9]
- 기본 슬라이싱
# m번 index ~ n-1번 index에 해당하는 리스트 반환하기
# (시작 index) < (마지막 index) -> 원하는 부분에 대한 리스트 반환
# (시작 index) >= (마지막 index) -> 비어있는 리스트 반환
a[m:n]
a[1:5]
- 결과
- # 1번 index ~ 4번 index a[1:5] == [2, 3, 4, 5]
# 시작지점 혹은 종료지점만 명시하기
a[n:] # n번째 index부터 마지막까지
a[:n] # 처음부터 n-1번째 index까지
a[:4]
a[4:]
- 결과
- a[:4] == [1, 2, 3] a[4:] == [4, 5, 6, 7, 8, 9]
- 기본 슬라이싱 (음수 index 이용)
음수 인덱스도 똑같은 형태로 사용할 수 있습니다. 다만, 시작 인덱스가 마지막 인덱스보다 작게 지정해 줘야 원하는 부분을 추출할 수 있습니다.
# (시작 index) >= (마지막 index) -> 비어있는 리스트 반환
# (시작 index) < (마지막 index) -> 원하는 부분에 대한 리스트 반환
a[-5:-2]
a[-2:-5]
- 결과
- step 개수 임의로 정하기 (양수 인덱스)
a[2:5:2]
a[1::3]
a[::4]
- 결과부연 설명 : 2번 인덱스에서 4번 인덱스까지에 대한 리스트를 반환해야합니다. 지정한 인덱스 간격이 2이기 때문에 3, 5만 담긴 리스트가 반환됩니다.부연 설명 : 1번 인덱스에서 마지막(8번) 인덱스까지에 대한 리스트를 반환합니다. 이 때, 지정한 인덱스 간격이 3이기 때문에, 2, 5, 8이 담긴 리스트를 반환합니다.부연 설명 : 0번 인덱스에서 마지막(8번) 인덱스까지에 대한 리스트를 반환합니다. 이 때, 지정한 인덱스 간격이 4이기 때문에, 1, 5, 9가 담긴 리스트를 반환합니다.
- a[::4] == [1, 5, 9]
- a[1::3] == [2, 5, 8]
- a[2:5:2] == [3, 5]
- step 개수 임의로 정하기 (음수 인덱스)
음수 인덱스는 인덱스가 작아지는 방향으로 가도록 하기 때문에, 반대 순서로 된 리스트를 반환합니다. 따라서 시작 인덱스가 종료 인덱스보다 크도록 지정해 줘야 합니다.
a[3:7:-2]
a[7:3:-2]
- 결과부연 설명 : 종료 인덱스가 시작 인덱스보다 크지만, 인덱스간 간격이 -2로 주어졌기 때문에, 비어있는 리스트가 반환됩니다.부연 설명 : 7번째 인덱스에서 4번째 인덱스까지에 대한 리스트를 반환합니다. 인덱스간 간격이 -2로 주어졌으므로, 8, 5가 담긴 리스트가 반환됩니다.
- a[7:3:-2] == [8, 5]
- a[3:7:-2] == []
a[:4:-2]
a[4::-2]
- 결과
- 자주 사용하는 리스트 활용 구문 - 얕은 복사 (Shallow Copy)
아래의 예시를 보시면, 기본적으로 파이썬은 직접적인 변수 할당에 대해서 얕은 복사를 지원합니다. 다시 말해, b에서 내용을 변경하면, 변경 내용이 a 에도 영구적으로 반영됩니다. 따라서 기존 내용을 유지한 상태로, 복사해서 다른 처리를 하기 위해서는 깊은 복사를 해야 합니다.
a = [1, 2, 3, 4, 5, 6, 7, 8, 9]
# 얕은 복사 (Shallow Copy)
b = a
b[0] = 1000
# 결과 : a == b
a == [1000, 2, 3, 4, 5, 6, 7, 8, 9]
b == [1000, 2, 3, 4, 5, 6, 7, 8, 9]
a = [1, 2, 3, 4, 5, 6, 7, 8, 9]
# 깊은 복사 (Deep Copy)
b = a[:]
# a[:] == a.copy()
b[0] = 1000
# 결과 : a != b
a == [1, 2, 3, 4, 5, 6, 7, 8, 9]
b == [1000, 2, 3, 4, 5, 6, 7, 8, 9]
- 자주 사용하는 리스트 활용 구문 - 순서 바꾸기
코딩 테스트를 하다 보면, 주어진 리스트의 순서를 반대로 만들고 싶을 때가 많습니다. 파이썬의 리스트에서 제공하는 순서 바꾸는 여러 방식이 있는데, 슬라이싱을 활용한 방법을 알려드리겠습니다.
# reversed() 내장함수 활용하기
b = reversed(a)
# 결과
a == [1, 2, 3, 4, 5, 6, 7, 8, 9]
b == [9, 8, 7, 6, 5, 4, 3, 2, 1]
print(b)
# <reversed object at 0x1025a2da0>
# 슬라이싱 활용하기
b = a[::-1]
# 결과
a == [1, 2, 3, 4, 5, 6, 7, 8, 9]
b == [9, 8, 7, 6, 5, 4, 3, 2, 1]
print(b)
# [9, 8, 7, 6, 5, 4, 3, 2, 1]
위의 두 방식 모두 순서를 바꾸면서 기존 리스트의 형태를 유지합니다. 다만, 반환에 차이가 존재합니다.
reversed() : 주어진 리스트를 반대로 접근할 수 있도록 하는 iterator를 반환합니다. 따라서 추가적인 메모리 소모가 없지만, 순서가 바뀐 리스트를 바로 확인할 수 없습니다.
[::-1] : 반대 순서로 된 리스트를 반환하기 때문에 메모리 소모가 존재합니다. 대신 리스트기 때문에 인덱싱, 슬라이싱이 모두 가능합니다.
그렇기 때문에 $10^6$과 같이 엄청 많은 데이터를 담은 리스트를 다룰 때는 reversed()가 [::-1]보다 효율적입니다. 하지만 리스트의 특성을 추가로 활용해야 한다면 [::-1]을 사용해야 합니다.
Linked List
💡 Linked List Linked List는 노드(Node)끼리 연결되는 형식으로 데이터를 저장하는 자료구조입니다.
일단 노드는 데이터값(value)과 다음 주솟값(next)로 구성되어 있습니다.
Node의 구현
class Node :
def __init__(self, value = 0, next = None):
self.value = value
self.next = next
물리적 비연속적, 논리적 연속적
Linked List는 메모리상에서는 비연속적으로 저장이 되어 있지만, 각각의 노드가 다음 노드의 메모리 주솟값을 가리킴으로써 논리적으로 연속성을 갖게 됩니다.
배열의 경우 연속성을 유지하기 위해 메모리상에서 순차적으로 데이터를 저장하는 방식을 사용하였지만, Linked list에는 메모리 상에서 연속성을 유지하지 않아도 되기 때문에 메모리 사용이 좀 더 자유롭습니다.
Linked List구현
우리는 앞서서 linked list는 Node라는 구조체가 연결되는 형식으로 정의되는 자료구조라고 언급하였습니다. 그러면 이 노드들을 어떻게 연결할 수 있을까요?
우선 아래와 같이 Node class를 활용해 여러 개의 노드를 만들어보도록 합시다.
class Node :
def __init__(self, value):
self.value = value
self.next = None
first = Node(1)
second = Node(2)
third = Node(3)
fourth = Node(4)
현재 4개의 노드가 만들어진 상태입니다. 하지만 논리적 연결성은 아직 존재하지 않습니다.
논리적 연결성은 아주 쉽게 만들 수 있습니다.
first.next = second
second.next = third
third.next = fourth
이렇게 하여, 간단한 linked list가 완성 되었습니다. 위의 과정들을 LinkedList 라는 class를 만들고, append(), remove()를 정의하면, 더욱 더 쉽게 linked list를 만들 수 있습니다.
기본적인 LinkedList 의 클래스는 다음과 같습니다.
class LinkedList(object):
def __init__(self):
self.head = None
아주 간단하게 생겼습니다.
self.head 는 Linked list의 첫 번째 원소를 가리킵니다.
생성 초기에는 비어있으므로 None으로 설정해 줍니다.
이제 linked list에서 원소들을 추가하는 함수 append를 볼 것입니다. append 함수는 다음 2가지를 기억해야 합니다.
- 첫 번째 원소인 경우, head로 지정해 주어야 합니다.
- 노드를 추가할 때는 마지막 노드 다음에 추가해야 합니다.
class LinkedList(object):
def __init__(self):
self.head = None
def append(self, value):
new_node = Node(value)
if self.head is None:
self.head = new_node
else:
ptr = self.head
while(ptr.next):
ptr = ptr.next
ptr.next = self.current = new_node
저희가 앞서 만든 linked list를 위의 LinkedList를 통해 구현되는 과정을 보도록 합시다.
우선 linked list를 하나 만들어줘야 합니다.
linkedlist = LinkedList()
linkedlist.append(1)
first에 해당하는 new_node가 Node class에 의해서 만들어집니다.
현재 self.head가 None임으로, 새로운 노드를 head가 가리키도록 해야 합니다.
linkedlist.append(2)
second에 해당하는 new_node가 Node class에 의해서 만들어졌습니다.
현재 self.head가 None이 아님으로, else문으로 가야 합니다. 저희는 앞서 말했듯이 마지막 노드 다음에 new_node를 추가해줘야 합니다.
그런데 head인 first 노드는 이미 첫 번째 노드이자 마지막 노드입니다.
그렇기에 ptr.next는 None 입니다.
따라서 while 반복문을 돌지 않고 ptr의 다음을 new_node로 연결해주면 됩니다.
linkedlist.append(3)
third에 해당하는 new_node가 Node class에 의해서 만들어졌습니다.
현재 self.head가 None이 아니므로, else문으로 가야 합니다. 저희는 앞서 말했듯이 마지막 노드 다음에 new_node를 추가해 줘야 합니다.
그렇기에 head 부터 시작하는 ptr 노드를 마지막 노드가 될 때까지 업데이트해 줘야 합니다.
ptr이 마지막 노드가 되면, ptr의 다음을 new_node로 연결해 주면 됩니다.
linkedlist.append(4)
fourth에 해당하는 new_node가 Node class에 의해서 만들어졌습니다.
현재 self.head가 None이 아니므로, else문으로 가야 합니다. 저희는 앞서 말했듯이 마지막 노드 다음에 new_node를 추가해 줘야 합니다.
그렇기에 head 부터 시작하는 ptr 노드를 마지막 노드가 될 때까지 업데이트 해줘야 합니다.
ptr이 마지막 노드가 되면, ptr의 다음을 new_node로 연결해주면 됩니다.
이렇게 하여 저희는 목표한 linked list를 완성하였습니다. 그런데 한 가지 불편함이 있었습니다. ptr의 시작을 항상 처음 노드(head)에서 시작하여, 마지막 노드로 보내는 과정을 거쳐야 했습니다.
처음부터 마지막 노드를 알 수 있으면, 코드를 더욱 쉽게 구현할 수 있을 것 같습니다. 따라서 마지막 노드를 가리키는 tail변수를 추가해 보도록 합시다.
class LinkedList(object):
def __init__(self):
self.head = None
self.tail = None
그렇게 되면 append 함수도 약간의 수정이 필요합니다. 새로운 원소가 추가 될 때마다, 마지막 노드인 tail을 업데이트해 줘야 하기 때문입니다.
전체 linked list 코드는 다음과 같습니다.
class Node(object):
def __init__(self, value):
self.value = value
self.next = None
class LinkedList(object):
def __init__(self):
self.head = None
self.tail = None
def append(self, value):
new_node = Node(value)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
self.tail = new_node
Doubly linked list로의 확장
저희가 지금까진 배운 linked list는 한쪽으로만 갈 수 있기에 singly linked list라고 합니다. 이와 같은 linked list는 뒤로 갈 수 없기에 불편함을 가지고 있습니다. 어떻게 하면 뒤로 갈 수 있을까요?
class Node(object):
def __init__(self, value):
self.value = value
self.next = None
self.prev = None
append의 코드 또한 그렇게 많이 바뀌지 않습니다. 단순히 노드가 추가 될 때, tail의 노드를 가리키기만 하면 되는 것입니다.
class Node(object):
def __init__(self, value):
self.value = value
self.next = None
self.prev = None
class LinkedList(object):
def __init__(self):
self.head = None
self.tail = None
def append(self, value):
new_node = Node(value)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
Doubly-linked list의 확장 : Deque 사용법
파이썬에는 이런 doubly linked list의 이점을 활용한 자료형인 데크(deque)가 있습니다. 리스트는, 앞서 언급한 바와 같이, 동적배열(dynamic array)로 이루어져 있습니다. 그래서 가변형 자료형이지만, 빠른 고정 길이 연산에 최적화 되어있어 처음 또는 중간 위치의 요소에 대한 삽입, 제거는 $O(n)$ 의 시간복잡도를 가집니다. 파이썬의 deque에서는 popleft와 appendleft를 지원하기 때문에 큐를 사용하고자 할 때 사용하는 것이 좋습니다. 관련 사용법은 큐에 대한 설명이 나올 때 자세하게 다루는 것으로 하겠습니다.
- deque를 사용하기 위해서는 collections 패키지를 import해야 합니다.
from collections import deque
- deque 선언하기 - 반드시 인자로 iterable 객체(리스트, 문자열, …)를 넣어야 합니다.
# deque 선언하기 (a, b : 빈 deque / c : 1, 2, 3, 4 담은 deque)
a = deque()
b = deque([])
c = deque([1, 2, 3, 4])
시간복잡도
배열의 경우 중간에 데이터를 삽입/삭제하게 되면 해당 index의 뒤에 있는 모든 원소은 한 칸씩 shift를 해야만 하기 때문에 O(n)의 시간복잡도를 갖게 되었습니다. 하지만 Linked list를 물리적으로 옮길 필요 없이 next address가 가리키는 주솟값만 변경하면 되기 때문에 O(1)의 시간복잡도로 삽입/삭제가 가능합니다.
insert_back과 remove_back의 경우 doubly linked list로 구현되어 있으면 O(1)의 시간복잡도를 가집니다.
1. 파이썬의 array
Python에도 array 자료형이 있습니다. 결국 dynamic array 기반이지만, 담는 자료형을 결정해 줘야 합니다.
# int형을 담은 array
array('i', [1, 3, 5, 7, 5])
# float형을 담은 array
array('f', [1.0, 2.5, 4.1, 8.11, 9.0])
2. 리스트 선언하기 : list() vs []
list()와 [] 모두 리스트 선언이 가능합니다만, 권장되는 방식은 [] 입니다. 바로 속도 차이 때문입니다.
- list() : 함수 호출 방식이기 때문에 함수 호출에 의한 추가적인 자원 소모가 발생합니다. 그리고 [] 방식보다 추가적인 메모리 할당이 요구됩니다.
- [] : 단순하게 비어있는 리스트만을 위한 메모리 할당이 이루어집니다.
그렇기 때문에, 필요한 경우가 아니라면, [] 방식으로 리스트를 선언하는 것이 더욱 효율적인 방식입니다.
'코딩테스트 [킬링캠프]' 카테고리의 다른 글
| 2.3 해시테이블 (Hash Table) (1) | 2024.01.03 |
|---|---|
| 2.2 큐 & 스택 (Queue & Stack) (1) | 2024.01.03 |
| 1.5 동적 계획법 (Dynamic Programming) (1) | 2024.01.03 |
| 1.4 분할정복 (Divide and Conquer) (1) | 2024.01.03 |
| 1.3 탐욕법 (Greedy) (0) | 2024.01.03 |