[알고리즘] 브루트포스 문제 풀이(백준 7568번, 1018번)

1. 덩치(백준 7568번)

 

7568번: 덩치 (acmicpc.net)

7568번: 덩치

 

▷ 풀이 코드

1. 이중 for문 사용

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Dungchi {
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int[][] arr = new int[n][2];
		
		for(int i=0; i<n; i++) {
			arr[i][0] = sc.nextInt();
			arr[i][1] = sc.nextInt();
		}
		
		for(int i=0; i<n; i++) {
			int rank = 1;
			
			for(int j=0; j<n; j++) {
				if(i == j) continue;
				if(arr[i][0] < arr[j][0] && arr[i][1] < arr[j][1]) {
					rank++;
				}
			}
			
			System.out.print(rank + " ");
		}
	
	}
}

2. 내부 class 사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Dungchi2 {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		List<Info> inputList = new ArrayList<>();

		for(int i=0; i<n; i++) {
			String inputArr[] = br.readLine().split(" ");
			int x = Integer.parseInt(inputArr[0]);
			int y = Integer.parseInt(inputArr[1]);
			Info info = new Info(x, y);
			inputList.add(info);
		}
		
        // Info 객체들의 x와 y 값을 비교하고 출력
		for(Info info : inputList) {
			int rank = 1;
			
			for(Info info2 : inputList) {
				if(info == info2) continue;
				if(info.getX() < info2.getX() && info.getY() < info2.getY()) {
					rank++;
				}
			}
            System.out.print(rank + " ");
        }
		

	}
	
	static class Info {
		int x; // 몸무게
		int y; // 키
		
		Info(int x, int y){
			this.x = x;
			this.y = y;
		}
		
		int getX() {
			return x;
		}
		
		void setX(int x) {
			this.x = x;
		}
		
		int getY() {
			return y;
		}
		
		void setY(int y) {
			this.y = y;
		}
	}
}

 

 

2. 체스판 다시 칠하기(백준 1018번)

 

1018번: 체스판 다시 칠하기 (acmicpc.net)

1018번: 체스판 다시 칠하기

 

▷ 풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
	public static boolean[][] arr;
	public static int min = 64;
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
	
		String inputArr[] = br.readLine().split(" ");
		
		int n = Integer.parseInt(inputArr[0]);
		int m = Integer.parseInt(inputArr[1]);
		
		arr = new boolean[n][m];
		
		for(int i=0; i<n; i++) {			
			String input = br.readLine();
			
			for (int j = 0; j < m; j++) {
				if (input.charAt(j) == 'W') {
					arr[i][j] = true;		// W일 때는 true 
				} else {
					arr[i][j] = false;		// B일 때는 false
				}
			}
		}
		
		for (int i = 0; i < n-7; i++) {
			for (int j = 0; j < m-7; j++) {
				min = find(i, j);
			}
		}
		System.out.println(min);
	}
	

	static int find(int x, int y) {
		int cnt = 0;
 
		boolean tf = arr[x][y];	// 첫 번째 칸의 색 
 
		for (int i = x; i < x+8; i++) {
			for (int j = y; j < y+8; j++) {
 
				if (arr[i][j] != tf) {	
					cnt++;
				}
				tf = !tf;
			}
			tf = !tf;
		}
		
		cnt = Math.min(cnt, 64 - cnt);
		
		return Math.min(min, cnt);
	}
}

 

 

 

이번에는 알고리즘 스터디에서 공부했던 브루트포스 탐색을 통해 백준 문제 풀이를 해보았습니다!!

 

브루트포스는 모든 경우의 수를 반복하는 것인데요

 

문제를 풀 때 우선 모든 경우의 수를 파악하는 것이 중요하겠어요!

 

더 다양한 문제들을 풀어보면서 문제 풀이 방법들에 대해서 익혀볼게요~

 

많은 분들의 피드백은 언제나 환영합니다!  많은 댓글 부탁드려요~~