Baekjoon - Brute-Force

Brute-Force Algorithm

• 문제를 해결하기 위하여, 모든 경우를 탐색하고 답을 도출하는 Algorithm.

=> 결과를 찾는다는 것에 중점을 둔다.

 

이것과 비슷한 것은 완전 탐색 알고리즘이 있다. (같지만 다른 점이 존재)

 

완전 탐색 알고리즘
모든 경우의 수를 전부 탐색하는 방식의 알고리즘으로, 결과보다는 탐색에 중점을 둔다.

 

이 Algorithm의 사용 조건은 다음과 같다.

• 문제에서 달성하고자 하는 Solution이 잘 정의되어야 한다.
• 문제를 해결할 수 있는 풀이의 수가 제한되어 있어야 한다.

Algorithm Example

1. 반복문을 사용하는 경우

-> 대부분 반복문과 조건문을 활용해서 모든 경우를 탐색한다.

2. 재귀를 사용하는 경우

-> 피보나치 수열 (DP (Dynamic Programming) 이 중복된 계산을 피할 수 있으므로 더욱 효율적인 계산), factorial

 

2798. 블랙잭

 

이 문제는 결국 N장의 카드 중에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구하라는 문제이다.

(3 <= N <= 100), (10 <= M <= 300,000)

Solution

나는 이 문제를 순열을 이용해서 풀어보았다. itertools라는 module에 있는 combinations function을 사용하여 문제를 풀었다.

combinations(iterable, r) : iterable에서 원소 개수가 r개인 조합을 뽑는 함수이다. 

N, M과 3장을 넣는 list를 정의하고 가장 큰 변수를 담는 변수, 그리고 nC3의 합을 담는 temp 변수를 사용하여 진행하였다.

from itertools import combinations

card_num, target_num = map(int, input().split())
card_list = list(map(int, input().split()))

if len(card_list) != card_num:
    print("Error 발생")
else:
    biggest_num = 0
    
    for cards in combinations(card_list, 3):
        temp_num = sum(cards)
        if biggest_num < temp_num <= target_num:
            biggest_num = temp_num
            
    print(biggest_num)

 

2231. 분해합

 

Solution

이 문제를 보고 처음에는 각각의 자릿수를 배정하려고 시도하였지만, 너무 많아질 것 같아서 바로 포기하였다.

그래서, 분해합을 주고 가장 작은 생성자를 구해내려고 목표를 다시 잡았다. 

n = int(input()) # 입력값 받기

result = 0
for i in range(1, n+1):
    nums = list(map(int, str(i)))
    result = sum(nums) + i
    if result == n:
        print(i)
        break
    if i == n:
        print(0)

 

 

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

 

Solution

나는 처음에 이 문제를 Brute-force 방식으로 접근하였다. i, j 를 -999~ 999 까지 반복시켜서 해를 찾는 방식으로 진행하였다.

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

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

 

그런데, 다른 방식으로 접근할 수는 없을까를 생각해보다가, 행렬 방식과 단순한 연립 방정식 방식을 생각해보았다.

 

위의 방식으로 접근하였는데, 물론 출력도 동일하게 나왔다. 하지만, 연립방정식 문제는 Python 에서는 제대로 출력이 나왔는데,

Algorithm 스터디를 같이 하는 친구에게서는 이 방식으로는 제대로 된 출력이 나오지 않는다는 의견이 나왔다. 그 이유는

그 친구는 Java 언어로 Algorithm 문제를 푸는데, 같은 알고리즘으로 동작하였지만 부동 소수점 관련 문제로 인해 문제가 발생하였다는 것이다. 듣고 보니 합리적이었고 예외사항이 발생할 수 있을것이라 생각하였다. 그렇지만 Python에서는 왜 부동소수점 오차가 발생하지 않았는지에 대해서는 아직까지도 의문이다...

 

1018. 체스판 다시 칠하기

 

 

Soluiton

N, M = map(int, input().split()) # N x M 정사각형 생성

board = [] # 보드판을 저장하는 리스트
result = [] # 결과값을 저장하는 리스트

for _ in range(N):
    board.append(input())

for i in range(N - 7): # 보드판을 넘어서지 않기 위해 시작점을 N-8까지 제한 (8x8 체스판 생성)
    for j in range(M - 7):
        b_index = 0 # black으로 칠할 변수
        w_index = 0 # white로 칠할 변수

        for a in range(i, i + 8): # i부터 i + 7까지 
            for b in range(j, j + 8): # j부터 j + 7까지
                if (a + b) % 2 == 0: # 행과 열의 index 합이 짝수인 경우
                    if board[a][b] != 'B': # 그 인덱스가 검은색이 아닌 경우
                        b_index += 1 # 검은색으로 색칠
                    if board[a][b] != 'W': # 인덱스가 하얀색이 아닌 경우 
                        w_index += 1 # 하얀색으로 색칠
                        
                else : # 행과 열의 index 합이 홀수인 경우
                    if board[a][b] != 'B': # 인덱스가 검은색이 아닌 경우
                        w_index += 1 # 하얀색으로 색칠
                    
                    if board[a][b] != 'W': # 인덱스가 하얀색이 아닌 경우
                        b_index += 1 # 검은색으로 색칠
                    
        result.append(b_index)
        result.append(w_index)

print(min(result))

 

1436. 영화감독 숌

 

Solution

종말의 수란 6이 적어도 3개 이상 연속으로 들어가는 수로, 제일 작은 종말의 수는 "666"이다. 따라서, N번째 영화 제목에 들어가는 수를 출력하는 프로그램을 작성하라는 의미이다.

내가 생각했던 건 아래의 두 가지 과정을 진행하였다.

1. "666"이라는 수를 포함하는 것을 찾는다.

2. count 변수로 N번째를 찾는다.

 

n = int(input())

cnt = 0 # N번째와 666 비교하려는 count 변수
num = 666
while True:
    if "666" in str(num): # num 변수 안에 666 이라는 종말의 수가 포함되어 있는 경우
        cnt += 1
       
    if cnt == n:
        print(num)
        break;
        
    num += 1

 

2839. 설탕 배달

 

Solution

봉지는 3, 5kg 봉지가 존재하는데 N kg 설탕을 배달할 때 봉지를 최소 몇 개로 담을 수 있는가를 묻는 문제로, 처음에는 5kg를 기준으로 진행하려고 했지만 그렇게 되면 3kg를 만드는데 문제가 생겼다. 따라서 5의 배수일 때만 생각한 후 나머지는 3kg로 넣어서 진행하였다.

n = int(input())

count = 0 # 봉지 개수를 세는 변수

while n >= 0: # 0kg가 될 때까지 반복
    if n % 5 == 0: # 5의 배수인 경우
        count += int(n // 5) # n을 5로 나눈 몫을 count 변수에 저장
        print(count)
        break
    
    count += 1
    n -= 3 # 5의 배수가 될 때까지 3kg 봉지에 저장
    
else:
    print(-1)