본문 바로가기

알고리즘

브루트포스

브루트포스를 사용할 때 마다 방식이 헷갈려서 참고용으로 저장해놓는 것이라, 최대한 간단하게 에시 코드만 적겠습니다.

기본적으로는 python을 이용합니다.

 

# 재귀를 통한 순열, DFS 라고도 하는 듯?

1
2
3
4
5
6
7
8
9
10
11
12
def brute(l, candidates):
    if len(l) == len(totalList):
        print(l)
    else:
        for c in candidates:
            _candidates=candidates[:]
            _candidates.remove(c)
            brute(l+[c], _candidates)
 
= int(input())
totalList = list(range(1, n+1))
brute([], totalList)
cs

 

# 백준 14888번 연산자 끼워넣기

위의 코드를 약간 변형해서 백준 14888번 브루트포스 문제를 풀 수 있다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#import sys
#sys.stdin = open("input.txt", "r")
 
= int(input())
numbers = list(map(int, input().split(" ")))
operators = list(map(int, input().split(" ")))
MIN, MAX = 1000000001-1000000001
sums=[]
def brute(_numbers, _ops, _i, s):
    if len(_numbers) == _i:
        global MIN, MAX
        sums.append(s)
        if s<MIN: MIN = s
        if s>MAX: MAX = s
    else:
        for _op_index in range(len(_ops)):
            _s=s
            if(_ops[_op_index] != 0):
                copiedOperators=_ops[:]
                copiedOperators[_op_index]-=1
                if( _op_index == 0 ):
                    _s+=_numbers[_i]
                elif( _op_index == 1 ):
                    _s-=_numbers[_i]
                elif( _op_index == 2 ):
                    _s*=_numbers[_i]
                elif( _op_index == 3 ):
                    if( _s < 0):
                        _s= -( (-_s)//_numbers[_i] )
                    else:
                        _s//=_numbers[_i]
                brute(_numbers, copiedOperators, _i+1, _s)
 
 
brute(numbers, operators, 1, numbers[0])
 
print(int(MAX))
print(int(MIN))
cs

'알고리즘' 카테고리의 다른 글

브루트포스  (0) 2019.08.17