Algorithm

백준 15657 N과 M(8) c++ // 중복조합 구현방법

https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 핵심로직 1 .1. 방문부분 주석 => 중복구현 1. 2. start=arr[k-1] // (이전에 저장된인덱스) 부터 시작 => 조합구현 2. 전체코드 #include using namespace std; int n,m; int num[10],arr[10]; int isused[10]; //현재까지 k개의 수를 선택함. void go(int k) { if (k==m){ for (i..

백준 15656 N과 M(7) c++ // 중복순열, 인덱스로 돌리고 return에서 원소에 접근하면 된다.

https://www.acmicpc.net/problem/15656 15656번: N과 M (7) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 순열 -> 중복순열 구현방법 방문체크 부분을 없애면된다! 2. 전체코드 #include using namespace std; int n,m; int num[10],arr[10]; int isused[10]; //현재까지 k개의 수를 선택함. void go(int k) { if (k==m){ for (int i = 0; i >m; for (int i ..

백준 15655N과 M(6) c++ // 조합, 인덱스를 돌리고 return에서 내용에 접근하라

https://www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 핵심코드 st=0임에 주의! //스타트=> 조합구현 int st = 0; if (k != 0) st = arr[k - 1]+1; for (int i = st; i < n; ++i) { 2. 전체코드 #include using namespace std; int n,m; int num[10],arr[10]; int isused[10]; //현재까지 k개의 수를 선택함. void go(i..

백준 15654 N과 M (5) c++ // 순열, 인덱스를 저장후 실제원소에 접근하는 방법

https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 핵심코드 for (int i = 0; i < n; ++i) { if (isused[i]) continue; arr[k] = i;//arr에 인덱스를 기록, return에서 인덱스로 접근하면됨. isused[i] = 1; go(k+1); isused[i] = 0; } 2. 전체코드 #include using namespace std; int n,m; int num[10],arr[10]..

백준 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 ==..