브루트 포스는 모든 경우의 수를 다 해보는 것이다.
가장 중요한 것은, 문제의 경우의 수가 전부 몇가지인지 알아보는 것이다.
브루트 포스를 위해 3가지 단계를 생각해볼 수 있다.
- 문제의 가능한 경우의 수를 계산 : 코드 x / 사람이 직접 계산
- 가능한 모든 방법을 다 만들어본다.
- 각각의 방법을 이용해 답을 구해본다.
시간 복잡도 = 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) 일 것이다.
시간을 줄일 때 가장 중요한 것은 중복되는 것을 많이 줄이는 것이다. -> 변화가 있을 수 있는 곳만 구하는 것이다.
반응형
'알고리즘 & 코딩 테스트 > code.plus' 카테고리의 다른 글
[기초] N과 M (0) | 2021.08.24 |
---|---|
[기초] 건너 뛰며 해보기 (0) | 2021.08.22 |
[기초] 날짜 계산, 리모컨, 테트로미노 (0) | 2021.08.22 |
[기초] 나머지 연산, 약수, 최대공약수, 소수 (0) | 2021.08.21 |
[기초] 시간 복잡도와 언어별 유의사항 (0) | 2021.08.21 |