코딩테스트에서 라이브러리를 의존하면 안돼! 시험볼 때 사용 못하게 할 수도 있어
- 그냥 라이브러리를 사용할 수도 있다~ 정도로 이해하자.
import itertools as it
- 이 라이브러리를 통해 순열과 조합을 자동으로 구할 수 있어
수열 추측하기
가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다.
N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오. 단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다.
▣ 입력설명
첫째 줄에 두개의 정수 N(1≤N≤10)과 F가 주어진다. N은 가장 윗줄에 있는 숫자의 개수를 의미하며 F는 가장 밑에 줄에 있는 수로 1,000,000 이하이다.
▣ 출력설명
첫째 줄에 삼각형에서 가장 위에 들어갈 N개의 숫자를 빈 칸을 사이에 두고 출력한다. 답이 존재하지 않는 경우는 입력으로 주어지지 않는다.
▣ 입력예제 1
4 16
▣ 출력예제 1
3 1 2 4
import sys
# sys.stdin = open("inAA.pyput.text", "rt")
import itertools as it
n,f = map(int, input().split())
b = [1] * n
for i in range(1,n):
A = b[i-1] * (n-i) #이항계수 분자
B = i #이항계수 분모
b[i] = A//B
data = list(range(1,n+1))
for tmp in it.permutations(data):
sum = 0
for L, x in enumerate(tmp):
sum += (x*b[L])
if sum == f:
for x in tmp:
print(x, end = " ")
break
위 문제에 대해서 라이브러리를 이용하여 풀어볼 것이다.
for tmp in it.permutation(data):
print(tmp)위 코드는 data라는 리스트를 가지고 모든 경우의 순열을 구해준다.
즉 n이 4일 때 4!에 해당하는 모든 경우를 출력해줘 ! (오름차순)
DFS가 아닌 라이브러리 활용하여 순열 구현
3개를 뽑아야 한다면
for tmp in it.permutation(data, 3):
print(tmp)위 코드는 data라는 리스트에서 3개만 뽑아서 순열을 만들고 모든 경우를 출력해준다 !
⚽ 라이브러리 itertools를 이용하여 순열 조합을 구할 수 있다는 것을 인지하고는 있자 !!
가장 중요한 것은 라이브러리로 순열 조합을 구하려고 해서는 안된다.
코테를 볼 때 라이브러리를 사용하지 못하게 하는 경우도 있으니까, 구현에 있어서는 완벽하게 이해하고 있어야만 한다.
그리고 복잡한 문제들, 무조건 순열을 만드는 것이 아닌 조건을 제시해서 어떤 조건을 만족하는 원소만 뽑아서 순열, 조합을 만드는 경우에는 사용도 못해 !
⚽ 기본은 재귀함수(DFS)를 이용해서 내가 순열과 조합을 만들어내는 방법. 이것이 기본이다.
수들의 조합
N개의 정수가 주어지면 그 숫자들 중 K개를 뽑는 조합의 합이 임의의 정수 M의 배수인 개수는 몇 개가 있는지 출력하는 프로그램을 작성하세요.
예를 들면 5개의 숫자 2 4 5 8 12가 주어지고, 3개를 뽑은 조합의 합이 6의 배수인 조합을 찾으면 4+8+12 2+4+12로 2가지가 있습니다.
▣ 입력설명
첫줄에 정수의 개수 N(3<=N<=20)과 임의의 정수 K(2<=K<=N)가 주어지고,
두 번째 줄에는 N개의 정수가 주어진다.
세 번째 줄에 M이 주어집니다.
▣ 출력설명
총 가지수를 출력합니다.
▣ 입력예제 1
5 3
2 4 5 8 12
6
▣ 출력예제 1
2
import sys
# sys.stdin = open("inAA.pyput.text", "rt")
import itertools as it
n,k = map(int, input().split())
data = list(map(int, input().split()))
m = int(input())
cnt = 0
for x in it.combinations(data, k):
if sum(x) % m == 0:
cnt += 1
print(cnt)
DFS가 아닌 라이브러리 활용하여 조합 구현
for x in it.combinations(data, k):
print(x)위 코드는 data 리스트에서 k개만큼을 뽑는 것을 말한다. (그걸 전부 출력해줌)
