브루트 포스
가장 간단한 알고리즘인, 모든 경우의 수를 검사하는 브루트 포스 알고리즘을 배워 봅시다.
완전탐색 알고리즘: 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식
2798번 - 블랙잭
세 장의 카드를 고르는 모든 경우를 고려하는 문제
N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.
N장의 카드 중에서 3장의 카드- 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게
첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.
합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력
import java.util.Scanner;
public class A_2798 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int [] a = new int[N];
for(int i=0;i<N;i++)
a[i]= sc.nextInt();
sc.close();
int min=M;
int sum;
for(int i=0;i<=N-2;i++){
for(int k=i+1;k<=N-1;k++){
for(int j=k+1;j<N;j++){
sum = a[i]+a[j]+a[k];
if(sum<=M)
if(min>(M-sum)) min= M-sum;
}
}
}
M -=min;
System.out.println(M);
}
}2231번 - 분해합
모든 경우를 시도하여 N의 생성자를 구하는 문제
시간초과였다가,
거꾸로 해보고 난 천재임 이랬는데 사실 아님이슈
import java.util.Scanner;
public class A_2231 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
sc.close();
if(N>10){//두자리 이상
int sum,a;
int cnt=0;
for(int M=1;M<N;M++){
sum = N-M;
a= sum;
//System.out.println( "sum:" + sum);
while (true) {
if(a/10>9){
sum += a%10;
a = a/10;
//System.out.println("a/10:"+a/10 +" sum:"+sum);
}
else{
sum += a/10;
sum += a%10;
//System.out.println("a/10:"+a/10+ " a%10:"+a%10+" sum:"+sum);
if(sum==N){
System.out.println(N-M);
cnt++;
break;
}
else break;
}
if(sum>N) break;
}
if(cnt>0) break;
}
if (cnt==0) System.out.println(0);
} else System.out.println(0);
}
}굳이 flag 변수같은거 안넣어도 됐던 것ㅜㅜ.. 어이없음
쉽게하려고 10부터 넣기 이런거 하다가 계속 실수나서 답답했당
//분해합 - 브루트포스 알고리즘
//첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.
//M의 분해합 N <-> M= N의 생성자 .. 생성자 없을수도 여러개일수도
// N의 작은 생성자(M)을 구하시오.
import java.util.Scanner;
public class A_2231 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
sc.close();
int sum,a;
int res=0;
for(int i=0;i<=N;i++){
sum=0;
a=i;
while(a>0){
sum += a%10;
a= a/10;
}
if( sum+i ==N ){
res=i;
break;
}
}
System.out.println(res);
}
}
19532번 - 수학은 비대면 강의입니다.
모든 x와 모든 y를 시도하여 해를 구하는 문제
런타임 에러용..?ㅜㅜㅜㅜ
//수학은 비대면강의입니다- 블루트포스
//연립방적식 풀이, x와 y출력
//ax+by=c
//dx+ey+f
// 모든 변수의 범위는 -999<= --- <= 999
import java.util.Scanner;
public class A_19532 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int [] a = new int[6];
for(int i=0;i<6;i++){
a[i] = sc.nextInt();
}//0,3=x / 1,4=y
sc.close();
int x=-999;
int y=0;
while (x<1000) {
if( (a[0]*(-x) + a[2])%a[1]==0 ){
y= (a[0]*(-x) + a[2])/a[1];
if( a[3]*x + a[4]*y ==a[5]){
System.out.println(x+" "+y);
break;
}
}
x++;
}
}
}
for문으로 고쳐도 런타임 에러..
int y;
for(int x=-999;x<1000;x++){
if( (a[0]*(-x) + a[2])%a[1]==0 ){
y= (a[0]*(-x) + a[2])/a[1];
if( a[3]*x + a[4]*y ==a[5]){
System.out.println(x+" "+y);
break;
}
}
}설명대로.. 블루트포스대로.. 풀 자......
//수학은 비대면강의입니다- 블루트포스
//연립방적식 풀이, x와 y출력
//ax+by=c
//dx+ey+f
// 모든 변수의 범위는 -999<= --- <= 999
import java.util.Scanner;
public class A_19532 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int [] a = new int[6];
for(int i=0;i<6;i++){
a[i] = sc.nextInt();
}
sc.close();
int x,y;
for(int i=-999;i<1000;i++){
for(int j=-999;j<1000;j++){
if( a[0]*i+a[1]*j==a[2] && a[3]*i+a[4]*j==a[5] ){
x=i; y=j;
System.out.println(x+" "+y);
break;
}
}
}
}
}
1018번 - 체스판 다시 칠하기
체스판을 만드는 모든 경우를 시도하여 최적의 방법을 찾는 문제
https://youtu.be/QQUb4b6iWSw?si=bnr1qXoreYlPN4HZ
유튜브 개발자로취직하기님의 체스판 다시 칠하기 백준 1018- 자바 java 문제 풀이 를 보고 따라하고 이해하며 풀이했다.
완전탐색 Solution
//체스판 다시 칠하기 - 블루트 포스 ( 완전탐색으로 해결)
//8<= N과 M <= 50
//8*8로 잘라서 사용할 것
//다시 칠해야 할 최소값
//1.체스판 자르기 2.체스판의 최소비용 3.전체 최적의 값과 비교해 갱신
//BWBW - black체스판
//WBWB - white체스판
import java.util.Scanner;
public class A_1018 {
public static int getSolution(int startRow, int startCol, String[] che) {
//정답지 만들기
String[] orgBoard = { "WBWBWBWB", "BWBWBWBW" };
int whiteSol = 0;
for (int i = 0; i < 8; i++) {
int row = startRow + i;
for (int j = 0; j < 8; j++) {
int col = startCol + j;
//체스판과 정답지를 비교해야 함
//현재 체스판의 row의 col 값을 가져옴 // %2하는 이유: 정답지 원소가 2개
// (col) 과 J를 비교하는 이유: WBWB 8칸만 만들었기 때문에 col값 까지 가면 넘칠 수 있음
if (che[row].charAt(col) != orgBoard[row % 2].charAt(j)) whiteSol++;
//정답지(white체스판)와 다르다면 칠해야 함 (수정++)
}
}
//White sol vs Black sol의 값에서 더 작은 값을 return
return Math.min(whiteSol, 64 - whiteSol);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); //row
int M = sc.nextInt(); //col
sc.nextLine();
String [] che = new String[N]; //체스판
for (int i = 0; i < N; i++) //row
che[i] = sc.nextLine();
sc.close();
// 체스판 자르기
int sol = Integer.MAX_VALUE;
//8X8 체스판을 위해 -8만큼 돌림
for (int i = 0; i <= N - 8; i++) { //row
for (int j = 0; j <= M - 8; j++) { //col
// 현 체스판의 최소 비용 구하기
int curSol = getSolution(i, j, che);
// 전체 최적의 값과 비교해 갱신
if (sol > curSol) sol = curSol;
}
}
System.out.println(sol);
}
}
1436번 - 영화감독 숌
N번째 종말의 수가 나올 때까지 차례대로 시도하는 문제
한자리씩 비교!
//영화감독 숌 - 블루트 포스
//N 번째로 작은 종말의 수 << 6이 적어도 3개이상 연속으로 들어감
import java.util.Scanner;
public class A_1436 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
sc.close();
int num=666, n1=0;
String num1;
int dee = 3, cnt;
char c1;
while (true) {
cnt=0;
num1= Integer.toString(num);
for(int i=0;i<dee;i++){
c1 = num1.charAt(i);
if(c1=='6') cnt++;
else cnt=0;
if (cnt>2){
n1++;
break;
}
}
if(n1==N){
System.out.println(num);
break;
}
num++;
if(num > (int)Math.pow(10, dee)) dee++;
}
}
}
2839번 - 설탕배달
한때는 이 문제가 "기본 수학 1" 단계에 있었지만, 사실 브루트 포스로 푸는 게 더 쉽습니다.
//설탕배달 - 브루트 포스
//N킬로그램을 배달해야함 / 봉지는 3킬로그램 봉지와 5킬로그램
//3 ≤ N ≤ 5000
// 몇 봉지를 배달해야 하는지?
//정확하게 N킬로그램을 만들 수 없다면 -1을 출력
import java.util.Scanner;
public class A_2839 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
sc.close();
int sum=N,min=N;
//나눌 수 있는지 확인
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
sum = i*5 + j*3;
if(sum==N){
if(min>i+j) min = i+j;
}
}
}
if(min==N) System.out.println(-1);
else System.out.println(min);
}
}
.png)
발바닥부터 시작하는 코딩공부