DeveloperJun

퀵 정렬(Quick Sort)이란? 기준키를 기준으로 작거나 같은 값을 지닌 데이터는 앞으로, 큰 값을 지닌 데이터는 뒤로 가도록 하여 작은 값을 갖는 데이터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방법입니다. 이전에 만나봤던 합병정렬과 비슷하게 두 영역으로 분리하여 비교하는 정렬 방법입니다. 이렇게 두 영역으로 분리하여 각각을 해결하고 다시 합치는 전략을 분할 정복 방법이라고 합니다. 퀵 정렬의 원리를 좀더 간단하게 단계별로 나누면 아래와 같습니다. 1. 피벗을 설정한다. 2. 피벗보다 큰 수는 오른쪽 작은 수는 왼쪽에 배치한다. 3. 피벗을 기준으로 두개의 배열로 나눈다. 4. 각각의 배열을 1번부터 재귀적으로 반복한다. // 위치 변경 const swap = (arr, leftIndex, ri..

병합 정렬이란 합병 정렬 또는 병합 정렬이라고 불리며 O(n log n) 비교 기반 정렬 알고리즘입니다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나입니다. 정렬하고자 하는 데이터의 모임을 비슷한 크기의 두 부분으로 반복하여 나눈 뒤, 나누어진 부분 데이터들을 정렬한 다음에 다시 병합하면서 하나의 정렬된 데이터 모임으로 만드는 방법입니다. // 합병 정렬 const merge = (left, right) => { let arr = []; while (left.length && right.length) { if (left[0] < right[0]) arr.push(left.shift()); else arr.push(right.shift()); } return [..

힙 정렬이란? 주어진 데이터들을 이진 트리로 구성하여 정렬하는 방법 입니다. 조금더 디테일 하게는 내림차순 정렬을 위해서는 최대 힙 트리를 구성하고 오름차순 정렬을 위해서는 최소 힙 트리를 구성하여 정렬을 하는 방법입니다. 그러고 보니 힙(heap)이라는 것이 무엇일까요? 힙(heap)이란? 힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조 입니다. 힙에서 두가지 최대힙과 최소힙으로 나눠집니다. 따라서, 최대힙(Max Heap)은 큰 값이 위로 오도록, 최소힙(Min Heap)은 작은 값이 위로 오도록 구성하는 트리구조 입니다. 이처럼, root에 가장 큰 값 또는 가장 작은 값을 올리고 최종적으로 해당 값을 마지막 위치로 교환하여 정렬을 하는 방식입니..

셸 정렬 이란? 1959년 이 방법을 발표한 창안자 도널드 셸의 이름을 따서 붙여진 이름인데, 리스트를 특정 매개변수 값의 길이를 갖는 부파일(subfile)로 쪼개서, 각 부파일에서 삽입 정렬을 수행하는 삽입 정렬의 단점을 보완한 정렬 알고리즘 입니다. 사실, 셸 정렬은 설명만 듣고는 이해가 가질 않았습니다. 쪼개는 것은 알겠는데, 쪼개진 데이터들을 각각 정렬하는 것도 아닌 것이, 쪼개진 간격의 데이터끼리 하나씩 비교를 하는 느낌이었습니다. 이러한 일정한 갭 간격을 설정하고 간격의 데이터끼리 비교 정렬을 합니다. 그 이후, 간격을 줄이고 또 간격의 데이터끼리 비교 정렬을 합니다. 최종적으로 간격이 없는 상태까지 도달했을 때, 삽입 정렬을 통해 마지막으로 정렬을 합니다. 가장 잘 표현된 영상입니다. 이 ..

삽입 정렬(Insertion Sort)이란? 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬하는 방식을 삽입 정렬이라고 합니다. 실제로 삽입 정렬의 데이터 이동 흐름은 위와 같습니다. 여기서의 핵심은 빨간색 데이터를 위로 잠깐 빼놓고, 값을 비교하여 오른쪽으로 계속 당기는 과정이 핵심입니다. 빨간색 데이터와 바로 왼쪽의 데이터를 자리 바꿈으로 정렬을 하는 예제들이 많은데, 그렇게 하면 버블 정렬보다 훨씬 느리답니다 ㅠㅠ 그럼 코드로 확인해보겠습니다. // 임의 데이터 생성 const makeRandomValueArr = (length) => { const arr = []; for (let i = 0; i < length; i++) { arr.push(i); } for (let i = 0; i < ar..

선택 정렬(Selection Sort)이란? 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식입니다. 좀 더 쉽게 표현하면, 각 자리마다 가장 작은 값을 선택하는 개념 이라고 이해하시면 됩니다!! 출처 - https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC 생각보다 이해하는데 어렵지 않았던 개념이라 바로 javascript로 구현해보겠습니다. // 랜덤 임의 배열 만들기 const makeRandomValueArr = (length) => { const arr = []; for (let i = 0; i < length; i++) { arr.push(i); } for (let i = 0; i <..

버블정렬이란? 서로 이웃한 데이터들을 비교하며 가장 큰 데이터를 가장 뒤로 보내며 정렬 하는 방식입니다. 이모습이 꼭 버블같다고해서 붙여진 이름이라고 합니다. 정렬에 있어서 가장 기본이며 처음으로 배우는 정렬이라고 하니, 이를 통해 정렬의 사고력을 가져보자구요. 버블정렬의 동작 과정입니다. 위에서 말했듯 순차적으로 돌면서 2개씩 쌍으로 비교하여 가장 큰 값을 마지막으로 보내는 작업을 반복하여 수행합니다. 때문에, 배열의 크기에 따라 반복 수행되고, 그 안에서 한번더 배열의 크기에 따라 가장 큰 숫자를 마지막으로 밀어 넣는 작업을 합니다. 이를 간단하게 javascript로 구현해보겠습니다. const arr = [7,5,9,1,3,2,4]; // 버블 정렬 const bubbleSort = (array)..

정렬이란? 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 것을 의미합니다. 이러한 정렬을 위해 효율적인 문제 해결 과정을 정렬 알고리즘((Sorting Algoritm) 이라고 합니다. 그럼 정렬을 왜 해야 할까요? 사실 알고리즘이라는 목표는 효율적인 문제 해결을 위함입니다. 어떤 문제냐에 따라 방식과 결과물이 다르겠지만 결국에는 가장 빠르고 효율적인 작동을 하나의 목표로 합니다. 그러기 위해서는 효율적으로 데이터를 저장하는 방법을 이해해야 하고 (자료구조) 저장된 데이터를 효율적으로 찾을 수 있어야 합니다. 시간 복잡도에 대해 알아보면서, 효율적이고 정말 빠른 예시 중 이진 검색 기억하시나요? 이진 검색 또는 검색에 특화된 이진 탐색 트리는 데이터가 정렬이 되어 있다는 가정하에 해당 검..

시간복잡도란?(Time Complexity) 문제를 해결하는데 걸리는 시간을 시간복잡도라고 합니다. 걸리는 시간을 명확하게 알면 좋겠지만 같은 알고리즘이라도 서로 다른 성능의 컴퓨터 처리에 따라서 걸리는 시간 또한 각각 달라질 수 있습니다. 때문에,주로 점근적 분석법을 통해서시간복잡도를 나타냅니다. 점근적 분석법이란 입력되는 데이터의 크기에 따라 수행 시간과 공간이 얼마나 차지하는지 알아보는 탐색법입니다. 점근적 분석법에는 아래와 같이 3가지 표기법으로 나뉩니다. 최상의 경우 : 오메가 표기법 (Big-Omega(Ω) Notation) 평균의 경우 : 세타 표기법 (Theta(θ) Notation) 최악의 경우 : 빅오 표기법 (Big-O Notation) 평균의 경우는 기준이 모호하고, 최악의 경우를 ..

파일구조란? 파일은 고유한 이름을 갖는 것을 말하며, 관련된 정보 단위의 집합을 의미합니다. 파일 시스템은 보조 기억 장치에 저장되어있는 파일들을 관리해주는 총체적인 기술 체계를 의미합니다. 파일구조라는 것은 파일에서의 데이터를 표현하는 방식과 데이터에 접근하는 연산에 관한 것을 다루는 학문이기도 하며, 파일의 구조는 파일을 구성하는 레코드들이 보조기억장치에 편성되는 방식을 의미합니다. 순차 파일(Sequential File) 파일 내용이 하나의 긴 줄로 늘어선 형태로 저장되어 있어 순차 접근만 가능한 구조입니다. 판독할 때도 순차적으로 접근하기 때문에 순차 접근 방식이라고도 합니다. 급여 업무처럼 전체 자료를 처리 대상으로 일괄 처리하는 업무에 사용됩니다. 장점은 모든 데이터가 순서대로 기록되기 때문에..