230604~230605_알고리즘, 데이터 구조 with Nico
강의 순서
Array 배열
검색 알고리즘
Big O
정렬 알고리즘
Hash Tables
자료구조
강의 출처
https://www.youtube.com/watch?v=NFETSCJON2M&list=PL7jH19IHhOLMdHvl3KBfFI70r9P0lkJwL&index=2
Array 배열
RAM Random Access Memory ↔ Hard Disk
차이점: 자료가 배열로 이루어져있고 자료 위치만 알면 바로 데이터를 확인할 수 있다. (순서대로 찾지 않음)
array 배열
1.Redaing
index로 데이터를 찾는다.
random access 덕분에 자료 위치에는 쉽게 접근한다.
따라서 reading은 쉬움.
2.Searching
데이터가 어딨는지 모를 때는 처음부터(인덱스 0부터) 순서대로 다 열어봐야하는 상황 발생
그런 검색 방법을 Linear Search라 함.
3.Inserting(Adding)
데이터를 추가할 때,
최고 시나리오 → 배열 최우측 빈 공간에 추가
보통 시나리오 → 배열 중간에 추가, 그러기 위해 중간부터 끝까지 있는 데이터를 오른쪽으로 한 칸씩 이동시킨 뒤 중간 빈 공간에 추가
최악 시나리오 → 배열 처음에 추가, 그러기 위해 처음부터 끝까지 있는 데이터를 오른쪽으로 한 칸씩 이동시킨 뒤 처음 빈 공간에 추가
*최고, 보통, 최악 - 속도
4.Deleting
데이터를 삭제할 때,
최고 시나리오 → 배열 최우측 데이터 삭제
보통 시나리오 → 배열 중간 데이터 삭제, 그러기 위해 중간부터 끝까지 있는 데이터를 오른쪽으로 한 칸씩 이동시킨다.
최악 시나리오 → 배열 처음 데이터 삭제, 그러기 위해 처음부터 끝까지 있는 데이터를 오른쪽으로 한 칸씩 이동시킨다.
Tip
1) array 를 이용할 때 데이터 검색/추가/삭제는 최우측에서 하도록
2) 속도를 줄일 수 있는 또 다른 알고리즘 있다. (다음 시간에...)
검색 알고리즘
Linear Search v.s. Binary Search
Linear Search : 배열의 인덱스 0부터 순서대로 데이터를 찾는다. 배열의 크기가 커질수록 데이터 찾는 속도도 선형으로 증가
Binary Search : 특정 배열(sorted array)에만 적용할 수 있는 검색법으로, 데이터 양이 많아질수록 빠른 속도를 자랑한다. 대신 검색 전 array를 정렬해야한다는 수고가 든다.
* sorted array : 임의의 배열은 랜덤하다고 보고, sorted array는 배열을 데이터(숫자) 크기 순으로 정렬한 상태이다.
Binary Searching
1. 배열(sorted array)의 중간 크기에 해당하는 데이터와 찾고자 하는 데이터 크기를 비교한다.
2. 찾고자 하는 데이터 크기보다 작으면 좌측 데이터는 전부 버린다.(vice versa)
3. 남은 우측 배열의 중간 데이터와 또 크기 비교를 한다.
마찬가지로 찾고자 하는 데이터 크기보다 크면 우측 데이터는 전부 버린다.(vice versa)
4. (반복)
5. 원하는 데이터를 찾았다!
*중간 데이터는 n번째 → 전체 데이터 개수가 홀수(2n+1)개이면 n번째( → 홀수번), 짝수(2n)개이면 n번째( → 짝수번)
예시.
1~10 까지의 배열에서 숫자 9 찾기
5 → 8 → 9
step 3번만에 찾았다.
1~20까지의 배열에서 숫자 13 찾기
10 → 15 → 12 → 13
step 4번만에 찾았다.
요약.
데이터 크기가 몇 천~몇억 처럼 어마어마해질 때
Linear Searching은 그만큼 시간이 많이 걸리지만
Binary Searching은 금방한다는 것
따라서 검색을 위주로 한다면 Binary Searching을 위해 배열을 정렬해두어야 한다!
*알고리즘 세계에서 시간이 많이 걸린다 = 원하는 결과를 내기까지 절차 수가 많다
즉, 시/분/초 가 아닌 step으로 따진다.
설명을 듣다보니
Binary Searching은 루미큐브와 up & down 게임 요소가 있는 것 같다.
sorted array를 만들 때는 루미큐브할 때처럼 수를 정렬해야 하고
그 과정에서 약간의 시간(일종의 delay)이 생긴다.
그걸 Binary Searching을 위한 수고라고 본다.
또한 Binary Searching을 본격으로 할 때에는
up & down 숫자 찾기처럼 진행한다.
Big O
: 시간 복잡도를 rough하게 설명해주는 개념
그래서 Big인가?
O(1), O(n), O(n²), O(log n), … 모두 그래프를 떠올리면 된다.
그래프가 상수함수>로그함수>선형함수>이차함수 일수록 시간복잡도가 낮은 것(상대적으로 좋은 알고리즘)
예시. y=1, y=x, y=x², y=log x
1. Constant time = O(1)
데이터 크기가 얼마나 큰지에 상관없이 수행을 완료하는데 동일한 step이 필요함, 가장 선호되는 알고리즘
예시. step이 1이건 1000이건 데이터 크기에 따라 변하지 않으면 rough하게 O(1)이라고 나타냄
2. O(n)
데이터 크기가 클수록 step이 선형 증가
예시. for 문이 하나 있는 함수
3. O(n²)
데이터 크기가 클수록 step이 이차 증가
예시. 중첩 for문
4. O(log n)
데이터 크기가 클수록 step이 로그 증가
Binary Searching의 시간복잡도를 나타낼 때 쓴다.
*여기서(컴퓨터 과학) log n는 log₂ n 를 나타냄
예시. 데이터 크기를 n이라 하면 Binary Searching에서는 반절씩 끊어가며 찾으므로 step은 다음과 같다.
step = log₂ n
= log n
+ 이외에도 O(nlog n), O(2ⁿ)이 있다.
정렬 알고리즘
Sort Algorithm : 정렬을 해주는 알고리즘
Bubble Sort, Selection Sort, Inserting Sort
1. Bubble Sort 버블 정렬
무작위한 배열이 있을 때, 배열의 처음 2개의 크기를 비교하고 그 다음 2개의 크기를 비교하면서
숫자가 작은 것은 왼쪽, 큰 것은 오른쪽으로 자리 바꾸기(swap)를 하는 정렬 방식
예시.
| 2 | 1 | 4 | 7 | 3 | 8 | 9 | 6 |
위와 같은 배열이 있을 때, 처음 2와 1을 비교 → 2>1 이므로 swap
| 1 | 2 | 4 | 7 | 3 | 8 | 9 | 6 |
그 다음 2와 4를 비교 → 정렬이 잘 됐음
그 다음 4와 7을 비교 → 정렬이 잘 됐음
그 다음 7과 3을 비교 → 7>3 이므로 swap
| 1 | 2 | 4 | 3 | 7 | 8 | 9 | 6 |
그 다음 7과 8을 비교 → 정렬이 잘 됐음
그 다음 8과 9를 비교 → 정렬이 잘 됐음
그 다음 9와 6을 비교 → 9>6 이므로 swap
| 1 | 2 | 4 | 3 | 7 | 8 | 6 | 9 |
1차례 결과 : 1 2 4 3 7 8 6 9
같은 방식으로 배열의 처음으로 돌아가서 반복한다.
이럴 경우 배열의 크기가 n일 때,
최고 상황 → n-1번 비교
최악 상황 → n-1, n-2, … ,1 번 비교, 즉 시간복잡도 : O(n²)
*O(n²) 이유: (n-1)*(n-1) 하므로 rough하게 n²
2.Selection Sort 선택 정렬
최솟값을 정해진 위치에 넣는 정렬
* 첫 번째 자리 : 최솟값, 두 번째 자리 : 그 다음 최솟값(결국 두 번째로 작은 값), 세 번째 자리 : 그 다음 최솟값(결국 세 번째로 작은 값), …
순서.
1. 무작위한 배열 내에 최솟값을 찾는다.
2. 찾은 최솟값을 첫 번째 자리의 데이터와 바꾼다.(swap) (첫 번째 자리 - 완료)
3. 미완료된 나머지 배열에서 최솟값을 찾는다.
4. 찾은 최솟값을 나머지 배열의 첫 번째 자리의 데이터와 바꾼다. ( 그 다음 첫 번째 자리 - 완료)
5. 반복
*바꿀 필요가 없다면 pass하고 같은 규칙으로 그 다음을 반복
선택정렬은 버블정렬보다 빠를 수 있다.
이유.
버블정렬 - 한 번의 사이클에 n-1 번의 swap 발생
선택정렬 - 한 번의 사이클에 한 번의 swap만 발생
그래도 시간복잡도는 rough하게 둘 다 O(n²)
3.Insertion Algorithm 삽입 정렬
배열의 두 번째 값부터 시작한다.
특정 자리의 데이터를 그 앞(왼쪽)과 비교하여 더 작은 값을 왼쪽자리로 삽입하는 방식
예시.
| 2 | 1 | 4 | 7 | 3 | 8 | 9 | 6 |
배열의 두 번째 값인 1이 주인공, 그 왼쪽 값은 2
1이 더 작으므로 swap 해 들어간다 (inserting)
| 1 | 2 | 4 | 7 | 3 | 8 | 9 | 6 |
배열의 첫째, 둘째번은 정렬 완료.
그 다음 값인 4가 주인공
왼쪽에 작은 값만 있으므로 정렬 완료
| 1 | 2 | 4 | 7 | 3 | 8 | 9 | 6 |
1, 2, 4는 완료됐으니 그 다음 7이 주인공
왼쪽에 작은 값만 있으므로 정렬 완료
| 1 | 2 | 4 | 7 | 3 | 8 | 9 | 6 |
1,2,4,7은 완료됐으니 그 다음 3이 주인공
7과 비교했을 때 더 작으므로 왼쪽으로 자리 바꾸어 (swap) 들어간다 (inserting)
4와 비교했을 때 더 작으므로 왼쪽으로 자리 바꾸어 (swap) 들어간다 (inserting)
| 1 | 2 | 3 | 4 | 7 | 8 | 9 | 6 |
이런 식으로 반복
Hash Tables
Key - Value로 데이터를 저장하는 형태
예시. Python → Dictuionary, JS → Object, …
Linear Search보다 시간복잡도가 작다 → O(n) v.s. O(1)
>>어떻게 Hash Tables는 Array보다 빠를까?
예시.
상황. pizza를 찾아라
I.Array → Linear Search, O(n)
menu = [
{name: "coffee", price: 1000},
{name: "cake", price: 5000},
{name: "pizza", price: 6000}
{name: "soup", price: 2000}
]
II.Hash Tables → 한 번에, O(1)
menu = {
"coffee":1000,
"cake":5000,
"pizza":6000,
"soup":2000,
}
>> Hash Tables 이름에는 왜 hash라는 글자가 들어갈까?
hash 함수가 배열에 적용된 형태이기 때문
즉, hash tables는 array와 hash functino의 조화
배열이 적용되었다고?
예시.
nations= [ '한국', '중국', '미국', '대만', '일본'] → Linear Search
nations={ '한국': false, '중국': false, '미국: false', '대만': true, '일본': false} → Hash Tables로 한번에
근데 이 때 nations hash tables에는 배열(python → List)의 개념이 들어가 있다.
['대만'] / true
['미국'] / undefined
['일본'] / undefined
…
이기 때문에 바로 찾은 것임.
Hash Function은 무엇인가?
간단히 말하면 값에 특정 숫자를 지정해주는 함수
예시.
문자열 크기와 같은 숫자를 지정해주는 hash 함수가 있다면,
'pizza'라는 데이터에 5라는 숫자를 지정한다. → index는 5가 돼 배열에 'pizza':6000 이 저장된다.
'cake'와 'soup'라는 데이터에 4라는 숫자를 지정한다. → index는 4가 돼 배열에 'cake':5000, 'soup':2000가 둘 다 저장 돼야하는 상황이 생긴다 → Collision (충돌)
충돌 발생 시, 배열 안에 배열로 저장된다. → index 4 - [ {'cake':5000}, {'soup':2000} ]
* 배열
| index | value |
| 0 | |
| 1 | |
| … | |
| 4 | [ {'cake':5000}, {'soup':2000} ] |
| 5 | { 'pizza':6000 } |
따라서 Hash Tables는 기본적으로 O(1)의 시간복잡도를 갖지만(= 원하는 값을 한 번에 찾지만)
충돌이 발생하는 경우가 있으므로 시간복잡도가 항상 O(1)은 아님( 보통의 case일 때 O(1) )
자료구조
Stack & Queue
추상적 자료구조이나 자료구조에 대한 인사이트를 줌
1. Stack
말 그대로 쌓는다는 뜻으로
팬케이크를 아래서부터 위로 쌓아나간다.
이 때 팬케이크는 제일 따끈한 팬케이크인 마지막(제일 위) 팬케이크부터 먹을 수 있다.
따라서 Li Fo (Last in, First out) 이다.
예시.
뒤로 가기, ctrl + z - 사용자가 쌓아놓은 데이터 중 가장 나중 것부터 접근가능
2. Queue
영어로 대기줄이란 뜻
버스 정류장이든 공항 대기줄이든
처음 온 사람이 먼저 나간다.
따라서 Fi Fo (First in, First out) 이다.
예시.
보통의 배열 - 인덱스만 알면 어디서든 수정/삽입/삭제 가능
| 0 | 1 | 2 | 3 |
Stack - 제일 나중(여기선 인덱스 3)만 수정/삽입/삭제 가능
| 3 |
| 2 |
| 1 |
| 0 |
Queue - 제일 처음(여기선 인덱스 0)만 수정/삽입/삭제 가능
| 0 | 1 | 2 | 3 |
time stamp: 11:00(?)-tom 10:00 (쉬면서 함)