오늘 TIL 3줄 요약

• 알고리즘은 지시사항을 나열한 것

• 배열은 읽는 속도가 빠르나 삽입,삭제가 느리다

• 배열의 크기가 크고 정렬되어 있다면 이진검색이 선형검색보다 훨씬 효과적이다

TIL (Today I Learned) 날짜

• 2023-08-31

오늘 읽은 범위

• EP22 자료구조와 알고리즘은 필수라고?

• EP23 배열이 뭐죠?

• EP24 알고리즘의 속도는 어떻게 표현할까?

• EP25 검색 알고리즘이 뭐죠?

책에서 기억하고 싶은 내용을 써보세요.

• 알고리즘은 컴퓨터에게 내리는 지시 사항을 나열한 것

  • 네비게이션에 적용하는 패스파인더(pathfinder) 알고리즘

  • 이미지 압축에 적용하는 압축(compression) 알고리즘

• 자료구조는 데이터를 효율적으로 보관하고 찾기 위해 사용

  • 작은 것부터 큰 순서로 정리하는 자료구조

  • 이름표를 붙여서 정리하는 자료구조

  • 데이터가 들어오는 순서대로 정리하는 자료 구조

• 배열

  • 컴퓨터는 배열의 시작 주소와 길이를 알고 있음 → 읽는 속도가 빠름

  • 배열은 맨 앞부터 채워져 있어야 하기 때문에 삽입과 삭제가 느림

  • 배열에 데이터가 꽉 차 있을 때 배열에 데이터를 추가하는 것이 가장 느림

    • 새 배열 만들기 → 복사하기 → 추가하기 과정이 필요함

• 시간복잡도는 프로그램의 작업 속도가 얼마나 빠른지 측정하는 방법

  • Big-O 표기법 : 알고리즘으로 작업을 완료할 때까지 걸리는 절차 수 N을 이용해서 O(N), O(log N)과 같이 표현

  • 시간복잡도가 O(1)인경우 상수 시간(constant time)내에 실행된다고 함

• 검색 알고리즘

  • 선형 검색(Linear search)

    • 배열의 첫번째 값부터 순서대로 비교해서 찾음

    • O(N)

  • 이진 검색(Binary search)

    • 데이터의 정렬이 끝난 배열에서만 사용 가능

    • 배열의 중앙에서 검색을 시작하고 검색하려는 숫자보다 중앙값이 크면 왼쪽, 작으면 오른쪽에서 동일 작업을 반복하여 찾음

    • O(logN)

  • 배열의 크기가 클 때 선형 검색보다 이진 검색이 훨씬 빠름

오늘 읽은 소감은? 떠오르는 생각을 가볍게 적어보세요

• linear ~ binary search~~ 학부 때 기억이 새록새록!

최애 TIL

• inalee님 TIL : 소감을 자세히 쓰신 게 인상적이었습니다.

• jihyun.an123 님 TIL : 큼지막한 글씨와 강조색이 눈에 띄었습니다.

• dlekddl43님 TIL : 페이지번호를 기록하는 것도 좋은 방법이겠다고 생각했습니다.