[유형]백트래킹 [문제링크]https://www.acmicpc.net/problem/1182 [요약]N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. [문제풀이]백트래킹 문제로 ans를 출력하면 다음과 같다.import sysfrom itertools import permutationsdef input(): return sys.stdin.readline().rstrip()def dfs(start): global cnt if sum(ans) == s and len(ans) >0: cnt+=1 for i in range(start,n): ans.append..

[유형]완전 탐색 [문제링크]https://www.acmicpc.net/problem/10974 [요약]N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. [문제풀이]itertools의 permutations를 사용한다.import sysfrom itertools import permutationsdef input(): return sys.stdin.readline().rstrip()n = int(input())result = list(permutations([i for i in range(1,n+1)],n))for r in result: print(*r)

[유형]백트래킹 [문제링크]https://www.acmicpc.net/problem/15666 [요약]N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.N개의 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.고른 수열은 비내림차순이어야 한다.한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. [문제풀이]import sysdef input(): return sys.stdin.readline().rstrip()def dfs(start,lst): # 종료조건 if len(lst) == M: ans.add(tu..

[유형]백트래킹 [문제링크]https://www.acmicpc.net/problem/15665 [요약]N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.N개의 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. [문제풀이]import sysdef input(): return sys.stdin.readline().rstrip()def dfs(lst): # 종료조건 if len(lst) == M: ans.add(tuple(lst)) return ..

[유형]백트래킹 [문제링크]https://www.acmicpc.net/problem/15664 [요약]N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.N개의 자연수 중에서 M개를 고른 수열고른 수열은 비내림차순이어야 한다.길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. [문제풀이]import sysdef input(): return sys.stdin.readline().rstrip()def dfs(start,lst): # 종료조건 if len(lst) == M: ans.add(tuple(lst)) return for j in rang..

[유형]백트래킹 [문제링크]https://www.acmicpc.net/problem/15657 [요약]N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.N개의 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다. [문제풀이]import sysdef input(): return sys.stdin.readline().rstrip()def dfs(start,lst): # 종료조건 if len(lst) == M: ans.append(lst) return for j in range(start,N): dfs(j,lst+[num_list[j]])..