코딩테스트 공부 START

내가 참고한 영상은 아래와 같다. 알고리즘을 굉장히 재미있고 쉽게 가르쳐준다.

 

https://www.youtube.com/watch?v=9TyyMtlk5i4&list=PL7jH19IHhOLMdHvl3KBfFI70r9P0lkJwL&index=1 

 

다음 4가지의 상황을 염두하고 데이터 구조를 살펴보기

1. 검색  2.읽기  3.삽입  4.삭제

1. Array 배열 

:데이터를 읽을때는 정말 빠르다. 다만, 검색하고 추가하고 삭제해야 할 경우는 속도가 느려질 수 있다.

만일 배열에서 검색하고, 추가하고 삭제해야하는 경우에는 배열 맨끝에서 작업하는 것을 추천한다. 

 

시간복잡도 : 데이터 구조의 오퍼레이션 혹은 알고리즘 얼마나 빠르고 느린지 측정하는 방법

(얼마나 많은 "단계(steps)"가 있는가로 측정 ⇒ 적은 단계로 진행되는 알고리즘이 좋은 알고리) 

 

2. 검색 알고리즘 (이진검색 알고리즘 vs 선형검색 알고리즘) 

1) 선형검색 알고리즘

 

IF 10개의 숫자 중에서 숫자 7을 찾는다면, 아래와 같은 형식으로 1번 아이템부터 차례로 7이 맞는지 확인

----------------------------------------------------------

33 2 20 1 7 9 11 8 28 40 

= 

7  

-----------------------------------------------------------

최악의 경우 ⇒ 찾고자 하는 숫자가 배열에 없거나 가장 맨 끝에 있는 경우 

배열이 커지면 커질수록 선형검색을 하는 시간 역시 선형적으로 증가 (선형 시간 복잡도 증가)

 

2) 이진검색 알고리즘 (반으로 쪼개다)

 

: 선형검색 알고리즘을 보완한 방법, 정렬된 배열 에서만 사용 가능

: 정렬의 정중앙에서 부터 검색 시작 

 

IF 숫자 9를 찾는다면 정중앙 숫자인 5부터 검색해 5보다 큰 쪽으로 이동하며 검색 

----------------------------------------------------------

1 2 3 4 5 6 7 8 9 10

-----------------------------------------------------------

 

⇒ INPUT이 늘어도 선형검색보다 유리

⇒ 검색을 많이 상황이라면 정렬을 해야 함 but 정렬을 할 경우 아이템 추가시 시간이 소요 됨.

 

3. Big O

알고리즘 스피드 표현은 시간이 아닌 "완료까지 걸리는 절차의 수" 로 결정

 

input size = N 

 

선형 검색의 시간 복잡도 = O (N)

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

위 코드의 시간 복잡도는 constant time (상수시간) = O(1)

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

위 코드도 동일하게 시간 복잡도는 constant time (상수시간) = O(1)

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

위 코드는 loop 안에서 loop를 도는 중첩 반복문이므로 시간복잡도 = O(N^2)

 

매 step마다 반으로 나눠서 검색되는 이진검색의 시간복잡도 = O(log n) 

 

4 .정렬 알고리즘

1) bubble sort (버블정렬) : 배열의 2개의 아이템을 선택하여 비교하여 교환 ⇒  O(N^2)

2) selection sort (선택정렬) : 전체 아이템 중에서 가장 작은 아이템의 위치를 변수에 저장하고 첫번쨰 아이템과 교환⇒  O(N^2)

3) insertion sort (삽입 정렬) : 자신의 왼쪽 아이템과 비교하여 작을 경우 교환 ⇒  O(N^2)

 

5. Hash Table : Key Value System

단어 = key

단어의 뜻과 설명 = value

#arrays
menu = [
	{ name : "coffee" , price : 10 },
    { name : "burger" , price : 15 },
    { name : "tea" , price : 10 },
    { name : "pizza" , price : 5 },
    { name : "juice" , price : 10 },
];


#Hash Tables
menu = {
	coffee : 10 ,
    burger : 15,
    tea : 5,
    pizza : 10,
    juice:5,
};

key를 가져다가 해시함수에 넣고 해시함수가 준 숫자에 value를 저장

6. 데이터 구조

: 배열 위에 어떤 규칙을 설정한 모습

1) 큐 : 버스 기다리는 형태를 생 (First In , Fisrt Out)

2) 스택 : 배열이 수직으로 쌓여 있는 형태 (Last In, First Out)

 

IF 웹 브라우저에서 "뒤로가기" 를 누르는 것 , 되돌리기(Ctrl + Z) ⇒ 스택

콜센터의 백엔드, 쇼핑몰의 주문처리 ⇒ 큐