행복한 개구리

N = int(input()) ops = [] nums = [] result = [] nums = list(map(int, input().split())) ops = list(map(int, input().split())) m = -1e9 n = 1e9 def DFS(num, depth, add, sub, mul, div): if depth == N: if num not in result: result.append(num) return if add > 0: DFS(num + nums[depth], depth + 1, add - 1, sub, mul, div) if sub > 0: DFS(num - nums[depth], depth + 1, add, sub - 1, mul, div) if mul > 0: ..

sudoku = [] blank = [] for i in range(9): sudoku.append(list(map(int, input().strip().split()))) for i in range(9): for j in range(9): if sudoku[i][j] == 0: blank.append((i, j)) def CheckRow(x, val): for i in range(9): if sudoku[x][i] == val: return False return True def CheckCol(y, val): for i in range(9): if sudoku[i][y] == val: return False return True def CheckSquare(x, y, val): startX = x /..

import sys arr = [] def DFS(idx, n, m): if len(arr) == m: sys.stdout.write(" ".join(map(str, arr)) + "\n") return for i in range(idx, n + 1): arr.append(i) DFS(i, n, m) arr.pop() N, M = map(int, sys.stdin.readline().split()) DFS(1, N, M) DFS를 활용합니다. 하지만 유의해야할 점이 있는데, 비내림차순(인덱스가 커 질수록 요소들이 같거나 커짐)이므로 시작인덱스를 정해주는게 좋습니다. => 시작인덱스를 정해주면 해당 검색경로에 나오는 모든 값을 다 사용할 수 있기 때문입니다. 따라서 재귀를 통해 인덱스가 증가하며 비내림차순..

arr = [] def DFS(n, m): if len(arr) == m: print(" ".join(map(str, arr))) return for i in range(1, n+1): arr.append(i) DFS(n, m) arr.pop() N, M = map(int, input().split()) DFS(N, M) 결괏값을 제한하는 조건없이 모든 경우의 수를 탐색하는 코드를 작성해야합니다. 따라서 DFS를 사용하지만 조건은 추가하지 않은 채로 구현했습니다.

arr = [] result = [] def DFS(n, m): if len(arr) == m: if sorted(arr) in result: return else: result.append(sorted(arr)) return for i in range(1, n+1): if i not in arr: arr.append(i) DFS(n, m) arr.pop() N, M = map(int, input().split()) DFS(N, M) for i in result: print(" ".join(map(str, i))) N과 M (1)때처럼 DFS를 사용하여 백트래키을 구현했습니다. 추가로 오름차순인 수열만 인정한다는 조건이 있습니다. 따라서 모든 경우의 수를 탐색할 arr리스트와 오름차순 수열을 저장할 re..

퇴각검색 - 위키백과, 우리 모두의 백과사전 퇴각검색(영어: backtracking, 한국어: 백트래킹)은 한정 조건을 가진 문제를 풀려는 전략이다. "퇴각검색(backtrack)"이란 용어는 1950년대의 미국 수학자 D. H. 레머가 지었다. 문제가 한정 조건을 가진 ko.wikipedia.org arr = [] def dfs(n, m): if len(arr) == m: print(" ".join(map(str, arr))) return for i in range(1, n+1): if i not in arr: arr.append(i) dfs(n, m) arr.pop() N, M = map(int, input().split()) dfs(N, M) 백트래킹을 활용한 문제풀이입니다. 백트래킹은 브루트포스와..