꾸준합니다

병합 정렬 : 자르고 합치기

이번 포스팅에서는 Merge sort - 병합 정렬에 대해 알아보도록 하겠습니다. 1. 병합 정렬 (Merge Sort) 이란? 이름에서 알 수 있듯이 병합정렬은 주어진 자료구조를 여러 조각으로 자르고 다시 합쳐 나가는 과정에서 정렬을 하는 정렬입니다. 구현 방식은 일반적으로 재귀로 구현되며 분할정복 방식이라는 데서 Quick Sort와 유사한 면이 있어 자주 비교 대상이 되곤 합니다. 퀵 정렬 : Pivot 이번 포스팅에서는 정렬의 종류 중 하나인 퀵 정렬에 대해서 알아보겠습니다. 대다수의 정렬이 구현된 언어, 프레임워크 등에서 자료구조를 정렬할 때 퀵 정렬 로직을 사용하고 있습니다. 어떠 hy1as.tistory.com 2. 병합 정렬의 진행 자료 구조의 길이가 0 또는 1이면 이미 정렬 된것으로 봅..

Big-O Notation - 공간 복잡도

이번 포스팅에서는 공간 복잡도에 대해 이야기해보도록 하겠습니다. 1. 공간 복잡도란? 공간 복잡도는 해당 문제를 해결하기위해 얼마나 많은 공간(메모리)을 필요로 하느냐를 나타내는 척도입니다. 공간 복잡도 또한 시간복잡도와 같이 빅 오 표기법으로 표현 할 수 있습니다. 빅 오로 공간복잡도를 표현할 때 핵심 질문은 "데이터 원소가 N개 일 때 알고리즘은 메모리 단위를 얼마나 소모할까?"입니다. 아래의 코드를 한 번 보겠습니다. function makeUpperCase(array) { let newArray = []; for (let i = 0; i < array.length; i++) { newArray[i] = array[i].toUpperCase() } return newArray; } 위의 코드는 크기..

퀵 정렬 : Pivot

이번 포스팅에서는 정렬의 종류 중 하나인 퀵 정렬에 대해서 알아보겠습니다. 대다수의 정렬이 구현된 언어, 프레임워크 등에서 자료구조를 정렬할 때 퀵 정렬 로직을 사용하고 있습니다. 어떠한 이유 때문에 이처럼 선호하는 것일까요? 지금부터 알아보도록 하겠습니다. 1. 퀵 정렬이란? 퀵 정렬 (Quick Sort)은 이름에서도 알 수 있듯이 지금까지 포스팅한 정렬 알고리즘 중 상대적으로 빠른 효율적 정렬 알고리즘입니다. 일반적인 평균 시나리오에서 효율적이며 최악의 시나리오라 할지라도 삽입 정렬, 선택 정렬 등과 유사한 시간 복잡도를 가지고 있습니다. 2. 핵심 개념 : 분할 (Partition) 퀵 정렬에서 배열을 분할 한다는 것은 배열에서 임의의 수 (pivot)을 선택한 후 pivot보다 작은 것은 왼쪽,..

재귀 (3) : 효율적인 재귀 사용

지난 포스트에서는 재귀 호출의 구현에 대해 알아보았습니다. 재귀 호출의 마법 같은 힘은 정말 대단하지만 주의해서 사용하지 않으면 아주 큰 비용을 치러야 할 수 있습니다. 오늘은 재귀 호출의 비용 이야기와 함께 재귀 호출의 효율성을 증대시킬 수 있는 방법에 대해 알아보고자 합니다. 1. 불필요한 재귀호출 여기 배열의 최댓값을 찾는 재귀 함수가 있습니다 function max(array) { if (array.length === 1) return array[0]; if (array[0] > max(array.slice(1))) { return array[0]; } else { return max(array.slice(1)) } } 각 배열을 하위 함수로 전달하며 반환 값을 배열의 첫번째 원소와 비교하고 있습..

재귀 (2) : 미래의 나야, 부탁해~

이번 포스트에서는 미래의 내가 풀어주는 재귀의 마법 같은 힘에 대해 알아보겠습니다. 1. 재귀의 카테고리 재귀에 관련된 문제를 풀이하다보면 해당 문제들이 비슷한 패턴을 띄고 있는 것을 발견할 수 있습니다. 그 패턴에 대해 알아보며 비슷한 문제를 발견 했을때 해결할 수 있는 힘을 길러 보겠습니다. (1) 패턴 1 - 반복 실행 반복적으로 하나의 작업을 실행하는 카테고리 입니다. 기저 조건을 가지고 단순히 하나의 작업을 기저 조건을 만족 할 때까지 반복 합니다. 이전 포스트에서 다뤘던 CountDown 함수가 그러 합니다. function countdown(number) { if (number < 0) return; console.log(number); countdown(number - 1); } 만일 배열..

재귀 (1) : Call me

오늘은 컴퓨터 과학에서의 재귀의 개념에 대해서 알아보도록 하겠습니다. 1. 재귀 ( Recursion )란? 재귀란 무엇일까요? 여기 너무나도 명확하게 답해줄 수 있는 예시가 있습니다. function foo() { foo(); } 이와같이 재귀란 함수가 자기 자신을 재호출하는 로직을 뜻하는 용어입니다. 다른 예를 하나 더 볼까요? function CountDown(number) { for(let i=number; 0 5는 기저 조건이 아니기에 $ Factorial(4) $를 호출합니다. $ Factorial(4) $가 호출 되었을 때 => 4는 기저 조건이 아니기에 $ Factorial(3) $를 호출합니다. ... $ Factorial(1) $가 호출 되었을 때 => 1은 기저 조건이기에 반환합니다...

삽입 정렬 - 여기 말고 저기 빈 자리 가서 앉으세요

이번 포스팅 내용은 삽입정렬입니다. 삽입 정렬은 선택 정렬의 정렬방식과 유사합니다. 선택 정렬이 정해진 위치에 조건에 부합하는 자료구조 내 원소들끼리 비교하여 하나의 원소를 배치 했다면 삽입 정렬은 조건에 부합하는 자료구조 내 원소들이 정해진 위치를 향해 이동합니다. 그럼 아래에서 더 자세히 알아보겠습니다. 1. 삽입 정렬 ( Insertion Sort )이란? 삽입정렬은 이름에서 대략적인 동작 방식을 표현하고 있습니다. 정렬하고자 하는 공간을 임시로 빈 공간으로 만들고 비교 대상 데이터들이 조건에 부합한다면 해당 위치로 이동시킵니다. 기존에 해당 위치에 있던 데이터는 남아있는 빈 공간으로 "삽입" 됩니다. 2. 삽입 정렬의 진행 더 자세히 알아 볼까요? 삽입정렬은 자료구조 내 두번째 원소부터 마지막 원..

선택 정렬 - 자리를 얻기 위한 경쟁

이번 포스팅 주제는 선택 정렬입니다. 선택정렬은 자료 구조 내의 한 위치를 두고 각 원소들이 순차적으로 경쟁을 하는 방식입니다. 이 문장만으로 어느정도 감이 오시지 않나요? 그러면 지금부터 선택정렬이 어떠한 방식으로 진행되는지 더 자세히 알아보겠습니다. 1. 선택 정렬 ( Selection Sort ) 이란? 선택 정렬의 이름은 어떻게 지어지게 되었을까요? "선택 정렬"은 각 패스스루마다 원소를 넣을 위치는 하나로 고정 되어있고, 자료 구조를 순차적으로 탐색하면서 해당 위치에 어떠한 원소를 넣을지 "선택" 하는 알고리즘 이라는데서 이름이 유래되었습니다. 2. 선택 정렬의 진행 크기가 N인 배열을 오름차순으로 선택 정렬해 보겠습니다. 첫 패스스루에서는 배열의 첫 번째 ( 인덱스 : 0 )의 위치에 위치할 ..