정렬(sorting) 알고리즘은 순서 있게 정리한 알고리즘이다. (e.g. 1,2,3,4 or 4,3,2,1)
시간 복잡도는 같으면서 성능은 다른 정렬 알고리즘 3가지
왼쪽, 오른쪽만 보면서 정렬하는 버블 정렬(bubble sort) - 2칸짜리 창문을 놓고 오른쪽으로 1칸씩 밀면서 왼쪽과 오른쪽을 비교하는 방식으로 정렬한다. 오른차순으로 정렬할 경우 왼쪽이 크면 오른쪽과 자리를 바꾸며 이런 작업을 한 사이클이라고 한다. 모두 올바르게 정렬될 때까지 여러 사이클을 반복한다. - 버블 정렬의 시간 복잡도는 비교 횟수, 교환 횟수 등을 고려하면 O(N^2)이다. 시간 복잡도가 O(N^2)인 알고리즘은 좋은 알고리즘이 아니기 때문에 잘 사용하지 않는다.
하나를 콕 집어가며 정렬하는 선택 정렬(selection sort) - 전체 데이터 중에서 가장 작은 데이터 또는 가장 큰 데이터의 위치를 따로 기억하는 방식으로 작업을 진행한다. 오름차순 정렬을 한다고 했을 때, 맨 앞 0번째 위치부터 시작해서 그 다음 위치와 데이터를 비교해 나가면서 가장 작은 데이터가 몇 번째 위치인지 저장한다. 가장 작은 데이터가 있는 위치와 0번째 위치의 값을 서로 교환하는 것이 한 사이클이며 모두 올바르게 정렬될 때까지 여러 사이클을 반복한다. - 선택 정렬의 시간 복잡도는 O(N^2)이다. 하지만 자리를 바꾸는 연산은 사이클당 1번씩만 하기 때문에 버블 정렬보다는 조금 더 효율적이다.
앞에 있는 데이터를 보면서 배치하는 삽입 정렬(insertion sort) - 삽입 정렬은 앞에 있는 데이터를 보면서 배치하는 특징이 있다. 그래서 0번째가 아닌 1번째 데이터부터 비교를 시작한다. 오름차순 정렬을 한다고 했을 때, 앞에 있는 데이터와 비교해서 더 작은 값을 앞쪽으로 밀어 넣고 한 사이클이 끝난다. 그 다음 사이클에서는 2번째 데이터부터 앞쪽 데이터들과 비교를 시작하고 더 작은 값을 앞쪽으로 밀어넣는다. 즉, 사이클마다 데이터 1개를 앞쪽으로 밀어넣기 작업을 한다. 모두 올바르게 정렬될 때까지 여러 사이클을 반복한다. - 삽입 정렬은 선택 정렬, 버블 정렬보다 빠르지만 시간 복잡도는 O(N^2)이다.
버블 정렬, 선택 정렬, 삽입 정렬의 시간 복잡도가 같지만 속도 차이가 나는 이유? - 단순히 기계적으로 측정한 시간 복잡도는 같을 수 있지만, 알고리즘은 초기 데이터 상태에 따라 처리 속도가 달라진다는 특징이 있기 때문에 시간 복잡도가 같다고 해도 알고리즘 별로 평균적으로 더 빠른 알고리즘이 있을 수 있다.
정렬은 개발자에게 매우 중요한 주제이다. 정렬에 어떤 작업이 필요한지, 시간 복잡도는 상황에 따라 다를 수도 있다는 콘셉트를 이해하자!
개발자의 책상 위 필수 아이템! ->컴퓨터(16인치 맥북 프로) / 기계식 키보드 / 큰 모니터+모니터암 / 캠 / 종이노트(할일 목록 작성 후 체크) / 스탠딩 데스크
ep.27 스택, 큐가 뭐죠?
큐(queue)와 스택(stack) 자료구조는 기존 프로그래밍 언어의 문법으로 데이터를 저장할 때 어떤 규칙만 부여하면 되기 때문에 배열 자료구조처럼 문법으로 구현되어 있지 않다. 즉, 배열에 큐의 규칙을 부여하면 그 배열은 큐라고 할 수 있다. 이런 개념을 추상 자료구조(abstract data type, ADT)라고 한다.
스택의 규칙 [ 팬케이크 쌓기 규칙! LIFO(last in, first out. 후입선출) ]
규칙 1: 위에서 데이터를 쌓는다.
규칙 2: 위에서부터 데이터를 뺀다.
=> 스택은 뭘로 구현해도 상관없다. 위의 규칙만 지키면 된다.
큐의 규칙 [ 버스정류장! FIFO(first in, first out. 선입선출) ]
규칙 1: 위로 데이터를 쌓는다.
규칙 2: 아래서부터 데이터를 뺸다.
=> Queue up: 줄을 서다 배열을 예시로 들었을 뿐 큐도 뭘로 구현해도 상관 없다. 위의 규칙만 지키면 된다.
스택과 큐는 언제 사용할까?
스택(stack) - 1. 웹 브라우저의 뒤로 가기 버튼 (마지막에 방문한 페이지를 뺀다) - 2. 되돌리기 단축키 (마지막 실행 기록을 빼서 없앤다)
큐(queue) - 1. 쇼핑몰 주문 처리 시스템 (주문이 들어온 순서대로 데이터를 쌓고, 처리한다)
ep.28 해시 테이블이 뭐죠?
해시 테이블은 키와 값을 짝지어 모은 것으로 데이터를 더 쉽게 정리할 수 있게 해준다. 해시 테이블을 사전에 비유하면 키는 단어, 값은 단어의 뜻으로 볼 수 있다.
배열로 데이터를 저장한 경우 특정 데이터를 찾고 싶다면 선형검색(처음부터 모두 확인)을 해야 하기 때문에 시간이 오래 걸린다. 선형 검색의 시간 복잡도는 O(N)이다. 하지만 해시 테이블을 이용하면 원하는 데이터만 바로 검색할 수 있다. 해시 테이블의 시간 복잡도는 O(1)이며 Big-O 표기법으로 표현할 수 있는 가장 빠른 시간(상수 시간)이다. 데이터 검색, 추가, 삭제할 때도 딱 한 단계만 거치기 때문에 효율성이 좋다.
해시 테이블은 배열 형태로 구성되어 있으며 검색할 때 쓰는 키를 숫자(인덱스)로 바꿔주는 역할을 하는 해시 함수를 통해 빠른 속도를 낼 수 있다.
각각 두 개의 다른 키값을 입력했지만 해시함수를 통해 같은 인덱스가 나와서 배열의 같은 위치 값을 가리키게 될 때, 그 값이 서로 일치하지 않은 상황을 해시 충돌(hash collison)이라고 한다.
해시 충돌 대처 방법 중 하나로 같은 인덱스에 또 다른 배열을 넣는 방법이 있다. 그렇게 되면 해시 함수를 통해 얻은 인덱스 안에 들어가서 선형 검색으로 원하는 값을 찾는다. 일반적으로 해시 테이블의 속도는 O(1)이지만, 해시가 충돌을 처리해야 하는 상황이 생길 수도 있기 때문에 해시 테이블에서 검색은 사실 항상 O(1)은 아니다.
해시 테이블 형태 (원하는 값 빠르게 찾기 가능!)
ep.29 개발자 필수 소양, 클린 코드!
어떻게 해야 깨끗하게 코딩할 수 있는지, 코드는 어떻게 개선해야 하는지 등을 담은 개발자 필독서 <클린 코드>. 다독을 권한다.
클린 코드란 설명이 필요 없는 코드를 말한다. 즉, 코드를 읽기만 해도 무슨 일을 하는지, 어떤 것을 의미하는지 물어보지 않아도 이해되는 코드이다. 내가 작성한 코드를 시간이 지나고 나서 봤을 때 무슨 내용인지 모른다면 그건 클린 코드가 아니다.
클린 코드를 위한 꿀팁 5가지
클린 코드 백서 1. 의미 있는 변수, 함수의 이름을 적절히 사용하라.
클린 코드 백서 2. 함수 이름은 가급적 동사로 지어라. - 함수 이름을 보고 어떤 기능을 하는 함수인지 유추할 수 있다. - 함수의 액션은 1개여야 한다.
클린 코드 백서 3. 매개변수는 너무 많이 쓰지 마라. - 매개변수는 3개 이하로 쓰는 것을 추천한다. - 매개변수가 많으면 호출할 때도 여러 인잣값이 전달되므로 타인이 함수의 역할을 쉽게 파악하기 어려워진다. - 매개변수를 불가피하게 많이 설정해야할 경우 컨피겨레이션 오브젝트 방식으로 매개변수를 묶어 전달하는 방법이 있다.
클린 코드 백서 4. 불린값을 인자로 보내지 마라. - 불린 값을 보낸다는 의미는 함수 내에서 if~else문을 사용한다는 뜻이다. 그렇다면 함수는 1개의 액션만 취해야 한다는 규칙에 위배되기 때문에 if 로직 함수, else 로직 함수를 각각 분리하는 것이 좋다.
클린 코드 백서 5. 축약어를 쓰지 마라.
매개변수를 묶어 전달하는 컨피겨레이션 오브젝트 방식
오늘의 파트에 대한 소감(떠오르는 생각) :
클린 코드의 중요성은 많이 들었지만 막상 적용하려고 노력을 잘 하지 않았던 것 같아서 좀 부끄러워졌다. 그동안 어렴풋이 주변에서 듣거나 다른 개발 블로그들을 통해 알게 됐던 내용들이 이 책에 기반한 내용이었다는 것을 알게 되어 이 <클린 코드> 책이 왜 개발자 필독서인지 새삼 느끼게 되었다. 책의 두께에 압도되어 읽을 엄두가 나지 않아 미뤄두었는데 오늘 파트를 읽고 <클린 코드>를 올해 안에 꼭 읽어보겠다는 다짐을 했다! 개발 바이블처럼 두고 두고 반복해서 보고 클린 코드의 원칙을 지키면서 코드를 작성하는 습관을 들이자!
추가로 알게된 것(책내용+a 로 궁금한 것, 이해가 가지 않는 것 등)
버블 정렬의 시간 복잡도 계산 과정 검색 해볼 것.
소감 3줄 요약(오늘 TIL 3줄 요약) :
버블 정렬, 선택 정렬, 삽입 정렬 알고리즘은 시간 복잡도가 같지만 속도의 차이가 있다. 이는 알고리즘은 초기 데이터 상태에 따라 처리 속도가 달라지기 때문이다.
