📖 노개북 TIL #06 ep.22~25
📌 기억하고 싶은 내용
ep.22 자료구조와 알고리즘은 필수라고?
알고리즘은 컴퓨터에게 내리는 지시 사항을 나열한 것이다. (133p)
지도 앱에서 목적지까지 최대한 빨리 가는 방법을 알려주는 기능을 구현하기 위해 사용되는 알고리즘은 패스파인더(pathfinder) 알고리즘이다.
이미지를 최대한 덜 손상하면서 용량을 효율적으로 줄일 수 있는 알고리즘은 압축(compression) 알고리즘이다.(134p)
어떤 자료구조를 사용하는지에 따라 프로그램의 속도가 달라진다. 데이터 크기, 검색을 위한 인덱스, 생성 시간 등을 기준으로 하는 방식들이 있다. (136p)
ep.23 배열이 뭐죠?
시간 복잡도는 프로그램의 작업 속도가 얼마나 빠른지 측정하는 방법이다. 이는 실제 작업에 걸리는 시간을 재는 것이 아니라, 작업이 얼마나 많은 단계를 거치는지 측정하는 것이다.(137p)
비휘발성 메모리는 C,D 드라이브 같은 컴퓨터의 하드 드라이브 같은 것이다. 이는 전원을 껐다가 켜도 데이터가 남아있다. 휘발성 메모리는 대표적으로 RAM이 있다. 이는 프로그램에 필요한 데이터가 저장되고, 전원을 끄면 데이터가 사라진다.(138p)
램에는 데이터마다 일정한 주소가 지정되어 있어서 데이터에 접근하는 속도가 매우 안정되고 빠르다. (139p)
배열은 램에 줄지어 이어진 형태로 공간을 차지하고 있다. 컴퓨터는 배열의 시작주소와 길이를 알고 있어서 읽는 속도가 빠르다. 배열은 맨 앞부터 채워져있어야 해서 삽입과 삭제가 느리다. (144p)
ep.24 알고리즘의 속도는 어떻게 표현할까?
시간 복잡도를 이야기할 때는 알고리즘으로 작업을 완료할 때까지 걸리는 절차 수 N을 이용해서 O(N), O(log N)과 같이 표현한다. 이를 빅오(Big-O) 표기법이라고 한다.(146p)
배열의 길이와 상관없이 딱 한번만 실행하고 끝나는 함수가 있다면, 이 함수의 시간복잡도는 O(1)이고, 이처럼 실행횟수가 고정으로 정해진 것을 상수 시간(constant time) 내에 실행된다고 한다. (146p)
또 다른 시간 복잡도로 이차 시간(quadratic time)이 있는데, 이는 중첩 반복문이 있을 때 발생한다. 이를 Big-O로 나타내면 O(N²)이다. (149p)
ep.25 검색 알고리즘이 뭐죠?
선형 검색 알고리즘이란 맨 처음부터 원하는 데이터가 나올때까지 검색을 하는 방법이다. 이 때 최악의 경우에 시간복잡도는 O(N)이다. (151p)
이진 검색 알고리즘이란 중간의 값부터 시작해 찾고자 하는 값이 포함되지 않은 부분을 제외해가며 검색한다. 다만 이때 데이터는 정렬된 상태여야 한다. 이 방법을 사용하면 최악의 경우에 시간복잡도는 O(log N)이 된다. (153p)
💬 오늘의 소감
같은 기능이더라도 시간복잡도는 다를 수 있다
지금까지 알고리즘 문제를 풀거나, 프로젝트를 진행하면서 어떤 기능을 구현할 때 시간복잡도라는 개념은 신경쓰지 않았다. 그저 정답을 맞추거나, 기능이 정상적으로 작동하는지에 초점을 맞췄던 것 같다. 이제는 시간복잡도라는 개념을 알게되었으니, 이 부분까지 고려해서 코드를 작성할 수 있도록 노력하지않을까 싶다.
🔍 궁금하거나 잘 이해되지 않는 내용
ep.24 알고리즘의 속도는 어떻게 표현할까?
이 코드는 배열의 첫번째 데이터를 두 번 출력하는 코드이다.
def print_first(arr):
print(arr[0])
print(arr[0])이때 시간복잡도가 O(2)가 아니라 O(1)이라고 하는데, Big-O는 실행 단계에 영향을 주는 요소만 보기 때문이라고 한다. 이 부분에 대해서는 잘 이해가 가지 않아 더 공부할 예정이다.
✅ 오늘의 미션
나의 최애 북 TIL 선정하기
세 TIL 모두 가독성이 좋고, 잘 정리되어 있어서 책을 읽지 않은 사람들이 보아도 내용을 잘 이해할 수 있을 것 같아 최애 TIL로 선정하게 되었다. 같은 내용을 읽고도 다른 생각을 떠올릴 수 있다는 점이 흥미로웠다.
📓 참고
