Brute force

Mechboy·2024년 6월 25일

algorithm python

Algorithm

목록 보기

2/5

Brute force algorithm

Brute force 알고리즘은 문제에서 제시하는 모든 경우의 수를 풀어보는 방법이다.
속도는 가장 느리지만 정확도가 가장 높은 장점이 있음

순열(permutations)

순열은 경우의 수를 구할 때, 뽑은 숫자 및 문자의 순서를 고려하여 진행하는 방법이다.
파이썬을 활용하면 itertools 라이브러리의 permutations 함수를 활용하여 활용이 가능함

$_nP_r = \frac{n!}{(n-r)!}$

N개의 숫자에서 R개를 꺼낼때 순열을 구하면 위의 공식의 계산에 따른 수열을 구할 수 있는데 이 경우의 수를 permutations 함수를 통해서 구할 수 있음

>>> test_lst = [1,2,3]
>>> list(itertools.permutations(test_lst,2))
[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

순열을 활용한 문제의 예시

백준 10819

import sys
import itertools
test_array = []

size_array = int(sys.stdin.readline())
input_array=list(sys.stdin.readline().split(" "))
input_array = list(map(int,input_array))
input_array=input_array[0:size_array]
result_array = []

test_array = list(map(list,itertools.permutations(input_array,size_array)))

for test_lst in test_array:
    temp_abs = list(map(abs, [test_lst[i]-test_lst[i+1] for i in range(size_array-1)]))
    result_array.append(sum(temp_abs))

print(max(result_array))

문제풀이 접근법

문제 입력조건에 맞춰 리스트의 길이(size_array) 및 리스트의 원소(input_array)를 입력 받는다.
입력된 리스트 변수에서 나올 수 있는 모든 경우의 수(순열)을 구하고 list자료형 (test_array)으로 저장을 한다.
test_array에서 각 순열을 문제조건에 맞춰 연산을 한 후 result_array에 값을 저장
그중 가장 큰값을 출력

조합(combinations)

순열은 경우의 수를 구할 때, 뽑은 숫자 및 문자의 순서를 고려하지 않고 구 할수 있는 경우의 수를 찾는 방법이다.
파이썬을 활용하면 itertools 라이브러리의 combinations 함수를 활용하여 활용이 가능함

$_nC_r = \frac{n!}{r!(n-r)!}$

N개의 숫자에서 R개를 꺼낼때 조합을 구하면 아래와 같이 표현이 가능하다

>>> test_lst = [1,2,3]
>>> list(itertools.combinations(test_lst,2)) 
[(1, 2), (1, 3), (2, 3)]

조합을 활용한 문제의 예시

백준 2039


import sys
from itertools import combinations

lst = []
result = []
test_status = False

for _ in range(9):
    lst.append(int(sys.stdin.readline()))

temp = list(combinations(lst,7))

for j in range(len(temp)):
    if sum(temp[j]) == 100:
        result=list(temp[j])
        break

result.sort()
for lst_index in range(len(result)):
    print(result[lst_index])