일련의 숫자에서 중앙값 찾기 중앙값이란 어떤 배열을 정렬했을 때 정 가운데에 위치하는 값 원소의 개수가 홀수인 경우: 가장 중앙에 위치한 원소가 중앙 값((전체 개수 + 1) / 2 번째 원소) [1, 2, 3]의 배열에서는 2가 중앙값 원소의 개수가 짝수인 경우: 가운데 두 원소의 평균이 중앙값 [1, 2, 3, 4]에서는 2와 3의 평균인 2.5가 중앙값 중앙값을 찾을 때 그냥 최소힙이나 최대힙 둘중 하나로 만들고 중앙에 해당하는 인덱스에 있는 값을 반환하면 되겠지만 데이터가 지속적으로 추가/삭제되고 있는 상황에서 중앙값을 찾으려면 중앙값을 찾을때마다 배열 전체에 대한 정렬을 시도하므로 시간 낭비임 🌟🌟🌟하나의 최소 힙과 최대 힙을 만들면 중간 값을 얻는 것은 단지 O(1) 시간 밖에 걸리지 않음 그..

힙 정렬 지난 시간 까지 힙 클래스를 생성했으니 힙을 사용해서 정렬을 하는 것은 간단함 정렬된 배열을 얻기 위해 힙이 빈 상태가 될 때까지 힙에 대해 .pop()을 호출하면서 꺼낸 객체를 저장하기만 하면 된다. 삼투(bubbleUp, bubbleDown)가 O(logN)가 걸리고 정렬이 n개의 항목들을 꺼내야 하기 때문에 힙 정렬의 시간 복잡도는 O(NlogN)이다. 최소 힙을 이용하면 오름차순 정렬이 가능할 것이고, 최대 힙을 이용하면 내림차순 정렬이 가능할 것이다. 두가지 모두 sort()라는 메소드를 추가하면 된다. (MinHeap 클래스에 추가하면 MaxHeap은 상속받을 것이다) sort(){ let sort = []; const count = this.items.length; for(let i..

힙(Heap) 힙이란? 최댓값이나 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조 힙에는 최소힙과 최대힙이 있음 최소힙 작은 값을 항상 트리의 위에 있게 해서 트리의 루트에는 가장 작은 값이 오도록 함 최대힙 가장 큰 값이 맨 위에 오도록 함. 모든 노드는 자기 부모 노드가 자기보다 큰 값을 가지고 있음 힙에 데이터를 삽입하고 값을 꺼내오는 방법 최소힙에 데이터를 삽입하는 방법 저런 트리가 있다고 하자 1을 삽입하려고 할 때 완전이진트리의 요건을 만족시키기위해 저 자리에 삽입 자신의 값과 자신의 부모노드값을 비교하여 자신의 값이 더 작으면 자리를 바꿈 3번의 과정을 자신의 값이 부모노드값보다 작을때까지 혹은 루트에 도착할 때까지 반복한다. 이 작업은 밸런스가 맞춰져있..

클래스(Class) 🍼 클래스(Class) vs 객체(Object) Class 붕어빵 틀에 비유 템플릿, 청사진이라고도 한다 클래스 안에는 데이터가 들어있지 않다 Object 붕어빵 틀로 만든 붕어빵 클래스에 데이터를 넣어서 만든 것이 객체 클래스를 이용해서 많은 객체를 만들 수 있음 붕어빵 클래스에 팥 데이터를 넣으면 팥 붕어빵, 크림 데이터를 넣으면 크림 붕어빵이 된다. 클래스는 ES6에 추가된 기능임 클래스가 없었을 때에는 function을 이용해서 바로 object를 만들었다(이게 prototype) 기존에 존재하던 프로토타입을 기반으로 하며 간편하게 쓸 수 있도록 문법적으로만 추가되었다고 해서 문법적 설탕(Syntatic sugar)이라고 한다. (여전히 클래스도 프로토타입 기반이다) 클래스 몸..

프로토타입 자바스크립트는 멀티 패러다임 프로그래밍 언어 - 자바스크립트는 명령형, 함수형, 프로토타입 기반, 객체지향 프로그래밍을 지원하는 멀티 패러다임 프로그래밍 언어이다. - C++나 Java 같은 클래스 기반 객체지향 프로그래밍 언어의 특징인 클래스,상속,캡슐화를 위한 키워드인 public, private, protected등이 없어서 자바스크립트는 객체지향 언어가 아니라고 오해하는 경우도 있으나 클래스 기반의 객체지향 프로그래밍 언어보다 효율적이며 더 강력한 객체지향 프로그래밍 능력을 지니고 있는 프로토타입 기반의 객체지향 프로그래밍 언어임 - ES6에서 클래스가 도입되었으나 ES6의 클래스가 기존의 프로토타입 기반 객체지향 모델을 폐지하고 새로운 객체지향 모델을 제공하는 것은 아님 클래스는 생성..

안녕하세요, 이번 시간에는 여태 작성했던 코드를 함수화 해보겠습니다. WEB HTML CSS JavaScript 지난시간 까지 작성했던 코드를 보면 중복이 발생하고 있습니다. 소프트웨어를 만드는 과정에서 언제나 고심해야할 부분은 '어떻게 하면 중복을 제거할 수 있을까?' 입니다. 여기 있는 이 코드 중에서 중복인 부분이 있고 중복이 아닌 부분이 있습니다. fetch('html').then(function(response){ response.text().then(function(text){ document.querySelector('article').innerHTML = text; }) }) 저 'html' 이부분은 중복이 아닌 부분이고, 나머지는 중복인 부분 입니다. 그러면 어떻게 하면 중복을 제거할 수..