Back to the Basics

appen는 동적 배열의 끝에 요소를 추가해주는 반면 insertion은 원하는 위치에 요소를 삽입한다. 추가 연산의 시간 복잡도 appen와 마찬가지로 아래 두 경우로 볼 수 있다. 경우1 : 정적 배열에 남는 공간이 있을 때 : 배열 중간에 새로운 요소를 넣을 경우, 가장 뒤의 요소부터 insertion 할 위치까지의 요소들을 하나씩 뒤로 밀어준다. 그 후 빈 공간에 요소를 저장한다. 시간 복잡도 : 최악의 경우 index 0에 요소를 추가할 경우엔 모든 index를 하나씩 뒤로 밀어주게 된다. index로 요소에 접근하는 경우 O(1)이며 n번 반복하므로 O(n)이 된다. 경우 2 : 정적 배열이 찼을 때 : 새로운 배열을 만든 후 기존 데이터를 복사하여 저장한다. 그 후 위와 비슷하게 인덱스를 뒤..

정적 배열 : 배열의 길이가 정해져서 변하지 않는 배열 동적 배열 (dynamic array) : 배열의 길이가 동적으로 변하는 배열: 배열이 꽉 찼을 때 다른 메모리 공간에 기존 배열 크기의 두 배의 공간을 할당하고, 기존 배열을 복사하는 형식으로 내부적으로 공간을 늘린다 동적 배열은 내부적으로는 정적 배열을 기반으로 한 자료구조라고 한다. 그림출처 추가 연산 (append operation) 시간 복잡도 append는 아래의 그림과 같이 배열의 끝에 요소를 추가해주는 연산이다. 그림출처 동적 배열에 값을 추가할 때 시간 복잡도를 알아보자 경우 1 : 정적 배열 남는 공간 있을 때 단순히 index를 이용하여 접근하므로 O(1)이다. 겨우 2: 정적 배열이 꽉 찼을 때 값을 추가하기 위해 현재 사용 중..

Async 이번 포스팅은 이번 주 진행했던 Pair Programming으로 진행한 Async Sprint에 대한 리뷰로 작성하였다. 이번 Sprint의 목표는 1. Node.js의 fs module을 사용하여 비동기 코드를 Callback , Promise, Asyn키워드로 코드를 작성하는 것과 2. fetch API를 활용한 Network 요청과 처리에 대한 간단한 코드를 짜보는 것이다. 구글링이나 강의를 통해 이해했던 것보다 훨씬 공부가 되었던 시간이었다. 1. 비동기 - fs 모듈을 사용한 파일 읽기 이번 Sprint에서 사용 할 Node.js 모듈인 fs.readFile에 대해 간단히 정리해보자. fs.readFile 공식문서 를 참고하였다. fs.readFile(path[, options], ..

이번 포스팅은 Node.js란 무엇이고 모듈을 사용하는 방법에 대한 공부한 내용에 대한 정리 포스팅이다. 1. Node.js란?? Node.js 의 정의 Node.js는 로컬 환경에서 JavaScript를 실행할 수 있는 자바스크립트 런타임이다. 런타임이란? Wikipedia에 따르면 , "In computer science, runtime, run time, or execution time is the final phase of a computer program's life cycle, in which theon the computer's central processing unit as machine code." 이라고 한다. 간단하게 해석을 해보면 CPU에서 기계어 코드가 실행되고 있는 단계하고 보면..

Asynchronous 이번 포스팅에서는 JavaScrit에서 Asynchronous 흐름을 구현하는 방법들에 대해 정리해 보겠다. JavaScript의 비동기 흐름은 callback, promise, async/await 중 하나의 문법으로 구현이 가능하다. 비동기 함수 전달 패턴 1: callback 패턴 비동기 함수 전달 패턴 2 : 이벤트 등록 패턴 1. Callback pattern callback 함수를 동기적으로 사용하는 경우와 비동기 적으로 사용하는 경우에 대해 비교해보자. 동기적으로 사용하는 경우 (이전에 예시로 사용했던 코드가 잘못되어 다시 수정했습니다ㅜ) 아래의 코드를 실행하면 sleep함수는 3초 후에 cb함수를 실행한다. 그리고 나서야 222를 출력한다. 즉, 222를 출력하는 코..

Asynchronous Achievement Goals Synchronous의 개념에 대해 이해한다. Asynchronous의 개염에 대해 이해한다. Asynchronous를 왜 사용하는지 이해한다. 1. 비동기 호출이란? 1. 동기(Synchronous) 비동기를 이해하기 위해 동기(Synchronous)를 먼저 알아보자. 실행 완료 시점과 실행 시작 시점이 같은 것을 동기적(Synchronous)이다 라고 한다. 요청에 대한 결과가 동시에 일어난다. 요청에 blocking이 있다. blocking이란, "A process that is blocked is one that is waiting for some event" 앞의 실행이 끝날 때까지 다른 작업을 하지 못함을 의미한다. 상당리 long-run..

그래프를 순회하는 방법 중 가장 일반적인 너비 우선 검색과 깊이 우선 검색에 대해 공부한다 1. 너비 우선 방법 (BFS , Breadth-First Search) 그림출처 위의 그림과 같이 그래프에서 연결된 노드와 해당 노드들 간의 간선을 순서대로 검색하는 알고리즘을 말한다. 한 단계씩 내려가면서 해당 노드와 같은 레벨에 있는 노드들을 먼저 순회한다. 이진트리검색의 차수 우선 순회와 비슷한 개념이다. 구현을 위해서는 Queue를 필요로 한다. 시간 복잡도 O(V+E) : V는 정점의 개수이고 E는 간선의 개수이다. 전체 그래프를 순회하기 위해 모든 정점과 간선을 방문해야 하기 때문 아래의 무지향성 그래프의 예와 함께 코드를 분석해보자 탐색 순서는 a → b → d→ c →e 이다. 아래 코드에서 ver..

이전에 파이썬 공부를 하면서 [빅오,자료형] 에 대해 정리를 한적이 있다. 빅오가 무엇이고 빅오 표기법의 종류, 상한과 최악에 대한 글을 작성하였다. 이번 포스팅 에서는 빅오 표기 규칙과 시간 복잡도를 구하는 방법에 대해 공부해 정리해보겠다. 빅오를 표기하기 위해서는 알고리즘의 처리해야 할 데이터의 수 n에 대한 연산횟수 f(n)을 구하여 빅오를 구한다. 각 알고리즘의 연산 획수 함수끼리 비교하지 않고 빅오를 계산 하는 이유는 데이터의 수가 많아짐에 따른 연산횟수의 증가 정도가 더 중요하기 때문이다. 빅오 표기법 규칙 계수 법칙 : "상수를 제거하라" 상수 k >0 , f(n)이 O(g(n)) 이면 kf(n)은 O(g(n))이다. n이 충분히 크기 때문에 상수항을 무시해도 되기 때문. 다음의 경우를 비교..