※포스트의 모든 내용은 박상길 저자의 "파이썬 알고리즘 인터뷰" 에서 참고한 내용이다.
• 리스트
리스트는 프로그래밍을 하면서 매우 자주 사용되는 자료형 중 하나이다. 그런 만큼 이를 잘 이해하고 활용할 수 있어야한다.
파이썬에서 리스트는 순서대로 데이터를 저장하는 시퀀스이며 변경이 가능한 목록이다. 파이썬에서 리스트는 동적 배열로 구현되어 있는데, C++에서는 std::vector, 자바에서는 ArrayList가 동적 배열로 구현된 자료형이다.
파이썬 리스트는 매우 많은 기능을 제공하여 다양하게 사용될 수 있다. 큐와 스택의 기능을 모두 갖추고 있어 고민하지 않아도 된다는 등의 다른 언어보다 이점을 가지고 있다. 이러한 리스트는 매우 좋은 알고리즘인 O(1)의 시간복잡도를 가진 기능들은 많이 제공한다. 먼저 파이썬 리스트가 제공하는 주요한 연산을 살펴보자.
• 주요 연산
•
l[idx]
시간복잡도: O(1)
인덱스 idx의 요소를 반환한다.•
l[idx1:idx2]
시간복잡도: O[k] (idx1부터idx2-1까지가 k개)
idx1부터idx2-1까지의 요소를 리스트로 만들어 반환한다.•
len(l)
시간복잡도: O(1)
l객체의 전체 요소의 갯수를 반환한다.•
elem in l
시간복잡도: O(n)
l객체 내에elem이라는 요소가 존재하는지 확인한다.•
l.count(elem)
시간복잡도: O(n)
l객체 내에elem이라는 요소의 갯수를 반환한다.•
l.index(elem)
시간복잡도: O(n)
l객체 내에elem이라는 요소의 인덱스를 반환한다.•
l.append(elem)
시간복잡도: O(n)
l객체 마지막에elem이라는 요소를 추가한다.•
l.pop(idx)
시간복잡도: O(n)
스택의 연산에 해당된다. 인덱스idx에 해당하는 요소를 추출한다. 만약 파리미터에 아무런 값도 넣지 않는다면(l.pop()) 가장 마지막의 요소를 추출하는데 시간복잡도는 O(1)이다.•
l.sort()
시간복잡도: O(n log n)
리스트를 정렬한다. 팀소트(Timsort)를 사용한다.•
l.reverse()
시간복잡도: O(n)
리스트를 거꾸로 뒤집는다. 입력 순서의 반대의 결과를 반환한다.•
del l[idx]
시간복잡도: O(n)
l객체 내에 인덱스idx에 해당하는 요소를 삭제한다.•
max[l], min[l]
시간복잡도: O(n)
각각 리스트 내에서 가장 큰 값과 작은 값은 반환한다.
• 활용
- 선언
먼저 리스트 선언은 다음과 같이 할 수 있다.
>>> l1 = list() # list()를 이용하여 생성
>>> l2 = [] # 대괄호를 이용하여 생성
>>> l3 = [1, 2, 3, 5, 7] # 리스트 생성과 동시에 초기화- 추가
또 append()와 insert()를 이용하여 요소를 추가할 수 있다. 파이썬에서 리스트는 하나의 리스트에 다른 자료형의 데이터를 삽입하고 관리할 수 있다.
>>> l = [1, 2, 3]
>>> l.append(7) # append()를 이용하여 리스트 마지막에 요소 추가
>>> l
[1, 2, 3, 7]
>>> l.insert(3, 5) # insert()를 이용하여 특정 인덱스에 요소 추가. 여기선 인덱스 3에 5 추가
>>> l
[1, 2, 3, 5, 7]
>>> l.append('apple')
>>> l.append(True)
>>> l
[1, 2, 3, 5, 7, 'apple', True]- 접근 및 조회
리스트 내의 값에 접근하고 추출할 때는 다음과 같이 할 수 있다.
>>> l[4]
7만약 존재하지 않는 인덱스에 접근할 시 IndexError 오류가 발생한다. 이에 대한 예외 처리를 하려면 다음과 같이 할 수 있다.
try:
print(l[11])
except IndexError:
print("The index does not exist.")- 슬라이싱
또 파이썬의 리스트에서 빈번하게 쓰이는 유용한 기능은 슬라이싱이라는 기능이다. 원래는 문자열에서 유용하게 활용되지만 리스트에서도 똑같이 사용할 수 있다. 슬라이싱을 이용하면 리스트 내에서의 특정 범위의 값을 같은 리스트의 형태로 다룰 수 있다. 활용 방법은 다음과 같다
>>> l = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> l[2:6] # 리스트 l의 인덱스 2부터 인덱스 6 전까지 슬라이싱
[2, 3, 4, 5]
>>> l[:5] # 시작 인덱스를 입력하지 않을 시 자동으로 0부터 슬라이싱
[0, 1, 2, 3, 4]
>>> l[7:] # 종료 인덱스를 입력하지 않을 시 자동으로 마지막 인덱스까지 슬라이싱
[7, 8, 9]
>>> l[2:8:2] # 세 번째 파라미터를 이용하면 얼마나 건너뛰면서 슬라이싱할 지 설정 가능
[2, 4, 6]- 삭제
파이썬의 리스트에서 요소를 삭제하는 방식은 두 가지다. 값으로 삭제하는 방식과 인덱스로 삭제하는 방식 두 가지인데, 다음과 같이 활용할 수 있다
>>> l = [1, 2, 3, 5, 7, 'apple', True]
>>> del l[3] # 인덱스 3에 해당하는 값인 5를 삭제
>>> l
[1, 2, 3, 7, 'apple', True]
>>> l.remove(2) # 값이 2인 요소 삭제
>>> l
[1, 3, 7, 'apple', True]
>>> a = l.pop() # 리스트에서 마지막 값 추출 및 삭제
>>> l
[1, 3, 7, 'apple']
>>> a
True
>>> b = l.pop(1) # 리스트에서 인덱스 1에 해당하는 값인 3을 추출 및 삭제
>>> l
[1, 7, 'apple']
>>> b
3• 특징
파이썬은 다른 원시 타입 자료형은 제공하지 않고 모든 자료형을 객체로 구현했기 때문에 어떠한 데이터가 필요하여 추출할 때, 그냥 그 메모리에 접근하여 데이터를 빼오는 것이 아니라 그에 해당하는 객체에 접근하여 타입코드를 찾는 등의 작업을 해야한다. 따라서 다른 원시 타입 자료형을 제공하는 C나 자바같은 언어보다는 매우 느린 동작 속도를 보이지만 장점이 있다. 이러한 특징 때문에 파이썬에서의 리스트는 내부적으로 객체를 가리키는 포인터의 나열로 구현되어 있다. 연속된 메모리 공간에 데이터 값이 직접 들어가 있는 것이 아니라, 포인터들이 나열되어 있고 각각의 포인터는 그에 해당하는 객체를 가리키고 그 객체가 해당 포인터의 인덱스의 값이 되는 것이다. 이러한 특징 때문에 파이썬 리스트는 단일 자료형만을 나열하는 게 아니라 다양한 자료형을 한 리스트에 나열할 수 있는 것이다. 다른 언어들은 각 자료형마다 크기가 다르기 때문에 동일한 크기를 가진 리스트 각각의 공간에 넣을 수 없지만 파이썬은 가능하게 된다. 이렇게 파이썬의 리스트는 엄청난 편의성이 있지만 앞서 말했 듯이 각 값에 직접 접근하기 위해서는 여러 부가적인 작업들이 필요하기 때문에 속도는 매우 느리다.
