IT 5분 잡학사전 - 에피소드 26~29

Gata·2023년 11월 18일

개발자북클럽

📘IT 5분 잡학사전

목록 보기

9/10

Today I Learned

2023.11.18

오늘 읽은 범위

에피소드 26. 정렬 알고리즘이 뭐죠?
에피소드 27. 스택, 큐가 뭐죠?
에피소드 28. 해시 테이블이 뭐죠?
에피소드 29. 개발자 필수 소양, 클린 코드!

📌에피소드 26. 정렬 알고리즘이 뭐죠?

정렬: 데이터를 1,2,3,4 또는 4,3,2,1 처럼 순서있게 정리하는 것

시간 복잡도가 $O(N^2)$ 으로 다 같으면서 성능은 다른 정렬 알고리즘 3가지
1~9까지의 숫자가 있다고 가정해보자.

버블 정렬(bubble sort): 맨 앞에서 부터 2칸짜리 창문을 열고 오른쪽으로 이동해가면서 두 숫자를 비교하는 방식

예) 8,1,2,6,3,4,9,5,7 --> 1,8,2,6,3,4,9,5,7 -> 1,2,8,6,3,4,9,5,7 -> ....-> 1,2,3,4,5,6,7,8,9 -> 한 사이클
선택 정렬(selection sort): 가장 작은 데이터(또는 가장 큰 데이터)의 '위치'를 기억하는 방식. 자리 바꾸는 연산은 사이클 당 1번씩 하기 때문에 버블 정렬보다 효율적.

예) 8,6,2,1,3,4,9,5,7
가장 작은 수 1은 3번째에 위치하고, 0번째에는 숫자 8이 위치한다. 0번째와 3번째 자리의 숫자를 바꾼다. -> 한 사이클
삽입 정렬(insertion sort): 앞의 데이터와 비교하면서 더 작은 수가 큰수를 '밀고' 들어가는 방식. 삽입 정렬은 버블 정렬과 선택 정렬보다 빠르다.

예) 8,6,2,1,3,4,9,5,7 -> 6,8,2,1,3,4,9,5,7 -> 한 사이클
-> 6,8,2,1,3,4,9,5,7 -> 2,6,8,1,3,4,9,5,7 -> 2,6,8,1,3,4,9,5,7 -> 1,2,6,8,3,4,9,5,7 ->
.....
-> 1,2,3,4,5,6,7,8,9

잠깐✋🏻

시간 복잡도는 같은데 왜 속도 차이가 날까?

시간 복잡도가 같다고 한 것은 시간 복잡도를 단순히 측정했을 때 그렇다는 뜻이고, 알고리즘은 초기 데이터 상태에 따라 처리 속도가 달라진다.

📌에피소드 27. 스택, 큐가 뭐죠?

추상 자료구조(abstract data type, ADT)

배열

array = ["사과", "배", "김치"]

추상 자료구조는 배열과 같이 뚜렷한 문법이 아닌 개발자의 상상에 의해서 만들어진 개념이다.

기존 프로그래밍 언어의 문법 (배열) ➕ 어떤 규칙 🟰 큐, 스택

스택 = 팬케이크

배열이 수직으로 쌓여있다고 생각해보자.

가장 마지막으로 올린 팬케이크 부터 먹듯이, 배열의 맨 위에 올라간 데이터부터 삭제하거나 추가할 수 있다.

스택의 규칙

규칙 1: 위에서 데이터를 쌓는다.
규칙 2: 위에서부터 데이터를 뺀다.

LIFO 방식 : Last In, First Out

큐 = 버스 정류장

가장 먼저 줄 선 사람이 버스에 먼저 타듯이, 가장 먼저 들어온 데이터가 먼저 빠져나간다.

큐의 규칙

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

FIFO 방식 : First In, First Out (선입선출)

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

웹 브라우저의 뒤로 가기 버튼 ➡️ 스택
되돌리기 단축키 ctrl+z ➡️ 스택
주문이 들어오는 순서대로 처리(식당,쇼핑몰) ➡️ 큐

📌에피소드 28. 해시 테이블이 뭐죠?

개발자가 가장 많이 하는 고민은 '어떻게 하면 프로그램 속도를 더 빠르게 만들 수 있을까'이다. 이럴 때는 자료구조와 알고리즘을 공부하면 도움이 된다.

해시 테이블

해시 테이블은 사전에 비유할 수 있다.

해시테이블	사전
키	단어
값	단어의 뜻

일반적인 배열

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

라떼의 가격을 찾으려면 배열을 처음부터 모두 확인(선형 검색) 해야하고 시간이 오래 걸린다.

해시 테이블

menu = {
  커피: 10,
  라떼: 12,
  카모마일: 15,
  케이크: 45
};

'라떼'만 검색하면 라떼 가격을 바로 알 수 있다.

배열 검색과 해시 테이블 검색의 시간 복잡도 차이는?

배열 검색 => 선형 검색 => $O(N)$
해시 테이블 => $O(1)$ : 어떤 값을 찾더라도 딱 한단계만 거침.

해시 테이블을 더 창의적으로 활용하기

일반적인 배열에서는 대한민국을 찾으려면 처음부터 모든 값들을 다 훑어봐야한다.

// 배열
countries = ["브라질","그리스","영국","대한민국","이탈리아"]

// 해시 테이블
countries = {
	"브라질": true,
    "그리스": true,
    "영국": true,
    "대한민국": true,
    "이탈리아": true,
}

해시 테이블에서 대한민국의 유무를 알고 싶다면 다음 코드 처럼 알아볼 수 있다.

countries["대한민국"] // true

반대로 6개에 포함되어 있지 않은 나라인 러시아를 검색해 본다면?

countries["러시아"] //undefined

📌에피소드 29. 개발자 필수 소양, 클린 코드!

개발자라면 누구나 읽어야할 책, <<클린 코드>>

클린코드란 설명이 필요없는 코드. 코드를 읽기만 해도 이 코드의 역할은 무엇이고, 어떤 의미를 갖는지 물어볼 필요가 없을 만큼 깔끔한 코드.

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