2020년 9월, 개발자에 관심을 갖고 처음 자바스크립트 공부를 시작하면서 눈에 보이는 무언가를 만드는 데에만 급급했다. 현실적인 문제로 취업이 급해서 리액트와 리액트 네이티브를 건드리면서 포트폴리오를 만들었고 취업을 했지만 알고리즘에 대한 지식과 문제풀이 실력이 너무 형편없었다 ㅜ.ㅜ 같은 기능을 하는 코드여도 더 깔끔한 코드로 만드는 것에 대해서도 부족함을 느꼈고.. 알고리즘 공부와 자바스크립트 기초를 다시 다져봐야겠단 결심을 했다.
이 게시글은 알고리즘의 개념들을 전체적으로 훑어보는 용으로 작성하였으며 코드 예시나 자세한 내용은 따로 게시글을 올릴 예정이다.
시간복잡도
문제를 해결하기 위한 시간(연산)의 횟수를 시간복잡도 라고 한다.
시간복잡도가 큰 알고리즘들은 더 큰, 혹은 많은 데이터를 처리할 때 훨씬 오랜 시간이 걸린다.
이 계산 횟수의 정확한 측정이 어렵기 때문에 보통 Big-O 표기법을 이용한다고 한다.
시간복잡도에서 중요하게 보는 것은 가장 큰 영향을 미치는 n의 단위이다.
- O(1)
: 상수 형태. n의 값에 상관없이 일정한 양의 계산만 한다. - O(logn)
: 로그 형태. - O(n)
: 선형. - O(nlogn)
: 선형로그 형태. - O(n²),O(n³),⋯
: 다차 형태. - O(2ⁿ)
: 지수 형태. - O(n!)
: 팩토리얼 형태.
자료구조
자료구조란 데이터 사이의 관계를 반영한 저장구조 및 그 조작방법을 뜻한다.
데이터에 맞는 특성의 자료구조를 사용하는 것이 중요하다.
선형 구조 : 한 종류의 데이터가 선처럼 길게 나열된 자료구조.
- 배열
- 해시
- 스택
- 큐
- 덱
- 연결리스트
비선형 구조 : 선형 구조가 아닌 모든 자료구조. i번째 값을 탐색한 뒤의 i+1이 정해지지 않는 구조
- 그래프
- 트리
정렬
시간복잡도 O(n²) 정렬 알고리즘
O(n²) : 계산 시간이 정렬할 자료의 수의 제곱에 비례해서 늘어난다. 즉, 1만 개를 1초에 정렬하면 10만 개를 정렬하는 데에는 100초 정도가 필요하다.
- 버블(bubble) 정렬
: 가장 쉬운 정렬 알고리즘이지만 비효율적이고 잘 사용하지 않는다.
바로 뒤의 원소와 비교하여 정렬한다. - 선택(Selection) 정렬
: 버블 정렬과 유사하다. 처음부터 끝까지 훑어서 가장 작은게 첫번째, 그 다음 2번째부터 끝까지 훑어서 가장 작은게 두번째.. 이런식으로 가장 큰 수가 배열의 마지막에 위치하게 되는 정렬이다. - 삽입(Insertion) 정렬
: 하나씩 삽입해 나가는 형태의 정렬방식.
특정 값에 대해서 그 값이 맞는 위치를 찾고, 나머지는 한칸씩 밀어낸다.
인덱스를 설정하여 현재 위치의 값을 아래쪽으로 순회하며 알맞은 곳에 넣어준다.
시간복잡도 O(nlogn) 정렬 알고리즘
- 병합(Merge) 정렬
: 원소 갯수가 1 또는 0이 될 때까지 쪼개나가며 좌측과 우측 리스트를 계속 분할해 나간 후 각 리스트 내에서 정렬 후 병합한다. - 힙(Heap) 정렬
: 힙이라는 자료구조를 통해 내림차순으로 숫자를 넣은후, 역순으로 꺼내어 정렬한다. - 퀵(Quick) 정렬
: 시간복잡도 O(nlogn) 인 정렬 알고리즘들 중 가장 빠르다.
원소 하나를 기준(pivot)으로 삼아 그보다 작은 것을 왼쪽으로 빼내고 큰 것을 오른쪽으로 보내는 걸 반복해 정렬한다.
개발을 게임처럼!