Backtracking

백준 15649번 문제 바로가기 permutations을 이용한 풀이 처음에는 보자마자 itertools에서 permutations을 불러와서 사용했다. 간편하고 빨라서 만족하면서 제출했는데 역시나 정답! 하지만 이 문제를 분석하면서 알고리즘 분류를 봤더니 백트래킹이라는 처음 보는 개념을 가리키고 있었다. 백트래킹에 대한 개념을 알아보고 그 풀이로 다시 풀어보기로 했다. # 입력 import sys from itertools import permutations n,m = map(int, sys.stdin.readline().split()) arr = [i+1 for i in range(n)] # 처리 for ans in permutations(arr, m): print(*list(ans)) 백트래킹(backtracking)이란? 백트래킹은 간단하게 말하자면 가지치기라고 말할 수 있다. DFS의 경우 모든 가지를 다 커버할 떄까지 탐색을 진행하지만, 백트래킹의 경우 특정 조건을 만족시키면 뒤로 돌아가서 다른 경우의 수를 찾아나간다. 이런 특징 때문에 Back+Tracking이라는 이름을 가지게 되었다. 백트래킹에 대한 추가 설명은 이 분이 정말 잘 설명해주셨으니 참고 바란다. (이거보다 더 잘 설명할 자신이 없다…) ...

백준 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()