순열과 조합 정복하기! 백준 15649~15666번

• www.acmicpc.net/workbook/view/2052

문제집: N과 M (시리즈)

• itertools 사용

1) 순열

from itertools import permutations as p

n,m=map(int,input().split())
for i in p(range(1,n+1),m):
    print(*i)

2) 조합

from itertools import combinations as p
n,m=map(int,input().split())
for i in p(range(1,n+1),m):
    print(*i)

3) 중복 순열

from itertools import product as p
n,m=map(int,input().split())
for i in p(range(1,n+1),repeat=m):
    print(*i)

4) 중복 조합

from itertools import combinations_with_replacement as p
n,m=map(int,input().split())
for i in p(range(1,n+1),m):
    print(*i)

 

• itertools 사용 X

# 조합
def combinations(arr,r):
    for i in range(len(arr)):
        if r == 1:
            yield [arr[i]]
        else:
            for next in combinations(arr[i+1:],r-1):
                yield [arr[i]] + next

# 중복 조합
def combinations_with_replacement(arr,r):
    for i in range(len(arr)):
        if r == 1:
            yield [arr[i]]
        else:
            for next in combinations_with_replacement(arr[i:],r-1):
                yield [arr[i]] + next

# 순열
def permutations(arr,r):
    for i in range(len(arr)):
        if r == 1:
            yield [arr[i]]
        else:
            for next in permutations(arr[:i]+arr[i+1:],r-1):
                yield [arr[i]] + next

# 중복 순열
def product(arr,r):
    for i in range(len(arr)):
        if r == 1:
            yield [arr[i]]
        else:
            for next in product(arr,r-1):
                yield [arr[i]] + next

for combi in permutations([1,2,3],2):
    print(combi)

• 위 수식을 통해서 다 풀었다.
• return과 yield의 차이점에 대해서 알게 되었고 순열, 조합, 중복 순열, 중복 조합, 동일 한 숫자 포함될 때 순열, 조합 까지 총 12문제에 대해 알아보았다.
• 아직 정확히 네 종류 순열, 조합이 머리 속에 정리가 잘 안 된다. 응용 문제 여럿 풀어봐야지

 

조합, 순열 구현 출처:

juhee-maeng.tistory.com/91