[기초] 브루트 포스

브루트 포스는 모든 경우의 수를 다 해보는 것이다.

가장 중요한 것은, 문제의 경우의 수가 전부 몇가지인지 알아보는 것이다.

브루트 포스를 위해 3가지 단계를 생각해볼 수 있다.

1. 문제의 가능한 경우의 수를 계산 : 코드 x / 사람이 직접 계산
2. 가능한 모든 방법을 다 만들어본다.
3. 각각의 방법을 이용해 답을 구해본다.

시간 복잡도 = O(방법의 개수 X 시도하는 복잡도)

재귀 호출을 사용 하는 방법이 가장 중요하다.

일곱 난쟁이 2309

• 아홉 명 중에 2명을 고르는 과정 O(N^2)
• 나머지 7명의 난쟁이의 키의 합을 구하는 과정 O(N) (직접 연산을 통해 O(1) 로도 가능)

사탕 게임 3085

• 인접한 두 칸을 고르고, (-> 한 칸을 고르고, 4개의 인접 칸 고르기)
• 사탕을 교환한다.

라는 방법이 쓰여져 있다. 이 방법을 다 해보는 것이 Brute force 이다

 

총 몇가지가 가능할 것인가.

 

임의의 한 칸에서 상하좌우 최대 4개를 인접한 것을 고를 수 있다.

 

그러므로, 한칸을 고르는 방법 N^2 개, * 4 = O(N^2)

 

또한, 가장 긴 연속 부분 행 또는 열을 고르는 문제가 O(N^2)

 

총 O(N^4) 이 될 수 있다.

 

50^4 이므로, 600만 정도이다. 1억보다 충분히 괜찮으므로 브루트 포스를 시도해볼 수 있다.

 

시간 복잡도를 더 줄일 수도 있다. 임의의 두 칸을 변경하였을 때, 정답에 변화가 있는 것은 최대 3개의 행 / 열이기 때문에 그부분만 다시 체크해준다면 O(N) 일 것이다.

 

시간을 줄일 때 가장 중요한 것은 중복되는 것을 많이 줄이는 것이다. -> 변화가 있을 수 있는 곳만 구하는 것이다.