1. 브루트 포스

• 브루트 포스(Brute Force) : 무식한 힘
• 즉, 발생할 수 있는 모든 경우를 무식하게 탐색한다는 뜻이다
• 장점
  • 알고리즘을 설계하고 구현하기 어렵다
  • 복잡한 알고리즘 없이 빠르게 구현할 수 있다
• 단점
  • 알고리즘의 실행 시간이 매우 오래 걸린다
  • 메모리 효율면에서 매우 비효율적이다
• 종류
  • 선형 구조 : 순차 탐색
  • 비선형 구조 : 백트레킹, DFS, BFS

2. 예제

2-1. 2798 블랙잭

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

2-1-1. 문제

• 카드 N장과 숫자 M이 주어질 때 카드 N장 중 3장의 합이 숫자 M을 넘지 않으면서 최대한 가까운 카드 3장의 합을 구한다

2-1-2. 예제

2-1-3. 풀이

• 5 6 7 8 9 를 리스트로 받아서 더할 수 있는 모든 경우를 더해보고
• 조건에 부합하면 출력한다

2-1-4. 코드

1) 파이썬

n, m = map(int, input().split())
card= list(map(int, input().split()))

s= 0
for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            sum= card[i] + card[j] + card[k]
            if sum > s and sum <= m:
                s= sum
print(s)

2) 자바

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 값 입력
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        int[] card = new int[n];

        for (int i = 0; i < n; i++){
            card[i] = sc.nextInt();
        }

        // 브루트 포스
        int sum = 0;
        int s = 0;

        for (int i = 0; i < n; i++){
            for (int j = i+1; j < n; j++){
                for (int k = j+1; k < n; k++){
                    sum = card[i] + card[j] + card[k];
                    if ((sum > s) && (sum <= m)){
                        s= sum;
                    }

                }
            }
        }
        System.out.println(s);
    }
}

2-2. 2231 분해합

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

2-2-1. 문제

• 245의 분해합은 256(=245 + 2 + 4 + 5)가 된다
• 따라서 245는 256의 생성자가 된다
• 어떤 자연수의 경우에는 생성자가 없을 수도 있다
• 반대로 생성자가 여러 개인 자연수도 있을 수 있으므로 가장 작은 생성자를 구해내는 프로그램을 작성하시오

2-2-2. 예제

2-2-3. 풀이

• 0부터 n까지를 반복하면 n에 각 자리수를 더해보고
• 조건에 부합하면 출력한다
• 0부터 하는 이유는 가장 작은 값을 출력하기 위해서이다

2-3-3. 코드

1) 파이썬

n= int(input()) // 값을 받는다
result= 0 // 정답이될 변수

for i in range(n):
    ord_i= i // 변형되기 전의 값을 미리 저장해 둔다
    for j in str(i):
        i += int(j) // n 문자열을 하나씩 더한다
    
    // 만약 더해진 값과 n의 값이 같다면
    if i == n:
        result= ord_i
        break
print(result)

2) 자바

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int result = 0;

        for (int i = 0; i < n; i++) {
            int ord_i = i;
            int temp_i = i;

            while (temp_i > 0) {
                // 각 자리수별로 더한다
                ord_i += temp_i % 10;
                temp_i /= 10;
            }

            if (ord_i == n) {
                result = i;
                break;
            }
        }

        System.out.println(result);
    }
}

2-3. 19532 수학은 비대면 강의입니다

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

2-3-1. 문제

• 연립방정식 x,y의 값을 구하라
• ax + by = c
• ex + ey = f

2-3-2. 예제

2-3-3. 풀이

x와 y의 범위가 -999 ~ 999 까지니까 이 사이로 반복문을 사용한다

2-3-3. 코드

1) 파이썬

from sys import stdin
input= stdin.readline

a,b,c,d,e,f = map(int, input().split())

for x in range(-999, 1000):
    for y in range(-999, 1000):
        if (a*x + b*y == c) and (d*x + e*y == f):
            print(x,y)
            break

2) 자바

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        int a= sc.nextInt();
        int b= sc.nextInt();
        int c= sc.nextInt();
        int d= sc.nextInt();
        int e= sc.nextInt();
        int f= sc.nextInt();

        for (int x= -999; x<1000; x++){
            for (int y= -999; y<1000; y++){
                if (((a*x + b*y)==c) && ((d*x + e*y)==f)){
                    System.out.print(x);
                    System.out.print(' ');
                    System.out.print(y);
                    break;
                }
            }
        }
    }
}

2-4. 1018 체스판 다시 칠하기

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

2-4-1. 문제

• 8x8 체스판을 만들거다
• 주어진 체스판을 잘라낸 후 몇 개의 정사각형을 다시 칠해야 한다면
• 칠해야 하는 정사각형의 최소 개수를 구하라

2-4-2. 예제

2-4-3. 풀이

주어진 코드에서 8x8 형태로 나올 수 있는 모든 경우를 value에 넣어두고 살펴본다 (미리 저장한 t1하고 t2를 비교한다)

• value, t1, t2 비교한것 중 적은 값을 카운트해서 result에 add한다

2-4-3. 코드

1) 파이썬

from sys import stdin
input= stdin.readline

n,m= map(int, input().split())
nm= [input() for _ in range(n)]

t1= 'WBWBWBWBBWBWBWBWWBWBWBWBBWBWBWBWWBWBWBWBBWBWBWBWWBWBWBWBBWBWBWBW'
t2= 'BWBWBWBWWBWBWBWBBWBWBWBWWBWBWBWBBWBWBWBWWBWBWBWBBWBWBWBWWBWBWBWB'

result= []
for i in range(n-7):
    for k in range(m-7):
        value= ''
        for r in range(i, i+8):
            value += nm[r][k:k+8]
            
        a= sum(s1 != s2 for s1, s2 in zip(t1, value))
        b= sum(s1 != s2 for s1, s2 in zip(t2, value))

        result.append(min(a,b))
    
print(min(result))

2) 자바

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);

        int n= sc.nextInt();
        int m= sc.nextInt();
        ArrayList<String> nm= new ArrayList<>();
        for (int i= 0; i<n; i++){
            nm.add(sc.next());
        }

        String t1= "WBWBWBWBBWBWBWBWWBWBWBWBBWBWBWBWWBWBWBWBBWBWBWBWWBWBWBWBBWBWBWBW";
        String t2= "BWBWBWBWWBWBWBWBBWBWBWBWWBWBWBWBBWBWBWBWWBWBWBWBBWBWBWBWWBWBWBWB";

        ArrayList<Integer> result= new ArrayList<>();

        for (int i=0; i<n-7; i++){
            for (int j=0; j<m-7; j++){
                String value= "";
                for (int r=i; r<i+8; r++){
                    String str= nm.get(r);
                    value += str.substring(j, j+8);
                }
                int a= 0;
                int b= 0;
                for (int k=0; k<t1.length(); k++){
                    if (t1.charAt(k) != value.charAt(k)){
                        a++;
                    }
                    if (t2.charAt(k) != value.charAt(k)){
                        b++;
                    }
                }
                result.add(Math.min(a,b));
            }
        }
        System.out.println(Collections.min(result));
    }
}

2-5. 1436 영화감독 숌

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

2-5-1. 문제

• 영화 제목을 만든다
• 1번째 영화 이름은 666, 2번째는 1666, 3번째는 2666, 4번째는 3666 이 된다
• 영화는 항상 차례대로 만든다
• 영화 제목에 666은 꼭 있어야 한다

2-5-2. 예제

2-5-3. 풀이

• 666에서 1을 계속 더하다가 값에 '666'이 있으면 입력받은 값에서 1을 뺀다
• 다시 1을 계속 더하다가 다시 값에 '666'이 있으면 입력받은 값에서 1을 뺀다
• 계쏙 반복하다가 입력받은 값이 0이 되면 멈추고 계속 더했던 값을 출력한다

2-5-3. 코드

1) 파이썬

from sys import stdin
input= stdin.readline

n= int(input())
name= 666

# 1을 계속 더하다가 666이 있는지 확인한다
while n > 0:
    if '666' in str(name): 
        n -= 1 
        # 1. 처음 name이 666 이니까 n은 1이 된다
        # 3. name이 1666이 됐으니까 n에서다시 1을 뺀다
     
    name += 1 
    # 2. name에 666이 만들어지기 전까지 계속 더한다
    # : 667, 668, 669, 670, 671, 672 ... 1666
    # 4. n은 0이 됐으므로 while문은 멈춘다

print(name-1) 
# 5. 반복문 나올 때 name에 +1 됐으므로 -1을 다시 해준다

2) 자바

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);

        int n= sc.nextInt();
        int name= 666;

        while (n > 0){
            if (String.valueOf(name).contains("666")){
                n --;
            }

            name += 1;
        }

        System.out.println(name-1);
    }
}

2-6. 1436 영화감독 숌

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

2-6-1. 문제

• 설탕을 배달한다
• 내가 가지고 있는 설탕은 3kg, 5kg 포대이다
• 손님이 주문한 설탕을 가져갈 때 최대한 포대를 적게 가져가고 싶다
• 18kg 설탕이라면 3kg를 6개 가져갈 수 있지만 5kg 3개, 3kg 1개 해서 4개만 가져갈 수 있다
• 딱 맞아 떨어지지 않으면 -1을 출력한다(4kg, 7kg 처럼)

2-6-2. 예제

2-6-3. 풀이

• 적개 가져가려면 아래 순서를 지켜야 한다
• n은 손님이 주문한 설탕 kg이다

1. n을 5로 나누었을 때 나누어 떨어질 때 (ex.15kg은 5로 나누어 떨어진다)
2. n을 5와 3으로 채웠는데 남는 값이 없을 때 (ex.11kg은 5 1개, 3 2개 로 채워진다)
3. n을 3으로 나누었을 때 나누어 떨어질 때 (ex. 6kg은 3으로 나누어 떨어진다)
4. n을 5와 3으로는 채울수 없을 때 (ex. 4kg은 채울 수 없다)

2-6-3. 코드

1) 파이썬

n= int(input())
cnt= 0
result= -1

# n이 5로만 채워지는 경우
if n % 5 == 0:
    print(n//5)
else:
    # n이 5와 3으로 채워지는 경우
    # n이 3으로만 채워지는 경우
    # 정확하게 채워지지 않는 경우
    for _ in range(n//3):
        cnt += 1
        n -= 3 # 3을 빼보면서
        # n이 0이 돼도 나머지는 0이 되니까 n이 3으로만 채워지는 경우도 성립한다
        if n % 5 == 0: # 5로 나누어 떨어지는 확인
            result= cnt + n//5 # 나누어 떨어지면 5로 나눈 몫만큼 더한다
            break
        # 값을 다 뺐는데도 if문에 들어가지 못하면 -1이 된다

    print(result)

2) 자바

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);

        int n= sc.nextInt();
        int cnt= 0;
        int result= -1;
        int num= n/3;

        if (n%5 == 0){
            System.out.println(n/5);
        }
        else{
            for (int i= 0; i<num; i++){
                cnt += 1;
                n -= 3;
                if (n%5 == 0){
                    result= cnt + (n/5);
                    break;
                }
            }
            System.out.println(result);
        }
    }
}

---

자바 파이썬 그냥 둘이 화해 하자
끝 🥳🥳