Implementation - Simulation, Brute-Force, Binary Search

 

 

구현 능력을 보는 대표적인 사례

 

 

시뮬레이션: 문제가 요구하는 복잡한 구현 요구 사항을 하나로 빠트리지 않고 코드로 옮긴다

완전 탐색: 모든 경우의 수를 전부 확인하여 문제를 해결한다

 

 

 

완전 탐색 알고리즘

Brute-Force Algorithm, 시행착오 방법론

 

 

지능형 전략을 사용하지 않고 컴퓨팅 성능에 의존하여 모든 가능성을 시도한다 (최적의 솔루션이 아니다)

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

한계: 문제 복잡도에 민감하다

 

 

🌿 순차 검색

for문을 활용해서 인덱스 0부터 마지막 인덱스까지 차례로 검색

 

🌿 문열 매칭

길이가 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;
      while (j < m && patternArr[j] == arr[i + j]) {
        j = j + 1;
      }
      
      if (j == m) {
        return true;
      }
   }
   return false;
 }

 

🌿 선택 정렬

오름차순: 현재 값이 나머지 값들 중 최소값보다 크다면 교환

public int[] SelectionSort(int[] arr) {

    for (int i = 0; i < arr.length - 1; i++) {

      int min = i;
      
      for (int j = i + 1; j < arr.length; j++) {
        if (arr[j] < arr[min]) {
          min = j;
        }
      }

      int temp = arr[i];
      arr[i] = arr[min];
      arr[min] = temp;
    }

  return arr;
}

 

🌿 버블 정렬

🌿 Tree 구조의 완전 탐색 - BFS, DFS

 

🌿 동적 프로그래밍 - DP

하나의 문제는 단 한 번만 풀도록 한다

· 큰 문제를 작은 문제로 나눌 수 있을 때
· 작은 문제에서 구한 정답이 그것을 포함한 큰 문제에서도 동일할 때

메모이제이션: 작은 문제의 답을 저장해 둔다

//DP를 활용하여 작성한 피보나치 수열
public class Main {
    public static void main(String[] args) {

        System.out.println(dp(30));
    }

    static int[] arr = new int[100]; //메모이제이션, 기본값 0

    static int dp (int x) {

        if (x == 1) return 1;
        if (x == 2) return 1;
        if (arr[x] != 0) return arr[x]; //기본값이 0이 아니면 이미 저장된 값 반환

        arr[x] = dp(x - 1) + dp(x - 2); //계산을 거치면 저장해 둔다
        return arr[x];
    }
}

/**
 * 만약 1, 2, 5원으로 10원을 만드는 경우의 수
 *    1  2  3  4  5  6  7  8  9  10
 * 1  1 "1" 1  1  1  1  1  1  1   1
 * 2  0 "1" 1  2  2  3  3  4  4   5
 * 5  0  0  0  0  1  1 "2" 2  3   4
 *    1  2  2  3  4  5  6  7  8  10
 * -> 예를 들어 5원으로 7원을 만드는 경우의 수는 5(=7-2)원을 만드는 경우의 수와 같다
 *    2원을 만드는 경우의 수에 5원만 더하면 되기 때문!
 */

 

+

Brute Force vs Dynamic Programing
Closet-Pair Problems by Brute Force
Convex-Hull Problems by Brute Force

 

 

탐색 알고리즘
Linear Search Algorithm(선형 탐색)
Binary Search Algorithm(이진 탐색)
Hash Search Algorithm(해시 탐색)

 

 

이진 탐색 알고리즘

Binary Search Algorithm

 

 

대규모의 데이터 검색
사전 검색, 도서 검색, 대규모 시스템 리소스 파악(부하 테스트 처리 CPU 양 파악), 반도체 테스트 프로그램

 

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

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

· O(logn), 데이터 양이 적고, 앞쪽에 위치한 데이터를 탐색할 때는 Linear Search가 빠르다

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

 

Binary Search Tree(BST)와는 다르다!

Tree: 하나의 노드가 두 개의 하위 트리를 가지는 이진 트리로 이루어진 자료구조
왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

Algorithm: 해결 방법

 

+

Linear Search Algorithm
Hash Search Algorithm
Divide-and-conquer algorithm
Binary Tree vs Binary Search Tree
Binary Search Algorithm vs Binary Search Tree