[Algorithm] 브루트 포스는 뭐야?

브루트 포스 알고리즘은 가능한 모든 경우의 수를 하나씩 확인해보는 알고리즘이다. 모든 경우의 수를 탐색하는 과정에서는 막대한 자원과 시간이 소모되지만 모든 경우의 수를 하나씩 확인해본다는 것은 100%의 정답을 도출할 수 있는 방법이기도 하다.

 

백준 2231번 문제를 예시로 확인해보자 문제 해설

 

문제를 확인하기 위해서는 주어진 수를 n, 계산 중인 값을 m이라 할 때 다음의 과정을 따른다.

 

1. m의 각 자릿수와 자기 자신을 더한다.
2. 해당 값과 n을 비교한다.
3. 2번 과정이 참이면 결과를 출력하고 종료한다.
4. 2번 과정이 거짓이면 m을 1 더해주고 1의 과정으로 돌아간다.
5. 모든 과정이 끝나도 출력 값이 없다면 0을 출력한다.

다음은 "216"을 계산 중인 값을 그림으로 표현한 것이다.

 

위의 그림에서 볼 수 있듯이 99 -> 100으로의 이동은 규칙이 없다. 따라서 브루트 포스를 이용하는 것이 이 문제에서는 효율적이다.

 

다음은 문제 해결 과정을 코드를 옮겨서 작성한 것이다.

 

n = int(input())
check = False
 
def valueSum(x):
  num = str(x)
  sum = 0
  for i in num:
    sum += int(i)
  sum += x
  return sum
 
for i in range(n):
  if n == valueSum(i):
    check = True
    print(i)
    break
 
if check == False:
  print(0)