[멀캠|Java] 9일차 수업
KB IT’s Your Life 4기 - Java 알고리즘 9일차
완전탐색
종류
- brute force - 반복문/조건문
- 순열
- 재귀호출
- 비트마스크(2진수 표현 활용)
- BFS, DFS
Brute Force 기법
- 반복/조건문
- 이걸로 문제를 풀순 X
순열
- 서로다른 N개를 일렬로 나열하는 방법(경우의 수)
- 순열에 원소를 채워가는 방식
- 시간복잡도 O(N!)
재귀함수
- 각 원소가 두 가지 선택지를 가질 때 유용하게 사용.
- 포함이 되면 해당 원소를 넣어 함수를 호출, 포함되지 않으면 그 상태에서 함수 호출
- 시간 복잡도 O(N)
- 반드시 종료조건 기술할 것!!!
비트마스크
- 나올 수 있는 모든 경우의 수가 각각의 원소가 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우 유용하게 사용
- 쓰였는가, 안쓰였는가?
BFS, DFS
- 너비 우선 탐색(BFS)
- 깊이 우선 탐색(DFS)
순열
- nCr 조합 : n개 중에 r개를 뽑는다. (12 = 21)
-
nPr 순열 : n개 중 r개를 뽑아 순서대로 나열한다. (12 != 21)
-
순열과 조합의 차이: 순서 고려 유무
-
조합 점화식 : D[i][j] = D[i-1][j] + D[i-1][j-1]
- 어제 경우의 수 review
경우의수(중복O)
package 재귀리뷰;
public class 경우의수 {
static int arr[]; // 원소
static int n; // 답의 길이
static int result[]; // 답 저장 배열
public static void main(String[] args) {
// 원소 {1,2,3}에 대한 모든 숫자 조합
arr = new int[] { 1, 2, 3 }; // 반복할 숫자
n = 3; // 출력할 숫자 조합길이
result = new int[n]; // 저장할 답의 배열
recur(0); // 깊이 0을 전달
}
private static void recur(int depth) { //level이라고 해도 됨
//종료조건
if(depth == n) { //깊이와 답 길이가 동일하면 답 출력
printResult();
return; //else를 쓰지 않을 경우, return을 사용하여 끝냄.
}
//처리코드(result에 숫자를 누적)
for(int i =0; i<n; i++) {
result[depth] = arr[i]; //깊이 자리에 i번째 숫자 저장
recur(depth+1); //깊이증가 후 재귀호출
}
}
//답출력
private static void printResult() {
for(int i : result) { //result에서 순서대로 추출
System.out.print(i); //붙여서 출력
}
System.out.println(); //줄바꿈
}
}
경우의수(중복X)
package 재귀리뷰;
public class 경우의수2 { //중복값을 사용하지 않는 경우,
static int arr[]; // 원소
static int n; // 답의 길이
static int result[]; // 답 저장 배열
static boolean[] visited; // 사용여부
public static void main(String[] args) {
// 원소 {1,2,3}에 대한 모든 숫자 조합
arr = new int[] { 1, 2, 3 }; // 반복할 숫자
visited = new boolean[arr.length]; // 원소길이만큼 기본 false값을 담음.
n = 3; // 출력할 숫자 조합길이
result = new int[n]; // 저장할 답의 배열
recur(0); // 깊이 0을 전달
}
private static void recur(int depth) { // level이라고 해도 됨
// 종료조건
if (depth == n) { // 깊이와 답 길이가 동일하면 답 출력
printResult();
return; // else를 쓰지 않을 경우, return을 사용하여 끝냄.
}
// 처리코드(result에 숫자를 누적)
for (int i = 0; i < n; i++) {
//arr[i]숫자가 미사용인, false경우에만 사용
if (!visited[i]) {
result[depth] = arr[i]; // 깊이 자리에 i번째 숫자 저장
visited[i] =true; //사용한 i번째 true로
recur(depth + 1); // 깊이증가 후 재귀호출}
visited[i] =false; //
}
}
}
// 답출력
private static void printResult() {
for (int i : result) { // result에서 순서대로 추출
System.out.print(i); // 붙여서 출력
}
System.out.println(); // 줄바꿈
}
}
순열
package 재귀리뷰;
public class 경우의수3 { //중복값을 사용하지 않는 경우, 2개의 숫자만 뽑은 경우의 수, 순열
static int arr[]; // 원소
static int n; // 답의 길이
static int result[]; // 답 저장 배열
static boolean[] visited; // 사용여부
public static void main(String[] args) {
// 원소 {1,2,3}에 대한 모든 숫자 조합
arr = new int[] { 1, 2, 3 }; // 반복할 숫자
visited = new boolean[arr.length]; // 원소길이만큼 기본 false값을 담음.
n = 2; // 출력할 숫자 조합길이
result = new int[n]; // 저장할 답의 배열
recur(0); // 깊이 0을 전달
}
private static void recur(int depth) { // level이라고 해도 됨
// 종료조건
if (depth == n) { // 깊이와 답 길이가 동일하면 답 출력
printResult();
return; // else를 쓰지 않을 경우, return을 사용하여 끝냄.
}
// 처리코드(result에 숫자를 누적)
for (int i = 0; i < arr.length; i++) {
//arr[i]숫자가 미사용인, false경우에만 사용
if (!visited[i]) {
result[depth] = arr[i]; // 깊이 자리에 i번째 숫자 저장
visited[i] =true; //사용한 i번째 true로
recur(depth + 1); // 깊이증가 후 재귀호출
visited[i] =false; //
}
}
}
// 답출력
private static void printResult() {
for (int i : result) { // result에서 순서대로 추출
System.out.print(i); // 붙여서 출력
}
System.out.println(); // 줄바꿈
}
}
조합
package 재귀리뷰;
public class 경우의수4 { //중복값을 사용하지 않는 경우, 2개의 숫자만 뽑은 경우의 수, 순서 고려X - 조합
static int arr[]; // 원소
static int n; // 답의 길이
static int result[]; // 답 저장 배열
static boolean[] visited; // 사용여부
public static void main(String[] args) {
// 원소 {1,2,3}에 대한 모든 숫자 조합
arr = new int[] { 1, 2, 3 }; // 반복할 숫자
visited = new boolean[arr.length]; // 원소길이만큼 기본 false값을 담음.
n = 2; // 출력할 숫자 조합길이
result = new int[n]; // 저장할 답의 배열
recur(0, 0); // 깊이 0을 전달, 시작 번호 0 을 전달
}
private static void recur(int depth, int start) { // level이라고 해도 됨
// 종료조건
if (depth == n) { // 깊이와 답 길이가 동일하면 답 출력
printResult();
return; // else를 쓰지 않을 경우, return을 사용하여 끝냄.
}
// 처리코드(result에 숫자를 누적)
for (int i = start; i < arr.length; i++) {
//arr[i]숫자가 미사용인, false경우에만 사용
if (!visited[i]) {
result[depth] = arr[i]; // 깊이 자리에 i번째 숫자 저장
visited[i] =true; //사용한 i번째 true로
recur(depth + 1, i+1); // 깊이증가 후 재귀호출 , 시작위치에서 for문이 모두 돌았으면 다시 돌지 못하게 막음. (ex. 123에서 1의 경우의수를 모두 찾았음으로 다음은 2부터 찾음.)
visited[i] =false;
}
}
}
// 답출력
private static void printResult() {
for (int i : result) { // result에서 순서대로 추출
System.out.print(i); // 붙여서 출력
}
System.out.println(); // 줄바꿈
}
}
백준 15649
- 순열 구하기
package b15649;
import java.util.Scanner;
public class Main {
static int N;
static int M;
static int[] arr;
static int[] answer;
static boolean[] visited;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
arr = new int[N];
answer = new int[M];
visited = new boolean[arr.length];
for (int i = 0; i < N; i++) {
arr[i] = i + 1;
}
recur(0);
}
private static void recur(int depth) {
if (depth == M) {
printResult();
return;
}
for (int i = 0; i < arr.length; i++) {
if (!visited[i]) {
answer[depth] = arr[i];
visited[i] = true;
recur(depth + 1);
visited[i] = false;
}
}
}
private static void printResult() {
for (int j : answer) {
System.out.print(j + " ");
}
System.out.println();
}
}
백준 9742
- 답을 구하면, 반복문을 멈추는 방법을 고민할 것.
package b9742;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main2 {
static char[] arr; // 원소 저장 배열
static char[] res; // 답 저장 배열
public static boolean[] visited; // 사용 여부 저장
static String N;
static int M;
static int cnt;
static String ans;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
String input;
while((input = br.readLine()) != null) {
st = new StringTokenizer(input);
N = st.nextToken();
M = Integer.parseInt(st.nextToken());
cnt = 0;
ans = "";
arr = new char[N.length()];
res = new char[N.length()];
visited = new boolean[arr.length];
for(int i = 0;i < N.length();i++) {
arr[i] = N.charAt(i);
}
permutation(0);
if(cnt < M)
System.out.println(N + " " + M + " = " + "No permutation");
}
}
private static void permutation(int depth) {
if(depth == arr.length) {
cnt++;
if(cnt == M) {
for (char i : res) {
ans += i;
}
print();
}
return;
}
for(int i = 0;i < arr.length && cnt!=M ;i++) { //cnt!=M을 추가한다면, 끝까지 검사하지 않고, 답을 찾으면 더 이상 증가하지 않고 멈추게 함.
if(!visited[i]) {
visited[i] = true;
res[depth] = arr[i];
permutation(depth+1);
visited[i] = false;
}
}
}
private static void print() {
System.out.println(N + " " + M + " = " + ans);
}
}
백준 1722 순열 숫자 구하기
//문제 설명
{ 1 2 3 4 } 원소
1. 1234
2. 1243
3. 1324
4. 1342
5. 1423
6. 1432
K=8, 8 <= 6*1 -> 1번째 숫자
8 <= 6*2 -> 2번째 숫자
K - (6*(자리수-1)) = 나머지
8 - (6*(2-1)) = 2
2 <= 2*1 ->OK : 남은숫자중에 1번째가 2번째 숫자
2 - (2*(1-1)) = 2 나머지 -> 남은 숫자중 2번째가 3번째 숫자
7. 2134
8. 2143
....
--------------------------------------------
K = 11
11 <= 6*1
11 <= 6*2 -> 2번째숫자(2)
11 - (6*(2-1)) = 5 나머지
K = 5
5 <= 2*1
5 <= 2*2
5 <= 2*3 -> 3번째숫자(4)
5 - (2*(3-1)) = 1 나머지 1번째숫자(1)
남은숫자(3)
2413