[백준]브루트 포스

브루트 포스, Brute Force:

 검색 대상이 되는 원본 문자열의 처음부터 끝까지 차례대로 순회하며

 문자들을 일일이 비교하는 알고리즘

 

시간 복잡도 :

O(mn) , m: 찾으려는 문자열 길이, n: 총 문자열 길이

장점 및 단점:

구현하기 쉬우나 시간적으로 매우 비효율적임

 

#2798. 블랙잭 https://www.acmicpc.net/problem/2798

문제 설명:

세 장의 카드를 고르는 모든 경우를 고려하는 문제

풀이:

브루트 포스에 따라 세 개의 제어인자를 생성하여 set을 통해 합의 집합을 생성한 후 조건 내 가장 큰 수 pick

N, M = map(int, input().split())
numbers = list(map(int, input().split()))
sum_set = set()

for i in range(N):
 for j in range(i + 1, N):
  for k in range(j + 1, N):
   sum = numbers[i] + numbers[j] + numbers[k]
   if sum not in sum_set:
    sum_set.add(sum)

# 합으로 이뤄진 set완성
sum_list = [x for x in sum_set if x <= M]
print(max(sum_list))

 

+ 순열과 조합을 내포하는 itertools 모듈의 combination 함수(https://amad-note.tistory.com/entry/itertools-%EB%AA%A8%EB%93%88-combination-%ED%95%A8%EC%88%98-%EC%82%AC%EC%9A%A9%ED%95%98%EA%B8%B0)

from itertools import combinations

N, M = map(int, input().split())
numbers = list(map(int, input().split()))

result = 0 #결과값을 저장할 result라는 변수 선언

for cards in combinations(numbers, 3): #combination 함수를 사용하여 numbers 리스트에서 중복없이 카드 3장 pick
	temp_sum  = sum(cards)
	if result < temp_sum <= m:
    	result = temp_sum  #기존에 max함수를 생각했었는데 max사용시 O2만큼의 시간복잡도 증가됨 

print(result)

#2231. 분해합 https://www.acmicpc.net/problem/2231

문제 설명:

모든 경우를 시도하여 N의 생성자를 구하는 문제

풀이:

map함수를 이용하여 주어진 분해합을 기준으로 숫자를 1부터 증가하면서 생성자를 찾음

코드 중 정수로 입력받은 num을 str으로 변환하여 각 자리수의 값을 더하는 코드를

1) map함수를 통해 변환할 수 있고 2)pythonic way의 방법으로 sum함수 이내 인자들을 변환하여 바꿔주는 방식이 있다.

 pythonic way(list comprehension)

ex. newlist = [expression for 변수 in iterable (객체 if 조건식)

N = int(input())
result = 0 //초기값을 0으로 설정하여 생성자가 없는 경우를 고려할 필요 없음

for num in range(1, N+1):
 Sum = sum(map(int, str(num))) // sum(int(x) for x in str(num)) pythonic way(complihension)
 total = num + Sum
 if total == N:
  result = num
  break
print(result)

#19532. 수학은 비대면강의입니다. https://www.acmicpc.net/problem/19532

문제 설명:

모든 x와 모든 y를 시도하여 해를 구하는 문제

풀이1:

브루트 포스식으로 범위 내 반복문 시행

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:

연립방적으로 x, y 풀이

(수학적인 사고가 바탕이 된다면 코드 구현에 있어 더욱 빨라질 것을 몸소 느)

a, b, c, d, e, f = map(int, input().split())
x = (c*e - f*b)//(a*e - b*d)
y = (d*c - a*f)//(b*d - e*a)
print(x, y)

#1018. 체스판 다시 칠하기 https://www.acmicpc.net/problem/1018

문제 설명:

체스판을 만드는 모든 경우를 시도하여 최적의 방법을 찾는 문제

풀이:

경우의 수를 나누는 데 아직 힘에 부쳐 보류...

#1436. 영화감독 숌 https://www.acmicpc.net/problem/1436

문제 설명:

N번째 종말의 수가 나올 때까지 차례대로 시도하는 문제

풀이:

사실 어떻게 풀이할지 몰라서 다른 분들의 코드를 참조하였다.

(출처: https://ittrue.tistory.com/70 )

666를 시작하는 수로 '666'이 들어간 숫자만을 카운트하여 N번째 수를 print를 한다.

N = int(input())
num = 666
cnt = 0
while 1:
	if '666' in str(num):
		cnt += 1
	if cnt == N:
		print()
		break
	num +=1

#2839. 설탕 배달

문제 설명:

N킬로그램 설탕을 5킬로그램 봉지와 3킬로그램 봉지로 나눠 담는 최소 봉지 수를 구함

<브루트 포스를 이용한 풀이 > 

: 가능한 경우를 나누어 각각의 조건을 작성함

1) N이 5로 나눠지는 경우

2) N이 5와 3의 조합으로 나눠지는 경우

3) N이 3으로 나눠지는 경우

4) 5와 3으로 나눠지지 않는 경우

N = int(input())
bag = 0

if N % 5 == 0:
    bag += N// 5
else:
    while (1):
        N -= 3
        bag += 1
        if N % 5 == 0:
            bag += N //5
            break
        elif N == 2 or N == 1:
            bag = -1
            break
        elif N == 0:
            bag += N
            break

print(bag)

<while_else를 이용한 풀이>

:for-else와 while-else를 사용하면 조건 내에 break가 실행되지 않는 경우, else 문이 수행된다.

#bag의 수를 최소화하기 위해서 5키로 봉지에 포커스를 두어야 함

N = int(input())
bag = 0

while N >=0 :
    if N % 5 == 0:
        bag += N // 5
        break
    else:
        N  -= 3
        bag += 1
#while문에 들어가서 break가 실행되지 않는 경우, 아래의 else가 실행됨        
else:
    bag = -1
print(bag)

두 코드의 비교: 메모리, 시간 동일, but while-else 코드가 간결함