Heap(히프) Heap 은 root 가 최대값인 max-heap, 최소값인 min-heap이 있는데 다른 언급이 없으면 max-heap 을 의미합니다. heap은 아래에서 위로 순서를 가지고 있는 이진 트리이므로 모든 leaf-root path 를 따라 가는 순회는 오름차순으로 key 를 방문합니다. 이것은 어떠한 key도 부모보다 크지 않다고 말하는 것과 같습니다. 히프화 알고리즘은 2 * log n 번 이상의 비교를 하지 않습니다. 히프화 알고리즘은 특정 노드를 root로 하는 서브트리에 대해 heap 특성이 만족됩니다. 가장 하위 내부 노드 부터 시작하여 root 에 이르기까지 각각의 x 에 대한 이 연산을 반복함에 의해 전체 트리를 히프화할 수 있습니다. 이러한 과정을 히프 구축(Heap Bui..
비트마스크란 정수의 이진수 표현을 자료구조로 사용하는 기법입니다. 부호없는 N비트 정수형 변수는 N자리의 이진수로 사용할 수 있습니다. 이때 각 비트가 표현하는 값은 2^0 부터 2^k-1 까지입니다. 2^k-1 에 해당하는 비트를 최상위 비트(most significant bit)라고 부르고, 2^0를 나타내는 비트를 최하위 비트(least significant bit) 라고합니다. 어떤 정수를 이진수로 표현했을 때 어떤 비트의 위치가 1이라면 해당비트가 "켜져있다"라고 말하고, 0이라면 꺼져있다고 말합니다. 비트 관련 연산 정의 비트별 AND 연산(&) 두 정수에 해당 비트가 모두 켜져있을때만 결과의 비트를 켭니다. (같의 위치에 있는 두 비트가 전부 1인 경우 결과가 1이고 그 이외에는 0입니다.)..
여러 가지 데이터 타입 및 자료구조가 있지만, 알고리즘에 집중하기 위해 정수(int) 배열을 오름차순으로 정렬하는 형식으로 진행하겠습니다. 각각의 정렬 알고리즘은 특정 환경에 에서 최적의 성능을 발휘합니다. 메모리 공간을 적게 쓴다든지, 배열의 길이가 얼마 이하이면 제일 빠르다든지, 이미 정렬된 경우 제일 빠르다든지.... 참고로 알고리즘의 성능은 비교 횟수와 교환횟수, 추가로 사용하는 저장 공간, 초기 정렬 상태 등 에 따라 결정됩니다. swap 함수 Bubble Sort(버블 정렬) 가장 단순한 정렬 알고리즘입니다. 비교하는 과정이 탄산음료를 담은 컵에 두개의 거품(크기가 서로 다른)이 수면 위로 상승하는 과정과 비슷합니다. 두 거품이 상승중에 충돌 하였을 때 큰 거품이 작은 거품보다 먼저 상승하게 ..
알고리즘 문제 해결 전략 책에서 앞부분 개인적으로 요약 정리해 보았습니다. 접근 방법 무식하게 풀 수 있는지 확인합니다. (문제를 일단 푸는게 우선이고, 나중에 회고를 통해서 더 좋은 알고리즘을 찾습니다.) 문제를 수식화가 가능한지 확인합니다. 문제를 부분 문제로 여러개 나누어 계산이 가능한지 확인합니다. (예 : 팩토리얼) 문제에서 주어진 순서에서 반대로 풀수 있는지 계산이 가능한 문제인지 확인합니다. (예 : 사다리타기) 실수 줄이기 1. 일관된 표현방식 사용 반 열린 구간 을 사용하여 실수를 예방습니다. (열린구간, 닫힌구간 등은 사용을 자제합니다.) low
nodejs 로 frontweb 을 개발할 때 bower module 을 사용하면 bowercomponets 폴더가 생기면서 이 폴더 안에 dependency로 등록된 bower 저장소의 모든 파일을 내려받습니다. 예를 들어 jquery 를 bower dependency 에 추가 하면 저장소의 소스를 전부 bowercomponets/jquery 폴더 안에 복사합니다. 본인은 jquery.js 만 필요한데 필요없는 파일들이 개발자를 더 혼란시키게됩니다. bower-installer 란 실제 개발시에 사용하는 주요 파일(css,js 등)만 내가 원하는 경로에 따로 보관하고 관리할 수 있도록 해주는 node 모듈입니다. 먼저 모듈을 전역으로 설치합니다. $ npm install -g bower-installe..
bintray 에서 만든 gradle-bintray-plugin 로 maven central(메이븐 중앙 저장소) 에 java library 를 배포해보겠습니다.절차 요약 본인의 bintray 저장소로 라이브러리 업로드 jCenter 저장소에 link 를 겁니다. (관리자 승인 필요) jCenter 와 mavenCentral 을 sync 합니다. (관리자 승인 필요) bintray 계정 생성 계정생성 페이지 - opensource user 로 가입하세요. 기업 유저로 가입하시면 안됩니다. 삭제 기능이 있는데 입력한 내용이 있다면서 삭제가 잘안되네요. (삭제가 안되서 계정 2개 만들었습니다..ㅜㅜ) bintray user's maven repository 생성 계정 생성 후 bintray 에 로그인하고 프..
최근에 사용한 쓸만한 JavaScript Library 를 몇개가 있어서 정리해보았습니다. Lodash.js 인지도 높은 underscore 와 비교되는 javascript library 입니다. underscore 의 모든 함수를 구현하였고, 추가적인 함수도 구현해 놓았습니다. 이 라이브러리는 arrays, objects, strings 등의 데이터를 다룰때 활용도가 높습니다. 예를 들어 [3,4,5,6,7,8] 등의 배열에서 5보다 큰 원소만 필터링해서 출력하는 간단한 로직을 직접 구현 하는 경우 적어도 for, if 문등을 사용하여 3줄 이상의 코딩을 하여야 하는데 lodash 를 사용하면 다음과 같이 한줄로 끝낼수 있습니다. _.find([3,4,5,6,7,8], function(o) { retu..
VOIP(Voice over Internet Protocol) 란 IP 네트워크를 이용하여 음성과 같은 실시간적인 정보를 전송하는 기법입니다. 쉽게 이야기하면 인터넷 전화라고 할수 있습니다. 상세한 내용은 Voice orver IP 를 참고하시기 바람니다. pjsip(voip 를 구현한 C library) 를 공부하면서 생소한 용어나 약자를 보고 그것의 기능 및 역할을 추측해보고자 정리하였습니다. 사용되는 용어 SIP SIP(Session Initiation Protocol)는 HTTP(웹 프로토콜) 와 SMTP(메일 프로토콜) 의 많은 영향을 받아서 설계되어서 주소체계, 헤더 정보, 응답코드 등에서 유사한 점을 많이 찾아 볼수 있습니다. 이 프로토콜은 하나 또는 그 이상의 참가자와 멀티미디어 세션들의 ..