Algorithm/back_tracking

백준 15652 N과 M(4) c++ // 백트래킹, n H m 중복(?)조합

https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 문제해결 start부분을 arr[k-1]로 바꾸면 된다. 기존 조합 : st=arr[k-1]+1 2. 전체코드 #include using namespace std; int n,m; int arr[10]; int isused[10]; //현재까지 k개의 수를 선택함. void go(int k) { if (k==m){ for (int i = 0; i < m; ++i) { cout m; go(0..

백준 15651 N과 M(3) // 백트래킹, n ∏m 중복순열

https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 중복순열 코드 : 순열코드에서 방문부분을 주석하면 된다! 2. 전체코드 #include using namespace std; int n,m; int arr[10]; int isused[10]; //현재까지 k개의 수를 선택함. void go(int k) { if (k==m){ for (int i = 0; i < m; ++i) { cout m; go(0); }

백준 15650 N과 M(2) c++ // n C m, 조합

https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 전체코드 #include using namespace std; int n,m; int arr[10]; int isused[10]; //현재까지 k개의 수를 선택함. void go(int k) { if (k==m){ for (int i = 0; i m; go(0); }

백준 1182 부분수열의 합 c++ // 백트래킹

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 1. 해결과정 함수정의 : (현재깊이, 총합) 탈출조건(기저사례) : 깊이>=n 재귀식 : 현재값(arr[cur])을 더한다 / 안더한다 2. 전체코드 #include using namespace std; int n,s,ret; int arr[24]; //현재깊이, 총합 void go(int cur, int tot) { if (cur==n){ if (tot ==..

백준 9663 N-Queen c++ // 재귀, 백트래킹, 일반식도출, 백트래킹 시간복잡도

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 일반식도출 1.1 / 대각선인경우 규칙 : (1,0) (0,1) -> x+y의 값이 1로 동일하다! -> (0,1)에 이미 두고 (1,0)에 두려고 할경우 isused[1]이 true이기 때문에 continue된다! 1.2 \ 대각선인경우 규칙 : (0,0) (1,1) -> x-y의 값이 0로 동일하다! -> (0,0)에 이미 두고 (1,1)에 두려고 할경우 isused[0]이 true이기 때문에 conti..