무차별 대입

이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
    https://github.com/AeroCodeX/

부르트 포스(Brute Force) 개념

가능한 모든 경우의 수를 검사하는 것.

많은 자원을 소모하지만 가장 확실한 방법이고,

무엇보다 다른 사람이 이해하기 쉬운 코드를 만들어낸다.

러닝타임은 꽤 걸리겠지만, 

구현하기 쉽고.  이해하기 쉽다. 

점진적 성능향상을 이용한 알고리즘 풀이

순진하게 부르트 포스를 적용했다간, 

굉장히 높은 확률로 시간제한에 걸린다.

확실하게 답이 아닌 영역을 배제함으로써 성능을 향상시켜야 한다.

다음은 부르트-포스의 중요한 특징이다.

• 첫 아이디어가 굉장히 단순하다.  (구현하기 쉽다.)

• 조금씩 성능을 개선해나갈 수 있다.

충분히 성능을 개선해나가면, 

부르트-포스로도 빠른 문제풀이가 가능하다.

예제 # N의 약수 구하기

• 간단하게 생각하자

어떤 수 N의 모든 약수를 구하는 알고리즘을 생각해보자.

단순히 1부터 N까지 순회하면서 나누어 떨어지는지 검사하면 된다.

나누어 떨어지는 수가 있다면 그 수는 N의 약수일 것 이다.

• 조금씩 성능을 개선하자

어떤 수 N의 약수가 a라면 N/a도 약수이다.

a는 증가할 때, N/a는 감소하고 sqrt(N)에서 교차한다.

따라서 sqrt(a)를 넘어서서 얻은 약수는 중복으로 발견되며,

반복문의 범위가 1..sqrt(N)로 줄었다.

간단한 개선같지만, 그 효과는 극적이다.

1/10,000 수준으로 러닝타임이 줄었다.

이 예제에 대한 자세한 설명은 이곳을 참조하기 바란다.