🔵 brute force - 입문

안녕하세요 ! 이번에 알아볼 것은 순한맛일땐 온순하지만, 매운맛일땐 정말 극악의 난이도를 자랑하는 brute force입니다. brute force는 가능한 모든 경우의 수에 대해 직접 실행, 연산 해보는 알고리즘입니다. 이 글에선 brute force를 공부하려는 사람이 알아두면 좋은 것들을 간단히 정리해보았습니다. 그럼 오늘도 화이팅 입니다🌿

 

1. brute force 알고리즘의 접근 방식

   1. 문제의 가능한 경우의 수를 계산해봅니다.

      • 브루트 포스 알고리즘은 시도해봐야하는 경우의 수가 중요합니다.
      • 1초 -> 1억 -10억번의 연산 -> 몇 백만 - 몇 천만의 경우의 수
        • 즉, 1초라는 제한시간이 있다면, BF로는 몇 백- 몇 천만의 경우의 수에 대해 해결할 수 있다고 생각하시면 좋습니다.

   2. 위 경우의 수에 대한 가능한 모든 방법을 다 만들어 봅니다.

   3. for문, 비트마스크, 순열 (순서가 중요할 때), 재귀 호출, etc,, 각각의 방법을 이용해 답을 구해봅니다. 아래 세가지 방법은 BF에서 유용하게 쓰이는 스킬이므로, 따로 정리해보도록하겠습니다 !

      🔵 brute force - 순열 사용하기

      🔵 brute force - 재귀 호출 사용하기

      🔵 brute force - 비트 마스크 사용하기

2. BF 알고리즘의 시간 복잡도는 경우의 수 * 각 경우에 대한 연산 횟수가 됩니다.

3. N 중 for문
   • 시간 복잡도로만 봤을땐, 어차피 같은 일을 하게 되므로, 재귀함수보다 나쁜건 없습니다.
   • 가독성이 좋지않습니다.
   • 자잘한 실수의 위험이 있습니다. (디버깅이 어렵습니다. )