브루트포스 - N과M
재귀로 풀수 있는 브루트포스 문제는
1.순서
N중에 M개를 뽑을때 순서가 중요한 문제 -> N! 시간복잡도를 가짐
2.선택
N가지 중에 어떤것을 선택하고 어떤것은 선택하지 않는 문제 -> 2^N
문제 1 ) N과 M(1)
문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1
3 1
예제 출력 1
1
2
3
예제 입력 2
4 2
예제 출력 2
1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3
풀이
이 문제는 순서와 관련이 있다.
1 2 3 != 1 3 2
재귀의 목표는 어떤 위치에 올수 있는 수를 선택(결정) -> 함수
첫번째 자리에 올수있는 수는 1부터 N 이다.
두번째 자리에 올수있는 수는 1부터 N (첫번째 자리 수 제외) 이다.
세번째 자리에 올수있는 수는 1부터 N (첫번째 자리 수, 두번째 자리 수 제외) 이다.
-> 1부터 N 수 중에서 앞에서 사용하지 않은 수
위치(자리) -> 함수 인자
앞에서 사용한 수 관리
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static StringBuilder builder = new StringBuilder();
static boolean[] c = new boolean[10];
static int[] a = new int[10];
static void go(int index, int n, int m) {
//1부터 n까지의 자연수 중에 중복없이 m개를 고르는 수열
if (index == m) { //m개를 다 채우면 return
for (int i=0; i<m; i++) {
builder.append(a[i]);
if (i != m-1) builder.append(' ');
}
builder.append("\n");
return;
}
for (int i=1; i<=n; i++) {//1~N중에
if (c[i]) continue; //c[i]가 true이면 사용한 수 이기 때문에 건너뛰기
c[i] = true; //i를 사용한것을 체크
a[index] = i; //i를 index번째 자리에 위치시킴
go(index+1, n, m);// 다음 자리로~
c[i] = false; //다시 사용해야 하므로 false로 초기화
}
}
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int n = Integer.parseInt(tokenizer.nextToken());
int m = Integer.parseInt(tokenizer.nextToken());
go(0,n,m); //0번째의 수를 결정
System.out.println(builder);
}
}문제 2 ) N과 M(2)
문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
고른 수열은 오름차순이어야 한다.
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1
3 1
예제 출력 1
1
2
3
예제 입력 2
4 2
예제 출력 2
1 2
1 3
1 4
2 3
2 4
3 4
예제 입력 3
4 4
예제 출력 3
1 2 3 4
풀이
N과 M(1)과 다른 점은 수열을 오름차순해야함
1 2 3
1 2 4
1 2 5
1 2 6
1 2 7
1 3 2
1 3 4
첫번째 자리 두번째 자리 세번째 자리
4 7
1 - N 5 - N 8 - N
변하는 것 : 위치, 자리에오는 수, 올수 있는 숫자 범위
-> start가 추가 되어야함
->이렇게 푸는 것은 순서로 푸는 것이였다.
이제는 선택으로 풀어보자
1 3 4 수열
1 2 3 4 5
o x o o x 로 볼수있다.
1 3 4
N과 M(1)을 선택으로 풀수 없는 이유는
1 2 3 4 5
o x o o x 일때
1 3 4
1 4 3
3 1 4
.... 경우의 수가 많기 때문에
선택한 수의 개수를 저장해야한다.
import java.util.*;
public class Main {
static int[] a = new int[10];
//이 함수 역할 : 수 index를 선택할지 안할지 결정해야함
static void go(int index, int selected, int n, int m) {
//index : 숫자
//selected : 선택한 수의 개수
if (selected == m) { //선택한 수가 m개가 되었을때 return
for (int i=0; i<m; i++) {
System.out.print(a[i]);
if (i != m-1) System.out.print(' ');
}
System.out.println();
return;
}
if (index > n) return; //더이상 선택할 수가 없을 경우
//선택했을 경우
a[selected] = index; // 선택한 자리에 index를 넣기
go(index+1, selected+1, n, m); //선택 했으므로 selected와 index 증가
//선택하지 않았을 경우
a[selected] = 0;
go(index+1, selected, n, m);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
go(1, 0, n, m);
}
}-> 시간복잡도 O(2^N)
문제 3 ) N과 M(3)
문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1
3 1
예제 출력 1
1
2
3
예제 입력 2
4 2
예제 출력 2
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4
풀이
N과M(1)과 다른 점은 중복 선택이 가능하다는 점이다.
N과M(1)에서 중복을 막는것을 제거하면 됨
c[i] : 수 i를 사용 여부를 check
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static StringBuilder builder = new StringBuilder();
static boolean[] c = new boolean[10];
static int[] a = new int[10];
static void go(int index, int n, int m) {
//1부터 n까지의 자연수 중에 중복없이 m개를 고르는 수열
if (index == m) { //m개를 다 채우면 return
for (int i=0; i<m; i++) {
builder.append(a[i]);
if (i != m-1) builder.append(' ');
}
builder.append("\n");
return;
}
for (int i=1; i<=n; i++) {//1~N중에
a[index] = i; //i를 index번째 자리에 위치시킴
go(index+1, n, m);// 다음 자리로~
}
}
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int n = Integer.parseInt(tokenizer.nextToken());
int m = Integer.parseInt(tokenizer.nextToken());
go(0,n,m); //0번째의 수를 결정
System.out.println(builder);
}
}문제 4 ) N과 M(4)
문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.
고른 수열은 비내림차순이어야 한다.
길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1
3 1
예제 출력 1
1
2
3
예제 입력 2
4 2
예제 출력 2
1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
4 4
풀이
N과 M(2)와 N과 M(3)을 합친 문제
아까 N과 M(2)에서는 start를 i+1로 정했다 .중복을 피하기 위해서
그치만 N과 M(4)중복도 괜찮기 때문에 start는 i이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static StringBuilder builder = new StringBuilder();
static boolean[] c = new boolean[10];
static int[] a = new int[10];
static void go(int index, int start, int n, int m) {
//1부터 n까지의 자연수 중에 중복없이 m개를 고르는 수열
if (index == m) { //m개를 다 채우면 return
for (int i=0; i<m; i++) {
builder.append(a[i]);
if (i != m-1) builder.append(' ');
}
builder.append("\n");
return;
}
for (int i=start; i<=n; i++) {//1~N중에
a[index] = i; //i를 index번째 자리에 위치시킴
go(index+1,i, n, m);// 다음 자리로~
}
}
// c[i] 부분는 없어져도 상관 없음
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int n = Integer.parseInt(tokenizer.nextToken());
int m = Integer.parseInt(tokenizer.nextToken());
go(0,1,n,m); //0번째의 수를 결정
System.out.println(builder);
}
}이제는 선택으로 풀어보자
이전 선택에서는 몇개를 선택했는 저장해 놔야하는데
import java.util.Scanner;
public class Main {
static int[] cnt = new int[10]; //cnt[i] : 수 i를 사용한 횟수
static StringBuilder go(int index, int selected, int n, int m) {
System.out.println("index "+index + " selected "+selected);
if (selected == m) {//선택한 수가 m개가 되었을때 return
StringBuilder sb = new StringBuilder();
for (int i=1; i<=n; i++) {
for (int j=1; j<=cnt[i]; j++) {
sb.append(i);
sb.append(" ");
}
}
sb.append("\n");
System.out.println(sb);
return sb;
}
StringBuilder ans = new StringBuilder();
if (index > n) return ans;//더이상 선택할 수가 없을 경우
//수를 사용하는 경우
for (int i=m-selected; i>=1; i--) { //거꾸로 i가 시작하는 이유->사전순 정의 때문에
cnt[index] = i;
ans.append(go(index+1, selected+i, n, m));
}
cnt[index] = 0;
//수를 사용하지 않는 경우
ans.append(go(index+1, selected, n, m));
return ans;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
System.out.print(go(1, 0, n, m));
}
}1 1 1 1
1 1 1
1 1
1
일때는 1이 가장 사전순으로 작지만
뒤에 순자가 붙는다면
1 1 1 1 2
1 1 1 2 2
1 1 2 2 3
1 2 2 3 3
일때는 1이 가장 많은게 사전순으로 작다.
Author And Source
이 문제에 관하여(브루트포스 - N과M), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yuiopre98/브루트포스-N과M저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
