19. Brute Force

완전 탐색(Brute Force)은 가능한 모든 경우를 확인하면서 문제를 해결하는 방법이다. 이렇게 하면 당연히 실행 시간이 늘어나 성능이 좋지 않게 되는 경우가 많지만, 문제에서 주어지는 입력의 제한이 작은 경우 이 방법으로 문제를 풀 수 있는 경우도 많다. 온라인 프로그래밍 대회의 경우 입력의 제한을 작게 한 완전 탐색 문제를 쉬운 난이도의 문제로 내는 경우도 많으므로 초보자의 경우 문제를 풀기 위해 이 방법을 쓸 수 있는지를 판단하는 훈련을 하는 것이 중요하다. 일반적으로 입력의 크기와 시간복잡도를 통해서 계산한 최대 연산 횟수$(n)$가 얼마나 되는지에 따라 문제를 제한시간 내에 해결할 수 있는지의 여부를 판별할 수 있다. 제한시간은 $1$초를 기준으로 한다.

• $n \le 10^6$: 웬만하면 풀 수 있다.
• $10^6 \le n \le 10^7$: 실수 연산, 나눗셈, 모듈러 연산, 함수 호출, 구조체 멤버 접근 같이 느리거나 무거운 작업 또는 STL의 멤버 함수 호출이 심하게 많지 않다면 풀 수 있다.
• $10^7 \le n \le 10^8$: 위에 나온 무거운 작업이 많지 않다면 풀 수 있다. STL의 멤버 함수 호출이 많다면 성능 차이가 꽤 커질 수도 있으므로 주의해야 한다. 전반적으로 느린 연산자의 사용을 최대한 줄이는 것이 좋다.
• $10^8 \le n \le 10^9$: 연산 횟수가 이 범위에 속할 경우 프로그램이 제한시간 내에 실행될 수도 있고 실행되지 않을 수도 있다. 주로 코드의 구조가 얼마나 단순한지와 코드에 들어간 작업의 속도가 얼마나 빠른지에 의해 성능이 결정된다.
• $10^9 \le n$: $10$억이라는 연산 횟수 자체는 현대 컴퓨터에서 $1$초 내에 충분히 실행할 수 있지만 실제로는 다른 요소의 영향을 받기 때문에 제한시간 내에 해결하기 쉽지 않다. 단 코드의 구조가 아주 단순할 경우 제한시간 내에 통과할 수도 있다.

[연습문제]

 

BOJ 6751. From 1987 to 2013 (Bronze II)

모든 자릿수가 다른 수를 찾을 때까지 $Y+1$부터 수를 하나씩 확인하면 된다.

 

BOJ 5555. 반지 (Silver V)

$n$개의 문자열의 각각의 위치를 확인하면서 찾는 문자열을 포함한 것이 몇 개인지 세면 된다.

 

BOJ 2615. 오목 (Silver III)

왼쪽 위부터 차례로 각각의 위치를 시작점으로 하는 이기는 경우가 존재하는지를 차례로 확인한다. 방향은 오른쪽 위, 오른쪽, 오른쪽 아래, 아래의 $4$방향만 체크해도 된다. 고려해야 할 것이 많기 때문에 구현이 약간 까다롭다.

 

BOJ 14500. 테트로미노 (Gold V)

각각의 위치에 테트로미노를 놓는 경우를 모두 확인하면 된다. 테트로미노 중 하나를 골라서 놓는 방법이 $19$가지나 되기 때문에 약간의 노가다가 필요하다.

 

CF 1465B. Fair Numbers (1000)

$1\text{~}9$의 최소공배수가 $2520$이기 때문에 $2520$의 배수는 모두 Fair Numbers이다. 따라서 $n$보다 큰 수를 하나씩 모두 확인하는 방법으로 풀 수 있다.

 

CF 1379A. Acacius and String (1500)

각각의 위치를 확인하면서 그 위치에서 시작하는 부분 문자열이 "ABACABA"가 되게 할 수 있다면 그 부분의 문자열을 "ABACABA"로, 나머지 ?는 모두 A, B, C가 아닌 다른 문자로 바꾼 후 다른 위치에서 문자열 "ABACABA"가 나타나지 않는지 확인한다. 풀이가 복잡하지 않지만 대회 당시에 이걸 제대로 구현하지 못한 참가자가 많아서 Div.2 A임에도 불구하고 *1500을 받는 참사가 일어났다.

 

→ solved.ac tag: bruteforcing