본문 바로가기

백 트래킹24

[백준] 10974번: 모든 순열 (python) 10974번: 모든 순열 문제 ) N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. 입력 : 첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다. 출력 : 첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다. 풀이) 중복을 허용하지 않은 n자리 수를 만드는 문제였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 # 중복허용 x n = int(input()) # 정답을 담을 리스트 arr = [0] * n # 방문 유무를 담을 리스트 visited = [0] * (n + 1) def recur(cur): # 재귀가 n번째까지 진입 했을때, # n자리 리스트가 만.. 2022. 3. 8.
[백준] 15654번: N과 M (5) (python) 15654번: N과 M (5) 문제 ) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 입력 : 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다. 출력 : 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 풀이) 오랜만에 시작한 백트래킹 문제이다. 길이가 m인 수열을 모두 구하는데, n개의 자연수는 모두 다른.. 2022. 3. 8.
[백준] 14888번: 연산자 끼워넣기 (python) 14888번: 연산자 끼워넣기 문제 ) N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. 예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다. 1+2+3-4×5÷6 1÷2+3+4-5×6 1+2÷3×4-5+6 1÷2×3-.. 2022. 2. 26.
[백준] 15652번: N과 M (4) (python) 15652번: N과 M (4) 문제 ) 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 입력 : 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 : 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 풀이) 1 2 3 4 5 6 7 8 9 10 11 12 13.. 2022. 2. 26.

티스토리툴바