TIL (2023.1.21.토)
DAY 9
📚 IT 5분 잡학사전
🔖오늘 읽은 범위: episode 26~29
📝 책에서 기억하고 싶은 내용을 써보세요.
26장. 정렬(Sorting) 알고리즘
정렬: 데이터를 1, 2, 3, 4 혹은 4, 3, 2, 1 처럼 순서대로 정리하는 것
시간 복잡도는 같으면서 성능은 다른 정렬 알고리즘 3가지
- 버블 정렬(bubble sort)
- 오른 쪽만 보면서 정렬
- 선택 정렬(selection sort)
- 하나를 콕 집어 가며 정렬
- 전체 데이터 중에서 가장 작은 데이터 또는 가장 큰 데이터의 위치를 따로 기억하는 방식으로 작업 진행
- 삽입 정렬(insertion sort)
- 앞에 있는 데이터를 보면서 배치
- 교환이 아닌 밀어 넣기
시간 복잡도는 O(N제곱)으로 동일하지만, 속도는 차이가 난다.
속도: 버블 < 선택 < 삽입
27장. 스택(Stack), 큐(Queue) 자료구조
스택과 큐는 규칙 개념의 자료구조로 추상 자료구조(abstract. Data type, ADT)라고도 한다.
큐나 스택은 배열처럼 실제로 존재하는 개념이 아니다. 즉, 문법으로 구현된 것이 아니다. 스택과 큐는 기존 프로그래밍언어 문법으로 데이터 저장시 어떤 규칙만 부여하면 된다.
| 스택(stack) | 큐(queue) | |
|---|---|---|
| 규칙 | 팬케이크 쌓기 규칙 | 버스 정류장 줄서기 규칙 |
| 1. 위에서 데이터를 쌓는다. | 1. 위로 데이터를 쌓는다. | |
| 2. 위에서 부터 데이터를 뺀다. | 2. 아래에서부터 데이터를 뺀다. | |
| LIFO (last in, first out) | FIFO (first in, first out; 선입선출) | |
| 사용 예시 | 웹 브라우저 뒤로가기 버튼, 되돌리기 단축키(Ctrl+Z) | 쇼핑몰 주문 처리 시스템(주문 들어온 순서대로 데이터 쌓고, 가장 먼저 온 주문부터 처리) |
28장. 해시 테이블(Hash table)
”어떻게 하면 프로그램의 속도를 더 빠르게 만들 수 있을까?“
자료구조와 알고리즘을 공부하면 된다.
1. 해시테이블의 콘셉트
해시테이블은 ”키”와 ”값”을 짝지어 모은 것으로 데이터를 쉽게 정리할 수 있다. 해시테이블은 사전과 같은데 키는 단어, 값은 단어 뜻이라고 생각하면 된다.
- 예시) 카페 메뉴 컴퓨터에 저장한 후 라떼 가격 알아내기
1. 배열로 저장할 경우
라떼 가격을 알고 싶다면 배열 데이터의 처음부터 모두 확인하는 선형 검색을 사용해야 한다. 그러면 시간이 오래 (시간 복잡도: O(N) 걸린다.
2. 해시테이블로 저장할 경우
해시테이블은 사전처럼 사용할 수 있다. 모든 데이터를 찾는 것이 아닌”라떼”만 검색가능하다.
시간 복잡도는 가장 빠른 상수시간인 O(1)이다.
어떤 값을 찾더라도 딱 한단계 밖에 안거친다.
데이터를 추가하고 삭제할 때도 O(1)이다.
2. 해시테이블의 형태
해시테이블은 해시함수가 있는 배열 형태이다.
따라서 인덱스 번호로 접근해야 한다.
3. 해시테이블 속도의 비결, 해시 함수
해시 함수는 검색할 때 쓰는 키를 숫자, 즉 인덱스로 바꿔주는 역할을 한다.
- 해시함수 구성 시 해시 충돌(hash collison)현상이 발생할 수 있는데 대처 방법으로 인덱스에 또 다른 배열을 넣어 주는 방법이 있다.
- 충돌 처리시 해시테이블의 시간복잡도는 O(1)이 아니다.
29장. 클린 코드 5가지 꿀팁
- 의미있는 변수, 함수의 이름을 적절히 사용하라.
- 함수 이름은 가급적이면 동사로 지어라.
- 매개변수는 너무 많이 쓰지 마라.
- 불린(boolean) 값을 인자로 보내지 마라.
- 축약어를 쓰지 마라.
💬 오늘 읽은 소감은? 떠오르는 생각을 가볍게 적어보세요
새롭게 배우는 개념들이 많이 등장!
❓ 궁금한 내용이 있거나, 잘 이해되지 않는 내용이 있다면 적어보세요.
해시함수
Always have hope🍀 & constant passion🔥