Day 7 (2023.01.19)
읽은 범위
EP22 ~ EP25
책에서 기억하고 싶은 내용 및 요약
EP22 자료구조와 알고리즘은 필수라고?
- 알고리즘은 컴퓨터에게 내리는 지시 사항을 나열한 것이다. (p.133)
- 패스파인더 알고리즘, 압축 알고리즘 같은 다양한 알고리즘이 있다.
- 데이터를 보기 좋게 보관하는 것을 넘어서 찾기 좋게 제대로 보관하기 위해 자료구조를 공부한다.
- 데이터 크기 기준, 검색을 위한 인덱스 기준, 생성 시간 기준 자료구조도 여러 가지 방식이 있다.
EP23 배열이 뭐죠?
- 배열은 0번째부터 시작하며, 데이터의 주소를 찾아가 데이터의 값을 찾는 방식이다.
- 예를 들어 "3번째 주소를 찾아줘" 라고 한다면 0번째부터 순서대로 쭉 3번째 주소를 찾는다. 이 검색 방식을 선형 검색(linear seach)이라고한다.
- 시간 복잡도는 작업이 얼마나 많은 단계를 거치는지를 측정한다.
EP24 알고리즘의 속도는 어떻게 표현할까?
- 알고리즘으로 작업을 완료할 때까지 걸리는 절차 수 N 을 이용해서 O(N), O(log N)과 같이 표현하며, 이를 빅오(Big-O)표기법이라고 한다.
def print_first(arr):
print(arr[0])- 배열에서 첫번째 데이터를 출력하는 함수가 있다고 친다면 이는 한번 실행되고 끝나기에 이 함수의 시간복잡도는 O(1)이다. 이걸 '상수(constant time) 내에 실행된다' 라고 이야기하기도 한다.
- Big-O는 실행 단계에 영향을 주는 요소만 본다. (p.147)
- 또 다른 시간 복잡도로 이차 시간(quadratic time)이 있다. (p.148)
EP25 검색 알고리즘이 뭐죠?
- 선형 검색 알고리즘이란 찾는 데이터가 N 일때 맨처음 배열부터 검색을 시작하여 배열의 데이터가 N 이 나올때까지 검색한다.
- 이진 검색 알고리즘이란 순서대로 정렬되있는 배열의 중앙에서 검색을 시작해 중앙값보다 찾는 값이 작은지 큰지 비교한 후 작으면 중앙값 기준 왼쪽으로 검색을 이어가며 여기서 다시 중앙값을 기준으로 비교를 반복하는 알고리즘이다. 큰 데이터에서 값을 검색할 때는 선형 검색 알고리즘보다 효율적이다.
소감 or 궁금한 점
오늘은 데이터의 구조적으로 처음 본 단어들이 많이 나와서 공부할게 많이 생겼다. 특히 시간 복잡도라는 뭔가 어려워보이는 용어가 나왔는데 복습을 하면서 좀 더 깊게 찾아보고 이해해봐야겠다!
TILog