노마드 코더에서 진행하는 챌린지 기록들
노개북 챌린지 6일차
오늘의 범위
- episode 26: 정렬 알고리즘이 뭐죠?
- episode 27: 스택, 큐가 뭐죠?
- episode 28: 해시 테이블이 뭐죠?
- episode 29: 개발자 필수 소양, 클린 코드!
Ep 26 정렬 알고리즘이 뭐죠?
정렬 알고리즘(sorting algorithm)은 말 그대로 데이터를 순서대로 정리하는 알고리즘이다. 다음 소개하는 세 가지 알고리즘은 시간 복잡도는 같지만, 성능이 다른 정렬 알고리즘이다.
버블 정렬(bubble sort)
버블 정렬은 데이터를 두 개씩 비교해가며 자리를 바꾸면서 정렬하는 방식이다.
오름차순을 기준으로 할 때, 한 바퀴를 돌면 제일 큰 숫자가 맨 오른쪽에 위치하게 된다. 이를 한 사이클이라 하며 데이터의 길이만큼 사이클을 돌고 나면 정렬이 끝난다. 버블 정렬의 시간 복잡도는 O(N^2)이다. (참고로 시간 복잡도가 O(N^2)인 알고리즘은 좋지 못한 알고리즘이다.)
선택 정렬(selection sort)
선택 정렬은 전체 데이터 중 가장 작거나 큰 데이터의 위치를 따로 기억하는 방식으로 작업을 진행한다.
오름차순을 기준으로 하면, 첫 번째 데이터부터 차례대로 읽어가며 제일 작은 데이터의 인덱스를 저장한다. 한 사이클이 끝나면 첫 번째 데이터와 최종적으로 저장한 인덱스에 해당하는 데이터를 교환한다. 그다음 사이클부터는 이전 처음 데이터보다 한 칸 뒤에 있는 데이터부터 사이클을 시작하며 마찬가지로 모든 사이클을 진행하면 정렬이 끝난다.
선택 정렬의 시간 복잡도는 버블 정렬과 동일한 O(N^2)이다. 그럼 성능도 같지 않을까 생각할 수 있겠지만 선택 정렬은 버블 정렬보다 효율적이다! 매번 교환을 거치는 버블 정렬과 달리 선택 정렬은 한 사이클 당 한 번의 교환만 하기 때문이다.
삽입 정렬(insertion sort)
삽입 정렬은 인덱스 1 즉, 두 번째 데이터부터 시작하여 앞의 데이터와 비교해 삽입하는 방식으로 이루어진다.
교환이 아닌 삽입으로 이루어진다는 것이 특징이고 다음 사이클부터는 이전 비교 인덱스보다 바로 뒤 인덱스부터 비교를 시작한다. 삽입 정렬 역시 시간 복잡도는 O(N^2)이다. 그러나 가장 중요한 핵심은 버블 정렬, 선택 정렬보다 빠르다는 것이다.
위 세 정렬은 왜 시간 복잡도는 O(N^2)로 같은데 성능은 다른 걸까?
알고리즘은 초기 데이터의 상태에 따라 처리 속도도 달라진다는 특징이 있어 단순히 기계적으로 측정한 시간 복잡도는 같아도 알고리즘의 속도에서 차이를 보일 수 있기 때문이다.
Ep 27 스택, 큐가 뭐죠?
스택과 큐는 배열처럼 실제로 존재하는 개념은 아니고 하나의 규칙이라고 생각하면 편하다. 배열에 스택의 규칙을 부여하면 스택이 되는 거고 큐의 규칙을 부여하면 큐가 되는 것처럼 말이다. 이러한 개념을 추상 자료구조(abstract data type, ADT)라고 한다.
스택과 큐의 규칙
스택은 위에서부터 데이터를 하나씩 쌓고 데이터를 빼낼 때도 맨 위에서부터 꺼내는 방식이다. LIFO(Last In, First Out), 즉, 나중에 넣은 것이 먼저 나온다는 것이다.
큐는 위에서부터 데이터를 쌓는 과정은 같지만, 스택과는 반대로 제일 처음에 쌓은 데이터를 먼저 꺼내는 방식이다. FIFO(First In, First Out)라고 한다.
언제 사용할까?
예를 들어 설명하자면, 웹의 뒤로가기 버튼과 되돌리기 단축키는 스택으로 구현한다. 맨 마지막에 방문하거나 실행한 데이터로 되돌리려고 하기 때문이다.
반면에 제일 먼저 들어온 주문부터 해결해야 하는 쇼핑몰 주문 처리 방식은 큐로 구현한다.
Ep 28 해시 테이블이 뭐죠?
해시 테이블은 키값 쌍을 모아놓은 것으로 전체 데이터를 하나씩 확인할 필요 없이 키를 검색하면 값을 바로 찾을 수 있다는 특징이 있다.
해시 테이블의 시간 복잡도는 무려 O(1)로 Big-O 표기법 중 가장 빠르다. 데이터를 추가하거나 삭제 또는 검색 모두 O(1)로 선형 검색의 시간 복잡도가 O(N)인 것에 비하면 효율이 매우 높다는 것을 알 수 있다.
해시 함수
이렇게 빠른 시간 복잡도를 가질 수 있는 것은 바로 해시 함수 때문이다.
해시 함수는 데이터를 검색할 때 사용하는 키를 인덱스로 바꾸는 역할을 한다. 예를 들어 배열 내 키의 글자 수를 인덱스로 반환하는 해시 함수를 구현했다고 한다면 키 “수달”의 값은 인덱스 2번에 있는 것이다.
그러나 만약 키가 두 글자인 데이터가 두 개 이상 존재한다면 어떨까. 먼저 해시 함수를 거친 후, 인덱스 2에 해당하는 배열에 들어가 선형 검색으로 해당 데이터를 검색한다. 그리고 일치하는 키의 값을 반환하는 것이다.
이런 충돌을 추가로 처리해 줘야 하는 상황이라면 시간 복잡도가 꼭 O(1)이 아닐 수도 있다.
Ep 29 개발자 필수 소양, 클린 코드!
개발자는 대부분 팀으로 일하는 직업이기 때문에 코드를 공유하고 여러 명이서 작업해야 할 때 클린 코드는 매우 중요한 소양 중 하나이다. 클린 코드란 코드를 읽기만 해도 코드가 무슨 일을 하는지, 어떤 의미가 있는지 이해할 수 있는 코드를 뜻한다.
클린 코드를 위한 꿀팁
1. 의미 있는 변수나 함수의 이름을 사용하기
변수나 함수의 이름을 딱 봐도 무슨 일을 하는지 알 수 있도록 의미 있게 짓는 것이 좋다.
2. 함수 이름은 가급적 동사로!
함수의 이름은 동사로 짓는 것이 좋다. 함수는 한 가지 역할만을 하는 것이 베스트인데, 동사로 이름을 짓게 되면 해당 함수가 적절하게 기능을 하는 건지 아니면 과도한 기능을 수행하고 있는지 확인할 수 있고 함수가 하는 일이 무엇인지 역할을 명확하게 알 수 있기 때문이다.
3. 매개변수는 너무 많이 쓰지 않기
함수의 매개변수는 3개 이하가 적당하다. 매개변수가 지나치게 많으면 함수를 호출할 때 인잣값만 보고 역할을 파악하기가 힘들기 때문이다.
4. 불린값을 인자로 보내지 말기
인자로 불린값을 보내게 되면 함수 내부에서 참, 거짓에 따라 두 가지 일을 처리해야 한다는 뜻이 된다. 이는 ‘함수는 한 가지 일을 잘해야 한다.‘라는 규칙에 위배되므로 하지 않는 것이 좋다.
5. 축약어 쓰지 않기
코드는 나뿐만 아니라 남이 보기에도 쉬워야 한다. 나만이 알아볼 수 있는 축약어는 쓰지 않는 것이 좋다.
느낀 점
정렬 알고리즘, 스택, 큐 모두 코테 문제 풀면서 많이 사용해봤던 알고리즘인데, 그냥 통과하기만을 위한 코드를 짜는 것도 좋지만 이렇게 다시 한번 복습하고 넘어가니 놓치고 있던 것도 기억나고, 해시도 잘 안 써보긴 했는데 가끔 해시 쓰면 엄청 빠를 때가 있어서 잘 다룰 수 있게 더 찾아봐야겠다.
어찌어찌 대부분은 그냥 문제 풀면서 터득한 거라 어떤 상황에서 제대로 활용할 수 있는지는 잘 몰랐다. 사실 알고리즘을 따로 공부해야겠다고 생각하긴 했는데 진짜 해야지 이제.
클린코드는 책 두께의 압박감이 심해서 아직 끝까지 읽어보진 못했는데 시간 날 때 정독하는 것도 좋을 것 같다. 본문 내용도 알고는 있지만 늘 실천은 힘들어.. 항상 이름 짓는 건 너무 괴롭다. 영어 공부도 더 해야겠지.
그렇지만 이렇게 할 게 많다는 것도 절대 심심할 틈을 안 주는 것 같아서 매일 새로워서 좋다. 우는 거 아님 암튼 아님
References
book - IT 5분 잡학사전