[백준] 15650번 - N과 M(2) 풀이 시간: 10분 이내 1) 문제 해결 아이디어 1부터 N까지의 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구하는 문제로 전형적인 백트래킹 문제다. 아래의 조건 2개로부터 이 문제는 조합을 구하는 문제임을 알 수 있다. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 너무 기본 문제라 쉽게 풀 수 있었다. DFS를 이용하거나 combinations 라이브러리를 이용하는 방식 2가지가 있지만 이 문제는 조합을 구현하는 것이 키포인트이기 때문에 DFS를 이용한 풀이만 할 것이다. 조합을 구할 때는 이전에 선택한 값보다 큰 값을 골라서는 안되므로 dfs 인자로 깊이(depth)에 탐색시작값(idx)를 추가로 넘겨주어야 ..
[백준] 1759번 - 암호 만들기 C개의 알파벳 목록에서 길이 L인 암호(모음 최소 1개, 자음 최소 2개)를 모두 구하는 것으로 전형적인 완전탐색(백트래킹) 문제다. 풀이 방법은 DFS를 이용하거나 combinations 라이브러리를 이용하는 2가지 방식이 있다. combinations 풀이가 DFS보다 시간측면에서 효율적이기는 했지만 코딩테스트에서 combinations 라이브러리를 사용할 수 없는 경우도 있으므로 1번 풀이로도 풀 수 있어야 한다. (풀이1) DFS 이용 풀이 시간: 30분 이내 1) 문제 해결 아이디어 dfs 매개변수로 (현재 암호 길이, 탐색 시작 인덱스, 모음 개수, 자음 개수) 를 넘겨주게 했다. dfs를 호출할 때마다 모음, 자음 개수도 함께 변경하여 넘겨주기 때문에 암호..
[백준] 2309번 - 일곱 난쟁이 풀이 시간: 10~15분 이내 9난쟁이 중에 키의 합이 100이 되는 7난쟁이를 구하는 문제로 조건에 맞는 조합을 구하는 전형적인 완전탐색 문제다. 그냥 for문으로 풀거나 DFS를 이용하여 풀거나 combinations 라이브러리를 이용하여 풀 수 있다. for문으로 푸는 방식이 가장 간편한 방식인 것 같다. 정답은 오름차순으로 출력해야하므로 입력받은 값(arr)을 오름차순 정렬하고 시작하면 무조건 출력은 오름차순 형태가 된다. (풀이1) DFS 이용 1) 문제 해결 아이디어 1. 찾음 여부 확인 정답이 여러가지인 경우에는 아무거나 출력하라고 했으므로 정답을 찾으면 찾음 여부(find)를 True로 바꾼 후 해당 목록(temp)를 출력한다. 그리고 찾음 여부(find..
[백준] 2798번 - 블랙잭 풀이 시간: 15분 이내 아주 쉽게 풀 수 있었고 완전탐색으로 풀어야하는 문제다. (풀이1) combinations 이용 1) 문제 해결 아이디어 itertools 모듈의 combinations 라이브러리를 이용하여 풀 수 있다. 2) 소스코드 from itertools import combinations # n: 카드 개수,m: 기준 숫자 n, m = map(int, input().split()) card = list(map(int, input().split())) max_res = 0 # M에 최대한 가까운 카드 3장의 합 # n개에서 3장 뽑아 m에 가장 가까운 3장의 합 찾기 for c in list(combinations(card, 3)): res = sum(c) ..
