데이터 구조 및 알고리즘을 위한 파이썬 기초 문법 - 리스트(list)

참고

http://www.yes24.com/Product/Goods/91433923

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24

 

목적

데이터 구조 및 알고리즘 공부 전 간단히 파이썬 문법을 살펴보는 의미에서 작성한다.

 

 

리스트(list)

리스트는 여러 개의 데이터를 연속적으로 담아 처리하기 위해 사용한다. 파이썬 리스트는 다른 언어의 배열(array)과 유사하다. 또한 내부적으로 Linked list를 채택하고 있다. 그래서 append(), remove() 함수를 지원한다. 

 

arrayList vs LinkedList

https://www.nextree.co.kr/p6506/

자료구조: Linked List 대 ArrayList

 

리스트는 대괄호[] 안에 원소를 하나 이상 넣어 초기화한다. 또한 쉼표로 원소를 구분한다. 리스트의 원소를 접근할 때 인덱스(index)를 괄호 안에 넣는다. 이때 인덱스는 0부터 시작한다. 그리고 비어 있는 리스트를 선언하고자 할 때 list() 혹은 대괄호[]를 이용할 수 있다.

 

a = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(a)

# 인덱스 4, 즉 다섯 번째 원소에 접근 
print(a[4]) # 5가 출력됨

# 빈 리스트 선언 방법 
a = list() # 또는 a = []도 가능
print(a)

 

인덱스 값을 입력하여 리스트의 특정한 원소에 접근하는 것을 인덱싱(Indexing) 이라고 한다. 파이썬 인덱스 값은 양의 정수와 음의 정수 모두 사용할 수 있다. 예를 들어 [2]나 [-1] 이런식으로 말이다. 양의 정수를 넣으면 처음부터 순차적으로 탐색하며, 음의 정수를 넣으면 거꾸로 오른쪽으로 순차적으로 탐색한다. 

 

a = [1, 2, 3, 4, 5, 6, 7, 8, 9]

# 뒤에서 첫 번째 원소 출력 
print(a[-1])

# 뒤에서 세 번째 원소 출력 
print(a[-3])

# 앞에서 네 번째 원소 값 변경 
a[3] = 7
print(a)


# 9 
# 7 
# [1, 2, 3, 7, 5, 6, 7, 8, 9]

또한 리스트에서 연속적인 위치를 갖는 원소들을 가져와야 할 때 슬라이싱을 적는다. 대괄호 안에 [가져올 첫 원소 인덱스 (생략 가능): 가져올 마지막 인덱스 -1 (생략 가능)] 콜론을 이용하여 설정할 수 있다. 

 

a = [1, 2, 3, 4, 5, 6, 7, 8, 9]

# 두 번째 원소부터 네 번째 원소까지 
print(a[1 : 4])

 

리스트 컴프리헨션(list comprehension)은 리스트를 초기화하는 방법 중 하나이다. 리스트 컴프리헨션을 이용한다면 리스트 대괄호 안에 조건문과 반복문을 넣는 방식으로 리스트를 초기화할 수 있다. 

 

# 0부터 19까지의 수 중 홀수만 포함하는 리스트 
array = [i for i in range(20) if i % 2 == 1]

print(array)

# 위의 리스트 컴프리헨션을 다른 방식으로 나타낸다면 다음과 같음 
array = [] 
for i in range(20) : 
	if i % 2 == 1: 
    	array.append(i)
        
print(array)

 

# 1부터 9까지 수의 제곱 값을 포함하는 리스트 
array = [i * i for i in range(1, 10)]

print(array)

/* 
 array = list()
 for i in range(1, 10) : 
 	array.append(i*i)
    
print(array)
*/

 

리스트 컴프리헨션은 2차원 리스트를 만들 때 효과적이다. 

 

# N * M 크기의 2차원 리스트를 초기화한다. 
n = 3 
m = 4 

array = [[0] * m for _ in range(n)]
print(array)

'''
n = 3 
m = 4 

array = []
for _ in range(n) : # 반복문과 _를 사용하고 range(n)을 사용하여 범위를 지정
    array.append([[0] * m]) # 가장 중요한 문법. 해당 문법을 사용하면 2차원 배열 형태로 놓이게 된다.

print(array)

'''

# [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] 출력

 

참고로 언더바(_) 역할은 파이썬 자료구조/ 알고리즘에서 반복을 수행하되 반복을 위한 변수의 값을 무시하고자 할 때 언더바(_)를 자주 사용함.

즉, for i in range(20) 에서 반복문에 대한 실행문에 반복문 인자 i 를 쓸 필요 없을 때 언더바(_)를 사용한다. 

 

 

리스트 관련 메소드 정리

 

메서드명	사용법	설명	시간 복잡도
append()	변수명.append()	리스트에 원소를 하나 삽입할 때 사용한다.	O(1)
sort()	변수명.sort() 변수명.sort(reverse = True)	기본 정렬 기능으로 오름차순으로 정렬한다. 내림차순으로 정렬한다.	O(NlogN)
reverse()	변수명.reverse()	리스트의 원소의 순서를 모두 뒤집어 놓는다.	O(N)
insert()	변수명.insert(삽입할 위치 인덱스, 삽입할 값)	특정한 인덱스 위치에 원소를 삽입할 때 사용한다.	O(N)
count()	변수명.count(특정 값)	리스트에서 특정한 값을 가지는 데이터의 개수를 셀 때 사용한다.	O(N)
remove()	변수명.remove(특정 값)	특정한 값을 갖는 원소를 제거하는데, 값을 가진 원소가 여러 개면 하나만 제거한다.	O(N)

 

a = [1, 4, 3]
print("기본 리스트 : ", a)

a.append(2)
print("삽입 : ", a)

a.sort()
print("오름차순 정렬 : ", a)

a.sort(reverse = True)
print("내림차순 정렬 : ", a)

a.reverse()
print("원소 뒤집기 : ", a)

a.insert(2, 3)
print("인덱스 2가 3 추가됨 : ", a)

print("리스트 내 3의 갯수 세기 : ", a.count(3))

a.remove(1)
print("값이 1인 데이터를 삭제한다 : ", a)

 

가장 중요한 부분인데, insert() 함수는 시간 복잡도가 O(N) 이다. 리스트의 원소가  총 N개 일 때 시간 복잡도가 O(N)이라는 뜻이다. 파이썬 리스트 자료형의 append() 함수는 O(1)에 수행되는 것에 반하여 insert() 함수는 동작이 상대적으로 느리다. 왜냐하면 중간에 원소를 삽입하고 리스트의 원소들을 재조정하기 때문이다. 따라서 insert() 함수를 남발하면 코드 실행 과정에서 시간 초과가 날 수 있다. (매우 비효율 적임)

 

remove() 함수도 insert() 함수와 마찬가지로 O(N) 이다. 이 역시 리스트에 중간에 있는 원소를 삭제하고 리스트 원소를 재조정 하기 때문이다. 

 

그러면 어떻게 하면 시간 복잡도를 해결할 수 있는가? list comprehension 구문을 사용하여 해결할 수 있다. 

 

a_list = [1, 2, 3, 4, 5, 6, 7, 7, 7, 9]
remove_set = {3, 5}

''' remove_set에 포함되지 않은 값만 저장한다.
 a_list의 원소 하나가 remove_set 세트 원소들 중 포함하지 않는다면 i 인자에 넣고 append(i) 시켜라
'''
result = [i for i in a_list if i not in remove_set]

print(result)


''' 
다르게 나타내면 이렇게도 나타낼 수 있다. 
a_list = [1, 2, 3, 4, 5, 6, 7, 7, 7, 9]
remove_set = {3, 5}

result = list()

# remove_set에만 포함되지 않은 값만을 저장한다. 
for i in a_list : 
    if i not in remove_set :
        result.append(i)
        
print(result)
'''