N과M(1)

15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹 문제다. 이 문제는 2가지 방식으로 풀 수 있다. # 15649번: N과 M(1) n, m = map(int, input().split()) result = [] visited = [False] * (n+1) def backTracking(num): if num == m: print(" ".join(map(str, result))) return for i in range(1, n+1): if not visited[i]: visited[i] = True ..

15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹 문제다. 파이썬 itertools모듈의 permutations 함수를 사용하면 쉽게 풀 수 있지만 문제의 출제의도와 벗어난다. 백트래킹 문제라고 해서 일단 백트래킹 개념을 공부했다. 백트래킹은 DFS의 향상된 버전이라고 한다. 기본적으로 DFS의 개념을 사용하는데 약간 변형한다. 시간 복잡도는 현재 중복이 불가능하므로 O(N!)이다. (N = 10까지 가능) 중복이 가능한 경우에는 O(N^N) (N = 8까지 가능) n, m = map(int, inpu..