[Algorithm] Brute Force(완전 탐색) Algorithm

🎯 목표 :  완전 탐색 알고리즘의 작동 원리를 이해하고 구현 할 수 있다.

📒 완전 탐색 알고리즘

📌 특징

• 무차별 대입 방법을 나타내는 알고리즘이다.
• 모든 가능성을 시도하여 탐색한다. - 최적의 해결방법이 아니다.
• 사용할 수 있는 다른 알고리즘이 없을때 사용한다.
• 여러 해결 방법이 있다면 각 해결 방법을 확인 해야 할 때 사용한다.
• 데이터의 범위가 커질수록 비효율적인 알고리즘이다.
• 문제의 복잡도에 매우 민감한 알고리즘이다.

---

📌 대표 알고리즘

• 순차 검색 알고리즘(Sequential Search) : 배열의 인덱스 0 부터 마지막까지 차례로 검색한다.
• 문자열 매칭 알고리즘(Brute-Force Striong Matching) : 길이가 n인 전체 문자열과 길이가 m 인 문자열 패턴을 포함하는지 검색한다.
• 선택 정렬 알고리즘(Selection Sort) : 전체 배열을 탐색하여 현재 요소와 비교하고 배열이 완전히 정렬될 때까지 오름차순 또는 내림차순에 따라 교환하는 알고리즘.
• Tree 구조의 BTS,DFS
• 동적 프로그래밍(Dynamic Programing)
• 버블 정렬(Bubble Sort)

---

📌 Sequential Search(순차 검색)

• 배열을 전체를 순회하며 탐색
• Ex) 배열 {5,2,7,3,8,9,4}에서 9가 있는지 여부 

arr = new int[]{5,2,7,3,8,9,4};
n = 9

public boolean SequentialSearch(int[] arr, int n) {
	boolean result = false;
    for(int i=0; i<arr.length; i++){
    	if(arr[i] == n){
          result = true;
        }
    }
    return result;
}

---

📌 Brute-Force String Matching(문자열 매칭)

• 해당 문자열을 포함하고 있는지 탐색

    public int bfMatching(String text, String pattern){
        int textIndex = 0;
        int patternIndex = 0;

        while (textIndex!=text.length()&& patternIndex!=pattern.length()){
            // 같은 문자를 발견했을때 text와 pattern의 인덱스 값을 증가 시키며 다시 탐색
            if(text.charAt(textIndex)==pattern.charAt(patternIndex)){
                textIndex++;
                patternIndex++;
            } else {
                // 같은 문자가 없다면 textIndex의 값은 1씩 증가하게 되고.
                // 같은 문자열을 찾았을때, pattern의 마지막 문자와 같은 text의 인덱스에서 탐색을 끝낸 상태라면.
                // pattern의 첫번째 문자가 포함된 text의 인덱스를 textIndex에 삽입.
                textIndex = textIndex - patternIndex + 1;
                patternIndex = 0;
            }
        }
        // 같은 문자열을 찾았을때 첫 문자 인덱스값을 반환
        if(patternIndex == pattern.length()) return textIndex-patternIndex;
        // 그렇지 않은 경우 -1 반환
        else return -1;
    }

---

📌 Selection Sort(선택 정렬)

• 하나의 요소로 전체 요소를 탐색하여 오름차순 또는 내림차순에 따라 요소를 교환하며 정렬.

    public int[] SelectionSort(int[] arr) {
        // 요소를 가지고 전체 배열을 순회하며 최소값을 찾아 교환한다.
        for (int from = 0; from < arr.length - 1; from++) {
            // 요소중 최소값의 인덱스를 가질 변수 min
            int min = from;
            for (int j = from + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            // from 인덱스 값을 가진 요소를 최소값과 교환한다.
            swap(arr,from,min);
        }
        return arr;
    }
    private void swap(int[] arr, int from, int min){
        int temp = arr[from];
        arr[from] = arr[min];
        arr[min] = temp;
    }

---

📌 Bubble Sort(버블 정렬)

• 배열의 끝 요소(index = n)부터 이웃한 요소(index = n-1)를 순차적으로 비교해서 교환하며 정렬하는 알고리즘

    public void bubbleSort(int[] arr){
        int n = arr.length;
        for (int i=0; i<n-1; i++){
            // 더이상 정렬할 요소가 있는지 없는지 확인 count
            int count =0;
            // 배열의 끝부터 인덱스 i 까지 탐색하며 요소 교환
            for(int t=n-1; t>i; t--){
                if(arr[t-1]>arr[t]) {
                    swap(arr,t-1,t);
                    count++;
                }
            }
            // 더이상 탐색해서 교환하는 요소가 없다면 break
            if(count == 0) break;
        }
    }
    private void swap(int[] arr, int idx, int idx2){
        int temp = arr[idx];
        arr[idx] = arr[idx2];
        arr[idx2] = temp;
    }