[코딩테스트] 브루트 포스(N과 M)

March 11, 2021

reference : 2021 코딩테스트 기초(최백준) 강의를 공부하며 정리한 내용입니다.

N과 M은 재귀에 많이 사용되기 때문에 중요하다.
브루트 포스에 재귀로 풀 수 있는 문제
1. 순서 : N가지 M개 뽑을 때 순서가 중요한 문제 O(N!)
2. 선택 : N가지를 다 할 수 있는데 M개를 어떤 순서로 할지 O(2ⁿ)

N과 M 1 (15649번)

https://www.acmicpc.net/problem/15649

문제
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구하는 문제

입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

풀이

순서와 관련된 브루트포스 문제, 재귀 이용해서 풀 수 있음.
재귀 함수 : 각각 자리에 올 수 있는 수를 정하게 만들어 주면 된다. 어떤 위치에 올 수 있는 수를 결정해주는 것. 이 문제에선 1~N 중에서 앞에서 사용하지 않은 수.
다음 값으로 갈 때 변하는 값이 무엇인지 정해줘야 한다. 이 문제에선 위치가 변한다. 위치 : 함수의 인자 / 사용한 수가 변한다. 앞에서 사용한 숫자를 잘 관리해줘야 한다.
재귀함수에서 가장 중요한 것 : 함수 호출하기 전 그 함수 호출을 위한 준비를 미리 하는 것과 종료조건.

bool c[10]; // i를 사용했으면 true, 사용 안했으면 false
int a[10]; // 수열을 저장
void go(int index, int n, int m){ // index 번째의 수를 결정
	if(index==m){
		//수열을 출력
		return; // 종료
	}
	for(int i=1; i<n; i++){ //1-n 중에서 앞에서 사용하지 않은 수를 찾는다
		if(c[i]) continue; // 사용했으니 건너뛰기
		//수 i를 사용할 수 있다
		c[i] = true; //index에서 수를 사용했으니 index+1로 가기 전에 사용했다 표시
		a[index] = i;
		go(index+1, n, m); // index에 i가 온 뒤 일어날 모든 일들 재귀로 여기서 다 처리, index엔 현재 i가 아닌 다른 i가 와야 한다.
		c[i] = false; //그래서 i 사용하지 않았다고 표현 바꿔줌.
	}
}

종료조건 : 0~M-1 (M개의 수) 까지 다 진행하고 M번째 호출한 경우. 위치가 M이 되면 M개의 수를 다 골랐다 = 종료조건이 된다.
시간복잡도 : O(N!)

자바코드

import java.util.*;

public class Main {
	static boolean check[] = new boolean[10];
	static int arr[] = new int[10];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		go(0, n, m);
	}

	private static void go(int index, int n, int m) {
		if (index == m) {
			for(int i=0; i<m; i++) {
				System.out.print(arr[i]+" ");
			}
			System.out.println();
			return;
		}
		for (int i = 1; i <= n; i++) {
			if (check[i])
				continue;
			check[i] = true;
			arr[index] = i;
			go(index + 1, n, m);
			check[i] = false;
		}
	}
}

N과 M 2 (15650번)

https://www.acmicpc.net/problem/15650

문제
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구하는 문제(오름차순)

입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

풀이

함수 역할이 어떤 위치에 올 수 있는지 결정하는 거라면, 위치 하나 바뀌었을 때 변하는 게 뭔지 확인해야 한다. 1번과 비교해서 변하는 값이 하나 더, 값의 시작점이 더 있어야 함.
start : index번째에 올 수 있는 수는 start부터 N까지

import java.util.*;

public class Main {
	static boolean check[] = new boolean[10];
	static int arr[] = new int[10];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		go(0, 1, n, m);
	}

	private static void go(int index, int start, int n, int m) { //start 추가
		if (index == m) {
			for (int i = 0; i < m; i++) {
				System.out.print(arr[i] + " ");
			}
			System.out.println();
			return;
		}
		for (int i = start; i <= n; i++) { // i = start
			arr[index] = i;
			go(index + 1, i + 1, n, m); // index+1, i+1
			// start로 다음수를 검사하게 했으니 check 없애도 됨
		}
	}
}

순서가 아닌 선택 관련된 문제로 볼 수 있음(오름차순이니 어떤 수를 사용할지 안할지 결정하면 그 수열은 하나밖에 안 나오니까)
선택일 땐 위치가 중요한 게 아니라 어떤 수를 사용할지 결정하면 되기에 기준은 그 수!
선택한지, 선택 안 하는지 / 선택한 수의 갯수
index : 수 index, selected : 선택한 수의 개수, O(N²)

N과 M 3 (15651번)

https://www.acmicpc.net/problem/15651

문제
1부터 N까지 자연수 중에서 M개를 고른 수열을 모두 구하는 문제(중복선택 가능)

입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)

풀이

import java.util.*;

public class Main {
	static int arr[] = new int[10];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		System.out.println(go(0, n, m));
	}

	private static StringBuilder go(int index, int n, int m) {
		if (index == m) {
			StringBuilder add = new StringBuilder();
			for (int i = 0; i < m; i++) {
				add.append(arr[i]+" ");
			}
			add.append("\n");
			return add;
		}
		StringBuilder result = new StringBuilder();
		for (int i = 1; i <= n; i++) {
			arr[index] = i;
			result.append(go(index + 1, n, m));
		}
		return result;
	}
}

-> 1번 풀이에서 중복체크만 없애주면 되는데 문제는 StringBuilder 사용하지 않고 printout을 사용하면 시간초과가 뜬다. BufferedReader를 사용하지 않아도 StringBuilder만 사용하면 시간초과가 뜨지 않는다. 15줄에서 StringBuilder를 생성하는 건 초기화를 위해서임.

N과 M 4 (15652번)

https://www.acmicpc.net/problem/15652

문제
1부터 N까지 자연수 중에서 M개를 고른 수열을 모두 구하는 문제(중복선택 가능, 비내림차순)

입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

풀이

import java.util.*;

public class Main {
	static int arr[] = new int[10];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		System.out.println(go(0, 1, n, m));
	}

	private static StringBuilder go(int index, int start, int n, int m) {
		if (index == m) {
			StringBuilder add = new StringBuilder();
			for (int i = 0; i < m; i++) {
				add.append(arr[i]+" ");
			}
			add.append("\n");
			return add;
		}
		StringBuilder result = new StringBuilder();
		for (int i = start; i <= n; i++) {
			arr[index] = i;
			result.append(go(index + 1, i, n, m)); //중복 허용이기 때문에 i+1였던 2번과 달리 i라고 작성
		}
		return result;
	}
}

문제 2번처럼 선택 개념으로 풀이 가능. 중복선택 가능이라 사용/사용x 경우로 나누면 안됨. 수를 사용했으면 몇 개를 사용했는지 기록해야함.

N과 M 5 (15654번)

https://www.acmicpc.net/problem/15654

문제
N개의 서로 다른 자연수 중에서 M개를 고른 수열을 모두 구하는 문제

입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

풀이

출력할 때 입력값을 인덱스로 가정해서 실제 수로 바꿔 출력해주면 된다. 3번 응용문제.

import java.util.*;

public class Main {
	static int arr[] = new int[10];
	static boolean check[] = new boolean[10];
	static int input[];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int input[] = new int[n];
		for(int i=0; i<n; i++) {
			input[i] = sc.nextInt();
		}
		Arrays.sort(input);
		System.out.println(go(0,n,m,input));
	}

	private static StringBuilder go(int index, int n, int m, int[] input) {
		if (index == m) {
			StringBuilder add = new StringBuilder();
			for (int i = 0; i < m; i++) {
				add.append(arr[i]+" ");
			}
			add.append("\n");
			return add;
		}
		StringBuilder result = new StringBuilder();
		for (int i = 1; i <= n; i++) {
			if(check[i])
				continue;
			check[i] = true;
			arr[index] = input[i-1];
			result.append(go(index + 1, n, m, input));
			check[i] = false;
		}
		return result;
	}
}

N과 M 6,7,8번은 주말에 풀고 업로드 할 예정임.

[코딩테스트] 브루트 포스(N과 M)

N과 M 1 (15649번)

N과 M 2 (15650번)

N과 M 3 (15651번)

N과 M 4 (15652번)

N과 M 5 (15654번)

댓글남기기

최근 포스트

[코딩테스트] bfs

[코딩테스트] 그래프의 탐색

210406 TIL

[코딩테스트] 그래프의 표현