# Brute-Force

\ <br>

## Brute-force

* 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

\ <br>

## Brute-force Search (Sequential Search)

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

<br>

* Results
  * Successful search
  * Failed search

<br>

* 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

\ <br>

### Baby-gin Game

#### Description

* 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.

<br>

### Complete Search Approach for 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

\ <br>

## Complete Search

* 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

\ <br>

## Permutation

* 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...)

<br>

### 1. Permutation Generation Through Recursive Calls - Generation Through Exchange

```python
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
```

\ <br>

## Subsets

* 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

<br>

### 1. Simple Method to Generate All Subsets

* Finding the `power set` for a set containing 4 elements

<br>

### 2. Binary Counting

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

\ <br>

## Combination

> Selecting r items from n different elements without considering order

* Combination formula
  * nCr = `n-1 C r-1` +`n-1 C r`
  * nC0 = 1


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://chloe-codes1.gitbook.io/til/algorithm/algorithm-basics/01_brute-force.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.