[노개북 - Day 7 ] 23.01.19

✍️ TIL (Today I Learned)

• 자료구조 && 알고리즘
• 배열
• 알고리즘 속도 표현
• 검색 알고리즘

---

📑 오늘 읽은 범위

에피소드 22 ~ 에피소드 25

---

🔖 책에서 기억하고 싶은 내용

• 자료구조 && 알고리즘
  • 코드를 효율적으로 만들기 위해
  • 알고리즘 : 컴퓨터에게 내리는 지시 사항 나열
    • 패스파인더(pathfinder)알고리즘 : 목적지까지 최대한 빨리 가는 방법,
    • 압축(compression)알고리즘 : 이미지를 덜 손상시키면서 용량을 효율적으로 줄일 수 있는 알고리즘(png, jpg)
  • 자료구조 : 데이터를 효율적으로 보관, 찾기 위해
    • 데이터를 다루는 방식(자료구조)에 따라 프로그램 속도가 달라짐
• 배열
  • 시간 복잡도 : 작업 속도 → 실제 시간을 재는 것보다 몇 단계를 거치느냐에 따라 다름
  • 메모리 : 컴퓨터의 기억공간
    • 휘발성 메모리 : 컴퓨터 전원을 껐을 때 저장한 값이 사라짐,
      • ex) 램(RAM, random access memory) : 프로그램에 필요한 데이터가 저장(프로그램 변수, 함수)
    • 비휘발성 메모리 : 컴퓨터 전원을 껐을 때도 저장한 값이 남아 있음
      • ex) 하드 드라이브(C, D)
  • RAM의 속도 : 데이터 저장 위치와 상관 없이 일정한 접근 속도 보장, 데이터에 접근하는 속도가 안정적, 빠름 → 램 = 주소지가 적힌 박스가 많이 있는 창고, 박스에는 데이터 1개 → 박스마다 주소가 있어서 데이터 찾는 속도 빠름
  • RAM의 관점에서 배열 : 배열의 길이를 알려주면 박스가 길이만큼 붙은 모양으로 배열 공간이 생긴다.
    • 특징 1 : 배열을 읽는 속도는 1단계 굉장히 빠름, 0부터 시작
    • 특징 2 : 배열 검색은 박스 속 데이터를 확인 → 빠르지 않음
    • 특징 3 : 배열에 데이터 삽입
      • 맨 마지막 데이터 추가 : 컴퓨터는 배열의 길이와 시작점을 기억하고 있어 끝에 데이터 추가
      • 중간에 데이터 추가 : 넣고 싶은 위치에서 뒤에 있는 데이터들을 뒤로 옮겨서 공간 확보 후 데이터 추가
      • 배열에 데이터가 꽉 차 있을 때 : 새 배열 만들기(더 큰 배열) → 복사하기 → 추가하기
    • 특징 4 : 배열 데이터 삭제 → 삽입하는 원리와 비슷, 배열은 맨 앞부터 채워야 해서 마지막 데이터 삭제가 쉽고 맨 앞 데이터 삭제가 어려움
• 알고리즘 속도 표현
  • Big-O : 알고리즘으로 작업을 완료할 때까지 걸리는 절차 수 N을 사용해 O(N), O(log N)과 같이 표현
  • 선형 알고리즘 : 배열을 앞에서부터 하나씩 검색 → 배열 길이 N, 절차 N → O(N)
  • 시간 복잡도를 표기하는 방법 → Big-O 표기법 → 장점 : 설명 간결, 알고리즘 분석 빠르게

  const arr = [1, 2, 3];
  // O(1) : 배열의 길이와 관련 없이 한 번 실행, O(2)라고 표현하지 않음 단계별로 표시
  console.log(arr[0]);
  console.log(arr[0]);
  
  // O(N) : 배열의 길이에 비례
  for(const n of arr){
  console.log(n)
  }
  
  // O(N^2) 배열의 길이에 제곱배로 느려짐
  for(let i=0;i<n;i++){
  	for(let j=0;j<n;j++){
  		console.log(i,n)
  	}
  }
  
  

• 검색 알고리즘
  • 선형 검색(linear search)
    • y = x
  • 이진 검색(binary search)
    • 데이터 정렬이 끝난 배열에만 사용할 수 있다.
    • 이런 특정 알고리즘은 특정 자료구조에서만 사용할 수 있다.
    • 중앙값을 기준으로 검색 시작 우리가 찾는 값(x)이 중앙값(middle)과 비교 시
      • x === middle return middle
      • x > middle 오른쪽 검색
      • x < middle 왼쪽 검색
    • 속도가 빠름 → 배열의 절반을 제외할 수 있어서 → y = log x
    • 거대한 배열을 다룰 때 효과적