[Java Algorithm] 탐욕 알고리즘(Greedy)

탐욕 알고리즘(Greedy)

선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.

항상 최적의 결과를 도출하는 것은 아니지만, 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다.(근사 알고리즘)

 

탐욕 알고리즘으로 문제를 해결하는 방법

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

 

탐욕 알고리즘을 적용하려면 해결해야 하는 문제

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

---

구현(implementation) - 시뮬레이션(simulation)

알고리즘 문제를 푼다는 것은, '내가 생각한 문제 해결 과정을 컴퓨팅 사고로 변환하여 코드로 구현'한다는 것과 같다.

문제 해결 과정은 여러 개의 카테고리로 묶여진다. 예를 들어, 숫자들의 순서를 조정하는 것을 정렬이라고 부르고, 그래프 탐색의 경우 방식에 따라 DFS, BFS로 나뉜다. 이처럼 각 카테고리는 원하는 의도가 분명히 있다.

 

본인이 선택한 프로그래밍 언어의 문법을 정확히 알고 있어야 하며, 문제의 조건에 전부 부합하는 코드를 실수 없이 빠르게 작성하는 것을 구현 문제, 구현 유형이라고 통칭할 수 있다.

 

구현 능력을 보는 대표적인 사례는 완전 탐색(brute force)과 시뮬레이션(simulation)이 있다.

• 완전 탐색: 가능한 모든 경우의 수를 전부 확인하여 문제를 푸는 방식을 뜻한다.
• 시뮬레이션: 문제에서 요구하는 복잡한 구현 요구 사항을 하나도 빠트리지 않고 코드로 옮기는 것이다.

---

완전 탐색 알고리즘(Brute-Force Algorithm)

컴퓨터 과학에서 Brute Force는 시행착오 방법론을 말한다. 암호학에서도 이 용어를 사용하며 Brute Force Attack이라고 부른다. 특정한 암호를 풀기 위해서 모든 값을 대입하는 방법을 말한다.

 

 

BFA란?

• 순수한 컴퓨팅 성능에 의존하여 모든 가능성을 시도하여 문제를 해결하는 방법이다.
• 데이터의 범위가 커질수록 비효율적이다.

주로 사용되는 경우?

• 프로세스 속도를 높이는데 사용할 수 있는 다른 알고리즘이 없을 때
• 문제를  해결하는 여러 솔루션이 있고 각 솔루션을 확인해야 할 때

 

BFA 사용의 예

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

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

public boolean SequentialSearch2(int[] arr, int K) {
 // 입력: n개의 요소를 갖는 배열 A와 검색 키 K
 
 boolean result = false; // 결과를 저장할 boolean, 초기값 false
  for(int i = 0; i < arr.length; i++) {
    if(arr[i] == K) {
      result = true;
    }
  }
  return result;
}
       
//배열을 순회하는 도중에, 해당하는 값이 발견되더라도 배열을 모두 순회한 이후에 결과값을 리턴

 

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

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

public boolean BruteForceStringMatch(int[] arr, int[] patternArr) {
    int n = arr.length; // 전체 문자열
    int m = patternArr.length; // 찾을 문자열 패턴
    
    // 패턴의 위치를 찾는 반복문. 전체 문자열에서 문자열 패턴의 개수를 뺀 만큼 반복
    for (int i = 0; i < n - m; i++) {

      int j = 0; // 패턴의 요소를 하나씩 비교할 변수

      // 패턴에서는 j인덱스와 전체에서는 i + j 인덱스의 값이 같은지 판단합니다.
      while (j < m && patternArr[j] == arr[i + j]) {

        j = j + 1; // 같을때 j에 +1 합니다.
      }
      if (j == m) { // j와 패턴 수가 같다는 것은 패턴의 문자열과 완전히 같은 부분이 존재한다는 의미
        return true;
      }
   }
   return false;
 }

 

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

전체 배열을 검색하여 현재 요소와 비교하며 완전히 정렬(오름차 or 내림차)될 때까지 교환하는 정렬 알고리즘이다.

public int[] SelectionSort(int[] arr) {
    // 주어진 배열을 Selection Sort로 오름차순 정렬합니다.
    // 입력: 정렬 가능한 요소의 배열 A
    // 출력: 오름차순으로 정렬된 배열
    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)

탐색 알고리즘은 크게 3가지 Linear Search Algorithm(선형 탐색 알고리즘), Binary Search Algorithm(이진 탐색 알고리즘), Hash Search Algorithm(해시 탐색 알고리즘)이 있다. 이 중에서 Binary Search Algorithm 에 대해 알아보자.

 

Binary Search Algorithm이란?

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

시간복잡도는 O(log n)로, 빠른 편이지만 항상 효율이 좋은 것은 아니다. (데이터의 양이 적고, 찾을 값이 끝쪽에 위치한 경우)

 

주로 사용하는 경우?

• 데이터가 많을 경우 -> 대규모 데이터 검색
• 정렬된 배열에서 요소값을 찾는 경우

한계점

• 배열에만 구현할 수 있다.
• 정렬되어 있어야만 구현할 수 있다.

동작 순서

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

 

 

Linear Search Algorihm와의 비교

같은 값 182를 찾는데 Linear Search의 경우 11번의 과정이 필요하다.