15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹 문제 아이디어 어차피 같은 숫자를 반복해서 사용해도 되므로, 문제에서 제공한 N개의 수에서 중복을 제거해 준다. 백트래킹을 활용해 문제를 해결하면 된다. 전체 코드 N, M = map(int, input().split()) numList = [int(x) for x in input().split()] numList = sorted(list(set(numList))) # 중복 제거후 정렬 n = len(numList) answer = list() seq..
https://www.acmicpc.net/problem/28286 28286번: 재채점을 기다리는 중 UCPC고등학교에 다니는 민규는 최근에 기말고사를 치게 되었다. 기말고사는 $N$문제로 이루어져 있고, 각 문제는 보기가 1 이상 5 이하의 정수로 이루어진 객관식 문제이다. 시간이 지나 학교에서 www.acmicpc.net 처음 문제를 읽었을 때는 시간을 어떻게 줄일까 고민했는데, 입력값이 매우 작다.(max(N) = 20, max(K) = 3) 무난한 문제. 백트래킹을 사용해서 최대 개수를 찾아준다. 아이디어 1. pull: 번호들을 왼쪽으로 당기는 기능. rotate를 써서 구현했다. for문으로 구현해도 된다. 2. push: 번호를 오른쪽으로 미는 기능. pull과 마찬가지로 rotate를 써..
https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 처음에는 itertools 라이브러리를 사용하여 순열을 구하고, 각 순열마다 검사하는 방법으로 했는데 시간초과 되었다. 생각해 보면 최대 경우가 15P15까지 나오므로 이 방법은 당연히 아니었다. 암호를 판별하는 방식이 아닌 처음부터 암호를 조건에 맞게 만드는 방법으로 문제를 풀어 해결하였다. 아이디어 1. 암호 조건 암호에 있는 알파벳을 증가하는 순서(aescend)로 배열되었다. 암호에는 모음 1개..
https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 아이디어 1. 구현이 먼저 문제를 보고 N최대가 20이고 이동도 5번 하므로 문제가 말한 그대로 구현하면 되겠다고 생각. 상, 하, 좌, 우 이동 중에 '좌'로 이동하는 것부터 구현하면 나머지도 쉽게 만들 수 있다. 만들수록 변수나 if문이 많아져 다시 밀고 처음부터 작성했다. 너무 많은 변수는 필요 없다. 이건 다른 구현 문제도 마찬가지라고 생각. '이동시킬 블록'과..
https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 아이디어 1. 백트래킹 이미 N과 M 문제를 풀어봐서 바로 떠올랐다. 깊이가 M이 될 때마다 주어진 숫자들을 탐색하면 된다. 이 문제에서는 순열, 중복되지 않은 숫자들을 나열해야 하므로 이미 추가된 숫자가 있으면 continue로 넘겨준다. 전체 코드 N, M = map(int, input().split()) numbers = [int(x) for x in input().split()] ..
