[TIL] 250605 - 완전 탐색 가능 여부 판단 기준(시간 복잡도)

알고리즘 문제를 풀다 보면 완전 탐색을 사용해 문제를 풀어야하는 것들이 많습니다.

그런데, 문제를 풀기전에 이 문제가 완전 탐색으로 풀어도 괜찮은 문제인지 생각해보고 코드를 짤 필요가 있어보여 그 기준을 정리해봤습니다.

• 모든 경우의 수 × 각 경우를 처리하는 시간이 1억(100,000,000) 이하 정도면 일반적으로 괜찮다고 보고 들어가면 된다고 합니다.
  • 프로그래머스 피로도 문제의 경우 제한사항을 보면 아래와 같습니다. 
    • k는 1 이상 5,000 이하인 자연수입니다.
    • dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
      • dungeons의 가로(열) 길이는 2 입니다.
      • dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
      • "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
      • "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
      • 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.
  • 던전 수는 최대 8개로, 가능한 던전 탐험 순서의 모든 경우의 수는 순열(permutation)문제입니다.
    • 던전 개수 : 8개
    • 가능한 순열 수 : 8! = 40320
  • 각 순열을 검사할 때 피로도를 계속 차감하며 최대 8번 탐험을 시도합니다
    • 즉, 순열 하나당 처리 시간은 O(8) ≈ 상수 시간
  • 이를 통해 전체 시간 복잡도를 구해보면
    • 40320 (순열 수) × 8 (각 순열 처리) = 약 32만 번의 연산 이므로 이는 1억보다 훨씬 작으므로 완전 탐색으로 충분히 풀리는 문제라는 판단을 내릴 수 있게 되는겁니다.