728x90 반응형 백트래킹2 [백준 실버1] 연산자 끼워넣기 (#14888, 백트래킹 문제) (문제 링크) 📌 1. 문제 설명 요약 • N개의 수가 주어지고, 이 사이에 N-1개의 연산자 (+, -, *, /)를 끼워넣어 계산해야 함. • 수의 순서는 바뀌지 않고, 연산자 순서를 바꿔서 가능한 모든 경우를 탐색해야 함. • 연산자 우선순위는 고려하지 않고, 왼쪽에서 오른쪽 순서대로 연산을 진행. • 가능한 모든 식을 만들고 최댓값과 최솟값을 출력해야 함. • 나눗셈(÷)은 C++14 기준으로 수행 (음수를 나눌 때 처리 방식이 다름). 📌 2. 문제를 보자마자 생각하는 풀이 흐름 💡 어떻게 접근해야 할까? • 주어진 숫자는 그대로 사용하고, 연산자들의 순서만 바꿔서 탐색해야 함. • 가능한 모든 연산 조합을 탐색하려면 완전 탐색(백트래킹)을 사용해야 함. • N-1개의 연산자가 있기 때문.. 2025. 2. 15. 백트래킹 & N-Queen 문제 정리 1️⃣ 백트래킹 (Backtracking) 개념백트래킹은 모든 경우를 탐색하면서, 불가능한 경우는 빠르게 포기(가지치기)하여 탐색량을 줄이는 기법. ✅ 기본 원리:1. 가능한 모든 경우를 탐색 (완전 탐색).2. 유효하지 않은 경우를 빨리 제거하여 탐색 시간을 줄임.3. 탐색이 실패하면 "이전 상태"로 돌아감 (백트래킹). ✅ 언제 사용하나?- N-Queen 문제, 순열/조합 문제, 수식 만들기, 미로 탐색 등에서 많이 사용됨.- 완전 탐색은 시간이 너무 오래 걸릴 때, 가지치기를 통해 불필요한 탐색을 줄여야 할 때 사용됨. 2️⃣ N-Queen 문제 풀이 방법 (문제 링크) ✅ 문제 요약:- NxN 체스판 위에 N개의 퀸을 서로 공격할 수 없게 배치하는 경우의 수를 구하는 문제.- 퀸(Queen): 같.. 2025. 2. 14. 이전 1 다음 728x90 반응형
