026 | Greedy, Brute-Force, Binary Search Algorithm

💙 Greedy Algorithm

• 선택의 순간마다 당장 눈앞에 보이는 최적의 상황으로 최종적인 해답에 도달하는 방법

1. 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택
2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사
3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정 반복

🤍 탐욕 알고리즘 조건

• 탐욕적 선택 속성(Greedy Choice Property): 앞의 선택이 이후의 선택에 영향을 주지 않음
• 최적 부분 구조(Optimal Substructure): 문제에 대한 최종 해결 방법은, 부분 문제에 대한 최적 문제 해결 방법으로 구성

⇒ 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점 때문에 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있음

💙 Brute-Force Algorithm

• 모든 알고리즘의 시작점으로, 모든 경우의 수를 시도하는 만큼 직관적이고 명확하지만, 입력값이 클수록 오래 걸림

• 암호학에서 Brute Force Attack: 특정한 암호를 풀기 위해서 모든 값을 대입하는 방법
  • 수많은 시행착오를 통해 민감한 데이터를 해킹하는 방법으로, 올바른 조합을 찾을 때까지 다양한 조합을 시도
  • 무차별 대입 공격이 다른 해킹 방법과 다른 점은 지능형 전략을 사용하지 않음

🤍 무차별 대입 방법

• 컴퓨터 성능에만 의존하여 모든 가능성을 시도하여 문제를 해결하는 방법
• Brute Force는 공간복잡도와 시간복잡도의 요소를 고려하지 않고 최악의 시나리오를 취하더라도 솔루션을 찾으려고 하는 방법 이기 때문에 최적의 솔루션이 아님

🤍 When Using of the Brute-Force Algorithm

• 프로세스 속도를 높이는데 사용할 수 있는 다른 알고리즘이 없을 때
• 문제를 해결하는 여러 솔루션이 있고 각 솔루션을 확인해야 할 때
• 문제의 규모가 현재 자원으로 충분히 커버가 가능할 때

⇒ Brute Force Algorithm은 문제에 더 적절한 해결 방법을 찾기 전에 시도하는 방법이지만 데이터의 범위가 커질수록 비효율적 이므로, 프로젝트의 규모가 커진다면 더 효율적인 알고리즘을 사용해야 함

🤍 Limit of the Brute Force Algorithm

Brute Force Algorithm은 문제의 복잡도에 매우 민감한 단점을 가지고 있어서, 문제가 복잡해질수록 기하급수적으로 많은 자원을 필요로 하는 비효율적인 알고리즘이 될 수 있음 (여기서 자원은 시간이 될 수도, 컴퓨팅 자원이 될 수도 있음). 만약 이를 벗어난 경우는 정확도를 조금 희생하고 더 효율적인 알고리즘을 사용

🤍 Where to Use Binary Search Algorithm

💫  순차 검색 알고리즘(Sequential Search)

• 배열 안에 특정 값이 존재하는지 검색할 때 인덱스 0부터 마지막 인덱스까지 차례대로 검색

public boolean SequentialSearch2(int[] arr, int K) {
	int n = arr.length;
	boolean result = false;
	for(int i = 0; i < n; i++) {
		if(arr[i] == K) {
		result = true;
		}
    }
    
	return result;
}
       
// 배열을 순회하는 도중에, 해당하는 값이 발견되더라도 배열을 모두 순회한 이후에 결과값을 리턴

💫  문자열 매칭 알고리즘(Brute-Force String Matching)

• 길이가 n인 전체 문자열과 길이가 m인 문자열 패턴을 포함하는지를 검색

public boolean BruteForceStringMatch(int[] arr, int[] patternArr) {
    // Brute Force 문자열 매칭을 구현
    int n = arr.length;
    int m = patternArr.length;
    for (int i = 0; i < n - m; i++) {
      // 전체 요소개수에서 패턴개수를 뺀 만큼만 반복 -> 그 수가 마지막 비교요소이기 때문
      // i 반복문은 패턴과 비교의 위치를 잡음
      int j = 0;
      // j는 전체와 패턴의 요소 하나하나를 비교
      
      while (j < m && patternArr[j] == arr[i + j]) {
        // j가 패턴의 개수보다 커지면 안되기때문에 개수만큼만 반복
        // 패턴에서는 j인덱스와 전체에서는 i + j 인덱스의 값이 같은지 판단
        // 같을때 j에 +1 
        j = j + 1;
      }
      
      if (j == m) {
        // j와 패턴 수가 같다는 것은 패턴의 문자열과 완전히 같은 부분이 존재
        // 이 때의 비교했던 위치를 반환
        return true;
      }
   }
   
   return false;
 }

💫  선택 정렬 알고리즘(Selection Sort)

• 전체 배열을 검색하여 현재 요소와 비교하고 컬렉션이 완전히 정렬될 때까지 현재 요소보다 더 작거나 큰 요소(오름차순 또는 내림차순에 따라)를 교환하는 정렬 알고리즘

public int[] SelectionSort(int[] arr) {
    // 주어진 배열을 Selection Sort로 오름차순 정렬
    for (int i = 0; i < arr.length - 1; i++) {
      // 배열의 0번째 인덱스부터 마지막인덱스까지 반복
      // 현재 값 위치에 가장 작은 값을 넣음
      int min = i;
      // 현재 인덱스를 최소값의 인덱스를 나타내는 변수에 할당
      for (int j = i + 1; j < arr.length; j++) {
        // 현재 i에 +1을 j로 반복문을 초기화하고 i 이후의 배열요소과 비교하는 반복문 구성
        if (arr[j] < arr[min]) {
          // j인덱스의 배열 값이 현재 인덱스의 배열 값보다 작다면
          min = j;
          // j 인덱스를 최소를 나타내는 인덱스로 할당
        }
      }
      // 반복문이 끝났을 때 min에는 최소값의 인덱스가 들어있음
      // i값과 최소값을 바꿔 할당
      int temp = arr[i];
      arr[i] = arr[min];
      arr[min] = temp;
    }
    
  // 모든 반복문이 끝나면 정렬된 배열 반환
  return arr;
}

💙 Binary Search Algorithm

• 데이터가 정렬된 상태에서 절반씩 범위를 나눠 분할 정복기법으로 특정한 값을 찾아내는 알고리즘

🤍 동작 과정

• Step 1. 정렬된 배열의 가장 중간 인덱스를 지정한다.
• Step 2. 찾으려고 하는 값이 지정한 중간 인덱스의 값이라면 탐색을 종료하고, 아니라면 Step 3으로 간다.
• Step 3. 찾으려고 하는 값이 중간 인덱스의 값보다 큰 값인지, 작은 값인지 확인한다.
• Step 4. 값이 있는 부분과 값이 없는 부분으로 분리한다.
• Step 5. 값이 있는 부분에서 다시 1단계부터 반복한다.

🤍 When Using of the Binary Search Algorithm

• 정렬된 배열에서 요솟값을 더 효율적으로 검색할 때
• 데이터의 양이 많으면 많을수록 효율이 높아서 정렬된 데이터의 양이 많을 때

⇒ 탐색을 반복할 때마다 탐색 범위가 절반으로 줄어들게 되어, 데이터 양이 많을수록 더 높은 효율을 가짐

🤍 Limit of the Binary Search Algorithm

• 정렬된 배열에만 구현 가능
  • 규모가 작은 배열이라도 정렬이 되어 있지 않다면 정렬을 한 후 Binary Search Algorithm을 사용해도 효율이 낮음

🤍 Where to Use Binary Search Algorithm

대규모의 데이터 검색에 주로 사용

• 사전 검색, 도서관 도서 검색, 대규모 시스템에 대한 리소스 사항 파악, 반도체 테스트 프로그램에서 디지털, 아날로그 레벨을 측정