본문 바로가기

분류 전체보기

 (153)
9-2. 로그 선형 정렬, 고급정렬 (Log-linear Sorting, Advanced Sorting) 지금까지 다뤄왔던 정렬 알고리즘들은 모두 최악의 경우의 시간 복잡도가 O(n^2)였다. 저번에 시간 복잡도에서 다뤘듯, 시간 복잡도가 기본적으로 O(n^2) 이상이 되면 비효율적이라고 한다. 연산시간이 오래 걸리기 때문이기도 하고, 데이터 수에 따라 수 초나 수 시간이 아닌 이론적으로 수 년이 걸릴 수도 있는 작업이 될 수 있기 때문이다. 그러나 정렬은 필수적인 작업이다. 따라서 이를 해결하기 위해 더 고급의 정렬 방식들이 등장하게 되었는데, 이 고급 정렬 방식들은 모두 O(n log n)의 시간 복잡도를 갖고 있다. sort( )와 sorted( ) 파이썬에수 흔히 사용되는 sort() 메서드는 원본 리스트를 정렬된 상태로 변환하며, sorted() 메서드는 원본의 변경 없이 정렬된 새로운 리스트를 반..
JavaScript - 함수, 화살표 함수와 기존 함수 (Function, Arrow Function and Classic Function) 자바스크립트의 ES6에서 추가된 문법 중 화살표 함수가 있다. 화살표 함수 (arrow function) 란 화살표로 인수를 전달하는 방식으로 함수를 선언하는 것을 말하는데, 기존의 방식의 함수 선언을 대체할 수 있지만, 화살표 함수에 없는 몇 가지가 있다. 이를 다뤄보려고 한다. 함수에 대한 내용은 아래 더보기를 누르면 나온다. 더보기 함수란 인수들을 넣었을 때 (또는 넣지 않았을 때), 어떠한 특정 작업들을 처리하는 코드의 모음이다. 어떠한 값들을 반환할 수도 있고 (return), 또는 반환하지 않을 수도 있으며 (void function), 인수 (arguments) 들을 넣을 수도, 넣지 않을 수도 있다. 함수는 코드의 재사용성을 높인다. 가령 사람이 입장할 때마다 그 사람에게 'Hello ~~..
JavaScript - 호이스팅 (Hoisting) 호이스팅이란 변수의 정의가 그 스코프에 따라 선언과 할당으로 분리되는 것을 의미한다. 쉽게 말하면 아직 선언되지 않은 변수나 함수를 호출하여 사용하는 것을 말한다. 이는 자바스크립트의 동작 방식 때문이다. 자바스크립트 함수는 실행되기 전 함수 안에 필요한 변수값들을 모두 모아서 유효범위의 최상단에 선언한다. 다음 코드를 노드에서 실행시켜보자. 기본적으로 함수를 호출하기 위해선 당연히 함수를 선언해주어야 한다. function myFunc () { console.log('hello world!'); } myFunc(); 결과 PS C:\Users\bumsu\nodejs-projects\노드js교과서> node hello hello world! 그런데 myFunc()을 선언되기 전 앞에다 두어도 실행이 잘 ..
JavaScript - 에어비앤비 자바스크립트 스타일 가이드 (Airbnb JS Style Guide) https://github.com/tipjs/javascript-style-guide#%ED%98%95types tipjs/javascript-style-guide Airbnb JavaScript 스타일 가이드 한국어. Contribute to tipjs/javascript-style-guide development by creating an account on GitHub. github.com 위 문서를 참고하였다. 위 문서 중 몇가지 내가 특히 주의하면 좋을 점들을 정리해 놓았다. 문자열 (string) 에는 싱크쿼트 (' ')를 사용한다. (6.1) 100문자 이상의 문자열은 문자열 연결을 사용하여 복수행에 걸쳐 기술한다. (6.2) 프로그램에서 문자열을 생성하는 경우 문자열 연결이 아닌 templ..
Node.js - REPL, 모듈, 내장 객체 (REPL, Module, Implicit Object) 앞으로의 노드 관련 포스트들은 Node.js 교과서 - 길벗, 조현영 책을 보고 배운 점들을 정리해 놓는 포스트들입니다. REPL 브라우저 콘솔 탭에서 자바스크립트 코드를 입력하는 것처럼, 노드 또한 비슷한 기능을 제공한다. 입력한 코드를 읽고 (Read), 해석하고 (Evaluate), 결과물을 반환하고 (Print), 종료할 때까지 반복한다 (Loop) 고 해서 REPL이라고 부른다. 파이썬의 IDLE 같은 기능이라고 생각하면 된다. 커맨드에 node라고 쳐서 실행한다. C:\Users\bumsu>node Welcome to Node.js v14.7.0. Type ".help" for more information. > const str = 'hello' undefined > console.log(s..
9-1. 2차 정렬과 선형 정렬 (Quadratic and Linear Sorting) : 파이썬 자료구조와 알고리즘 어떤 항목들을 크기가 작은 순서대로 정렬 (sorting) 하고 싶다고 하면, 가장 간단한 방법은 가장 작은 항목을 그룹에서 맨 앞으로 이동시키는 것을 반복하는 것이다. 그러나 이 알고리즘은 시간 복잡도가 O(n^2) 이므로, 더 나은 알고리즘을 찾아야 한다. 제자리 정렬 (in-place sort) 은 정렬할 항목의 수에 비해 아주 작은 저장 공간을 더 사용하는 정렬 알고리즘을 뜻한다. 삽입 정렬은 주어진 원소들을 옮긴 뒤 적절한 위치에 원소를 삽입하는 연산을 반복하는데, 이로 인해 항목을 담는 공간 외에 추가로 사용될 수 있는 공간은 옮겨지는 항목이 저장되는 공간과 반복문 변수 정도에 불과하다. 안정적 정렬 (stable sort) 은 데이터 요소의 상대적인 순서를 보존한다. 데이터의 두 항목이 크기..
8. 점근적 분석 (Asymptotic Analysis): 파이썬 자료구조와 알고리즘 점근적 분석 (asymptotic analysis) 은 어떤 알고리즘에 큰 입력 데이터셋을 적용할 때 알고리즘의 제한 동작과 성능을 설명하기 위한 방법이다. 일반 컴퓨터에서 10억개의 숫자 (10^9) 를 정렬한다고 가정해보자. 숫자는 1 바이트라고 가정하고. 컴퓨터의 CPU 클록은 1GHz (초당 약 10^9 번의 연산) 라고 가정하면, 만약 실행 시간이 O(n^2) 인 알고리즘을 사용하여 숫자를 정렬한다면, 최악의 경우 약 10억초 (약 32년) 가 걸릴 것이다. 끔찍하다. 그러나 O(n)인 알고리즘을 사용하면 대략 수 초가 걸릴것이며, O(log n) 또는 O(1)인 알고리즘을 사용한다면 그보다 훨씬 작은 시간 내에 연산을 완료할 수 있을 것이다. 이와 같이 알고리즘의 시간 복잡도는 알고리즘에 있어..
JavaScript - 이벤트 루프 (Event Loop) 비동기와 동기에 대해서 더 깊게 알아보자. 먼저, 자바스크립트의 언어의 특징 중 하나는 자바스크립트의 함수가 실행되는 방식인데, 이를 보통 "Run to Completion" 이라고 한다. 이는, 하나의 함수가 실행되면 이 함수가 실행이 끝나기 전 까진 다른 어떤 작업도 중간에 못 끼어든다는 이야기이다. 자바스크립트 엔진은 하나의 호출 스택만을 사용한다. 따라서, 현재 스택에 쌓여있는 모든 함수들이 실행을 마치고, 스택에서 제거되기 전 까진 다른 어떠한 함수도 실행될 수 없다. 아래 코드를 보자. function delay() { for (let i = 0; i < 1000000000; i++); } function foo() { delay(); bar(); console.log('foo!'); // (..

티스토리툴바