전공 영상처리 과목에서 numpy로 파이썬을 처음 접하였기 때문에, 차마 몰랐던 개념이나 라이브러리 함수들이 보였습니다.
따라서 이 책을 학습하기 전 코딩테스트를 위해 필요한 파이썬 기본 라이브러리나 문법을 한 번 훑으려 합니다.
0. 학습계획
알고리즘 공부에 사용할 교재는 이것이 코딩 테스트다 (나동빈 저)입니다. 줄여서 이코테라고 부르고, 코딩테스트에 입문하는 데에 바이블 격으로 정평이 나있는 책입니다. 금학기 내로 책을 다 뗄 계획에 있으며, 약 4달이 되는 기간 중 6주는 이론과 실전 문제를, 나머지 10주는 유형별 기출문제를 풀어보며 블로그와 깃허브에 아카이빙하려 합니다.
1. 리스트 컴프리헨션
리스트를 초기화하는 방법 중 하나로, 대괄호 안에 조건문과 반복문을 넣는 방식으로 사용한다. 특히 코딩 테스트에서 2차원 리스트를 초기화할 때 매우 효과적이다.
# 0~20 중 홀수만 포함하는 리스트 생성
array1 = [i for i in range(20) if i%2==1]
>>array1
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
# 2차원 리스트 초기화
n=3
m=4
array2 = [[0] * m for _ in range(n)]
>>array2
[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
2. 튜플 자료형
리스트와 비슷한 형태를 하고 있지만, 한 번 선언된 값을 변경할 수 없다는 특징이 있으며 소괄호를 이용한다.
튜플 자료형은 그래프 알고리즘을 구현할 때 자주 사용된다고 한다. 아직 관련 개념을 배우지 않아 자세히는 모르지만, 우선 순위 큐에 들어간 데이터는 변경되는 일이 없어 튜플 자료형으로 사용된다고 한다.
튜플은 리스트에 비해 공간 효율적이고, 사전 데이터의 키-값 쌍 처럼 서로 다른 성질의 데이터를 (A,B) 형태로 함께 튜플로 묶어 관리한다고 한다.
3. 사전 자료형
키-값 쌍으로 구성된 자료형으로, 쌍으로 구성된 데이터를 처리함에 있어 리스트보다 훨씬 빠르게 동작한다.
dict()로 초기화하며, ['key']='value' 형태로 데이터를 삽입할 수 있다.
keys() 함수를 통해 키 데이터만 추출, values() 함수를 이용해 값 데이터만 추출할 수 있다.
4. 집합 자료형
리스트, 튜플과 달리 순서가 존재하지 않아 인덱싱이 불가능하다. 값 데이터만을 담고 있다.
set() 혹은 중괄호 ( {} ) 로 초기화한다.
add() 함수를 통해 데이터를 추가, update() 함수를 통해 여러 개의 데이터를 한 번에 추가, remove() 함수를 통해 인자와 일치하는 값을 제거할 수 있다.
5. 입출력
입력 기본적으로 입력을 받기 위해서 input()을 이용한다. 또한 코딩 테스트에서는 여러 개의 데이터를 입력받을 때 공백으로 데이터를 구분하는데, 이 때는 list(map(int, input().split()))을 사용한다. 사용 빈도가 굉장히 높기 때문에 필수적으로 알고 있어야 하는 코드이다.
해당 코드의 동작 과정을 분석해 보자면, input으로 입력받은 문자열을 split으로 공백을 기준으로 데이터를 구분한 후에, 정수 자료형으로 mapping 시킨다. 이를 마지막으로 list화 시켜 주면 입력받은 정수를 공백으로 구분하여 저장할 수 있다. 데이터 수가 많지 않다면 list를 사용하지 않고 a,b,c = 등으로 변수에 저장해 줄 수도 있다.
주의할 점이 있다면, 문제 처리 시간이 굉장히 중요한 코딩테스트에서 input()함수를 그대로 사용하지는 않는다. 이 경우 sys 라이브러리 내의 sys.stdin.readline() 함수를 이용한다고 한다.
import sys
sys.stdin.readline().rstrip()
Hello World
>>'Hello World'
b = sys.stdin.readline().rstrip()
Hee
>>b
'Hee'
c = sys.stdin.readline().rstrip()
43 25 3
>>c
'43 25 3'뒤에 rstrip() 함수를 호출해 주어야 하는데, 이를 호출하지 않으면 엔터 키가 입력에 포함되어 출력된다. 이를 방지 하기 위함.
데이터를 구분하지 않고 한 줄씩 입력 받는 것을 확인할 수 있다.
6. 주요 라이브러리
* 이코테에서 모든 라이브러리를 다루지는 않으므로, 필요한 라이브러리 함수가 있다면 이곳을 통해 공부하면 될 듯 하다.
기본 내장 함수
별도의 import 없이 바로 사용할 수 있는 함수들이다. 대표적으로 입출력 함수가 여기 포함된다.
이 외에도 sum(), min(), max(), sorted() 등이 있다.
eval() : 문자열 형식으로 들어오는 수식을 계산해 결과를 반환
itertools
반복되는 데이터를 처리하기 위한 라이브러리이다. 가장 유용하게 사용하는 permutations와 combinations 함수가 있다.
permutations 함수는 r개의 데이터를 추출해 일렬로 나열하는 모든 경우의 수 (순열)를 계산해 준다.
combinations 함수를 순서를 고려하지 않고 나열하는 모든 경우 (조합)를 계산한다.
from itertools import permutations
data = ['A','B','C']
result = list(permutations(data,3))
>>result
[('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A', 'C'),
('B', 'C', 'A'), ('C', 'A', 'B'), ('C', 'B', 'A')]from itertools import combinations
data = ['A','B','C']
result = list(combinations(data,3))
>>result
[('A', 'B', 'C')]
result = list(combinations(data,2))
>>result
[('A', 'B'), ('A', 'C'), ('B', 'C')]이 외에도 중복순열을 계산해 주는 product() 와 중복조합을 계산해 주는 combinations_with_replacement가 종종 사용된다고 한다.
heapq
다양한 우선순위 큐 기능을 구현하고자 할 때 사용된다. heapq.heappush() 를 통해 데이터를 삽입하고, heapq.heappop()을 통해 데이터를 꺼낸다.
bisect
이진 탐색 알고리즘을 구현 할 수 있도록 제공되는 라이브러리이다. 정렬된 배열에서 특정한 원소를 가장 왼쪽에서부터 찾는 bisect_left(a,x)와, 가장 오른쪽에서부터 찾는 bisect_right(a,x)가 효과적으로 사용된다. 이 두 함수는 시간 복잡도 O(logN)에 동작하는데, 시간 복잡도에 대한 정리는 빠른 시일 내에 자세히 정리할 예정이다.
collections
파이썬에서 큐를 규현하기 위해 사용하는 deque가 포함되어 있다. 리스트는 append()와 pop() 메서드로 데이터를 제어할 때 가장 뒤쪽 원소를 기준으로 작업을 수행하기 때문에 많은 시간이 소요될 수 있는데 이를 해결할 때 deque 함수를 사용한다.
deque는 첫 번째 원소를 제거할 때 popleft(), 마지막 원소를 제거할 때 pop()을 사용한다.
첫 번째 원소 위치에 데이터를 삽입할 때엔 appendleft(x)를, 마지막 위치에서는 append(x)를 통해 데이터를 삽입한다.
from collections import deque
data = deque([2,3,4])
data.pop()
4
>>data
deque([2, 3])
data.append(3)
>>data
deque([2, 3, 3])
deque 외에도 등장 횟수를 세는 Counter 함수를 제공하는데, 해당 객체 내부의 원소가 몇 번씩 등장했는지를 반환한다. (사전 자료형으로도 반환이 가능하다.)
from collections import Counter
counter = Counter(['red','blue','red','red','green'])
print(counter['red'])
>>3
print(dict(counter))
>>{'red': 3, 'blue': 1, 'green': 1}
이 정도로 정리해 볼 수 있겠네요. 내일부터는 본격적인 알고리즘 공부가 시작됩니다.....커밍 쑨...
참고
이것이 코딩테스트다 with Python (나동빈 저)
