• Brute-force is a simple and straightforward approach to problem solving
  • Just-do-it
  • The meaning of force refers to computer force rather than human intelligence
• The brute-force method is applicable to most problems
• It allows relatively quick problem solving (algorithm design)
• Useful when the size of data (elements, instances) included in the problem is small
• Used as a measure to judge algorithm efficiency for academic or educational purposes

: To find a key value in a list of data, start comparing from the first data and proceed

• Results
  • Successful search
  • Failed search

• Since all possible cases are generated and tested, the execution speed is slow, but the probability of not finding an answer is small
  • Complete search involves writing a program that gets answers simply and quickly by making the input size small
• Based on this, efficient algorithms can be found using greedy techniques or dynamic programming
• When solving problems in coding tests, it's advisable to first approach with complete search to derive answers, then use other algorithms for performance improvement and verify the answers

• When 6 cards are randomly drawn from number cards between 0-9, a case where 3 cards have consecutive numbers is called a run, and a case where 3 cards have the same number is called a triplet.
• When 6 cards consist only of runs and triplets, it's called baby-gin
• Write a program that takes a 6-digit number as input and determines whether it's baby-gin.

1. Generate all possible cases
   • All number arrangements that can be made with 6 numbers (including duplicates)
2. Test the solution
   • Cut the first 3 digits and last 3 digits, test for run and triplet, and finally determine baby-gin

• Many types of problems involve finding cases or elements that satisfy specific conditions
• Typically associated with combinatorial problems such as permutations, combinations, and subsets
• Complete search is a brute-force method for combinatorial problems

• Arranging some items selected from different things in a row
• The permutation of selecting r items from n different items is nPr
• The following formula holds:
  • nPr = n x (n-1) x (n-2) x ... x (n-r+1)
• nPn = n! is written as Factorial
  • n! = n x (n-1) x (n-2) x ... 2x1
• Permutations are related to finding the best method in a set of ordered elements
  • ex) TSP (Traveling Salesman Problem)
• For N elements, there are n! permutations
  • When n >12, time complexity explosion!!! (because it goes up exponentially...)

def perm(n,k):
    if k == n:
        #do something
 else:
        for i in range(k, n):
            swap(k,i)#swap!
            perm(n, k+1)
            swap(k,i) #restore to original state

• Selecting elements included in a set
• Many important algorithms involve finding the optimal subset from a group of elements
  • ex) knapsack problem
• Set containing N elements
  • The number of all power sets including itself and the empty set is 2^n
  • As the number of elements increases, the number of subsets increases exponentially

• Finding the power set for a set containing 4 elements

• Use N bit strings corresponding to the number of elements
• If the nth bit value is 1, it means the nth element is included

Selecting r items from n different elements without considering order

• Combination formula
  • nCr = n-1 C r-1 +n-1 C r
  • nC0 = 1