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

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

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

a=list(combinations(a, m))

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

for i in a:
    print(*i)

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

문제

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

• N개의 자연수 중에서 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

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

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

출력

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

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

예제 입력과 출력

정답

from itertools import combinations

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

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

a.sort()

a=list(combinations(a, m))

for i in a:
    print(*i)

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

문제

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

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

출력

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

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

예제 입력과 출력

정답

from itertools import combinations

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

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

for i in a:
    print(*i)

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

순열(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)

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

예제 입력과 출력

알고리즘 분류

브루트 포스

정답

import itertools

n,s=map(int,input().split(' '))
a=list(map(int,input().split(' ')))
c=0

for i in range(1,n+1):
    d=list(itertools.combinations(a,i))
    
    for j in d:    
        if sum(j) == s:
            c=c+1

print(c)

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

문제

독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

예제 입력과 출력

알고리즘 분류

BFS

브루트 포스

DFS

백트래킹

입문용

정답

import itertools

while True:

    s=list(map(int,input().split(' ')))
    k=s.pop(0)
    
    if k == 0:
        break
    
    a=list(itertools.combinations(s,6))

    for i in a:
        for j in i:
            print(j,end=' ')
        print()

    print()

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