[취준 | 노개북] IT 5분 잡학사전 - DAY7

TIL 3줄 요약

• 효율적인 코드를 작성하기 위해서는 자료구조와 알고리즘 학습이 필수!
• 램은 휘발성 메모리이며 배열 형태로 구성되어 있다.
• 알고리즘의 속도를 표현하는 방법은 시간 복잡도 표기법 Big-O

---

TIL 날짜
2023. 02. 23

오늘 읽은 범위

에피소드 22: 자료구조와 알고리즘은 필수라고?

에피소드 23: 배열이 뭐죠?

에피소드 24: 알고리즘의 속도는 어떻게 표현할까?

에피소드 25: 검색 알고리즘이 뭐죠?

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

• 코드를 효율적으로 만들기 위해서는 알고리즘과 자료구조에 대해 배워야 한다.
  • 알고리즘 : 컴퓨터에게 내리는 지시 사항을 나열한 것
  • 자료구조 : 데이터를 효율적으로 보관하고 찾는 방식이며 여러 방식이 존재한다.
    • 검색을 위한 인덱스 기준
    • 생성 시간 기준
    • 데이터 크기 수준

• 메모리는 컴퓨터의 기억 공간을 뜻하며 비휘발성 메모리 (하드 드라이브)와 휘발성 메모리 (램)이 존재한다.

• 램은 배열로 구성되어 있어 데이터가 저장된 위치와 상관 없이 일정 접근 속도를 보장한다. 그리고 데이터에 접근하는 속도가 안정되고 빠르다.

• 배열의 특징

  • 배열은 램이 줄줄이 이어진 형태로 공간을 차지하고 있다.
  • 컴퓨터는 배열의 시작 주소와 길이를 알고 있어서 읽는 속도가 빠르다.
  • 선형 검색(linear search)로 0번 부터 모든 위치를 검색해서 속도가 느리다.
  • 배열은 맨 앞부터 채워져 있어야 한다. 그래서 배열은 삽입과 삭제가 느리다.

• 알고리즘의 속도를 표현하는 방법은 Big-O

  • 알고리즘으로 작업을 완료할 때까지 걸리는 절차수 N을 이용해서 O(N), O(log N)으로 표현
  • "선형 검색 알고리즘의 시간 복잡도는 O(N)이다"

• 시간 복잡도 예시 및 종류

  // 시간 복잡도 O(1), Big-O는 실행 단계에 영향을 주는 요소만 확인
  
  function print_first(arr) {
    console.log(arr[0])
  }
  
  function print_first(arr) {
    console.log(arr[0])
  }

  // 배열 arr의 모든 데이터를 출력 하는 코드 시간 복잡도 : O(N)
  
  function print_all(arr) {
    for (let i of arr){
      console.log(arr[i])
    }
  }
  

  // 이차 시간(Quadratic time) : O(N^2)
  
  function print_twice(arr) {
    for (let i of arr) {
      for (let j of arr) {
        console.log(arr[i]);
      }
    }
  }

• 검색 알고리즘

  • 선형 검색 (Linear Search)

    • 맨 처음 배열 부터 검색을 시작한다.
    • 배열의 길이가 길어지는 만큼 검색 시간도 길어진다.
    • y = x

  • 이진 알고리즘(Binary Search)

    • 데이터 정렬이 끝난 배여레서만 사용할 수 있다.
    • 배열 중앙에서 검색을 시작한다.
    • 배열 길이가 길어저도 검색 시간이 커지지 않는다.
    • y = log x

오늘 읽은 소감은? 떠오르는 생각을 가볍게 적어보세요
더 나은 개발자가 되기 위해서는 "자료구조 와 알고리즘"에 대한 학습이 필요할 것 같다.