<알고리즘> 노마드 코더_메모

출처: https://youtu.be/9TyyMtlk5i4

<Array>

알고리즘 스피드?

- 완료까지 걸리는 절차(Step)의 수 
시간복잡도?

- 로직이 얼마나 빠르고 느린지 측정 -> 얼마나 많은 단계가 있는가

휘발성 vs 비휘발성

- 컴퓨터 꺼지면 처음부터 다시 시작하나?
      Ex) RAM  vs 하드디스크
- 변수 생성시 RAM에 저장 -> 프로그램이 RAM 메모리에게 해당 주소로 가달라 명령 -> 즉각 접속

배열(Array)
- 공간 미리 예약/할당(배열 최대길이)  But! python, javascript는 자동 핸들링
READ  
- 많은 자료에서 읽어야 한다면 배열(Array)사용! Why?즉각(랜덤) 접속 가능   
SEARCH
- 배열 어디에 있는지 모르기 때문에 전체를 다 봐야 함
- 선형검색: 0~끝까지 순차적으로 찾는 방법
INSERT/WRITE  
- 중간 or 앞에 추가시 기존 값 뒤로 밀어야 함 
- 공간이 부족하다면 더 큰 배열에 복사
DELETE

- 배열 중간 요소 삭제시 앞으로 밀어줘야 함  

▶ 배열에서 추가&삭제 작업 할 시 가장 마지막 요소에서 작업 

 

<검색 알고리즘>

Binary Search [이진검색 알고리즘] 
- 정렬의 정중앙부터 시작, 목표 숫자와 비교
- 매 스텝마다 배열의 절반을 없앰
단점

- Sorted Array(순서대로 정렬된 배열) 에서만 사용 가능
- 정렬된 배열에 insert시 해당 배열에서 기준 아이템보다 큰 값을 찾아 왼쪽에 추가 

Linear Search [선형검색 알고리즘]
- 처음부터 끝까지 순차적으로 목표값을 찾음 
단점

- 목표값이 마지막에 있거나 아예 없다면 시간이 길어짐 
- 선형 시간 복잡도: input과 time이 비례 

▶ 검색을 많이 해야한다면? 일단 정렬! But 정렬을 하려면 아이템 추가시 시간 소요됨 

<Big O>

Big O ? 

- 알고리즘의 퍼포먼스를 이해하기 쉽고 효율적으로 작성하는 방법

O(1)
- 상수시간(Constrant Time)
- input이 N일때 정해진 step

var arr = [0,1,2,3,4,5,6,7,8,9];
console.log(arr[0]); // 1step
console.log(arr[1]); // 2step     -> arr에 무슨 값이 있든 동일 step

 

O(N)
- 선형검색(Linear Search)
- input이 N일때  N step

var arr = [0,1,2,3,4,5,6,7,8,9];
arr.forEach((arr, index, array) => console.log(arr))   //10step -> arr길이만큼의 step

O(N^2)
- 2차 시간(Quadratic Time) : 중첩반복(Nested Loops)이 있을때 발생
- input이 N일때 N^2 step 

for(var i=0; i< arr.length; i++)
	for(var j=0; j< arr.length; j++)
		console.log(i, j); 			//arr길이 10일때 100 step

 

O(log N)
- 로그 시간(Logarithmic Time) 
- 정렬된 배열의 이진탐색 알고리즘 설명시 사용
- 선형시간 O(N)보다 빠름
Ex) 32길이 배열에서 1을 찾을 때 횟수 (가장 최악의 경우 예제)

      - 32/2 = 16,   16/2 = 8,  8/2 = 4, 4/2= 2,  2/1 = 1  // 최대로 많아봐야 5step 

BigO 그래프

 

<정렬 알고리즘>

버블 정렬(Bubble Sort)
- O(n^2)
- 아이템 두개 선택, L(기준)>R 이면 교환 후 다음인덱스 이동
     -> 가장 큰 수가 가장 끝에 가게 됨
단점

- 내림차순된 배열을 오름차순으로 정렬시 매 싸이클마다 모든 아이템을 교환해야함

선택 정렬(Selection Sort)
- O(n^2)
- 변수에 가장 작은 아이템이 있는 인덱스 값 저장
- 정렬되지 않은 배열에서 찾은 가장 작은 아이템(기준)과 배열의 첫번째 아이템을 교환
장점

- 매 싸이클마다 한번만 교환하면 됨
단점

- 모든 아이템을 스캔 함

 

삽입 정렬(Insertion Sort)
-  O(n^2)
- 인덱스 1에서 시작, L<R(기준) 이면 다음인덱스(기준+1) 이동
                                 L>R(기준) 이라면 교환 후 이전인덱스(기준-1)와 비교  
장점

- 필요한 아이템만 스캔 함, 최고의 경우 O(N)의 시간복잡도를 가짐

▶속도: 버블 < 선택 < 삽입 But 시간복잡도는 동일 함! 
               -> 최악/최고가 아닌 평균 시나리오가 중요  

 

<Hash Table>

Hash Table(해쉬 테이블)

- Key:Value System

menu = {
 coffee: 10,
 burger: 15,
 tea: 5
} //key:val

 

- Hash Table의 Read, Insert, Delete 선형 복잡도: O(1)

Ex) 해쉬테이블 에서 특정 값 찾을 시

나라들 = {
"한국": true,
"미국": true,
"중국": true
}
console.log(나라들["영국"]);  //undefined
console.log(나라들["한국"]);  //true

 

Hash Tables에는 array구조 존재
- Hash Function이 저장하고 싶은 Key를 index 숫자로 바꿔줌, 해당 index에 value 저장됨
- Key name - <HashFunction> - 해쉬함수가 준 index -  value 접근

HashFunction

*만약 같은 index숫자가 지정된다면 index안의 배열에서 순차탐색

index4의 value

<자료구조>

추상적 자료구조(ADT)

- 자료구조 방법이 코드로 정의된 것이 아닌 행동 양식만 정해진 것   
큐 (Queue)
- FIFO: First In First Out
- Ex) 줄서기, 이메일, 푸쉬알림, 선착순 주문 처리
스택 (Stack)
- LIFO: Last In First Out
- Ex) 팬케이크 쌓기, 뒤로가기, Ctrl+Z, 프링글스 통이랑 비슷