크래프톤정글 2주차; 이분탐색, 분할정복

참고: 부스트코스 CS50 모두를 위한 컴퓨터과학
에드위드 파이썬으로 배우는 알고리즘 기초

검색 알고리즘

1. 검색 알고리즘이란?
2. 선형 검색linear serach
3. 이진 검색binary search
   1. 배열이 정렬되어 있음을 가정(미리 정렬해야함)
   2. 중간 인덱스부터 시작 → 찾고자 하는 값과 비교하며 오른쪽, 왼쪽으로 갈지 결정 → 오른쪽 중간, 왼쪽 중간에서 똑같은 과정 반복
   3. 슈도코드

       If no items
           Return false
       If middle item is 50
           Return true
       Else if 50 < middle item
           Search left half
       Else if 50 > middle item
           Search right half

분할정복 알고리즘 설계

1. 알고리즘 설계 종류
   1. Brute-force (단순무식)
   2. divide-conquer (분할, 정복)
      • 필요하면 통합까지!
      • 탑다운 방식
      • 작은 입력 사례를 각각 정복하는데 작은 입력 사례가 충분히 작지 않으면 재귀 호출
   3. greedy(탐욕법): 가장 비효율적인 분할정복 알고리즘
   4. dynamic programming(동적계획): 바텀업 개념