완전 탐색

• 모든 경우의 수를 전부 탐색해보는 알고리즘
• 다음과 같은 방법이 있음
  • 브루트포스
  • 순열
  • 백트래킹(재귀) 탐색
  • 비트 마스크
  • DFS, BFS 탐색

완전탐색 사용법

다음을 고려하여 사용

• 해결하고자 하는 문제의 가능한 경우의 수 대략적으로 계산
• 가능한 모든 방법을 전부 고려
• 실제 답을 구할 수 있는지 적용

브루트포스(Brute Force)

• for문 or if문을 활용해 모두 테스트하는 방법
• 시간복잡도: O(n2)
• 알고리즘을 풀 때 우선 브루트포스로 가능한지 확인 후 불가능하다면 어떤 알고리즘을 적용해 시간복잡도를 줄일지 확인

  1. 사용되는 알고리즘이 적절한 방법인가?
     (제한 조건 내에서 해결될 수 있는가)
  2. 효율적으로 동작하는가?

순열(Permutation)

• 순열 알고리즘 구현 설명 포스팅
• 임의의 수열에 대하여 다른 순서로 연산하는 방법
• 시간복잡도: 전체 N개의 숫자에 대해 O(N!)
• 순서가 중요

  수열에서 숫자 {1, 2, 3}이 있다면 보는 순서에 따라 {1, 2, 3}과 {3, 2, 1}은 서로 순서에 차이가 있기 때문에 서로 다른 수열로 봄

• 전체 숫자의 개수가 적을 때 사용 (총 8개 이하)
  👉 주어진 N의 범위 파악 중요
• 사용하는 경우

  1. 순서와 관련된 경우
  2. 선택과 관련된 경우
  3. 수가 고정된 경우

백트래킹(재귀) 탐색

• 자기 자신을 호출
• 주의할 점
  • 재귀문을 종료시키기 위한 종료 조건이 반드시 필요
  • 현재 함수의 상태를 저장하는 parameter(인자)가 필요
  • return문 신경쓰기
• Dynamic Programming(DP)와 다른 점
  • DP: 작은 문제가 큰 문제와 동일한 구조를 가져, 큰 문제의 답을 구할 때 작은 문제의 결과를 참고해 수행 속도를 빠르게 함
  • 완전탐색: 크고 작은 문제의 구조가 다를 수도 있으며, 이전 결과를 반드시 기억할 필요가 없이 해결 가능할만한 모든 방법을 모두 탐색

비트 마스크

• 비트 연산을 통해 부분 집합을 표현하는 방법

• 활용 방법

  • 집합 포함 여부 검사 - AND(&) 비트 연산

  • 숫자 추가하기 - OR(|)연산

  • 특정 숫자 제거하기 - NOT(~) 비트 연산, AND(&) 비트 연산 동시 사용

  • 토글 연산하기 - 0, 1을 왔다갔다 할 수 있게 하는 연산, XOR(^) 비트 연산 사용

  • 전체 집합, 공집합 표현 - 전체 집합은 모든 숫자가 1, 공집합은 0

DFS, BFS 탐색

• 모든 정점을 탐색하기 위함