2022-07-06
🚩itertools 라이브러리에 대하여
사실 종종 파이썬으로 특히 완전탐색 문제 같은데서나 우리는 문제적으로 조합을 해야 하는 경우나 순열적으로 만들어야 하는 경우를 종종 발견할 수 있다.
과연 그럼 일일이 내가 그 때마다 몇 중 for문을 돌리면서 여러 경우의 수를 다 만든다??...흠 이건 사실 좀 귀찮고 나름 매번 복잡한 일이다
이럴 때 사용할 수 있는
itertools!!
itertool에서는 우리가 흔히 사용하는 순열,조합,중복순열,중복조합 이런 것들에 대해서 쉽게 구할 수 있도록 제공한다.
itertools에서 제공하는 것들은 클래스이기에 나중에 list()형 변환은 필요하다
🔑사용방법-순열
from itertools import permutations
tmp=[a,b,c]
p=list(permutations(리스트,자릿수))
#이렇게 하면 순열에 대한 경우의 수를 모두다 p에 담김🔑사용방법-중복순열
from itertools import product
tmp=[a,b,c]
p=list(product(리스트,repeat=자릿수))
#이렇게 하면 중복순열에 대한 경우의 수를 모두다 p에 담김🔑사용방법-조합
from itertools import combinations
tmp=[a,b,c]
p=list(combinations(리스트,자릿수))
#이렇게 하면 조합에 대한 경우의 수를 모두다 p에 담김🔑사용방법-중복조합
from itertools import combinations_with_replacement
tmp=[a,b,c]
p=list(combinations_with_replacement(data, repeat=2))
#이렇게 하면 중복조합에 대한 경우의 수를 모두다 p에 담김그럼 과연 언제 이런 거를 쓸 수있고 어떤 식으로 코드패턴이 나온지는 보면
대체로 예를 들어 사전에서 모음의 순서처럼 쭉 나열할 때 이런 경우처럼
A,E,I,O,U 사전식 배열 순서에서 몇번째가 무엇인지 궁금할때 처럼 이럴때 많이 사용함
대체적인 패턴-해당케이스(중복순열)
case=[]
for i in range(1,6):
for p in list(product(['A','E','I','O','U'],repeat=i)):
case.append("".join(p))
#이 때 중요한 건 join을 통해서 문자열을 함쳐준다 이 포인트
#join 앞에는 내가 원하는 구분자를 넣어줄 수 있다🚩에라토스테네스의 체 소수 알고리즘
사실 해당 알고리즘은 정말 전통적으로 옛날부터 널리 알려져있는 알고리즘으로서
가볍게 알아두기만 해도 적절히 상황별로 갔다 쓸 수 있을 것 같다.
약수나 소수를 구할 때 포인트는
해당 숫자의 제곱근까지만 구해라!!
n=8
for i in range(2,int(n**0.5)+1):
if n%i==0:
소수,약수
#포인트는 대칭이라는 것을 사용하여 굳이 다 구할필요 없다는 것
반만 구하기 에라토스테네스의 체(구간내에서 여러 소수구하기)
def prime_number_find(n):
tmp=[True]*n
#처음에는 모든 숫자가 소수라고 가정
for i in range(2,int(n**0.5)+1):
if tmp[i]==True:
for j in range(i+i,n,i):
tmp[j]=False
#즉 해당 소수의 배수들을 제거
return [i for i in range(2, n) if tmp[i] == True]이걸 외우지는 말고
배수를 지워나가는 원리를 기억해두자
🚩문제를 풀면서 느낀 점
1.어떤 문제에서 숫자를 문자열로 주어서 해당 숫자들을 나열한다고 가정할 때에
ex)"30", "3"를 정렬로 비교해보면 문자열로 보면 30이 먼저나올 것이다
근데 해당 부분만 그러는게 아니라 정수형 변환으로 한 후 정렬이 하기 어려울 것 같다면!!
한 번 문제의 최대 제한 범위를 봐보구 정렬 순서를 위해 조작을 해보자
최대범위가 1000자리면
해당 문자열*3을 해서 최대로 늘려 비교를 다시 해보는 아이디어
303030,333이렇게 되면 결론적으로 333이 먼저오기에 순서가 바뀐다
2.카펫문제처럼 너비가 주어졌을 때 가로,세로의 조합이 필요한 문제에서는 해당 너비의 약수를 구하는데 해당 약수를 구할때 모두다 순회하지말고 에라토스테네스의 체 알고리즘을 사용해서 제곱근까지 구해서 대칭으로 구해 순회하는 반복수를 줄이자!
3.사전식 배열문제를 할 때에 접근 생각은
1)어떻게 하면 중복순열의 경우의 수를 다 만들까?-product
2)중복순열을 만들고 정렬
3)타겟값의 index()를 찾기
🚩하지만 여기에서 만약 제한범위가 엄청컸다면 중복순열의 모든경우를 구하는게 불가능할수도있다 그럴땐 dp관점으로 풀어야한다
