[ 알고리즘 ]/Back Tracking

[백준] 9663. N-Queen

📌문제 https://www.acmicpc.net/problem/9663 🎖️난이도 ✔️풀이 # sol1) 재귀 # python3 오답 (시간 초과) & pypy3 정답 (30044ms) n = int(input()) queen = [0 for _ in range(n)] # 각 행마다의 퀸의 위치(열) cnt = 0 # 해당 행에 퀸을 놓을 수 있는 곳이 있는지(유망한지) 현재 queen 배열 상태 체크 def isPromising(row): # 체크하려는 행의 이전 행까지만 체크 for i in range(row): # 퀸을 놓을 수 없는 경우 2가지 (유망 x) # 1. 같은 열에 위치한 퀸이 있거나 or 2. 왼쪽 위 or 오른쪽 위 대각선에 퀸이 있거나 if queen[row] == queen[i..

[백준] 15651. N과 M (3)

📌문제 https://www.acmicpc.net/problem/15651 🎖️난이도 ✔️풀이 from itertools import product # 중복 순열 n, m = map(int, input().split()) for i in product(range(1, n+1), repeat = m): # product는 꼭 repeat!! print(' '.join(map(str, i)))

[백준] 15650. N과 M (2)

📌문제 https://www.acmicpc.net/problem/15650 🎖️난이도 ✔️풀이 n, m = map(int, input().split()) result = [] def dfs(k): if len(result) == m: print(' '.join(map(str, result))) for i in range(k, n+1): if i not in result: result.append(i) dfs(i+1) # 다음 값부터 dfs 돌도록 넣기! result.pop() dfs(1)

[백준] 15649. N과 M (1)

📌문제 https://www.acmicpc.net/problem/15649 🎖️난이도 ✔️풀이 # sol1) back tracking (recursion) N, M = map(int, input().split()) result = list() def func(): if len(result) == M: print(' '.join(map(str, result))) return for i in range(1, N+1): if i not in result: result.append(i) func() result.pop() func() # sol2) itertools - permutations (순열) from itertools import permutations n, m = map(int, input().spl..