조합

[python] 조합을 DFS로 구하기

항상 combinations로만 조합을 구했는데 이제는 한번 정리를 해야할것 같아서 오랜만에 글을 쓴다. 이문제는 백준 15650번으로 조합을 구하면 되는 문제이다. 사실 라이브러리를 사용한다면 상당히 쉬운 문제이다. from itertools import combinations N, M = map(int, input().split()) for com in list(combinations([i for i in range(1, N+1)], M)): print(" ".join(map(str, com))) 그러나 이렇게 푸는게 습관이 되어 나중에 백트래킹 문제가 어렵게 느껴졌고 기초적인 문제를 코테에서 틀리는 상황이 발생했다. 따라서 이걸 DFS로 풀어보자. 4에서 3개를 뽑는 경우는 [1,2,3],[1,2,..

[python] 코테 대비 알고리즘 모듈 정리

정렬 arr = [(1,2),(2,3), (1,1)] arr.sort() # 일반적으로 처음인자부터 차례로 정렬 nlogn arr.sort(key=lambda x:x[1],x[0]) # 두번째 인자 우선순위로 정렬 arr.sort(key=lambda x:x[0], reverse=True) # 첫번째 인자 기준으로 반대로 정렬 곱집합, 조합, 순열 from itertools import product product([1,2,3],['a','b','c','d']) # 하나씩 선택하는 모든 케이스(곱집합)가 만들어진다. from itertools import combinations combinations(iterable, r=None) # 조합 구하기 from itertools import permutatio..