크래프톤 정글에 와서 파이썬이란 언어와 상당히 친해졌다.
이전에는 진짜 안다고 할 수도 없는 수준이었는데... 알고리즘 문제를 하나씩 깨면서 파이썬의 수많은 메소드, 문법들에 조금은 익숙해진 것 같다.
알고리즘 문제를 풀면서 새로 알게 된 문법들, 표현 방식들, 기타 알고리즘 문제 풀이 팁들을 공유한다.
python3 vs pypy3
pypy3 : 실행 시 자주 쓰이는 코드를 캐싱
간단한 코드상에서는 Python3가 메모리, 속도 측에서 우세
복잡한 코드(반복)을 사용하는 경우에서는 PyPy3가 우세
재귀, 큐 쓸 때는 python3가 좋음
최적화
input
input 대신에 sys.stdin.readline()을 쓰는 게 더 빠름
ex)
import sys
input() 대신에 sys.stdin.readline() 쓰기
print 대신에 sys.stdout.write() 쓰는 게 더 빠른듯
ex)
from sys import stdin, stdout
stdout.write(’dd’)
list
list를 쓰는데 메모리 초과가 날 경우,
for문 안에서 append를 사용하면 메모리 재할당이 이루어져서 효율적으로 사용할 수 없다.
입력값이 많이 주어질 때에는 메모리를 좀 더 효율적으로 관리하기 위해, 최대 입력값만큼의 list를 만들어 두고, append를 하지 않고 index로 찾아가서 값을 추가하는 식으로 구현한다.
ex) 백준 10989
최대 재귀 깊이 늘리기
소스코드 가장 윗 부분에 다음 코드 추가
import sys
sys.setrecursionlimit(10**7)sys.stdin - 여러줄 입력 받을 때
nums = []
for line in sys.stdin:
nums.append(line)
print(nums)
"""
1
2
3
4
5
^Z
['1\n', '2\n', '3\n', '4\n', '5\n']
"""^Z를 입력받으면 종료되며, 개행문자까지 입력되므로 strip()이나 rstrip()으로 제거해 주어야 함
pypy3 메모리 초과 날 때
재귀 허용 깊이를 낮춰주면 되는 경우가 있다
기타 참고자료
파이썬 자료구조, 시간복잡도
스택
기본 리스트로 구현
append()로 push
pop()로 pop
시간복잡도 : 각 행위에 O(1)
큐
collections에서 deque 모듈을 임포트해서 구현
from collections import deque
q = deque()
q.append(1)
print(q)
q.append(2)
print(q)
q.popleft()
print(q)
q.popleft()
print(q)
.............출력 결과
deque([1])
deque([1, 2])
deque([2])
deque([])append()로 뒤에 push
popleft()로 앞 값 제거
시간복잡도 : 각 행위에 O(1)
리스트를 queue로 만들기
deque(list)
힙
파이썬의 heapq 모듈로 힙 자료구조 사용하기
heapq 라이브러리를 임포트해서 사용
(추가, 제거 시간복잡도 O(logN))
import heapq
h=[]
# 힙에 원소 삽입
heapq.heappush(h, value)
# 힙에 삽입된 원소를 꺼내기
result = heapq.heappop(h)heapq모듈은 파이썬의 보통 리스트를 힙처럼 다룰 수 있도록 도와줌
→ 그냥 빈 리스트를 생성한 다음, heapq 모듈의 함수를 호출할 때마다 이 리스트를 인자로 넘겨야 함.
즉, heapq 모듈을 통해서 원소를 추가하거나 삭제한 리스트가 최소 힙임
heappush(list, val)
list에 val을 추가
heappop(list)
리스트에서 가장 작은 원소를 삭제 후 그 값을 리턴
최소값 삭제하지 않고 얻기
리스트에 접근하듯이 인덱스로 접근(list[0])
기존 리스트를 힙으로 변환
heapify() 사용
from heapq import heapify
heap = [4, 1, 7, 3, 8, 5]
heapify(heap)
print(heap)파이썬의 경우, heapq 라이브러리는 min-heap 형태로 동작함(루트 노드가 최소값. 오름차순 정렬)
만약 max-heap 형태로 만들고 싶다면, 원소를 삽입하고 꺼낼 때 -를 붙이면 max-heap 형태로 구현 가능
트리
dictionary를 사용해서 구현한다.
root를 key로, left/right 자식들을 value로 할당
tree = {}
tree["A"] = "B", "C"
>>> {"A" : ("B","C")}자식에 인덱싱할 때는 tree[’부모노드’][인덱스]로 접근한다.
ex) B에 접근할 때 ⇒ tree[”A”][0]
파이썬 내장 함수
map
리스트의 요소를 지정된 함수로 처리해주는 함수(새 리스트를 생성)
# 사용방식
map(함수, iterable한 데이터)
# ex:
list(map(함수, 리스트))
tuple(map(함수, 튜플))ex) 실수가 저장된 리스트가 있는데 이 리스트의 모든 요소를 정수로 변환하고자 할 때,
a = [1.2, 2.5, 3.7, 4.6]
a = list(map(int, a))map은 기본적으로 map class 객체를 반환한다.
따라서 인덱스로 접근하는 등 리스트로서의 처리를 하려면, list같은 자료형으로 형변환을 해줘야 한다.
join
파이썬에서는 string 내장 함수임
문법 : “seperate할 문자”.join(리스트)
⇒ 리스트를 해당 문자로 seperate한 문자열로 변환
이때 해당 리스트에는 string만 있어야 하는 듯?
index
list 내장 프로퍼티
js의 indexOf와 같은듯
ex : list.index(2) ⇒ list 안에서 2의 index를 찾아 줌
zip()
여러 개의 순회 가능한 객체를 인자로 받고, 각 객체가 담고 있는 원소를 터플의 형태로 차례로 접근할 수 있는 반복자(iterator)를 반환
>>> numbers = [1, 2, 3]
>>> letters = ["A", "B", "C"]
>>> for pair in zip(numbers, letters):
... print(pair)
...
(1, 'A')
(2, 'B')
(3, 'C')unzip도 가능하고…
병렬반복처리도 가능하고…
두 개의 리스트나 튜플에서 쉽게 딕셔너리 데이터를 만들 수도 있음…
람다 함수
이름 없는 함수를 표현할 때 사용하는 형식
문법)
lambda 매개변수 : 표현식예시)
>>> (lambda x,y: x + y)(10, 20)
30리스트 슬라이싱
11. 파이썬 리스트 슬라이싱 활용하기 - Codetorial
format
수를 지정한 형식으로 반올림해서 출력하는 함수
- Number format()
문법 : format(수, ‘%형식을 지정하는 string’)
format(수, “.nf”)
⇒ 수를 소수점 이하 n자리까지의 정확도로 반올림
(즉, 소수점 이하 n자리만 나오도록 반올림)
ex) format(3.141592, ‘.2f’) ⇒ 3.14
- String format()
string 내에 있는 number 변수를 지정한 format에 맞게 출력할 수 있는 함수
strip()
문자열의 양 끝에서 인자로 전달된 문자를 제거하는 메소드
Python - String strip(), rstrip(), lstrip() 사용 방법 및 예제
인자를 전달하지 않으면 string 양 끝에서 공백을 제거함(js trim()같은거일듯)
인자로 문자 1개를 전달하면 그 문자와 동일한 것을 모두 제거함(동일하지 않은 문자가 나올 때까지)
ex: ‘00000water dffe 000’.strip()
→ water dffe
인자로 여러 문자를 전달하면 그 문자들과 동일한 것들을 모두 제거. 동일하지 않은 문자가 나올 때까지 제거함
ex: “,,,,,123…..water…..pp”.strip(’,123.p’)
⇒ water
비슷한 것으로 lstrip(), rstrip()이 있음
lstrip() : 문자열의 왼쪽에서 제거
rstrip() : 문자열의 오른쪽에서 제거
reverse()
리스트 순서 반대로 뒤집음
주의 : 아무것도 리턴 안함. 그냥 reverse 붙인 list를 반대로 뒤집어 주는 기능적인 역할인듯
리스트 메소드
count()
리스트에서 파라미터 value의 개수를 반환
insert(idx, value)
리스트의 idx번지에 value 삽입
insert(0, ‘ddd’)처럼 쓰면 js의 unshift 기능 가능
sort()
정렬. 기본값은 오름차순 정렬
시간복잡도 : 평균적으로 nlogn
옵션 :
- reverse : True/False. True시 내림차순 정렬
ex)
a.sort(reverse=True)- key : 함수. 해당 옵션에 지정된 함수의 결과에 따라 정렬
ex) 원소의 길이로 정렬하고 싶을 경우,
m.sort(key=len)다중 조건으로 key를 설정하고 싶을 경우
words.sort(key=lambda x:(len(x),x))
# => x의 길이를 우선 조건으로 정렬하고, 길이가 같을 경우 x 자체 값으로 정렬한다.sort() vs sorted()
sort : 리스트에만 적용. 리턴으로 None 반환(원본 데이터가 정렬됨)
sorted : iterable 데이터에 전부 적용되는듯. 리턴으로 sort 적용된 값 반환(원본 데이터는 정렬되지 않음)
쓰는 방식
sort : list.sort()
sorted : sorted(list)
두 리스트 합치기
더하기 연산자로 간단하게 두 리스트에서 원소를 뽑아서 합친 리스트를 생성할 수 있다.
ex)
arr = [0] + list(map(int, input().split()))
print(arr)
>>> 4 5 6 7
=>[0, 4, 5, 6, 7]파이썬 데이터 타입
set
중복값이 없는 집합
값 1개 추가 : add
값 여러 개 추가 : update
특정 값 제거 : remove
ex)
s1 = set([1,2,3])
s1.add(4)
>>>[1,2,3,4]
s1.update([5,6])
>>>[1,2,3,4,5,6]
s1.remove(2)
>>>[1,3,4,5,6]파이썬 기타 방법론
string을 리스트로 분해해서 담는 법
우선 string 자체가 iterable하다. 굳이 형변환 하지 않아도, string에서도 리스트 슬라이싱이나 for문 등을 사용할 수가 있음
분해해서 list로 만들고 싶으면, 그냥 list()로 형변환하면 분해해서 담김
ex : list(str)
f string
js의 ${} 그거
형식 : f’string{변수}’
:을 붙여서 숫자에 추가적인 formatting을 해줄 수 있음
ex : f’{above:.3f}’⇒ above변수의 수를 소숫점 3자리까지 출력
print("문자열", 옵션이름=”옵션값”)
end 옵션 : 마지막 문자열을 출력하고 그 다음에 출력할 문자.
sep 옵션 : 출력할 때 출력 값들 사이에 넣어줄 구분자.
end 옵션의 기본값은 개행(줄바꿈) 이고, sep 옵션의 기본값은 공백(띄어쓰기)
형변환
파이썬 정수 변환 - int()
파이썬 실수 변환 - float()
파이썬 문자열 변환 - str()
파이썬 문자 변환 - chr()
파이썬 불리언 변환 - bool()
array filter
list comprehension을 이용해서 js의 array.filter()함수와 똑같은 기능을 할 수 있다
파이썬에도 filter 함수가 있긴 함
ex)
isStartWithF 함수의 조건을 통과하는 값들로 필터링을 하고 싶을 때,
results = [x for x in animals if isStartWithF(x)] # <== list comprehension 방법
print(results)
함수 안 써도 가능
ex)
[x for x in arr if x!=''] ⇒ x가 빈값이 아닌 애들로 arr을 필터링해줌
삼항연산자
제공하는 연산자는 없지만, if else elif를 한 줄로 써서 삼항연산자처럼 표현 가능
문법 : A if 조건 else B
ret = dog if animal is dog else cat
=> animal이 dog이면 dog이고, 아니면 cat혹은 and or 써서 삼항연산자로 표현 가능
animal = 'dog'
ret = animal == 'dog' and 'dog' or 'cat'
print(ret)
>>> dogstring 순서 뒤집기
리스트 슬라이싱으로 간단하게 구현가능
ex:
a = '734'
a = a[::-1]
>>>'437'array.fill()
js에서 array에 기본값을 할당하기 위해 fill()을 이용했던 거
파이썬에서는 그냥 곱셈형식으로 표현가능
ex) sieve = [True] * 3
[True, True, True]
제곱근 구하기
- 기본 연산자로 구하기
- 수**0.5
- Math 라이브러리 사용 가능
import math
# Math 라이브러리를 이용한 루트 계산
print("2의 루트 : ", math.sqrt(2))
2의 루트 : 1.4142135623730951enumerate
리스트의 엘리먼트를 추출할 때(list comprehension 같은거 할 때) 인덱스를 붙여서 추출하는 방법
enumerate()는 index와 element로 이루어진 tuple을 돌려주며, 각각 다른 변수에 할당하고 싶으면 unpacking을 해야 한다.
ex)
>>> list_a = ['first', 'second', 'third']
>>> for i, e in enumerate(list_a):
print(i, e)
0 first
1 second
2 thirdarray에 특정 원소가 있는지(includes)
if myitem in list: 이런 형식으로 사용함
없을 경우를 원하면 → 조건 앞에 not 붙임
ex: if not (1 in group):
중복값 제거하기
list를 set으로 만들고 다시 list로 만들기
ex) list(set(arr))
array의 값 모든 조합 구하기
라이브러리 이용
itertools - Functions creating iterators for efficient looping - Python 3.11.0 documentation
itertools의 permutations 임포트, 이용
이용방식 : list(permutations(array, 개수))
리턴 : 해당 array의 원소들의 모든 순서의 경우의 수를 조합한 튜플
Array.every / array.some
파이썬에서는 all과 any 있음
ex)
>>> items = [[1, 2, 0], [1, 2, 0], [1, 2, 0]]
>>> all(flag == 0 for (_, _, flag) in items)
True
>>> items = [[1, 2, 0], [1, 2, 1], [1, 2, 0]]
>>> all(flag == 0 for (_, _, flag) in items)
False
>>> any(flag == 0 for (_, _, flag) in items)
True초기화된 리스트 구하기
리스트 길이를 지정하고 특정 값(예 : 0)으로 초기화하고 싶을 경우,
list = [0 for i in range(n)]2차원 배열을 만들고 싶을 경우,
[[0 for col in range(n)] for row in range(n)]구조분해
파이썬에서는 언팩이라고 함
x = [1,2,3]
a,b,c = x
a,b,c
>>> 1,2,3여러 변수에 한꺼번에 값 대입
a,b,c = 1,2,3
>>>a=1,b=2,c=3
x=6
y=2
x,y = y+2, x+3
>>> x=4, y=9함수 어노테이션
함수의 매개변수 자료형에 대한 주석
def max_of(a: Sequence) -> Any:
# 함수로직
# 건네받는 매개변수 a의 자료형은 Sequence
# Sequence : 시퀀스형. 리스트, 바이트 배열, 문자열, 튜플, 바이트 열 형이 있음
# 반환하는 것은 임의의 자료형인 Any어노테이션은 주석 달기일 뿐이며 코드 자체에는 어떠한 영향도 미치지 않음
리스트 얕은 복사, 깊은 복사
얕은 복사 : list.copy()
ex) y = x.copy()깊은 복사 : copy 모듈을 임포트하고 copy.deepcopy(list) 사용
ex)
import copy
y = copy.deepcopy(x)
pow(num1, num2, num3)
num3 생략 시 → num1의 num2승 반환
num3 있을 시 → num1의 num2승을 num3으로 나눈 나머지 반환
spread operator in python
*이 unpacking을 위한 연산자
Multiple assignment and tuple unpacking improve Python code readability
ex)
>>> numbers = [1, 2, 3, 4, 5, 6]
>>> first, *rest = numbers
>>> rest
[2, 3, 4, 5, 6]
>>> first
1다음 두 줄은 같은 기능을 한다.
>>> beginning, last = numbers[:-1], numbers[-1]
>>> *beginning, last = numbersbool(참과 거짓) 기준
문자열, 리스트, 튜플, 딕셔너리 등의 값이 비어 있으면(" ", [ ], ( ), { }) 거짓이 됨
숫자에서는 그 값이 0일 때 거짓이 됨
None도 거짓
int타입의 무한 값(매우 큰 값) 넣기
int(1e9)를 넣어서 10억으로 설정 가능
ex) inf = int(1e9)
혹은 sys 라이브러리를 통해 설정가능
import sys
max_int = sys.maxsize
min_int = -(sys.maxsize + 1)범위를 정확하게 할 필요가 없다면 음의 무한대에 1을 추가할 필요가 없음
정규 표현식
기본 라이브러리인 re 모듈 사용
패턴을 컴파일하여 패턴 객체로 만들고, 해당 객체의 메서드를 통해 검색을 수행한다.
수행 결과는 match 객체로 리턴된다.
import re
p = re.compile('ab*') #'ab*' 패턴을 컴파일
m = p.match('python')
print(m)
>>>None컴파일된 패턴 객체의 메소드
| Method | 목적 |
|---|---|
| match() | 문자열의 처음부터 정규식과 매치되는지 조사한다. |
| search() | 문자열 전체를 검색하여 정규식과 매치되는지 조사한다. |
| findall() | 정규식과 매치되는 모든 문자열(substring)을 리스트로 돌려준다. |
| finditer() | 정규식과 매치되는 모든 문자열(substring)을 반복 가능한 객체로 돌려준다. |
match 객체의 메소드
| method | 목적 |
|---|---|
| group() | 매치된 문자열을 돌려준다. |
| start() | 매치된 문자열의 시작 위치를 돌려준다. |
| end() | 매치된 문자열의 끝 위치를 돌려준다. |
| span() | 매치된 문자열의 (시작, 끝)에 해당하는 튜플을 돌려준다. |
정규표현식으로 split 하기
re 안에 split 메소드 제공
re.split(패턴 string, 분리할 target string) 형식으로 쓴다
참고자료
[Python 변수] mutable과 immutable의 차이
[Python] 'NoneType' object is not iterable
기타 글 내의 링크들