IT세상

https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net #include using namespace std; int n; bool ch[11]; int ans = 1e9; int w[10][10]; void go(int start, int index, int cnt, int sum) { // 최초 출발지점, 현재 위치, 지나간 마을수, 이동비용 if(cnt == n){ if(w[index][start] ==..

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net #include using namespace std; int k; int num[50], arr[50]; bool isused[50]; void backtrack(int k, int n){ if(k==6){ bool flag = true; int tmp = -1; for(int i=0; i arr[i]) flag = false; tmp = arr[i]; } if(flag){ for(in..

https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net #include using namespace std; int n, m; int arr[8]; void backtrack(int k){ if(k==m){ for(int i=0; i

https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net #include using namespace std; int n, m; int arr[8]; void backtrack(int k){ if(k==m){ for(int i=0; i

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

https://github.com/encrypted-def/basic-algo-lecture/blob/master/workbook/0x0C.md GitHub - encrypted-def/basic-algo-lecture: 바킹독의 실전 알고리즘 강의 자료 바킹독의 실전 알고리즘 강의 자료. Contribute to encrypted-def/basic-algo-lecture development by creating an account on GitHub. github.com 설명 영상 https://www.youtube.com/watch?v=Enz2csssTCs

헤더파일 #include 사용방법 next_permutation(arr, arr+n) // 배열 next_permutation(v.begin(), v.end()) // 벡터 현재 수열을 사전 순으로 생각했을때 다음 수열을 만들고 true를 반환 만약 현재 수열이 가장 마지막이어서 다음 수열에 존재하지 않는다면 false를 반환 순열 예시 #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(0); int a[3] = {1, 2, 3}; do{ for(int i=0; i

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 해결 방법 k를 차례로 증가시키면서 k번째 원소를 합하거나 합하지 않는 두가지 경우로 백트래킹을 한다 #include using namespace std; int n, s; int arr[21]; int result = 0; void backtrack(int k, int tot){ if(k == n){ if(tot == s) result++; return;..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해결 방법 백트래킹을 사용하여 풀수있다 퀸은 상, 하, 좌, 우, 대각선으로 움질일 수 있고 시간을 줄이기 위해 세가지 조건을 검사할 수 있다 우선 퀸이 좌우로 움질일 수 있기 때문에 한 행에는 하나의 퀸 만 놓을 수 있다는 것을 전제로 두고 시작한다 1번 조건 (상하로 움직일 수 있기 때문에 같은 열에 있는지 확인하는 조건) : i의 값이 같으면 continue 해준다 2번 조건 ( / 모양 대각선 위에 ..

https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 문제 해결 방법 백트래킹을 사용하여 가능한 수열을 모두 만들고 각각 주어진 식의 최대값을 구해 제일 큰 값을 찾는다 #include using namespace std; int n; int arr[10]; // 만든 수열을 담을 배열 int num[10]; // 입력받을 배열 bool isused[10]; // 사용했는지 체크 int result = 0; void solve(){ // 주어진 식을 이용하여 최대..