Day 7

2023년 2월 23일
에피소드 22 ~ 25

기억하고 싶은 내용

자료구조와 알고리즘

결국 모두 코드/프로그램의 효율성을 위해 필요하다!

알고리즘

컴퓨터에게 내리는 지시사항을 나열한 것

• 패스파인더(pathfinder), 압축(compression) 등

자료구조

데이터를 효율적으로 보관하고 찾기 위해 사용

시간복잡도

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

Big-O 표기법

ex) O(N) => 배열의 길이가 N일 때 총 N번 검색하는 과정이 필요하다

• 상수 시간(constant time) : 이미 실행 횟수가 고정으로 정해진 것
• 이차 시간(quadratic time)

배열

• 읽기: 매우 빠름
  • 컴퓨터는 배열의 시작 주소와 길이를 알고 있기 때문
• 검색: 빠르지 않음
• 삽입: 마지막 < 배열 중간 < 배열 맨 앞 < 꽉 차 있는 배열에 데이터 추가
• 삭제: 삽입과 유사

메모리

컴퓨터의 기억 공간

비휘발성 메모리

ex) 하드디스크

휘발성 메모리

ex) 램(RAM)

RAM (Random Access Memory)
프로그램의 변수, 함수 등이 저장됨
데이터가 저장된 위치와 상관없이 일정하게 안정되고 빠른 접근 속도 보장
like 주소지가 적힌 박스가 많이 있는 창고

검색 알고리즘

선형 검색(linear search)

배열의 맨 처음부터 찾고자 하는 요소를 탐색

이진 검색(binary search)

배열의 중앙값 기준으로 오른쪽/왼쪽 범위로 계속 이동하면서 탐색

• 배열이 클 때 선형 검색보다 매우 효율적
  • 단계마다 배열의 절반을 제외할 수 있으니까!
• 정렬된 배열에서만 사용 가능

읽은 소감

예전에 이론 공부 했던 내용들이 새록새록.. 그때 정리했던 것들도 다시 읽어 봐야겠다. 몸으로는 알고 있지만 설명하는 건 또 다른 영역이니까.. 구어체로 책에서 설명해준 걸 참고해서 기억하면 좋을 것 같다!

오늘 본 TIL

abcdeomdain님