[TIL]20220528

CS 스터디

챕터 18: 알고리즘과 초콜릿 케이크 레시피

챕터 19: 반에서 가장 키 큰사람 찾기: 선형 알고리즘

알고리즘

• 세심하고, 정확하고 명료하게 작성된, 결과를 정확하게 계산되도록 보장된 일련의 단계
• 각 단계는 기본적인 연산으로 표현되어 있고 연산의 의미는 완전하게 명시됨
  • 모든 가능한 상황을 다루어야 하며, 다음에 무엇을 해야할지 모르는 상황이 발생하면 안된다.
  • 알고리즘을 이루는 모든 구성 요소가 애매하거나 모호한 부분이 있으면 안됨!
  • 인간의 언어를 컴퓨터도 이해할 수 있을 정도로 단계를 명확하고 상세하게 설명해야 한다!
  • 알고리즘은 결국 멈춰야 한다.
• 정확하고 신속한 알고리즘의 설계부터 구현까지 모두 컴퓨터과학, 데이터 분석, 웹 개발 등 모든 소프트웨어 분야에서 매우 중요하다
  • 결국 한정된 자원(메모리, 시간 등)을 효율적으로 사용해야하기 때문이다!
• 코테를 보는 이유 → 주어진 자원을 효율적으로 사용하고 문제 해결 능력을 판단하기 위해 → 효율적인 어플리케이션 개발은 실제 프로젝트에서 매우 중요

선형 알고리즘 (선형 탐색)

• 배열의 맨 앞이나, 맨 뒤부터 순서대로 하나씩 찾아보는 알고리즘!
  • 요소가 직선으로 늘어진 배열에서 원하는 키 값을 갖는 요소를 찾을 때까지 순서대로 탐색
• 계산시간이 데이터의 양에 정비례하거나 선형적으로 비례한다. 
• 최선의 경우 원하는 키 값이 맨 앞에 있음 → O(1)

• 원하는 키 값이 맨 뒤에 있거나 원하는 키 값이 없는 경우 혹은 배열을 끝까지 탐색해야 하는 경우(최대, 최소 판별)인 경우 → O(N)

---

알고리즘 

이진탐색(1)

이진탐색이란?

• 배열이 정렬되어있을 경우, 절반씩 줄여나가면서 탐색하는 기법

 

이진탐색의 효율성

• 1억 개 목록을 선형탐색할 때, 1억 번을 연산해야 한다. 이진탐색으로 찾는다면, 27번 안에 찾을 수 있다.
• import math math.log2(100000000) # 26.575424759098897
• 이진탐색을 위해서는 정렬되어 있어야 한다

 

이진 탐색 구현

def binary_search(nums, target):
    def bs(start, end):
        if start > end:
            return -1

        mid = (start + end) // 2

        if nums[mid] < target:
            return bs(mid + 1, end)
        elif nums[mid] > target:
            return bs(start, mid - 1)
        else:
            return mid

    return bs(0, len(nums) - 1)

 

def binary_search_builtin(nums, target):
    idx = bisect.bisect_left(nums, target)
		# idx == len(nums) 가능하기 떄문.
		"""Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e < x, and all e in
    a[i:] have e >= x.  So if x already appears in the list, a.insert(x) will
    insert just before the leftmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """
    if idx < len(nums) and nums[idx] == target:
        return idx
    else:
        return -1

---

알고리즘 문제

 Binary Search

Intersection of Two Arrays

Search in Rotated Sorted Array

Two Sum II - Input Array Is Sorted

Search a 2D Matrix II

범위를 반씩 좁혀나가는 탐색 (이것이 코딩 테스트다 CH07)부품 찾기 (이것이 코딩 테스트다 CH07)\