세상엔 수많은 문제가 있다(컴퓨터 연산문제...)
각 문제마다 해결 과정이 다 다르지만, 여러개의 카테고리로 묶여진다..
각 카테고리는 원하는 의도가 분명히 있고, 해결하는 것이 목표이다..

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

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

시뮬레이션(Simulation)

• 시뮬레이션은 모든 과정과 조건이 제시되어, 그 과정을 거친 결과가 무엇인지 확인하는 유형
  • 로직 그대로 작성하면 되어서 문제 해결을 떠올리긴 쉬울 수 있으나, 길고 자세하여 코드구현이 까다로울 수 있음.

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

• 무차별 대입 방법을 나타내는 알고리즘
• 모든 가능성을 시도하여 문제를 해결하는 방법
• Brute Force는 최적의 솔루션이 아니라는 것을 의미하기도 한다.
• 공간복잡도와 시간복잡도의 요소를 고려하지 않음.
• 최악의 시나리오를 취하더라도 솔루션을 찾으려고 하는 방법을 의미

Brute Force Algorithm를 사용하는 경우

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

Brute Force Algorithm의 특징

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

Brute Force Algorithm의 한계

• 문제의 복잡도에 매우 민감한 단점
  • 문제가 복잡해질수록 기하급수적으로 많은 자원을 필요로 하는 비효율적인 알고리즘이 될 가능성 존재.
    _자원이란, 시간 or 컴퓨팅 자원이 될 수도 있다.
• 일반적으로 문제의 규모가 현재 자원으로 충분히 커버가 가능한 경우에 Brute Force Algorithm을 사용
  • 이 경우에 해당하지 않으면, 정확도를 낮추고, 더 효율적인 알고리즘 사용.

Brute Force Algorithm 사용 예

• 배열 안에 특정 값이 존재하는지 검색할 때 인덱스 0부터 마지막 인덱스까지 차례대로 검색 - 순차 검색 알고리즘 (Sequential Search)
• 길이가 n인 전체 문자열과 길이가 m인 문자열 패턴을 포함하는지를 검색 - 문열 매칭 알고리즘 (Brute-Force String Matching)
• 전체 배열을 검색하여 현재 요소와 비교하고 컬렉션이 완전히 정렬될 때까지 현재 요소보다 더 작거나 큰 요소(오름차순 또는 내림차순에 따라)를 교환하는 정렬 알고리즘 - 선택 정렬 알고리즘 (Selection Sort)

이진 탐색 알고리즘(Binary Search Algorithm)

탐색알고리즘

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

• 데이터를 찾을 때 사용하는 방법

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

• 시간복잡도는 O(logn)로 빠른 편이지만 항상 효율이 좋은 것은 아님.

  • 데이터양이 적고, 앞쪽에 위치한 데이터를 탐색할 때는 Linear Search Algorithm이 빠른 구간도 존재..

Binary Search Algorithm의 한계

• 배열에만 구현가능.
• 정렬되어 있어야만 구현가능.
  • 규모가 작은 배열이라도 정렬이 되어 있지 않으면, 정렬하고, Binary Search Algorithm을 사용해도 효율이 높지 않음.

Binary Search Algorithm 사용 예

• 대규모의 데이터 검색에 주로 사용
  • 사전 검색
  • 도서관 도서 검색
  • 대규모 시스템에 대한 리소스 사항 파악
    • 시스템 부하 테스트에서 예측된 부하를 처리하는데 필요한 CPU 양에 대해서 파악할 때 사용합니다.
  • 반도체 테스트 프로그램은 디지털, 아날로그 레벨을 측정하는데 Binary Search Algorithm을 사용합니다.

Binary Search Tree는 Binary Search Algorithm와는 확실히 다름!!
Binary Search Tree는 자료구조를 나타내고, Binary Search Algorithm과는 해결 방법을 나타냄.