cedis 님의 블로그

정글 알고리즘 · 중 [백준 9663] N-QueenDFS 백트래킹 완전 정복 cedis · 2026.03.10 | Python · 백트래킹 · DFS 백트래킹 하면 항상 나오는 문제가 있다. N-Queen이다. 처음 봤을 때는 "체스판에 퀸 N개를 놓는다"는 말만 들었는데, 막상 어떻게 풀어야 할지 감이 안 잡혔다. 이 글은 그 감을 잡는 과정을 처음부터 하나씩 따라가는 기록이다. 🔗 문제 링크: 백준 9663번 - N-Queen N×N 크기의 체스판에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 구하라. ① 퀸은 어떻게 공격하나 체스의 퀸은 가로, 세로, 대각선 방향으로 몇 칸이든 이동할 수 있다. 즉, 같은 행, 같은 열, 같은 대각선에 두 번..

크래프톤 정글 · 백준 10819차이를 최대로순열(Permutation) × DFS 백트래킹 — 최적 배열 순서 찾기BEFOREif not used[i]: # 단순 반복 dfs(depth + 1)→AFTERpath.append(a[i]) # 선택dfs(depth + 1) # 탐색path.pop() # 복원 ✔처음에는 단순히 모든 경우를 시도하면 된다고 생각했다. 배열 길이가 최대 8이니까 8! = 40,320가지. 완전 탐색이 충분하다. 그런데 막상 DFS로 짜다 보니 백트래킹의 핵심 패턴을 빠뜨렸다. 선택 → 재귀 → 복원. 이 세 단계 중 하나라도 빠지면 다른 분기가 오염된다.이번 포스트에서는 itertools 풀이와 DFS 백트래킹 풀이 두 가지를 시각 자료와 함께 비교한다..

BEFORE for j in range(2, left): if left % j == 0: 소수 아님... AFTER if prime[left] and prime[right]: → 즉시 확인 크래프톤 정글 / 정글에서 문제풀기[정글 베이직] 골드바흐의 추측백준 9020 · 수학, 소수 · Gold V처음에 소수 판별을 매번 하려고 했다.테스트케이스마다 for j in range(2, left)를 돌리면 되겠다고 생각했다. 논리는 맞는데, 뭔가 너무 많이 도는 것 같았다.그때 에라토스테네스의 체를 처음 제대로 이해했다. 미리 계산해두면 조회가 O(1)이 된다는 것을 여기서 처음 느꼈다.· · ·문제 소개4 이상의 짝수 n을 두 소수의 합으로 나타내되, 두 소수의 차이가 ..