Posts

백준 15650번 문제 바로가기 combinations을 이용한 풀이 솔직히 이 문제의 가장 쉬운 방법은 itertools에서 combinations을 불러와서 사용하는게 아닐까? 일단 정답 처리는 되었는데 백트래킹을 이용해서 다시 풀어보려고 한다. 백준 15649 - N과 M (1)과 같은 맥락 # 입력 import sys from itertools import combinations n,m = map(int, sys.stdin.readline().split()) arr = [i+1 for i in range(n)] # 처리 for ans in combinations(arr, m): print(*list(ans)) backtracking을 이용한 풀이 백준 15649 - N과 M (1)와 비슷하면서도 중복을 허용하지 않기 때문에 가지치기에 고려할게 늘었다. backtrack() 재귀 함수에서 매개변수로 start 숫자를 전달해주면 오름차순으로 쉽게 해결할 수 있다. ...

백준 15650번 문제 바로가기 combinations을 이용한 풀이 솔직히 이 문제의 가장 쉬운 방법은 itertools에서 combinations을 불러와서 사용하는게 아닐까? 일단 정답 처리는 되었는데 백트래킹을 이용해서 다시 풀어보려고 한다. 백준 15649 - N과 M (1)과 같은 맥락 # 입력 import sys from itertools import combinations n,m = map(int, sys.stdin.readline().split()) arr = [i+1 for i in range(n)] # 처리 for ans in combinations(arr, m): print(*list(ans)) backtracking을 이용한 풀이 백준 15649 - N과 M (1)와 비슷하면서도 중복을 허용하지 않기 때문에 가지치기에 고려할게 늘었다. backtrack() 재귀 함수에서 매개변수로 start 숫자를 전달해주면 오름차순으로 쉽게 해결할 수 있다. ...

백준 15655번 문제 바로가기 combinations을 이용한 풀이 N과 M (2)에서 주어진 숫자를 가지고 한다는 점만 다른 사실상 동일한 문제. # 입력 import sys from itertools import combinations n,m = map(int, sys.stdin.readline().split()) arr = sorted(list(map(int, sys.stdin.readline().split()))) # 처리 for ans in combinations(arr, m): print(*list(ans)) backtracking을 이용한 풀이 백준 15649 - N과 M (1)와 비슷하면서도 중복을 허용하지 않기 때문에 가지치기에 고려할게 늘었다. backtrack() 재귀 함수에서 매개변수로 (현재숫자의 index) + 1을 전달해주면 오름차순으로 쉽게 해결할 수 있다. # 입력 import sys n,m = map(int, sys.stdin.readline().split()) arr = sorted(list(map(int, sys.stdin.readline().split()))) ans = [] # 처리 def backtrack(start=0): if len(ans) == m: print(*list(map(str, ans))) return for i in arr[start:]: if i not in ans: ans.append(i) backtrack(arr.index(i)+1) ans.pop() # return이 실행되면 여기로 돌아옴. (전 단계로 돌아감 = backtrack) backtrack()

백준 15651번 문제 바로가기 product을 이용한 풀이 N과 M (1)은 순열(permutation), N과 M(2)이 조합(combination)이었다면, 이번 문제 **N과 M (3)**은 중복순열(permutation with repetition)문제이다. 아마 4탄은 중복조합이 아닐까 추측해본다. 갓python은 중복조합과 중복순열에 대한 라이브러리도 가지고 있었으니… 바로 product이다. # 입력 import sys from itertools import product n,m = map(int, sys.stdin.readline().split()) arr = [i+1 for i in range(n)] # 처리 for ans in product(arr, repeat=m): print(*list(ans)) backtracking을 이용한 풀이 중복순열도 backtracking을 이용해서 풀어보자! 간단하게 순열 풀이에서 for문만 지우면 된다ㅎㅎ # 입력 import sys n,m = map(int, sys.stdin.readline().split()) ans = [] # 처리 def backtrack(): if len(ans) == m: print(*list(map(str, ans))) return for i in range(1, n+1): ans.append(i) backtrack() ans.pop() # return이 실행되면 여기로 돌아옴. (전 단계로 돌아감 = backtrack) backtrack()

백준 15654번 문제 바로가기 permutations을 이용한 풀이 ‘1부터 n까지의 숫자’ 대신에 ’n개의 숫자’가 주어진다는 점을 제외하면 N과 M (1)과 다를게 없다. ㅇ # 입력 import sys from itertools import permutations n,m = map(int, sys.stdin.readline().split()) arr = sorted(list(map(int, sys.stdin.readline().split()))) # 처리 for ans in permutations(arr, m): print(*list(ans)) backtracking을 이용한 풀이 숫자가 주어진 다는 점만 고려해주면 금세 끝낼 수 있다. # 입력 import sys n,m = map(int, sys.stdin.readline().split()) arr = sorted(list(map(int, sys.stdin.readline().split()))) ans = [] # 처리 def backtrack(): if len(ans) == m: print(*list(map(str, ans))) return for i in arr: if i not in ans: ans.append(i) backtrack() ans.pop() # return이 실행되면 여기로 돌아옴. (전 단계로 돌아감 = backtrack) backtrack()