[TIL] 알고리즘

🫶🏻 알고리즘 Algorithm

  - 어떠한 입력이 있다면 이 입력에 따라 명령을 명확하게 실행하고 효과적으로 입력에 따른 결과물을 도출

  - 원하는 결과를 도출하기 위해 처리하는 의사결정 과정

---

👍🏻 구현 implementation

  - 문제 해결과정을 컴퓨팅 사고로 변환하여 코드로 구현

  - 구현을 잘 하기 위해서는

    ① 프로그래밍 언어 문법을 정확히 알고 있어야 함

    ② 문제의 조건에 부합하는 코드를 실수 없이 빠르게 작성해야 함

  - 구현 능력 판별 방법 : 완전탐색 (Brute force) & 시뮬레이션 (Simulatiion)

---

 🙏🏻  시뮬레이션 Simulation

    - 문제에서 요구하는 복잡한 요구사항을 빠뜨리지 않고 코드로 옮기는 것

    - 모든 과정과 조건이 제시되어 그 과정에 거친 결과가 무엇인지 확인

---

🙏🏻  완전 탐색 알고리즘 :  BFA

   - 정답은 무조건 구하는 치트키

   - 무차별 대입 방법을 나타내는 알고리즘

   - 가능한 모든 경우의 수를 전부 확인하여 문제를 푸는 방식

   - 순수한 컴퓨팅 성능에 의존하여 모든 가능성을 시도하여 문제 해결

(1) 해결하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산
(2) 가능한 모든 방법을 다 고려
(3) 실제 답을 구할 수 있는지 적용

  💡 무차별 대입 

      - 특정한 암호를 풀기 위해서 모든 값을 대입하는 방법

      - 지능형 전략을 사용하지 않고 수많은 시행 착오를 통해 데이터를 해킹

---

 📍 완전 탐색 알고리즘 종류

  ① 단순 Brute-Force

   - 특별한 방법 대신 단순히 반복문과 조건문으로 모든 경우의 수를 따짐

  ② 비트 마스크

   - 각 원소가 두 가지 상태만을 가질 수 있음

   - 2진수 표현 기법을 활용하는 방법

   - 나올 수 있는 경우의 수가 각각 원소에 포함되거나 포함되지 않는 두 가지 선택으로 구성되는 경우 유용

  ③ 재귀 함수

   - 컴퓨터가 수행할 작업 중 반복되는 작업을 쪼개어 한 작업 실행 후 나머지 작업을 자기 자신에게 호출하여 결과 완성

   - 원소가 포함이 되면 원소를 넣고 함수를 호출하고 포함되지 않으면 그 상태에서 함수 호출

  ④ 순열

   - n개의 값 중에서 r개를 순서대로 뽑는 경우

  ⑤ DFS / BFS (깊이우선/너비우선)

---

 📍완전 탐색 알고리즘 사용

     : 프로세스 속도 높일 때 & 여러 솔루션을 각각 확인해야 할 때 사용

     ① 순차 검색 알고리즘 Sequential Search

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

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

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

     ③ 선택 정렬 알고리즘 Selection Sort

      - 전체 배열을 검색하여 현재 요소와 비교하고 컬렉션이 완전히 정렬될 때까지 요소들끼리 교환하는 알고리즘

      + 그 외 : 버블 정렬 알고리즘, Tree 자료구조의 완전 탐색 알고리즘, 동적 프로그래밍(DP)

---

 📍 완전 탐색 알고리즘 한계 및 주의점

     - 한계 : 문제의 복잡도에 매우 민감

         → 문제가 복잡해질 수록 필요한 자원(시간, 컴퓨팅 자원 등)이 많아짐

     - 주의점 : 입력의 개수(N)이 적을수록 좋음

         → 시간복잡도가 N의 크기가 증가할수록 복잡도 증가

---

👏🏻  탐색 알고리즘

 ① 선형 탐색 알고리즘 Linear Search Algorithm

 ② 이진 탐색 알고리즘 Binary Search Algorithm

 ③ 해시 탐색 알고리즘 Hash search Algorithm

---

🙌🏻  이진 탐색 알고리즘 : BSA

   - 정렬된 배열 또는 리스트에 적합한 고속 탐색 방법

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

   - 시간 복잡도는 O(logN) : 시간이 빠르지만 항상 좋은 건 x

     → 데이터 양이 적고 데이터가 앞쪽에 위치한다면 선형탐색 알고리즘이 적합

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

     → 정렬된 배열에서 요솟값을 더 효율적으로 검색할 때 사용

     → 데이터 양이 많을 때 사용

  * 이진 탐색 트리와(BST) 이진 탐색 알고리즘(BSA) 차이
   (1) 이진 탐색 트리는 자료구조
     - 하나의 노드가 두 개의 하위 노드를 가지는 자료구조
     - 왼쪽에는 작은 값, 오른쪽에는 큰 값이 들어감
   (2) 이진 탐색 알고리즘은 해결방법

---

   📍 이진 탐색 알고리즘 한계

     - 배열에만 구현 가능 & 정렬되어야 구현 가능