조합
[Python]알고리즘/백준
[DFS/BFS/완전탐색] 15650번 - N과 M(2)(DFS, 백트래킹)
[백준] 15650번 - N과 M(2) 풀이 시간: 10분 이내 1) 문제 해결 아이디어 1부터 N까지의 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구하는 문제로 전형적인 백트래킹 문제다. 아래의 조건 2개로부터 이 문제는 조합을 구하는 문제임을 알 수 있다. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 너무 기본 문제라 쉽게 풀 수 있었다. DFS를 이용하거나 combinations 라이브러리를 이용하는 방식 2가지가 있지만 이 문제는 조합을 구현하는 것이 키포인트이기 때문에 DFS를 이용한 풀이만 할 것이다. 조합을 구할 때는 이전에 선택한 값보다 큰 값을 골라서는 안되므로 dfs 인자로 깊이(depth)에 탐색시작값(idx)를 추가로 넘겨주어야 ..
[Python]알고리즘/백준
[DFS/BFS/완전탐색] 2798번 - 블랙잭(완전탐색)
[백준] 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) ..
