브루트포스 개념정리

Brute Force

 

브루트포스가 무엇인가?

-> 직역하면 짐승같은힘이다 

멧돼지 블로그와 잘맞는 알고리즘 인거같다

직역한 그대로 짐승같이 컴퓨팅 파워로 조져서 해결하는것이다.

문제를 해결하기 위해 가능한 모든 경우의수와 그 경우의 결과를 구하는것이다
브루트 포스 알고리즘으로 문제를 푼다면 무조건 정답이 나온다 -> 당연하다 다 구해보니까 ㅋㅋㅋㅋ 
한마디로 노가다 이다

ex) 6자리의 암호를 구해보자!
하나씩 죄다 넣어서 어렸을때 자물쇠 풀듯이 푼다
6! 가지수

한마디로 그냥 경우의수 다 가져다 넣어보는것이다 

 

1~50까지 더하기 예시

//1부터 50까지 더한 값 구하기 - Bruteforce
sum = 0

for i in range(1, 51):
	sum += i

 

🤔 근데 그럼 모든문제를 브루트포스로 풀면되지않나?

분명히 문제점이있다 -> 숫자가 커지면 커질수록 시간복잡도가 엄청 올라간다.

 

적절한용도 -> 입력 데이터 크기가 작고 ,구현해야하는 시간복잡도 내에서 해결 가능할때 사용하면 된다. 

 

 

---

 

어떤 방법으로 풀어야하나?

-> 재귀함수(top-down) 혹은 반복문(bottom-up)을 많이 사용한다.

 

 

1~50 까지 더하는 문제를 재귀, 반복문으로 구현해보자

 

1. 반복문으로 갈겨(bottom-up)

sum = 0
for i in range(1,51):
	sum += i
    
print(sum)

2.재귀로 갈겨(top-down)

def recursionAdd (num):
    if num == 1 : 
        return 1
    return num +recursionAdd(num-1)

print(recursionAdd(50))

 

뭐 어쩃든 이렇게된다.

 

어떤 문제 유형이 나오면 브루트 포스를 사용하면 좋을까?

1. 순열만들기 O(N!)
-> n 제한을 확인해보자 n 이 11만 넘어가도 1초를 넘긴다!!!!

2. 조합 만들기

3. 중복순열(2^n 경우의 수)만들기 
-> 모든 질문에 yes/no로 나눠질때 전체 2^n가지

---

순열 조합 이런거 기역 안날수있으니까 간단한 설명

 

 

 

 

 

 

어후 이거 중학교 수학이란다 중학생때가 언제야

---

파이썬에서 순열은 itertools.permutation. 조합은 itertools.combination 이다

 

 

 

7568번: 덩치

 

일단 이문제 풀어볼꺼다!!