Algorithm/back_tracking

백준 15666 N과 M(12) c++ // 서로같은 n H m , 중복조합 구현

https://www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 핵심로직 1.1 스타트부분 추가 => 조합구현 1.2 방문부분 주석 => 중복구현 1.3 이전 막항과 추가할 값 비교 추가 => 중복된 수열이면 pass! 2. 전체코드 #include using namespace std; int n,m; int num[10],arr[10]; int isused[10]; //현재까지 k개의 수를 선택함. void go(int k) { if (k==m){ ..

백준 15665 N과 M(11) c++ // 서로다른 n ∏m, 중복순열 구현방법

https://www.acmicpc.net/problem/15665 15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 핵심로직 1.1 방문처리주석 => 중복구현 1.2 스타트부분 주석 => 순열구현 1.3 이전막항과 추가할값 비교 추가 => 중복된 수열 제거! 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 (in..

백준 15664 N과 M(10) c++ // 서로다른 n C m 구현하기

https://www.acmicpc.net/problem/15664 15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 핵심로직 for문에 start추가 => 조합구현. //스타트=> 조합구현 int st = 0; if (k != 0) st = arr[k - 1]; int tmp = 0; for (int i = st; i < n; ++i) { if (isused[i]) continue; if (tmp == num[i]) continue; //(이전수열의 막항 == 새로추가할 값)중복된 수열이면 패스! ar..

백준 15663 N과 M(9) c++ // 서로같은 n P m, 중복된수열 검사하는 방법

https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 중복된수열 검사하는 방법 1.1 tmp 배열에는 이전수열의 막항 저장 1.2 tmp == num[i] (추가할값) 이면 중복된 값을 저장하는것 -> pass 해야함. int tmp = 0; for (int i = 0; i < n; ++i) { if (isused[i]) continue; if (tmp == num[i]) continue; //(이전수열의 막항 == 새로추가할 값)중복된 수열..

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