브루트 포스 (Brute Force)

브루트 포스는 컴퓨터 알고리즘 중 하나로, 가능한 모든 경우의 수를 일일이 검사하여 원하는 결과를 도출하는 방법을 말한다. 이 방법은 가장 직관적이고 단순하지만, 경우의 수가 많은 문제에서는 처리 시간이 매우 길어질 수 있다. 따라서 브루트 포스는 대개 다른 알고리즘과 함께 사용되며, 입력값이 매우 작다던지 특정한 조건에서만 사용된다.

예시

만약 암호가 4자리의 숫자이고, 각 자리가 0~9의 수 중 하나인 경우, 가능한 암호의 수는 10,000개이다. 이 경우 브루트 포스를 사용하여 모든 경우의 수를 일일이 검사하여 암호를 찾을 수 있다.

백트래킹 (Back-Tracking)

• 알고리즘 기법 중 하나로 재귀적으로 문제를 해결하되 현재 재귀를 통해 확인 중인 상태가 제한 조건에 위배가 되는지 판단하고, 해당 상태가 위배되는 경우 해당 상태를 제외하고 다음 단계로 넘어간다.
• 말이 어렵지만, 위에서 말한 대로 해를 찾는 도중 해가 절대 될 수 없다고 판단되면, 되돌아가서 다시 해를 찾는다고 생각하면 된다.
• DFS와의 차이점은 더 이상 탐색할 필요가 없는 상태를 제외한다, 이를 가지치기라고 한다.
• 다은은 백트래킹 중 유명한 문제 N-QUEEN의 백트래킹 방법을 트리화 한것이다

비트마스크(Bitmask)

• 비트를 이용하여 집합을 표시

• 컴퓨터는 기본적으로 이진수를 활용하기에 매우 빠른 연산 속도를 보여줌, 메모리 사용량 감소, 간결한 코드 작성

• 예를 들어 1,6,7번의 성질이 존재한다면 11000010(2) = 194(10)으로 표현

• 비트 연산

  

• 원소 추가(p번 비트를 on)

  cur = cur | (1 << p)
  

• 원소 삭제

  cur = cur & ~(1 << p)
  

• 원소 토글 (1→0, 0→1)

  cur = cur ^ (1 << p)
  

• 공집합

  cur = 0
  

• 전체 집합

  cur = 63