개발

해당 포스팅은 알고리즘 자료구조에 대해 다룹니다. Udemy JavsScript 알고리즘 & 자료구조 마스터 클래스를 공부하며 정리한 내용입니다. 최고의 자료 구조는 무엇일까요? 어떤 공통적인 것들이 자료 구조임을 나타낼 수 있을까요? 배열, 객체등 모두가 공통적으로 가지고 있는 특징은 값(value)들의 모음이라는 것이다. 왜 이렇게 많을까요? 특정 유형의 문제는 특정한 자료 구조가 효율적이기 때문이다. 일부 자료 구조는 매우 특화되어 있다. 배열과 객체와 같이 자주 사용되고 있는 일부 자료 구조들은 매우 일반적이며, 이것이 바로 이들이 무료로 제공되는 이유이기도 하다. 그러나 RB(Red and Black) 트리, 비방향 그래프, 혹은 그와 유사한 자료 구조로 작업해야 할 경우에 이들 자료 구조가 보..

기수 정렬: 소개 (Radix sort) 지금까지 살펴 본 모든 정렬들은 비교 정렬 알고리즘이라는 그룹에 속한다. 그 의미는 이렇습니다. 버블 정렬에 대해 다루거나, 더 발전된 퀵 정렬을 다루더라도 결국 본질적으로 기본 비교는 주어진 시점에서 두 개의 항목을 비교한다. 한 항목은 왼쪽에 있고, 하나는 오른쪽에 있으며 정렬 방식에 따라 어느것이 먼저 오고 나중에 올지 결정합니다. 그러므로 비교 정렬은 두 가지 비교한다는 의미이다. 더 작은 것과 더 큰 것을 비교한 다음에 항목의 위치를 결정합니다. 문제는 비교 정렬보다 더 나은 방법이 있을까요? O(n log(n))에서 더 나아질 수 있을까요? 더 좋아질 수 있나요? 답은 yes입니다. 하지만 비교를 통한 방법이 아니다. 수학적으로, 비교 정렬의 평균 시간..

퀵정렬 소개 퀵 정렬은 합병 정렬과 같은 방법으로 작동한다. 바로 재귀이다. 이건 기본적으로 데이터를 분할하여 배열에 0개 또는 1개의 항목이 남을 때까지 분할하고 개별적으로 정렬하는 방식이다. 이때 피벗포인트라고 불리는 단일 요소를 선택하여 수행한다. 어떤 배열에서 어떤 요소를 선택하든 중요하지 않다. 그저 만약 한 요소를 선택했다면 해당 요소보다 작은 것은 왼쪽으로 큰 것은 오른쪽으로 옮겨야한다. 이건 정렬이 아니라 그저 옮기에 가깝다. 즉 배열을 순회하면서 선택한 수보다 작은 것을 모두 선택해서 왼쪽으로 옮긴다. 모두 확인한 다음에 가져온 것끼리 배열한다. 피봇 helper 소개 배열이 주어질 때 한 요소를 피벗 포인터로 지정한다. 그 후 배열 속 요소를 재배치하는 함수를 작성한다. 피벗보다 작은 ..

기가 막히게 빠른 정렬 소개 목표 지금까지 배운 기초 알고리즘의 한계를 이해하기 합병 정렬 구현 퀵 정렬 구현 기수 정렬 구현 왜 배우나요? 버블 선택 삽입 정렬은 큰 규모에 적합하지 않다. 시간복잡도 O(n^2) → O(n log n)으로 바꿀 수 있다. 단순성은 떨어지지만 효율성이 더 좋다. 효율적인 알고리즘은 확실히 더 길고 이해하기 어렵다. 합병 정렬 소개(Merge Sort) 1948년 조나다 벤 노이만이 처음 고안했다. 이를 뒷받침하는 개념은 실제로 합병과 정렬이라는 두 가지 조합으로 이루어져 있다. 사실을 세가지 조합이라고 볼 수도 있다. 분할, 정렬, 합병이 모두 일어난다. 0개 요소, 1개 요소 배열이 이미 정렬되어 있다는 점을 활용한다. 배열을 더 작은 배열로 나누는 방식이다. 흔히 분..

💡요약 알고리즘의 효율 측정을 위해 빅오 표기법 사용한다. 빅오는 실행 시간이나 공간 복잡도에 대해 알려준다. 빅오는 정확도가 아니라 전체적인 추세가 중요하다. 빅오로 측정되는 알고리즘의 시간과 공간 복잡도는 하드웨어에 영향받지 않는다. 빅오란? 어떤 문제에는 해결법이 여러가지가 존재한다. 내가 사용한 방법이 여러 방법 중에서 가장 나은 방법인가? 에 대한 고민을 해결해주는 것이 빅오이다. 빅오는 숫자로 코드의 성능을 표기해준다. 알고리즘 효율성을 비교할 때 빅오 표기법을 사용한다. 알고리즘을 공부하려면 가장 첫 번째로 배워야한다. 코드 시간 재기 function addUpTo1(n) { let total = 0; for (let i = 0; i < n; i++) { total += i; } return..