백준-백트래킹

백트래킹 알고리즘이란?

• 해를 찾아가는 도중, 지금의 경로가 정답(해)이 될거 같지 않으면 그 경로를 더이상 가지 않고 되돌아가서 다시 해를 찾는 기법!
• 최적화 문제와 결정 문제를 해결할 수 있다.

15649번 문제

문제

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

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

출력

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

풀이

언어 : python 이용

Itertools

• Itertools란 파이썬에서 제공하는 자신만의 반복자를 생성해주는 함수로 특정 배열이나, 순열에 대한 조합을 만들어 이를 이용한느 알고리즘 문제를 풀때 유용하게 사용.
• 무한 , 조합형, 종료 이터레이터가 있다.

조합형 이터레이터 중 permutations()를 사용하여 문제를 풀었다.

이터레이터	인자	결과
product()	p,q,... [repeat=1]	데카르트 곱(cartesian product), 중첩된 for 루프와 동등
permutations()	p[, r]	r-길이 튜플들, 모든 가능한 순서, 반복되는 요소 없음
combinations()	p, r	r-길이 튜플들, 정렬된 순서, 반복되는 요소 없음
combinations_with_replacement()	p, r	r-길이 튜플들, 정렬된 순서, 반복되는 요소 있음

💡 좀 더 자세히 알아보기

permutations

>>> from itertools import permutations
>>> arr = [1,2,3]
>>> list(permutations(arr,2))
[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

: 순열 구하기
: (1,2)와 (2,1) 둘다 존재.

combinations - 반복되는 요소 x

>>> from itertools import combinations
>>> arr = [1,2,3]
>>> list(combinations(arr,2))
[(1, 2), (1, 3), (2, 3)]

: 조합 구하기
: (1,2)와 (2,1)은 같은 경우로 뽑아 둘 중 한 경우만 있음.

product

>>> from itertools import product
>>> arr = [1,2,3]
>>> arr2 = ['a','b','c']
>>> list(product(arr,arr2))
[(1, 'a'), (1, 'b'), (1, 'c'), (2, 'a'), (2, 'b'), (2, 'c'), (3, 'a'), (3, 'b'), (3, 'c')]

: 여러 요소 값 조합

>>> from itertools import product
>>> arr = [1,2,3]
>>> list(product(arr,repeat=2))
[(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]

: 한 요소에서 repeat 사용하여 값 조합
: 앞에서 나오지 않던 (1,1)이 나옴

참고 문서

---

🔎 정답 코드

import sys
from itertools import permutations
n,m = sys.stdin.readline().split()

arr = []

for i in range(int(n)):
    arr.append(i+1)

for a in permutations(arr,int(m)):
    for b in range(len(a)):
        print(a[b], end = " ")
    print("")

😂 코드 간결하게 하는 것 연습하기