IT-garden

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력과 출력

정답

from itertools import combinations_with_replacement

n,m=map(int,input().split())

a=list(map(int,input().split()))
a.sort()
a=list(combinations_with_replacement(a, m))

a=sorted(list(set(a)))

for i in a:
    print(*i)

백준 알고리즘 15666번 : www.acmicpc.net/problem/15666

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력과 출력

정답

from itertools import combinations_with_replacement

n,m=map(int,input().split())

a=list(map(int,input().split()))

a.sort()

a=list(combinations_with_replacement(a, m))

for i in a:
    print(*i)

백준 알고리즘 15657번 : www.acmicpc.net/problem/15657

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력과 출력

정답

from itertools import combinations_with_replacement 

n,m=map(int,input().split())

a=combinations_with_replacement(range(1,n+1),m)

for i in a:
    print(*i)

백준 알고리즘 15652번 : www.acmicpc.net/problem/15652

순열(permutation)은 순서를 고려해서 선택한 경우의 수를 의미합니다.

from itertools import permutations

permutations(인자(반복 가능한 것 ex. 리스트, 문자열),뽑을 개수)

순열의 기본 구조입니다.

순열의 개수는 n! / (n-r)! 입니다.

1, 2, 3 숫자 3개가 있다고 할 때 순서를 고려해서 2장을 뽑으면 다음과 같습니다.
개수 : 3! / (3-2)! = 6 / 1 = 6
(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)

순서를 고려한다는 것은 (1, 2)와 (2, 1)를 다른 것으로 생각한다는 의미입니다.

from itertools import permutations

p=list(permutations([1, 2, 3], 2))

# 출력>>[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
print(p)

a=[1,2,3]

for i in permutations(a):
    # 출력>>(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)
    print(i,end=' ')
    
for i in permutations(a,2):
    # 출력>>(1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2) 
    print(i,end=' ')

조합(combination)은 순서를 고려하지 않고 선택한 경우의 수를 의미합니다.

from itertools import combinations

combinations(인자(반복 가능한 것 ex. 리스트, 문자열),뽑을 개수)

조합의 기본 구조입니다.

조합의 개수는 n! / r! (n-r)! 입니다.

1, 2, 3 숫자 3개가 있다고 할 때 순서를 고려하지 않고 2장을 뽑으면 다음과 같습니다.
개수 : 3! / 2! (3-2)! = 6 * 2 = 3
(1, 2), (1, 3), (2, 3)

순서를 고려하지 않는다는 것은 (1, 2)와 (2, 1)를 같은 것으로 생각한다는 의미입니다.

from itertools import combinations

c=list(combinations([1, 2, 3], 2))

# 출력>>[(1, 2), (1, 3), (2, 3)]
print(c)

a=[1,2,3]
    
for i in combinations(a,2):
    # 출력>>(1, 2) (1, 3) (2, 3)  
    print(i,end=' ')

중복 가능한 순열은 product를 이용해 표현할 수 있습니다.

from itertools import product

product(인자(반복 가능한 것 ex. 리스트, 문자열), repeat)

중복 가능한 순열의 기본 구조입니다.

중복 가능한 순열의 개수는 n^r 입니다.

repeat라는 인자를 통해 앞의 인자를 반복해서 뽑는 기능입니다.

1,2,3 숫자 3개가 있다고 할 때 순서를 고려해서 2장을 뽑으면 다음과 같습니다.
개수 : 3^2 = 9
(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)

from itertools import product

a=list(product([1, 2, 3], repeat=2))

# 출력>>[(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]
print(a)

중복 가능한 순열은 combinations_with_replacement를 이용해 표현할 수 있습니다.

from itertools import combinations_with_replacement

combinations_with_replacement(인자(반복 가능한 것 ex. 리스트, 문자열),뽑을 개수)

중복 가능한 조합의 기본 구조입니다.

중복 가능한 조합의 개수는 (n+r-1)! / r! / (n-1)!  입니다.

1,2,3 숫자 3개가 있다고 할 때 순서를 고려해서 2장을 뽑으면 다음과 같습니다.

개수 : (3+2-1)! / 2! / (3-1)! = 24 / 2 / 2 = 6 
(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)

from itertools import combinations_with_replacement

a=list(combinations_with_replacement([1,2,3], 2))

# 출력>>[(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]
print(a)