브루트포스(1) - 무작정 해보기

브루트 포스 알고리즘

모든 경우의 수를 해보는 알고리즘이다.

무작정 반복문을 돌려 구할 수도 있다.

 

브루트포스 알고리즘 예시

문제 : n이 주어졌을때, 1부터 n 중에 2의 배수의 수는? (1<= n < 10000000)

n을 1부터 n까지 확인하면 시간 복잡도는 O(n)이다.

n의 최악의 경우 1천만이므로 브루트포스로 다 구해볼 수 있다. (수식을 사용하면 상수시간으로 처리 가능하다.)

public int Solution(){
  int n = sc.nextInt();

  int cnt = 0;
  for(int i = 1; i <= n; i++){
      if(i%2 == 0)
          cnt++;
  }
  return cnt
}

 

시간 복잡도 계산

O(경우의 수* 처리)의 시간이 걸리므로 구현 전에 확인하여 가능한지 체크한다.

O(n!)의 복잡도일 경우 n이 보통 10 이하일 경우 가능

O(2^n)는 n이 20이하에 가능하다.

처리하는 알고리즘에 따라 다르다.

 

브루트 포스를 풀며 느낀 점은 처리하는 것에 있어 불필요한 반복이 많다.

시간을 줄이기 위해서는 불필요한 반복 확인하고 줄이는 것이 중요하다.