[파이썬] 단계별 문제 풀기 - 15650번 백트래킹 (N과 M 2)
문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
- 고른 수열은 오름차순이어야 한다.
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
<<소스코드>>
#순열을 구하는 combinations 조합 모듈을 이용하여 문제 해결
import sys
from itertools import combinations
#input값 자연수 n까지, 중복없이 m개를 고르는 수열
n,m = map(int,sys.stdin.readline().split())
#combinations(리스트,골라서 나열할 원소의 갯수)
c = combinations(range(1,n+1),m) #[(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]
#튜플형태의 요소를 전부(map) 문자열로(str)바꿔서 ' '공백으로 구분한 뒤 반환
for i in c:
print(' '.join(map(str, i)))<<결과값>>
4 2
1 2
1 3
1 4
2 3
2 4
3 4DFS로 문제를 풀고 싶었다.. 어렵다...
아니 왜 쉬운 combinations 모듈을 있는데 재귀를 써서... 재귀를... 재귀를 (๑ •̀ω•́)۶
그래도 백트래킹의 개념은 짚고 넘어가야겠다아
순열과 조합
import itertools순열=Permutation
몇개를 골라 순서를 고려해 나열한 경우의 수 . 서로 다른 n개중 r개를 골라 순서를 정해 나열하는 가짓수
nPr 이며, 중복값이 존재
(A,B) != (B,A) -> 두개는 다른 것임
조합=Combinations
서로 다른 n개 중에서 r개를 취하여 조를 만들때, 이 하나하나의 조를 n개중에서 r개 취한 조합
조합은 중복값이 없다.
(A,B) = (B,A) -> 두개는 같은 것임
combinations(range(1,n+1),m)
#combinations(반복가능한 객체, 뽑으려는 갯수)
# n이 4이고, m이 2일 경우
#[(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]
백트래킹
해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법
최적화 문제와 결정 문제를 푸는 방법이다.
DFS는 가능한 모든 경로를 탐색하기때문에 불필요한 경로까지 탐색하여 경우의 수를 줄이지 못한다.
백트래킹은 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아간다. 반복문의 횟수를 줄일 수 있으므로 효율적인 방식이다. "가지치기"라고 하는데 불필요한 부분을 쳐내고 최대한 올바른쪽으로 간다는 의미이다. 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정된다.
백트래킹은 모든 가능한 경우의 수 중에서 특정 조건을 만족하는 경우만 살펴본다. 답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하지 않고 가지치기한다.
DFS로 모든 경우의 수를 탐색하는 과정에서 조건문을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현한다.