1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 이 문제는 이전에 itertools 라이브러리의 combination함수를 사용해서 풀었던 문제다. 근데 백트래킹으로도 풀 수 있다고 해서 백트래킹으로 다시 풀어봤다. # 1759번: 암호 만들기 l, c = map(int, input().split()) arr = sorted(list(input().split())) vowels = ['a', 'e', 'i', 'o', 'u'] # 모음 result = [] visited = [False] * c def is_pos..
알고리즘/백준
6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 백트래킹 문제다. 1~45까지의 숫자 중 6보다 큰 N개의 숫자를 고른다. 고른 N개의 숫자 중 6개를 고르는 경우의 수를 모두 출력하면 되는 문제. N과M 문제중, 중복되지 않고, 오름차순으로 숫자를 출력하는 경우와 동일한 문제라고 생각했다. # 6603번: 로또 import sys input = sys.stdin.readline def backTracking(num): if len(result) == 6: print(*result) return f..
1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net N개의 정수가 주어질 때, 크기가 양수인 부분수열 중 해당 부분수열의 합이 S가 되는 경우의 수를 구하는 문제. 문제의 설명이 약간 부족한 면이 있는 것 같다. 만약 N개의 정수 중 같은 숫자가 주어질 경우에는 어떻게 해야 하는지 명확하게 나와있지 않다. 일단 같은 숫자도 부분 수열에 포함될 수 있다고 생각하고 문제를 풀었다. # 1182번: 부분수열의 합 n, s = map(int, input().split()) arr = ..
15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹 문제다. 이번 조건은 같은 수를 여러번 골라도 되고, 비내림차순 수열이어야 한다는 것이다. 여기서 같은 수라는 것은 같은 인덱스에 있는 수를 의미한다. 그러므로 visited 리스트를 사용할 필요가 없다. 그리고 backTracking함수의 인자로 현재 탐색한 인덱스를 넘겨줘서 다음 backTracking시 for문의 시작값으로 넣어줘서 비내림차순으로 만들어준다. # 15666번: N과 M (12) n, m = map(int, input().split..
15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이전 문제에서 다른 점은 중복이 허용된다는 점이다. 여기서의 중복은 수열의 중복이 아니라, 같은 인덱스의 수가 들어갈 수 있다는 것이다. # 15665번: N과 M (11) n, m = map(int, input().split()) arr = sorted(list(map(int, input().split()))) result = [] def backTracking(depth): if depth == m: print(*result) return remember ..
15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N과M 10번째 문제다. 이전에 풀었던 문제와 거의 비슷하다. # 15664번: N과 M (10) n, m = map(int, input().split()) arr = sorted(list(map(int, input().split()))) visited = [False] * n result = [] def backTracking(num): if len(result) == m: print(*result) return remember = 0 for i in ran..
15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N과M 문제중에 제일 까다로운 문제가 아닐까 싶다. 기존 N과 M문제에다가 중복되는 수열을 제외해야하는건데 조건이 까다롭다. # 15663번: N과 M(9) n, m = map(int, input().split()) arr = sorted(list(map(int, input().split()))) result = [] visited = [False] * n def backTracking(): if len(result) == m: print(*result) ret..
15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 백트래킹 이번에는 고른 수열이 비내림차순이어야 한다. # 15657번: N과 M(8) n, m = map(int, input().split()) arr = list(map(int, input().split())) result = [] arr.sort() def backTracking(num): if len(result) == m: print(*result) return for i in range(num, n): result.append(arr[i]) ba..
15656번: N과 M (7) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 백트래킹 문제 같은 수를 골라도 된다는 점에서 제일 쉬운 백트래킹 문제다. # 15656번: N과 M(7) n, m = map(int, input().split()) arr = list(map(int, input().split())) arr.sort() result = [] def backTracking(num): if num == m: print(*result) return for i in range(n): result.append(arr[i]) bac..
15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 백트래킹 문제를 또 풀어보자 이번에도 수열이 주어진다. 이전 문제에서 추가된 조건은 고른 수열은 오름차순이어야 한다는 점이다. # 15655번: N과 M(6) n, m = map(int, input().split()) arr = list(map(int, input().split())) arr.sort() result = [] def backTracking(num): if len(result) == m: print(*result) return for i i..
