[노개북] IT 5분 잡학사전 #09 - EP26~EP29

 

🏷️ 오늘 읽은 범위: Ep.26 ~ Ep.29

 

---

 

💡 책에서 기억하고 싶은 내용을 써보세요.

---

EP.26 정렬 알고리즘이 뭐죠?

[🏷️154p-159p]

정렬(sorting) 알고리즘 - 시간 복잡도: O(N²)

   1. 버블 정렬 (bubble sort)

   2. 선택 정렬 (selection sort)

   3. 삽입 정렬 (insertion sort)

 

버블 정렬

출처: WIKI

• 왼쪽과 오른쪽 두 수를 비교하여 오름차순이라면 a < b, 내림차순이라면 a > b로 숫자를 바꾸면서 정렬하는 알고리즘
• 이렇게 배열의 끝까지 작업하는 것을 한 사이클이라고 한다.
• 한 사이클이 진행됐을 때 오름차순의 경우, 배열의 가장 큰 요소가 맨 끝에 위치하게 되고 다음 사이클에는 마지막 위치를 제외하고 진행할 수 있다.
• 시간 복잡도가 O(N²)인 알고리즘으로, 대체적으로 O(N²)인 알고리즘은 좋은 알고리즘이라고 하지 않는다.

선택 정렬

출처: WIKI

• 가장 작은 데이터 또는 가장 큰 데이터의 위치를 따로 기억한다.
• 화살표를 배열의 0번째부터 N번째까지 이동하면서 가장 작은 데이터 혹은 가장 큰 데이터의 위치를 기억한다.
• 오름차순일 경우 가장 작은 숫자의 위치는 0번째가 되어야 하기 때문에 0번째에 있는 데이터와 가장 작은 데이터를 교환한다.
• 이렇게 한 사이클이 진행되고, 다음 사이클에는 0번째 위치를 제외하고 사이클을 진행한다.
• 버블 정렬과 시간 복잡도는 O(N²)으로 동일하지만, 한 사이클에 자리를 바꾸는 연산이 1번 실행되기 때문에 선택 정렬이 훨씬 효율적이다.

삽입 정렬

출처: WIKI

• 앞에 있는 데이터를 보면서 배치한다.
• 앞에 있는 데이터를 봐야하기 때문에 0번째가 아닌 1번째 데이터부터 비교를 시작하고, 포인트는 교환이 아니라 밀어 넣는다는것.
• 비교가 완료되어 밀어 넣어서 정렬이 끝나면 해당 사이클은 끝난다.
• 선택 정렬, 버블 정렬보다 빠르다.

시간 복잡도는 같은데 속도 차이가 나는 이유

• 알고리즘은 초기 데이터 상태에 따라 처리 속도가 달라진다.
• 따라서 기계적으로 측정한 시간 복잡도는 같아도 평균적으로 빠른 알고리즘이 있을 수 있다.

 

EP.27 스택, 큐가 뭐죠?

[🏷️163p-166p]

큐나 스택은 실제로 존재하는 개념이 아니다.

이러한 큐나 스택을 추상 자료구조(abstract data type, ADT)라고 한다.

배열 + 규칙 ⇒ 스택 또는 큐가 된다.

 

스택

출처: WKI

like 팬케이크! 🥞

스택의 규칙은 팬케이크와 같다.

최근에 구운 녀석이 맨 위에, 먹을 때는? 맨 위에 있는 녀석부터!

스택의 규칙
규칙 1: 새로운 데이터를 위에서 쌓는다.
규칙 2: 위에서부터 데이터를 뺀다.

이러한 스택의 방식을 LIFO(Last In First Out)이라고 한다.

 

큐

출처: WIKI

like 버스 정류장! 🚏

큐의 규칙은 버스 정류장과 같다.

가장 먼저 줄 선 사람이 버스에 먼저 타는 것!

큐의 규칙
규칙 1: 새로운 데이터를 위에서 쌓는다.
규칙 2: 아래에서부터 데이터를 뺀다.

이러한 큐의 방식을 FIFO(First In First Out)라고 한다.

 

스택, 큐는 언제 사용할까?

• 스택 - 웹 브라우저의 뒤로 가기 버튼, 되돌리기 단축키
• 큐 - 쇼핑몰 주문 처리 시스템

 

EP.28 해시 테이블이 뭐죠?

[🏷️167p-172p]

해시 테이블

데이터를 더 쉽게 정리할 수 있게 키와 값을 짝지어 모은 것

# 배열
menu = [
	{ name: "아메리카노", price: 10},
	{ name: "라떼", price: 12},
	{ name: "카모마일차", price: 15},
	{ name: "케이크", price: 45},
];

# 해시 테이블
menu = {
	커피: 10,
	라떼: 12,
	카모마일차: 15,
	케이크: 45
}

배열에서 ‘라떼’를 찾기 위해서는 선형 검색 알고리즘을 사용하여 모든 요소를 확인해야한다.

해시 테이블을 사용하면 바로 라떼를 찾을 수 있기 때문에 시간 복잡도를 O(N)에서 O(1)로 줄일 수 있다.

 

해시 테이블 구조

해시 테이블은 배열의 구조 되어 있다. 그럼에도 배열보다 빠를 수 있는 이유는 해시 함수 때문이다.

 

해시 함수

배열은 인덱스로 접근해야하는데 해시 테이블은 어떻게 키 값으로 검색을 할 수 있을까?

해시 함수는 해시 테이블에서 검색할 때 쓰는 키를 숫자, 즉 인덱스로 바꿔 주는 역할을 한다.

 

해시 충돌

키를 인덱스로 바꿔주는 일종의 규칙을 가지고 있는 해시 함수에서 다른 입력 값에 동일한 출력값을 내는 상황을 해시 충돌(hash collison)이라고 한다.

해시 충돌의 해결 방법으로는 같은 인덱스에 또 다른 배열을 넣는 방법 등이 존재한다.

충돌을 추가로 처리해야할 경우가 있으므로 해시 테이블에서의 검색은 항상 O(1)은 아니다.

 

EP.29 개발자 필수 소양, 클린 코드!

[🏷️173p-178p]

클린코드

설명이 필요 없는 코드

읽기만 해도 이 코드가 무슨 일을 하는지, 어떤 것을 의미하는지 이해되는 코드이다.

 

5가지 클린 코드 백서
클린 코드 백서 1. 의미 있는 변수, 함수의 이름을 적절히 사용하라
클린 코드 백서 2. 함수 이름은 가급적 동사로 지어라
클린 코드 백서 3. 매개변수는 너무 많이 쓰지 마라
클린 코드 백서 4. 불린값을 인자로 보내지 마라
클린 코드 백서 5. 축약어를 쓰지 마라

 

🤔 오늘 읽은 소감은? 떠오르는 생각을 가볍게 적어보세요.

---

맥북 프로를 구매하면 본전을 뽑겠다는 생각으로 더 열심히 코딩하게 되더라고.

기계식 키보드는 보통 10만 원이 넘거든? 그러니 코딩을 열심히 해야겠다는 생각이 자연스럽게 들지!

 

🔍 궁금한 내용이 있거나, 잘 이해되지 않는 내용이 있다면 적어보세요.

---