DeveloperJun

힙 정렬이란? 주어진 데이터들을 이진 트리로 구성하여 정렬하는 방법 입니다. 조금더 디테일 하게는 내림차순 정렬을 위해서는 최대 힙 트리를 구성하고 오름차순 정렬을 위해서는 최소 힙 트리를 구성하여 정렬을 하는 방법입니다. 그러고 보니 힙(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) 파일 내용이 하나의 긴 줄로 늘어선 형태로 저장되어 있어 순차 접근만 가능한 구조입니다. 판독할 때도 순차적으로 접근하기 때문에 순차 접근 방식이라고도 합니다. 급여 업무처럼 전체 자료를 처리 대상으로 일괄 처리하는 업무에 사용됩니다. 장점은 모든 데이터가 순서대로 기록되기 때문에..

그래프란? 자료 간의 관계가 망구조와 같이 복잡한 경우에 사용하며, 연결되어 있는 정점과 정점 간의 관계를 표현할 수 있는 자료구조입니다. 트리와 그래프의 차이점을 살펴보면 그래프는 루트 노드가 존재하지 않고, 방향 또는 무방향 그래프가 모두 존재합니다. 예시로 위 사진과 같은 최단 경로를 예시로 들 수 있습니다. 그래프는 vertex와 edge로 구성됩니다. 그래프는 대표적으로 위와 같은 종류의 그래프가 있습니다. 무방향 그래프 - 방향이 없는 그래프. 방향 그래프 - 정점 간의 간선이 방향을 갖고 있는 그래프. 가중치 그래프 - 정점 간의 간선에 가중치를 부여한 그래프. 순환 그래프 - 순환이 존재하는 그래프. 비순환 그래프 - 순환이 없는 그래프. 그래프 표현 방법 인접 행렬 (Adjacency M..

트리(tree)란? 나무가 하나의 뿌리에서 줄기가 나와 가지로 나누어지는 것처럼 나무를 거꾸로 뒤집어 놓은 형태로, 자료가 가지처럼 나뉘어서 계속 뻗어 나가는 계층구조를 트리 구조라고 합니다. 루트노드(root node) - 부모가 없는 최상위 노드 부모노드(parent node) - 노드에 연결된 한 단계 상위 레벨 노드 형제노드(sibling node) - 같은 부모를 가지는 노드 단말노드(leaf node) - 자식이 없는 노드 높이(height) - 깊이 최댓값 크기(size) - 모든 노드의 개수 깊이(depth) - 루트 노드로부터의 거리 차수(degree) - 각 노드의 간선 개수 레벨(level) - 노드의 특정 깊이를 가지는 노드의 집합 * 전체 간선의 개수는 (트리가 N개 일 때) N ..