IT 5분 잡학사전 #5

TIL 날짜 및 읽은 범위

• 2023.01.18
• Ep.22 ~ Ep.25

에피소드 22 : 자료구조와 알고리즘이 필수라고 ?

알고리즘이란 ? 컴퓨터에게 내리는 지시 사항을 나열한 것

알고리즘은 컴퓨터에게 내리는 지시 사항을 나열한 거야
등교 준비하기 알고리즘
1. 이부자리에서 일어나기
2.가방 챙기기
3.머리 정돈하기
4. 교복으로 갈아입기
5. 세수, 양치하기
6. 집 나서기
등교 준비하기 알고리즘 중에서도 효율설이 더 좋은 것도 있어
다른 사람보다 빠르게 학교에 도착할 수 있을거야!
즉, 등교 속도가 빨라질 거야. 이건 컴퓨터도 마찬가지야!

다양한 컴퓨터 알고리즘
예로는 지도 앱을 생각해봐. 바로 목적지까지 최대한 빨리 가는 방법을 알려 주는 거겠지!
그 기능을 구현하기 위해 패스파인더 (pathfinder) 알고리즘을 사용해
다른 예는 압축 (compression) 알고리즘이야
이미지를 최대한 덜 손상하면서도 용량을 효율적으로 줄일 수 있는 알고리즘이지

데이터를 효율적으로 보관하고 찾기 위한 자료 구조

데이터가 마구잡이로 보관되어 있다면 어떨까?
개발 효율을 크게 떨어뜨릴거야
데이터를 보기 좋게 보관하는 것을 넘어서 찾기 좋게 제대로 보관해야돼
자료구조에도 여러 가지 방식이 있어
데이터 크기 기준 : 데이터를 작은 것부터 큰 순서로 정리하는 자료 구조
검색을 위한 인덱스 기준 : 이름표를 붙여서 정리하는 자료 구조
생성 시간 기준 : 데이터가 들어오는 순서로 정리하는 자료 구조
프로그램의 목적이 다양하기 때문에 자료 구조의 방식도 다양해
만약 데이터 크기에 따른 데이터 사용을 목적으로 하는 프로그램이라면 데이터 크기 순서로 정리하는 자료구조를 쓰면 효율적일거야

에피소드 23 : 배열이 뭐죠?

시간 복잡도는 작업 속도!

시간 복잡도는 프로그램의 작업 속도가 얼마나 빠른지 측정하는 방법
시간 복잡도는 '준비-시-작!' 뭐 이런 식으로 실제 시간을 재지 않아
대신 작업이 얼마나 많은 단계를 거치는지를 측정해

메모리 간단 설명

메모리: 컴퓨터의 기억 공간
비휘발성 메모리: 컴퓨터의 하드 드라이브, 컴퓨터를 껐다가 다시 켜도 데이터 존재
휘발성 메모리: 대표적으로 "램" (RAM: random access memory), 컴퓨터를 끄면 램에 있는 데이터는 사라짐, 프로그램에 필요한 데이터가 저장됨

램과 함께 생각하는 배열

배열의 특징

1. 배열을 읽는 방법과 속도
   배열은 0부터 숫자 매긴다
   배열에서 데이터를 찾는 속도가 빠르다 (몇 번째 데이터를 보라고 하기 때문, 1단계 알고리즘)
2. 배열을 검색하는 원리와 속도
   배열에서 검색과정은 박스를 모두 뒤지는 방법으로 진행
   박스를 모두 열어 보고 들어 있는 데이터를 확인
   검색은 읽기보다 시간이 많이 필요
   데이터를 찾는 방식을 선형 검색 (linear search)으로 한정
3. 배열에 데이터를 삽입하는 원리와 속도
   배열의 길이 5 , 현재 아이템의 수 4
   a. 배열에 데이터를 삽입, 맨 마지막에 아이템을 추가 : 컴퓨터는 배열이 어디서 시작하는지, 배열의 길이는 얼마인지 기억하고 있어서 배열의 시작점을 찾고 길이만큼 뒤로 가서(끝에) 새 아이템을 추가 한다
   b. 배열 중간에 아이템을 추가 : 해당 위치와 그 뒤의 아이템을 뒤로 옮긴 후 새 아이템을 추가한다
   c. 배열에 데이터가 모두 차 있을 때 : 새 배열 만들기 > 복사하기 > 추가하기
4. 배열에서 데이터를 삭제하는 원리와 속도
   삽입하는 원리와 비슷
   배열은 맨 앞으로 차곡 차곡 채워야 함 > 중간 데이터를 삭제하면 뒤쪽 데이터를 앞으로 다 끌어당김

배열의 원리

• 배열은 램에 줄줄이 이어진 형태로 공간을 차지하고 있다
• 컴퓨터는 배열의 시작 주소와 길이를 알고 있다. 그래서 배열은 읽는 속도가 아주 빠르다
• 배열은 맨 앞으로 차곡 차곡 채워져 있어야 한다. 그래서 배열은 삽입과 삭제가 느리다

에피소드 24 : 알고리즘의 속도는 어떻게 표현할까 ?

빅오(Big-O) 표기법: 시간 복잡도를 이야기할 때는 알고리즘으로 작업을 완료할 때까지 걸리는 절차 수 N을 이용해서 O(N), O(log N)과 같이 표현

알고리즘의 속도를 표현하는 방법은 ? Big-O

선형 검색 알고리즘은 배열을 앞에서 부터 하나씩 검색하고, 그래서 배열 크기가 커지면 검색 시간도 정비례로 커진다고 했어
배열의 길이를 N이라고 하면 검색 횟수는 최대 N이 되는거지
그리고 이때 시간 복잡도는 O(N)과 같이 표현해
"선형 검색 알고리즘의 시간 복잡도는 O(N)이다"

def print_first(arr):
	print(arr[0])

배열의 길이와 상관없이 이 함수는 딱 한번 실행하고 끝날거야. 왜냐하면 첫 번째 데이터만 출력하는 함수니까!
배열의 길이가 10이라도, 100이라도 이 함수는 단 한 번 실행하지
그래서 이 함수의 시간 복잡도는 O(1)이야
이걸 '상수 시간(constant time)내에 실행된다 라고 해
또한 Big-O는 실행 단계에 영향을 주는 요소만 봐

def print_all(arr):
	for n in arr:
    	print(n)

이 코드는 배열의 길이에 따라 실행시간이 달라져
배열 길이가 10이면 10번을, 100이면 100번을 출력하겠지
그래서 이럴 때 시간 복잡도는 O(N)이야

def print_twice(arr):
	for n in arr
    	for x in arr
        	print(x, n)

시간 복잡도로 이차 시간(quadratic time)이 있어
이차 시간은 중첩 반복문이 있을 때 발생해
배열 길이가 길어질수록 작업 속도는 제곱배로 느려져
그리고 이걸 Big-O로 나타내면 $O({N^2})$ 이야
제곱배 (N*N)를 그대로 표현

에피소드 25 : 검색 알고리즘이 뭐죠?

검색 알고리즘

선형 검색 알고리즘: 가장 자연스러운 검색 방법, 배열의 길이가 길어지면 검색 시간도 길어짐
이진 검색 알고리즘: 배열의 크기가 클 때 선형 검색보다 훨씬 좋은 알고리즘, 데이터의 정렬이 끝난 배열에서만 사용할 수 있다
정렬이 끝난 배열: 데이터가 순서대로 정렬된 상태

이진 검색 알고리즘 ?

1. 이진 검색은 배열의 중앙에서 검색을 시작
   찾으려는 숫자보다 중앙값이 작으면 ?
2. 중앙값 기준으로 왼쪽 배열의 숫자는 삭제
3. 중앙값을 다시 정하고, 찾으려는 숫자와 중앙값을 비교
4. 중앙값을 기준으로 점프!
   이진 검색에서 속도가 빠른 이유는 단계마다 배열의 절반을 제외할 수 있기 때문이야
   이진 검색에서 배열 길이와 검색 시간 y = log x 의 그래프 형태를 보여

이진 검색 정리

• 이진 검색 알고리즘은 거대한 배열을 다룰 때 효과적이다
• 이진 검색 알고리즘은 사용하고 싶다면 배열은 항상 정렬되어 있어야 한다

오늘 읽은 소감은?

"복잡하고 어려워서 시작하기 어려웠던 알고리즘을 예시를 통해 가볍고 재미있게 배웠다. 오히려 더 자세히 알고 싶다는 호기심까지 생겼다. 같이 알려준 유튜브까지 보니 더 이해가 잘 되었다."

관련 유튜브 영상 (노마드 코더 Nomad Coders)

알고리즘 시리즈 영상