[Algorithm] 3. Brute Force Algorithm

✔️ Brute Force Algorithm

- 가장 간단하고 직접적인 방식으로 문제를 해결

- 효율적이고 정교한 알고리즘보다 많은 작업을 할 가능성이 높음

- 그렇지만 구현하기가 쉬우며 이로 인해 더 효율적일 수도 있음

- Exhaustively enumerate all the possibilities.

 

1) Selection Sort

- 현재 idx 값 ↔ 배열에서의 최솟값

for i ← 0 ~ n-2
    min ← i
    for j ← i+1 ~ n-1
        if A[j] < A[min] min ← j
            swap A[i] and A[min]

- Time efficiency: O(n^2)

 

2) Bubble Sort

- 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환

for j = 1 to n
    for i = 0 to n-1
        if A[i] > A[i+1]
            swap A[i] and A[i+1]

- Time efficiency: O(n^2)

 

3) String Matching

# n: 전체 string 길이, m: 찾으려는 string 길이
for i ← 0 to n - m
    j ← 0
    while j < m and P[j] = T[i + j]
        j ← j + 1
    if j = m return i
return -1

- Time efficiency: O(m*n)

 

4) Sequential Search (= linear search)

- 처음부터 끝까지 차례대로 원소 비교하여 탐색 (중간에 찾아도 계속 진행)

- 데이터 따로 조작할 필요 없으나 비효율적

- Time efficiency: O(n)

 

5) Exhaustive Search

- 문제에 대한 모든 해결책을 찾아내고 그중 가장 적합한 것을 골라냄

 

5-1) Traveling Salesman Problem

- Input: 완전(모든 vertex가 서로 연결됨) + 가중치(edge에 값) 그래프

- Output: Hamilton circuit of minimum weight

 

- Hamilton circuit: 하나의 vertex에서 시작하여 모든 vertex를 한 번씩 거쳐 다시 첫 vertex로 돌아오는 경로

1) 모든 Hamilton circuit을 구함

2) 각 circuit의 total weight를 구함

3) 가장 작은 weight를 가진 circuit을 선택

 

- 모든 vertex를 거쳐야 하지만 모든 edge를 거칠 필요는 없음

- Hamilton path: 시작 vertex와 끝 vertex이 같지 않아도 됨

- Optimal Hamilton circuit: 브루트포스 방식으로 해결하는 경우

- 정확하다는 장점이 있지만 작업량이 아주 많음

 

5-2) Knapsack Problem

- Weight capacity가 정해진 배낭에 value, weight를 가진 아이템이 주어졌을 때 value가 최대가 되도록 아이템을 집어넣는 문제

- Time efficiency: O(2^n)

- 전략

   - 아이템을 쪼갤 수 있는 경우: greedy algorithm (take any fraction of the item)

   - 아이템을 쪼갤 수 없는 경우: dynamic programming (take the item or not)

 

구현하는 데 참고한 자료

https://gsmesie692.tistory.com/113 기본 개념 이해, 기본 코드

https://www.geeksforgeeks.org/printing-items-01-knapsack/ Tracing(Backtracking으로 선택된 아이템 출력하기) 

 

5-3) Job Assignment Problem

- 각 사람이 각 일을 수행하는 데 필요한 비용이 주어지고, 한 명당 하나의 일을 맡을 때 비용이 최소가 되도록 하는 문제