노마드코더 북클럽 잡학사전 Day09 - 정렬 알고리즘 | 클린코드

 

 

📚 범위 : Ep26. 정렬 알고리즘 - Ep29. 클린코드

 

 

 

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

---

시간복잡도는 같으면서(O(N²)) 성능은 다른 정렬 알고리즘 3가지 = 버블 / 선택 / 삽입 정렬

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

모두 시간복잡도는 같지만 알고리즘은 초기 데이터 상태에 따라 처리 속도가 달라지기도 하고, 최악의 경우에는 시간이 매우 길어지기도 한다.

하지만 최악의 경우는 정발 드물기 때문에 보통 평균적인 시간이 측정된다. 따라서 시간복잡도는 같지만 성능이 달라지기도 한다.

실제로는 bubble < selection < insertion 순으로 성능이 좋다.

 

• 버블정렬 (Bubble Sort)
  • 실제로 썩 효율적이지는 않아서 많이 사용하지는 않음
  • 왼쪽, 오른쪽을 비교하면서 자리를 이동하며 한 사이클을 도는 알고리즘
  • 최악의 경우에는 모든 데이터의 자리가 바뀔 수도 있음

 

@노마드코더 유튜브

 

 

• 선택 정렬 (Selection Sort)
  • 가장 작거나 가장 큰 데이터의 위치를 기억해서 데이터를 정렬한다.
  • 선택된 데이터까지만 순서가 정렬되므로 버블 정렬보다 효율적이다.
   

@노마드코더 유튜브

 

 

• 삽입 정렬 (Inserttion Sort)
  • 앞의 데이터를 보면서 자리를 정렬해 준다.
  • 한 사이클당 이동은 한 번만 한다.
  • 데이터의 자리를 교환하는 것이 아니라 밀어 넣는 방식이다.

@노마드코더 유튜브

 

• 스택 (Stack) VS 큐 (Queue)
  • 이 두 가지는 배열처럼 실제로 존재하는 개념은 아니고, 상상 속의 개념 ⇒ 큐나 스택은 문법으로 구현된 것이 아님
  • 프로그램 문법으로 데이터를 저장 시 규칙을 부여하기만 하면 된다. 
  • 이런 개념을 추상구조 (Abstract Data Type, ADT)라고 한다.
  • 스택 (Stack)
    • 팬 케이크 먹을 때와 같다고 생각하면 쉽다.
    • 맨 아래부터 쌓이고, 맨 위의 데이터부터 사용된다. = LIFO ( Last in, First out)
    • 웹 브라우저의 뒤로 가기 단축키(⬅) , 되돌리기 키(Ctrl + z)
  • 큐 (Queue)
    • 버스 탈 때와 같다고 생각하면 쉽다.
    • 맨 아래부터 쌓이고, 맨 아래에 있는 데이터부터 사용된다. = FIFO (First in, First out)
    • 쇼핑몰 처리 시스템 ( 주문이 들어온 순서대로 data 쌓고, 제일 먼저 들어온 주문부터 처리함)
• 해시 테이블
  • 프로그램의 속도를 더 빠르게 하기 위해서 사용한다.
  • 키와 값을 짝지어서 모은 것
  • 어떤 값을 찾을 때 배열은 선형 검색 (데이터를 처음부터 확인하며 검색) 해야 하는데, 해시테이블은 사전처럼 원하는 값을 바로 검색할 수 있다.
  • 선형 검색 시간복잡도 : O(N), 해시 테이블 시간복잡도 : O(1)

IT 5분 잡학사전 - Array와 Hash Table 비교

▼ 해시테이블 자세히 알아보기

• 해시테이블에는 해시 함수라는 것이 있어서 key를 특정 Index로 변환 해준다.
• 해시 충돌 : 변환 된 Index의 값이 겹칠 경우를 말한다.
  • 이 경우 여러가지 해결방법이 있는데 2가지 정도만 소개하면 다음과 같다.
    • 먼저 변환된 key의 번호를 해당 Index에 부여하고, 겹치는 key를 다음 Index에 부여하기
    • 겹치는 Index에 또 다른 배열을 넣어서 해결하기
  • 충돌이 일어나는 경우에는 사실 시간복잡도가 O(1)은 아니다.

 

• 클린코드
  • 의미 있는 변수, 함수 이름을 적절히 사용하기
  • 함수이름은 동사로 작성하기 (ex. userData < loadUserData)
  • 매개변수를 너무 많이 쓰지 말자 (많을 경우 Configuration object 방식으로 사용가능)
  • Boolean 값을 인자로 보내지 말자 (true / false일 경우 따로 작성하면 함수가 2가지 일을 해야 한다.)
  •  축약어를 쓰지 말자 (다른 사람이 알아보기 쉽게 작성)

 

 

 

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

---

오늘 내용 중에는 책으로 보고 이해하기에는 어려운 개념이 많아서 이해하는 데 시간이 많이 걸렸다.

그래도 잘 이해가 되지 않아서 이 책의 원본?이라고 할 수 있는 유튜브 영상을 봤더니 정말 쉽게 이해할 수 있었다.  확실히 글 < 그림 < 영상 순으로 이해가 잘 되는 것 같다고 느꼈고 앞으로 블로그에 개념을 정리할 때 글로만 정리하지 말고 다른 자료들도 함께 사용하여 정리해야겠다는 생각이 들었다.

그리고 클린코드에 대한 내용이 다시 나왔는데, 책으로 읽었을 때 분명 기억했던 것들인데 막상 코드 작성할 때는 소홀히 한 적이 많은 것 같아서 앞으로 코드 짤 때 조금 더 생각하면서 작성해야겠다고 다짐했다.

 

 

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

---

3가지의 정렬 알고리즘이 잘 이해가 되지 않아서 다른 자료들을 찾아보다가 니콜라스가 잘 설명해 둔  영상을 발견해서 첨부해 두었다.

- 알고리즘 & 데이터 구조 Sort