Brute Force 기본 개념

https://namu.wiki/w/%EB%B8%8C%EB%A3%A8%ED%8A%B8%20%ED%8F%AC%EC%8A%A4

브루트 포스 - 나무위키

 

 

브루트 포스를 단순한 알고리즘이지만 강력하다

브루프 포스는 문제에서 발생할 수 있는 모든 경우에 대해 다 따져보면서 문제를 해결한다

그러기 때문에 정확도는 100%이다

 

하지만, 문제가 있다

바로 무식하게 모든 경우를 따지기 때문에 효율적인 알고리즘은 아니다

즉, 이 알고리즘을 적용했을 때 제한 시간내에 작동하는지 따져봐야 한다

 

문제에서 보통 시간 제한과 입력값의 크기가 주어진다

 

브루트 포스 알고리즘을 설계하고 시간 복잡도를 계산했으면 최대 크기의 입력값을 대입해서

제한 시간 내에 작동하는지 따져봐야한다

 

보통 1초가 1억이라는 기준을 잡고 계산을 하면된다

 

브루트 포스를 구현하는 방식은 다양하다

- 반복문 형태

- 재귀호출

- 다음 순열

- 비트마스킹

,,,,

이 외에도 많은 방식이 있다

 

재귀 호출 방식을 구현하는 데에 사용되는 틀이 있다

1. 종료 조건 : 재귀 호출을 멈춤

2. 재귀 호출 : 작업 처리 과정

3. 정답 반환 : 정답 출력

 

다음 순열은 주로 순열과 비슷한 뉘앙스를 뛰는 문제에서 사용된다

예를 들어 [1, 2, 3, 4] 가 있다고 했을 때,

1234

1243

1324

1342

1423

1432

,,,,

이렇게 1, 2, 3, 4의 바꿀 수 있는 모든 위치를 바꾼 것을 확인해 나갈 수 있다

이는 단순한 순열 문제에서부터 순열 뉘앙스를 풍기는 다양한 문제에 적용된다

 

비트 마스킹을 구현하는 데에 필요한 개념들이 있다

일단, 기본적인 전산 개념을 알아야한다

 

이진수는 1과 0으로 이루어진 숫자이다

이진수는 2가지 정보를 담기에 적합한 구조를 뛴다

이는 매우 유용하게 쓰인다

 

브루트 포스 알고리즘 문제를 풀다보면 무언가를 "선택할지 말지"결정해야하는 경우가 있다

예를 들어서, 공을 선택할지 말지, 사탕을 선택할지 말지 등이 있다

이를 이진수로 표현할 수 있다

 

사탕이 5개가 있고 이를 선택할지 말지를 이진수로 표현한다고 했을 때 밑에와 같이 표현할 수 있다

 

00000

00001

00010

00100

,,,

111111

 

그리고 비트 연산 &을 통해서 특정 위치의 사탕을 선택했는지 하지 않았는지 확인할 수 있다

예를 들어서 사탕 5개를 선택하는 경우중 2번째 사탕 만을 선택한 경우는 00010으로 나타낼 수 있고

두 번째 사탕을 선택했는지 안했는지 확인하는 방법은 밑에와 같다

00010 & (1<<1) != 0

 

자세한 내용은 앞으로 문제를 풀어나가면서 설명하겠습니다

---

브루트 포스의 핵심 키워드

- 정확도 100 

- 제한 시간내에 작동하는지 따져보야함

- 반복문, 재귀, 다음 순열, 비트 마스킹 활용