노개북 - DAY7. TIL 작성

🗓️ 2024.02.15 목

Today I Learned

 

DAY7

📌 오늘 읽은 범위: 22 - 25

 

 

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

• 알고리즘

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

패스파인더 알고리즘 : 목적지까지 최대한 빨리 가는 방법
압축 알고리즘 : 이미지를 최대한 덜 손상하면서도 용량을 효율적으로 줄일 수 있는 알고리즘
             (ex. PNG, JPG)

 

 

• 자료구조

데이터를 효율적으로 보관하고 찾기 위해 사용
어떤 자료구조를 사용하는지에 따라 프로그램 속도가 빨라지거나 느려짐

• 데이터 크기 기준 : 데이터를 작은 것부터 큰 순서로 정리하는 자료구조 
• 검색을 위한 인덱스 기준 : 이름표를 붙여서 정리하는 자료구조 
• 생성 시간 기준 : 데이터가 들어오는 순서로 정리하는 자료구조 

 

 

• 시간 복잡도

프로그램의 작업 속도가 얼마나 빠른지 측정하는 방법 
작업이 얼마나 많은 단계를 거치는지를 측정

알고리즘으로 작업을 완료할 떄가지 걸리는 절차 수 N을 이용해서 O(N), O(log N)과 같이 표현하는데,
이것을 "빅오(Big-O)" 표기법 이라고 한다.

 

 

예1)

배열 arr의 첫 번째 데이터를 출력하는 코드
def print_first(arr):
	print(arr[0])

 

배열의 길이와 상관없이 이 함수는 딱 한 번 실행하고 끝날 것이다. 첫 번째 데이터만 출력하는 함수이기 때문! 

 

배열의 길이가 10 이거나 100이라도 이 함수는 단 한 번 실행!

 => 시간 복잡도 O(1) 

상수 시간 내에 실행된다 라고 이야기 할 수 있다.

 

*상수 시간*
실행 횟수가 고정으로 정해진 것

 

 

 

예2)

배열 arr의 첫 번째 데이터를 2번 출력하는 코드
def print_first(arr):
    print(arr[0])
    print(arr[0])

 

예1과 달라진 점은 그냥 배열의 첫 번째 데이터를 2번 출력한다는 것이다.

그러면 '이 작업을 수행하려면 단계가 2번 필요할 것이고, 시간 복잡도는 O(2)라고 쓰면 될 것 같다' 라고 생각하지만! ❌

 

Big-O는 이 경우에도 O(1) 이라고 표현한다.

Big-O는 실행 단계에 영향을 주는 요소만 보기 때문이다. 

 

 

예3)

위의 코드에서 arr의 모든 데이터를 출력한다면?

배열의 길이에 따라 실행 시간이 달라진다. 배열 길이가 10이면 10번, 100이면 100번 

이럴 때 시간 복잡도는 O(N)이다.

 

 

 

• 검색 알고리즘

선형 검색 : 처음부터 끝까지 하나씩 순서대로 비교하며 검색하므로 배열의 길이가 길어지면 검색 시간도 길어진다. 
y = x 형태


이진 검색 : 배열의 중앙, 즉 중간 값 부터 검색을 시작하며, 데이터의 정렬이 끝난 배열에서만 사용 가능하다. 
y = logx 형태

단계마다 배열의 절반을 제외할 수 있기 때문에 거대한 배열을 다룰 때 효과적이다.

* 정렬이 끝난 배열이란?
  데이터가 순서대로 정렬된 상태를 말한다.
  보기 좋게 정렬된 배열! 
  ex) 1,2,3,4,5 or 5,4,3,2,1

 

 

👀 읽은 소감 

아직까지 알고리즘 자료구조에 대해 부족한게 많다고 생각한다.

이해하기 쉽도록 책에 설명이 되어 있지만 반복적으로 읽고, 더 많은 정보를 습득해야겠다.