안녕 세상아,

백트래킹이란? - ( DFS + 조건문 )​해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아 간다.모든 가능한 경우의 수 중 특정한 조건을 만족하는 경우만 살펴보는 것이다.​일반적으로 불필요한 경로를 조기에 차단할 수 있기 때문에 경우의 수가 줄어들 수 있지만, 최악의 경우에는 여전히 지수함수 시간을 필요로 하기 때문에 처리가 불가능할 수 있다. 즉, 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정된다. ​주로 문제 풀이에서는 DFS(깊이 우선 탐색) 등으로 모든 경우의 수를 탐색하는 과정에서 조건문을 걸어 답이 절대로 될 수 없는 상황을 정의하고 그런 상황일 경우 탐색을 중단한 뒤 그 이전으로 돌아가서 다른 경우를 탐색하게끔 한다.  예시​https://w..

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net n과 m (7) 문제랑 같은 방식으로 풀면 된다. 기존 배열과 다른 배열을 하나 더 만들어서 새로운 값을 넣어준 후 조합으로 출력해주면 된다. #include #include //memset 사용 #include //sort 사용 using namespace std; int k; bool isVisited[14] = { false }; int map[14]; int ans[14]; vo..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 팀 나누고 최솟값 구하는게 중요한 것 같다. #include #include using namespace std; int n; int arr[21][21]; bool isVisited[22]; int minNum = 10000000;//최솟값 찾기 위함 void dfs(int x, int idx) { if (x == n / 2) { int start, link; start = 0; link = 0; //start와 l..

https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net N과 M (4)번 문제에서 새로운 배열만 만들어주면 된다. #include #include using namespace std; int n, m; int arr[10];//입력받은 원래 배열 bool isVisited[10] = { false }; int ans[10];//출력할 배열 void dfs(int depth, int x) { if (x == m) { for (int i = 0;..

https://www.acmicpc.net/problem/10974 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net 전형적인 백트래킹 문제이다. N과 M 문제 풀어봤으면 걍 눈 감고도 풀기 가능하다. https://hello-world-cpp.tistory.com/2 [백준/c++] 15649 N과 M(1) https://www.acmicpc.net/problem/15649 전형적인 백트래킹 문제,, DFS를 참고해서 풀면 된다. 중복도 허용하기 때문에 백트래킹계의 순열이라고 볼 수 있다. DFS의 재귀를 이용하여 풀었다. 자세한 설명은 코 hello-world-cpp.tistory.com 여기 더 ..

https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 이번 시리즈는 새로운 배열을 하나 만들고 입력받는 그러한 과정만 거치면 N과 M (1)과 똑같다. 배열 값을 입력 받은 후 sort만 해주면 된다. 계속 풀다보니까 백트래킹을 100중에 3정도는 알 것 같은 느낌이다. 다양한 문제를 더 풀다보면 갑자기 어느순간 확 느는 느낌을 받을 수 있길 바라며.. #include #include #include using namespace std; i..

https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N과 M(1)에서 조건만 조금 추가하면 해결 가능하다. N과 M(1)이 중복도 허용하는 순열이라면 이 문제는 중복을 허용하지 않는 조합과 같은 문제라고 생각하면 된다. 출력되는 모든 숫자는 첫번째 숫자는 두번째 숫자보다 작도록, 두번째 숫자는 세번째 숫자보다 작도록 하면 된다. #include #include using namespace std; int arr[9] = {}; bool visit..

https://www.acmicpc.net/problem/15649 전형적인 백트래킹 문제,, DFS를 참고해서 풀면 된다. 중복도 허용하기 때문에 백트래킹계의 순열이라고 볼 수 있다. DFS의 재귀를 이용하여 풀었다. 자세한 설명은 코드에 적어놓았다. #include #include #include using namespace std; bool checked[9] = { false, }; int arr[9] = {}; int a, b; void dfs(int depth) { //만약 dfs의 depth가 b와 같으면 arr배열에 담긴 순열 출력, 종료 if (depth == b) { for (int i = 0; i < b; i++) { cout b; dfs(0);// 백트래킹 0부터 시작 } 백트래킹에..