본문 바로가기
힙정렬 구현 힙이란 우선순위 큐를 표현 한 완전이진트리 기본적으로 i 번째 자식의 요소는 2*i번(왼쪽) 2*i+1이다. 최대 힙 트리(MaxHeapify)나 최소힙 트리를 구성해 정렬 삽입 Insert 트리의 끝부분에 값을 삽입하는 함수 upHeap 삽입된 값의 위치를 찾아주는 함수 삭제 DeleteMax 트리의 뿌리 부분에 존재하는 최대값을 제거 downHeap대소 관계에 의해 트리를 재구성 최대힙 정렬 예 N개의 노드에대한 완전 이진트리 구성 ->배열로 최대 힙 구성 부모노드가 자식노드보다 큰 트리 MaxHeapify 배열 마지막 값과 배열 첫번째 값을 교환 배열의 길이를 1줄인후 2,3반복() -> 2번을 수행하게 되면 배열의 첫번째 값에 가장큰 값 3번을 통해 큰값을 맨뒤로 보낸 후 맨 뒷값을 제외하고 2,.. 더보기
힙정렬 힙 구조 맥스 힙 특성 ( A[PARENT(i)]>=A[i] ) 부모 노드의 값은 항상 자식의 노드의 값보다 크다. 따라서 전체 트리의 Root 노드 값이 가장 크다. 또한 각 하위 트리 구조의 Root 노드가 가장 큰 값을 가진다. 최소 힙 특성 부모노드의 값보다 크다. - 힙구조 PARENT(i) Return[i/2] LEFT(i) Return[2i] RIGHT(i) Return2i+1 노드의 높이 Simple path vertax가 곂치지 않고 제일 쉽게 내려가는 경우 힙의 높이 O(logN) 2. 힙특성 관리 Max-Heapify 의 수행시간.,T(n) N을 하위 트리의 노드의 개수라고 할 때, '노드의 값을 바꿀때 수행시간: O(1) 힙의 높이 O(h)=O(lgn) 따라서 전체 수행시간은 : O.. 더보기
합병정렬 합병정렬 머지소트의 디자인 패턴 : divide- conquer Divide 단계에서 입력 값이 기준 값보다 작거나 같으면 정렬 그렇지 않으면 더 작은값으로 쪼갠다. Conquer 단계에서는 재귀로 더 작은값으로 쪼개진 하위 부분을 정렬 Combine 단계에서 합병을 통해 정렬 완성. 구현 배열의 원소가 없거나 하나가 있다면 return 함.// 정렬 완료 Conquer: 재귀적으로 나눠진 배열 을 divide와 정렬 Combine 정렬된 배열 합병 더보기
정렬 2016-05-18 오후 4:16 정렬이란?? 정렬을 n개의 숫자로 입력받아 점점 커지거나 작아지는 순서로 배열, 나열 하는것 오름차순 increasing order 내림차순decreasing order 선택정렬 설명을 하자면 단계적으로 설명하는게 효과적이다. 한마디로 "선택을 해서 정렬을 하는 알고리즘이다. " 그럼 무엇을 선택할래 ? 최소값 선택 오름차순 최대값 선택 내림차순 최소값이나 ㅅ최대값을 선택해서 정렬한다. - 최소값 선택정렬 정렬되지 않은 숫자중에 가장 작은 숫자 선택 선택한 숫자를 정렬되지 않은 숫자들 중 첫번째 숫자와 바꾸면 정렬된것이다. 다시 1번 부터 반복 정확성 증명 수학적 귀납법 이용 i 번째 선택한 숫자가 i번째 작은 숫자인지를 증명 성능분석 최고차 항을 세타로 표현 모든 숫자.. 더보기
8장 버그와 에러 # Chapter 8 - Bugs and Error Handling 프로그램은 생각을 구체화 하는 것이다. 때때로 그 프로그램들은 혼란스러워 진다. 다른때에는 그런 혼란스러운 것들이 코드에 들어갈때 실수가 발생한다. 어느쪽이든 그 결과는 결점이 있는 프로그램이라는 것이다. 프로그램의 결점들은 대게 **버그** 라고 불려진다. 버그들은 프로그래머의 실책이 될 수도 있고 상호작용하는 다른 프로그램의 문제를 일으킬 수도 있다. 어떤 버그들은 즉시 식별할 수 있는 반면에 나머지들은 미묘하거나 시스템에 수년동안 숨어서 남이있을 수 있다. 문제는 프로그래머가 최초에 고려하지 못했던 상황에서 드러나게 된다. 때때로 이 상황은 피하기 어려운 것이다. ## Programmer mistakes 프로그래머의 잘못에 대해서 .. 더보기
9장 정규 표현식 Regular Expression! 정규표현식 정규표현식? : string data에서 패턴을 묘사하는 방법 정규표현식은 끔찍하게 이상하면서도 무지하게 유용하다! 문자열을 다루는 강력한 도구! 정규표현식 만들기! 정규표현식 = Object 타입! RecExp 생성자 앞뒤 슬래쉬(/) var reg1 = new RegExp("abc"); var reg2 = /abc/; //두 정규표현식 오브젝트 모두 abc 패턴을 나타냅니다 첫번째 방법, 생성자를 이용하면 보통 스트링처럼 쓰기 때문에 문자열 쓸 때의 백슬래시 룰이 적용됩니다 console.log("\a\c"); -> ac console.log("\\a\\c"); -> \a\c 두번째 방법은, 슬래시 사이에 놓기 때문에 백슬래시 사용방법이 다릅니다 슬래시를.. 더보기
5장 Higher - Order Functions 핵심적인 이야기는 추상화 규모가 커질수록 복잡도가 증가 추상화… 1) 추상화(Abstraciton) - 공통의 속성이나 기능을 묶어 이름을 붙이는 것 - 객체 지향적 관점에서 클래스를 정의하는 것을 바로 추상화라고 정의 내릴 수 있겠다. - 좀 더 살펴보면 물고기, 사자, 토끼, 뱀이 있을 때 우리는 이것들을 각각의 객체라 하며 이 객체들을 하나로 묶으려 할 때, 만약 동물 또는 생물이라는 어떤 추상적인 객체로 크게 정의한다고 하자. 이때 동물 또는 생물이라고 묶는 것을 추상화라고 한다. 출처: 배열순회 추상화 더보기
4장. 데이터 구조: 객체와 배열 숫자, 부울 , 문자열 은 데이터 구조 에서 내장 된 벽돌 입니다. 하지만 당신은 하나의 벽돌 에서 많은 수의 집을 만들수 없습니다. 객체는 그룹 값들과 함께 더 복잡한 데이터 구조를 만들수 있습니다. 우리가 구축한 프로그램은 지금까지 단순 데이터 유형에서만 동작하고 있다는 사실에 의해서 방해를 받았습니다. 이 장에서는 툴킷에 데이터 구조에 대한 기본적인 이해를 추가 할 것입니다. 이 장의 끝에서 당신은 몇가지 유용한 프로그램을 충분히 이해하고 사용 할 수 있습니다. 이 장에서는 다소 현실적인 프로그램을 통해 동작할 것입니다. 예제코드는 이전의 텍스트에서 function과 변수를 활용 할 것입니다. - The Weresquirrel 8시에서 10시 사이에 자크는 덥수룩한 털과 함께 작은 모피 설치류로 변.. 더보기
Chapter 1 - VALUES, TYPES, AND OPERATERS 1. Values ● 컴퓨터는 전기신호가 강하면 high pulse, 약하면 low pulse로 0,1이라는 2진수의 bit 단위로 구성 ● 다수의 bit를 사용한 정보의 최소 단위 'chunk' 즉, value ● Number, String, Boolean, Undefined value, Fucntion, Object 6가지의 기본타입 2. Numbers ● JavaScript Numbers are Always 64-bit Floating Point ●64-bit Floating Point의 한계 ex) function myNumber(){ var x = 999999999999999; // x will be 999999999999999 var y = 9999999999999999; // y will b.. 더보기
[안드로이드 개발기간] gcm menifest 설정 용어정리용어정리 - senderID : developer console에 들어가서 Project Number이다. - Sender AuthToken = 서버 키 라고도 불리며, 우리 서버가 gcm서버를 요청할 때, 자신의 서버키를 등록하는 것이다. 유출되지 않도록 보안에 신경을 써야한다. - Registration Token : Gcm Server로부터 앱이 발급받은 ID - Application ID = manifest에 등록된 앱의 pakage명 menifest설정 1. permissin 4개 설정2. receiver 설정 Permission 정의wake.Lock 폰이 꺼져있을때 키는 permission googleplayservice가 메세지를 날릴때, c2dm.permission.RECEIVE퍼미.. 더보기

티스토리툴바