6. EP22-25

2023.01.19
였어야하는데 01.21에 작성ㅠㅠ

EP22 자료구조와 알고리즘은 필수라고?

코드를 효율적으로 만들기위해 배워야함

알고리즘

컴퓨터에세 내리는 지시사항을 나열한 것
- 패스파인더 알고리즘 (목적지까지 최대한빠르게 가는 방법)
- 압축 알고리즘 (이미지 손상을 최소화하며 용량을 효율적으로 줄이는 방법)

자료구조

데이터를 효율적으로 보관하고 찾기 위한 것
- 데이터 크기 기준
- 검색을 위한 인덱스 기준
- 데이터 생성 시간 기준

=> 프로그램의 목적에 따라 어떤 자료구조를 사용하는 것이 효율적인지 공부할 필요가 있음

EP23 배열이 뭐죠?

Array

시간 복잡도 = 작업속도

메모리

컴퓨터의 기억공간

비휘발성메모리

하드드라이브
컴퓨터 전원을 꺼도 데이터가 남아있음

휘발성메모리

RAM(random access memory)
전원을 끄면 데이터가 사라짐

램과 함께 생각하는 배열

1. 배열을 읽는 방법과 속도
   - index는 0부터
   - index를 지정해서 읽는 속도는 매우 빠름
2. 배열을 검색하는 원리와 속도
   - linear search : 처음부터 순서대로 하나하나 확인하는 방법
   - (다른 방법도 있지만 일단) 빠르지는 않음
3. 배열에 데이터를 삽입하는 원리와 속도
   1) 맨마지막에 추가하는 경우 : 배열의 길이를 기억하고 있으므로 배열의 시작점에서 길이 만큼 뒤로 이동한 후 추가
   2) 중간에 추가하는 경우 : 추가할 위치부터 그 이후의 모든 element를 뒤로 옮기고 추가
   3) 배열이 꽉 차있는 경우 : 더 큰 배열을 새로 만들고, 이전 배열을 복사해서 옮긴 후, 새 데이터를 추가
4. 배열에서 데이터를 삭제하는 원리와 속도
   추가하는 원리와 비슷

EP24 알고리즘의 속도는 어떻게 표현할까?

빅오 표기법 : 알고리즘으로 작업을 완료할 때 까지 걸리는 절차 수 N을 이용한 표현

Big-O 표기법

시간복잡도의 예

O(1)    : 배열의 길이와 상관없이 딱 한번 실행되는 경우
O(N)    : 배열의 길이 만큼 실행되는 경우
O(N^2)  : 중첩되는 반복문의 경우 배열의 제곱배의 단계가 실행되는 경우

EP25 검색 알고리즘이 뭐죠?

선형검색(linear search)

배열의 맨처음부터 하나씩 검색하는 방법

이진검색(binary search)

* 정렬이 끝난 배열에서만 사용할 수 있음
중앙값을 기준으로 왼쪽, 오른쪽으로 검색
1) 중앙값이 찾으려는 값보다 작다면 중앙값 오른쪽만 검색
2) 오른쪽의 중앙값과 다시 비교하여 중앙값을 기준으로 점프
=> 배열의 절반을 제외할 수 있으므로 빠름 (log x그래프)