백트래킹

패스트캠퍼스 챌린지 10일차

시청 날짜 : 11/10/2021 시청 강의 : 어떻게든 푼다. 완전 탐색 (Brute Force) 응용편 오늘은 완전탐색 강의 2를 듣기 위해 문제를 푸는것을 중심으로 학습했다. 연산자 끼워넣기 https://www.acmicpc.net/problem/14888 부분수열의 합 https://www.acmicpc.net/problem/1182 암호 만들기 https://www.acmicpc.net/problem/1759 위의 연습문제를 모두 dfs를 사용하여 풀었다. 연산자 끼워넣기 무려 삼성 기출문제로 분류되어있다. 이렇게만 나오면 얼마나 행복할까.. DFS private static void dfs(int depth , int calculated){ ... } //main 함수: dfs(1,nums[..

패스트캠퍼스 챌린지 9일차

날짜 : 2021 년 11 월 9 일 시청 강의 : 01. 어떻게든 푼다. 완전 탐색 (Brute Force) 완전탐색 모든 경우를 전부 탐색 4가지 문제 유형으로 나누어 볼 수 있음. [문제유형] 1. N개의 원소 중 중복 없이 M 개를 순서있게 나열 2. N개의 원소 중 중복 없이 M 개를 고르기 3. N개의 원소 중 중복 허용하여 M 개를 순서있게 나열 4. N개의 원소 중 중복 허용하여 M 개를 고르기 완전탐색으로 문제를 풀 때, 백트래킹이 자주 사용되는데 dfs는 백트래킹 문제 방법 중 하나임 따라서, 완전탐색으로 문제를 풀이하는 경우에, public static void recurrsive(int depth){ //재귀 } public static void main(String[] args){..

패스트캠퍼스 챌린지 8일차

날짜 : 2021 년 11 월 8 일 시청 강의 : 백트래킹 알고리즘 이해 (1) 벌써 8일차라니..신기하다.. 오늘은 백트래킹 알고리즘이해 (1)을 들었다. 포스팅 작성 후, N 퀸을 직접 구현해보고 백트래킹 알고리즘 이해 (2)를 듣는게 나을 것 같다. 애니웨이.. 백트래킹 제약 조건 만족 문제에서 해를 찾기 위한 전략 해가 될 수 있는 다양한 후보근을 트리 형태로 표현 (State Space Tree) 진짜 트리는 아니고, dfs 로 풀 수 있다. How it works... 1. 루트 노드를 하나 잡아서, 해가 될 수 있는지 판단 2. 해가 될 수 있다면 해당 해의 child 가 해가 될 수 있는지 판단 3. 해가 될 수 없다면, 다시 그 전 조건으로 돌아간다. 이때, 해가 될 수 없는 노드의 자..