[코테]02-브루트 포스

브루트 포스

모든 경우의 수를 다 해보는 것이다.
brute force attack을 생각하면.. 쉬움
0000부터 9999까지 다 입력해보는 것 -> 경우의 수가 10,000가지.
O(방법의 개수*시도하는 복잡도)

• 브루트 포스 문제를 풀기 위해서는 3가지 단계를 생각해볼 수 있다.

1. 문제의 가능한 경우의 수를 계산해본다.

• 직접 계산을 통해서 구한다. 대부분 손으로 계산.

2. 가능한 모든 방법을 다 만들어본다.

• 하나도 빠짐없이 다 만들어야한다.
• for문 등 반복문을 이용, 재귀호출, 비트마스크 사용 등.

3. 각각의 방법을 이용해 답을 구해본다.

1.일곱 난쟁이

• 아홉명의 난쟁이 중 일곱명의 난쟁이를 찾는 문제
• 일곱 난쟁이 키의 합은 100이다.

1) 9명 중에 7명을 찾기
2) 9명 중에 2명을 찾기

• 방법의 개수 N^2
• 난쟁이 키의 합을 고르는 시간 복잡도는 O(N)
• 이 문제는 O(N^3)으로 해결.
  -> O(N^2)으로도 해결 가능함.

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args)  {
		Scanner sc = new Scanner(System.in);
		int arr[] = new int[9];
		int sum = 0;
		boolean chk = false;
		
		for(int i=0; i<arr.length;i++) {
			arr[i]=sc.nextInt();
			sum += arr[i];
		}
		for(int i=0;i<arr.length;i++) {
			if(chk) 
				break;
			for(int j=0;j<arr.length;j++) {
				if(i==j) continue;
				if((sum-arr[i]-arr[j])==100) {
					arr[i]=0;
					arr[j]=0;
					chk=true;
					break;
				}
					
			}
		}
		Arrays.sort(arr);
		for(int i=0;i<arr.length;i++) {
			if(arr[i]!=0) {
				System.out.println(arr[i]);
			}
		}
		
	}
	
}

=> 이건 예전에 풀었었던 코드가 있어서 그냥 올림.

2.사탕 게임

• N X N 크기의 테이블에 사탕이 있음.
• 인접한 두 칸을 고르고, 사탕을 교환한다.
• 그 다음, 같은 색으로 이루어져 있는 가장 긴 연속 부분 행 또는 열을 고르는 문제

처음에 문제 이해가 잘 안됐다.. 돌대가리인가ㅠ

import java.util.Scanner;

public class Main {
	static char [][] board;
	static int N;
	static int max=0;
    
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	N = sc.nextInt();
    	board = new char[N][N];
    	
    	//사탕 입력받기
    	for(int i=0;i<N;i++) {
    		String str = sc.next();
    		for(int j=0;j<board[i].length;j++) {
    			board[i][j] = str.charAt(j);
    		}
    	}
    	
    	//가로 인접 두 사탕 교환하고 최대 사탕 개수 찾기.
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<N-1;j++) {
    			char tmp = board[i][j];
    			board[i][j]=board[i][j+1];
    			board[i][j+1] = tmp;
    			
    			// 오른쪽이랑 아래쪽 체크하기
    			chk();
    			
    			//다시 복구
    			tmp=board[i][j];
    			board[i][j]=board[i][j+1];
    			board[i][j+1]=tmp;
    		}
    	}
    	
    	//세로 인접 두 사탕 교환하고 최대 사탕 개수 찾기.
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<N-1;j++) {
    			char tmp = board[j][i];
    			board[j][i]=board[j+1][i];
    			board[j+1][i] = tmp;
    			
    			// 오른쪽이랑 아래쪽 체크하기
    			chk();
    			
    			//다시 복구
    			tmp = board[j][i];
    			board[j][i]=board[j+1][i];
    			board[j+1][i] = tmp;
    		}
    	}
    	
    	System.out.println(max);
    }
    
    static void swap(char a,char b) {
    	char tmp = a;
    	a=b;
    	b=tmp;
    }
    static void chk() {
    	// 가로 체크
    	for(int i=0;i<N;i++) {
    		int cnt=1;
    		for(int j=0;j<N-1;j++) {
    			if(board[i][j]==board[i][j+1])
    				cnt++;
    			else
    				cnt=1;
    			if(max<cnt)
    				max=cnt;
    		}
    	}
    	// 세로 체크
    	for(int i=0;i<N;i++) {
    		int cnt=1;
    		for(int j=0;j<N-1;j++) {
    			if(board[j][i]==board[j+1][i])
    				cnt++;
    			else
    				cnt=1;
    			if(max<cnt)
    				max=cnt;
    		}
    	}
    		
    	}
    }
    
 

3. 블랙잭(백준 2798번)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        
        int num = Integer.parseInt(st.nextToken());
        int num2 = Integer.parseInt(st.nextToken());
        
        int arr[] = new int[num];
        int rs = 0;
        
        st = new StringTokenizer(br.readLine()," ");
        for(int i=0;i<num;i++) {
        	arr[i]=Integer.parseInt(st.nextToken());
        }
    	
    	for(int i=0;i<num-2;i++) {
    		for(int j=i+1;j<num-1;j++) {
    			for(int k=j+1;k<num;k++) {
    				int sum = arr[i] + arr[j] + arr[k];
    				
    				if(rs<sum && sum<=num2) {
    					rs = sum;
    				}
    			}
    		}
    	}
        System.out.println(rs);
    }
    
}

=> for문을 3번 돌리는 방법밖에 없는 것 같아서 이렇게 작성했다. 카드는 총 3가지이기 때문에 i는 0부터 n-2까지, j는 i+1부터 n-1, k는 i+2부터 n까지 3중 for문을 사용한다. if문을 사용해서 num2의 값보다 크면 continue 시키려고 했는데 굳이 필요없을 것 같아서 넣지는 않았다.