목록알고리즘 & 자료구조 (6)

그럼에도 불구하고

[알고리즘 with JS] 기수 정렬(Radix Sort)란?

기수 정렬에 대해 알아보겠습니다. 🧑🏻‍💻 기수 정렬 (Radix Sort) 기수 정렬이란 낮은 자릿수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬입니다. 이는 요소 간의 비교를 하는 것이 아니며 숫자의 크기에 대한 정보가 자릿수로 인코딩 된다는 사실을 이용합니다. 📌 Radix Sort Helpers 기수 정렬을 구현하려면 먼저 몇 가지 도우미 함수를 구축하는 것이 도움이 됩니다. ⭐️ getDigit(num, place) 주어진 자릿값에서 num의 숫자를 반환합니다. function getDigit(num, i) { return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10; } getDigit(12345, 0); // 5 getDigit(1234..
알고리즘 & 자료구조/알고리즘 2023. 8. 25. 14:50
[알고리즘 with JS] 퀵 정렬(Quick Sort)이란?

퀵정렬에 대해 알아보겠습니다. 🧑🏻‍💻 퀵 정렬 (Quick Sort) - 퀵 정렬은 병합 정렬과 마찬가지로 0 또는 1개의 요소로 구성된 배열이 항상 정렬된다는 사실을 활용합니다. - 하나의 요소 ("피벗"이라고 함)를 선택하고 정렬된 배열에서 피벗이 끝나야 하는 인덱스를 찾는 방식으로 작동합니다. - 피벗이 적절하게 배치되면 피벗 양쪽에 퀵 정렬을 적용할 수 있습니다. 📌 Pivot Helper 병합 정렬을 구현하려면 먼저 피벗 양쪽의 배열 요소를 배열하는 기능을 구현하는 것이 유용합니다. 배열이 주어지면 이 도우미 함수는 요소를 피벗으로 지정해야 합니다. 그런 다음 피벗보다 작은 모든 값은 피벗의 왼쪽으로 이동하고 피벗보다 큰 모든 값은 피벗의 오른쪽으로 이동하도록 배열의 요소를 재정렬해야 합니다...
알고리즘 & 자료구조/알고리즘 2023. 8. 24. 22:09
[알고리즘 with JS] 병합 정렬(Merge Sort)이란?

병합 정렬에 대해 알아보겠습니다. 🧑🏻‍💻 병합 정렬 (Merge Sort) 병합 정렬은 존 폰 노이만(John von Neumann)이라는 사람이 제안한 방법입니다. 이 알고리즘을 사용하면 O(n^2)에서 O(nlogn)까지 시간 복잡도를 개선할 수 있습니다. 일반적인 방법으로 구현했을 때 이 정렬은 분할 정복 알고리즘의 하나입니다. 📌 분할 정복(divide and conquer) 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략입니다. 분할 정복 방법은 대개 순환 호출을 이용하여 구현합니다. ⭐️ 과정 설명 - 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 봅니다. - 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눕니..
알고리즘 & 자료구조/알고리즘 2023. 8. 23. 16:31
[알고리즘 with JS] 버블 정렬, 선택 정렬, 삽입 정렬에 대하여

버블 정렬, 선택 정렬, 삽입 정렬에 대해 알아보겠습니다. 🧑🏻‍💻 정렬이 무엇인가? 정렬은 항목이 일종의 순서가 되도록 컬렉션(예: 배열)의 항목을 재정렬하는 프로세스입니다. 📌 정렬을 왜 알아야 하는가? - 정렬은 매우 일반적인 작업이므로 작동 방식을 아는 것이 좋습니다. - 물건을 분류하는 방법에는 여러 가지가 있으며, 기술마다 장단점이 있습니다. ⭐️ 버블 정렬 (Bubble Sort) 버블 정렬은 잘 사용되지 않고 엄청 효율적이지는 않습니다. 하지만 어떻게 사용하는지 알면 재미있는 정렬 방식입니다. 버블 정렬의 개념은 배열을 가장 작은 숫자에서 가장 큰 숫자 순으로, 즉 오름차순으로 정렬한다면 더 큰 숫자가 한 번에 하나씩 뒤로 이동한다는 것입니다. 📚 버블 정렬 예시 - 배열의 끝인 i라는 변..
알고리즘 & 자료구조/알고리즘 2023. 7. 19. 11:15
[알고리즘 with JS] 검색 알고리즘이란?

검색 알고리즘에 대해 알아보겠습니다. [ 목적 ] - 검색 알고리즘이 무엇인지 알아보자 - 배열에서 선형 검색 구현 - 정렬된 배열에서 이진 검색 구현 - Naive String 검색 문자 알고리즘 구현 [ How do we search? ] 배열이 주어지면 값을 검색하는 가장 간단한 방법은 배열의 모든 요소를 살펴보고 원하는 값인지 확인하는 것입니다. [ 선형 검색 (Linear Search) ] 첫 부분에서 시작해서 끝 부분으로 이동하면서 한 번에 하나의 항목을 확인할 수도 있고, 끝 부분에서 시작해서 첫 부분으로 이동할 수도 있습니다. 중요한 것은 세트 간격으로 이동하면서 한 번에 하나의 항목을 확인하는 식으로 모든 항목을 확인한다는 것입니다. 📌 Linear Search Pseudocode ( 의..
알고리즘 & 자료구조/알고리즘 2023. 7. 14. 01:11
[알고리즘 with JS] 빅 오 표기법(Big O Notation)이란?

빅 오 표기법(Big O Notation)에 대해 알아보겠습니다. 목차 우선, 문제 하나 풀고 가실까요? 💡 quiz. 1부터 특정한 N 값과 그 사이에 있는 모든 숫자들을 더하는 함수를 만들어보세요. 📌 해답 1 function addUpTo(n) { let total = 0; for (let i = 0; i O(n) 앞의 상수는 중요하지 않습니다. 📌 2. O(500) => O(1) O(500)은 쉽게 말하면 연산 갯수가 어떤 상황에든 500개가 있다는 것입니다. 즉, 변동이 없습니다. 📌 3. O(13n²) => O(n²) 13n²이 무진장 많이 커진다면, 정말 셀 수 없이 커진다면 앞에 있는 13이 큰 의미가 있을까요? n² 보다?? ※ 더 작아지는 것도 중요하지 않습니다. 📌 1. O( n + ..
알고리즘 & 자료구조/알고리즘 2023. 6. 28. 23:52
이전 Prev 1 Next 다음