본문 바로가기

전체 글64

병합 정렬 (Merge Sort) 병합 정렬 병합 정렬은 1) 분할 정복 알고리즘의 하나로, 중복된 수의 입력된 순서와 정렬된 순서가 같은 안정 정렬입니다. 1) 분할 정복 분할 정복은 문제를 2개의 문제로 분리하여 각각 해결하고, 결과를 모아 원래의 문제를 해결하는 전략입니다. 병합 정렬은 하나의 배열을 두 개의 배열로 분할하고, 분할된 배열을 정렬한 후, 정렬된 두 개의 배열을 다시 결합하는 방식으로 정렬합니다. 병합 정렬은 다음과 같은 세가지 과정으로 진행됩니다. 분할(Divide) : 배열을 동일한 크기의 배열 2개로 분할한다. 정복(Conquer) : 분할된 배열을 조건에 맞게 정렬한다. 분할된 배열의 크기가 충분히 작지 않으면 재귀 호출로 다시 분할 정복 과정을 거친다. 결합(Combine) : 정렬된 배열들을 다시 결합한다... 2021. 9. 13.
삽입 정렬 (Insertion Sort) 삽입 정렬 삽입 정렬은 자신의 위치를 찾아서 삽입하여 정렬을 완성하는 알고리즘 입니다. 선택 정렬의 순서는 다음과 같습니다. 두 번째 자료에서 시작하여 앞의 원소들과 비교해 삽입할 위치를 정합니다. 삽입될 위치가 정해지면, 뒤쪽의 원소들을 한 칸씩 뒤로 이동시킵니다. 원소를 정해진 위치에 삽입합니다. 앞쪽의 원소들과 비교 후, 자신의 위치를 정하고 그 위치에 삽입하는 방법으로 정렬을 합니다. 시간 복잡도 최악의 경우 selection sort와 마찬가지로, $O(n^2)$의 시간 복잡도를 가집니다. 수식으로 나타내면 아래와 같습니다. $$ (n-1) + (n-2) + ... + 2 + 1 = {n(n-1)} / {2} $$ 그러나 모두 정렬이 되어 있는 경우, 한 번씩만 비교하기 때문에 $O(n)$의 시.. 2021. 9. 13.
선택 정렬 (Selection sort) 선택 정렬 선택 정렬은 데이터의 순서에 따라 위치는 이미 정해져 있고, 그 위치에 들어갈 원소를 선택하는 알고리즘입니다. 선택 정렬의 진행 과정은 다음과 같습니다. 먼저, 데이터들 중에 최소값을 찾습니다. 찾은 최소값을 맨 앞에 위치한 데이터와 교화합니다. 정렬된 맨 앞의 값을 제외하고 위와 같은 방식으로 데이터의 위치를 교환합니다. 선택 정렬은 버블 정렬과 반대로 회전마다 맨 앞의 데이터를 제외합니다. 선택 정렬은 n번의 회전 마다 n번째 데이터의 위치가 정해집니다. 시간 복잡도 선택 정렬은 버블 정렬과 마찬가지로 $O(n^2)$ 입니다. 한 번의 회전에 데이터 하나를 제외하기 때문에, 데이터가 n개 일 때, n-1 번의 순회가 필요합니다. 이를 수식으로 나타내면 아래와 같습니다. $$ (n-1) + .. 2021. 9. 10.
버블 정렬 (Bubble Sort) 버블 정렬 버블 정렬(bubble sort)은 인접한 두 수를 비교하여 조건에 맞지 않으면 두 수의 자리를 교환하여 정렬하는 알고리즘입니다. 오름차순으로 정렬하는 위의 그림을 보면, 첫 번째 데이터와 두 번째 데이터를 비교하여 크기가 큰 데이터를 오른쪽의 자리로 교환하는 것을 볼 수 있습니다. 이후 두 번째와 세 번째, 다시 세 번째와 네 번째 ... 한 칸씩 이동하면서 조건이 맞지 않으면 서로의 자리를 교환합니다. 1회전이 끝나면 가장 큰 수가 맨 뒤에 위치하기 때문에 맨 끝 데이터는 정렬에서 제외됩니다. n회전에서 n개의 데이터가 정렬이 되었다고 판단하기 때문에, 뒤에서 n개의 데이터를 정렬에서 제외합니다. 시간 복잡도 버블 정렬은 최악의 경우에 $O(n^2)$의 시간 복잡도를 가집니다. 버블 정렬은.. 2021. 9. 10.
[JavaScript] 화살표 함수 (Arrow Function) 화살표 함수는 ES6부터 사용되는 문법입니다. function을 사용하여 함수를 만드는 것보다 간단하게 함수를 작성할 수 있는 장점이 있습니다. 오늘은 화살표 함수에 대해 알아보겠습니다. \'_'/ 1. 화살표 함수 먼저, 기존의 함수와 화살표 함수의 작성 방법에 대해 보겠습니다. var a = function() { // 내용 }; var a = () => { //내용 }; 화살표 함수 특징 화살표 함수는 자신의 this, arguments, super 또는 new.target을 바인딩 하지 않습니다. 화살표 함수는 항상 익명 함수 입니다. 화살표 함수는 메소드 함수가 아닌 곳에 적합하기 때문에 생성자로는 사용할 수 없습니다. - MDN 2. 화살표 함수의 기본 문법 // 매개 변수가 없는 화살표 함수.. 2021. 9. 8.
[JavaScript] 클로저 (Closure) 클로저는 스코프(Scope)에 대해 이해하고 있지 않으시다면, 클로저도 이해하시기 힘드실 것입니다. 이 글을 읽기전에 스코프에 대해 공부하시고 오시는 것을 추천 드립니다. : ) 1. 클로저 MDN에서는 "클로저는 함수와 함수가 선언된 어휘적 환경(lexical scope) 의 조합이다."라고 정의하고 있습니다. 조금 풀어서 설명하자면, 클로저는 외부 함수의 실행이 끝나 함수가 소멸되어도 내부 함수가 외부 함수의 변수에 접근할 수 있는 것을 말합니다. 역시 글로만 설명하니 무슨 이야기인지 정확하게 이해하기 힘듭니다. 설명을 위해 아래의 코드를 보겠습니다. function ex() { var id = '01'; function inner() { console.log(id); } return inner; }.. 2021. 9. 8.
[JavaScript] 스코프 (Scope) 스코프는 번역하면 '범위'라는 뜻을 가지고 있습니다. 이것이 자바스크립트에서 어떠한 것을 의미하는지 알아보겠습니다. : ) 1. 스코프 (Scope) 스코프는 전역(Global) 스코프과 지역(Local) 스코프 두 가지로 나눌 수 있습니다. 전역 스코프는 어느 곳에서든지 참조할 수 있는 것을 말합니다. 지역 스코프는 정의된 지역(함수) 안에서만 참조될 수 있는 것을 말합니다. 코드를 보고 조금 더 설명하겠습니다. var a = 'global'; function test() { var a = 'local'; console.log(a); } test(); // local console.log(a); // global 위 코드에서 함수 밖에 선언된 변수 a는 전역 변수이고, 함수 내부에 선언된 변수 a는 지.. 2021. 9. 8.
[JavaScript] async/await 비동기 처리의 마지막 부분입니다. async/await을 이해하기 위해서는 앞의 글을 읽고오셔야 이해가 가능할거 같습니다. 어짜피 알아야 하는 내용이니까 한 번씩 읽고 오시는 것을 추천드립니다. \('_')/ [JavaScript] 비동기 처리 아래의 그림을 보면 동기적 처리와 비동기적 처리를 간단하게 확인할 수 있습니다. 대충 이해가 가시나요? 그림만 보고 정확하게 이해하기는 힘드니 어떤 상황에 사용하는지 어떤 의미인지 알 oagree0123.tistory.com [JavaScript] Promise 이전 글에서 비동기 처리를 위해 콜백 함수를 사용했습니다. 그런데 콜백 함수를 사용하면 비동기 처리 작업이 많아질 수록 코드가 복잡해지는 것을 볼 수 있었습니다. 이번에는 이를 해결하는 oagree0123.. 2021. 9. 6.
[JavaScript] Promise 이전 글에서 비동기 처리를 위해 콜백 함수를 사용했습니다. 그런데 콜백 함수를 사용하면 비동기 처리 작업이 많아질 수록 코드가 복잡해지는 것을 볼 수 있었습니다. 이번에는 이를 해결하는 Promise 사용법에 대해 알아보겠습니다. [JavaScript] 비동기 처리 아래의 그림을 보면 동기적 처리와 비동기적 처리를 간단하게 확인할 수 있습니다. 대충 이해가 가시나요? 그림만 보고 정확하게 이해하기는 힘드니 어떤 상황에 사용하는지 어떤 의미인지 알 oagree0123.tistory.com 1. Promise Promise는 자바스크립트에서 비동기 처리를 위해 사용되는 객체입니다. Promise는 성공을 할 수도 있고, 실패를 할 수도 있습니다. 성공을 하면 resolve를 호출하고, 실패하면 reject를.. 2021. 9. 6.

티스토리툴바