반응형

프론트엔드 개발자는 가끔 자바스크립트로 문제를 풀어야한다. 하지만, 애처롭게도 c++에는 내장 라이브러리로 존재하는 binary_search, lower_bound, upper_bound가 존재하지 않느다. 따라서, 우리는 이분탐색을 "직접" 만들어야한다. 이분탐색에 대해 알아보자

 

Binary Search

const binarySearch =(arr, target)=>{
    let left = 0;
    let right = arr.length - 1;

    while(left <= right){
        let mid = Math.floor((left+right)/2);

        if(arr[mid] === target){
            return mid;
        }else if(arr[mid] < target){
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }

    return -1;
}

 

Lower Bound

const lowerBound =(arr, target)=>{
    let left = 0;
    let right = arr.length - 1;

    while(left < right){
        let mid = Math.floor((left+right)/2);

        if(arr[mid] < target){
            left = mid + 1;
        }else{
            right = mid;
        }
    }
    return left;
}
  • lower bound 는 배열에서 타겟값 이상이 처음으로 나타나는 위치를 찾는다.
  • 이분탐색 하다가 target 값 이상인 left 값이 타겟값을 넘는 첫 위치다.

Upper  Bound

const upperBound =(arr, target)=>{
    let left = 0;
    let right = arr.length - 1;

    while(left < right){
        let mid = Math.floor((left+right)/2);

        if(arr[mid] <= target){
            left = mid + 1;
        }else{
            right = mid;
        }
    }
    return left;
}
  • upper bound 는 배열에서 타겟값보다 큰 값이 나타나는 첫 위치를 찾는다.
  • 타겟값을 초과하는 인덱스를 반환한다.

이분탐색 vs lower, upper

  • 이분탐색은 탐색값을 찾는것 이므로 while의 조건이 left<=right다.
  • lower, upper 는 탐색값의 바운더리를 찾는 것 이므로 while의 조건이 left < right다.
반응형

'Language > Javascript' 카테고리의 다른 글

코딩테스트를 위한 PriorityQueue  (1) 2024.10.31
[JS] 프로토타입  (0) 2024.09.29
반응형

프론트엔드 개발자는 가끔 자바스크립트로 문제를 풀어야한다. 하지만, 애처롭게도 흔하디 흔한 우선순위큐는 내장되어있지 않다. 따라서, 우리는 우선수위큐를 "직접" 만들어야한다. 우선순위큐에 대해 알아보자

우선순위 큐

생성자

constructor(){
    this.heap = [];
}
  • heap 배열을 초기화하는 생성자다.

삽입 enqueue

  enqueue(value){
    this.heap.push(value);
    this._heapifyUp();
  }
  • heap 배열에 value를 push하고 힙정렬을 진행한다.

삭제 dequeue

dequeue(){
    const min = this.heap[0];
    const end = this.heap.pop();

    if(this.heap.length > 0){
      this.heap[0] = end;
      this._heapifyDown();
    }

    return min;
}
  • 삭제하려는 값은 맨위의 최소값이므로 (현재 코드는 최소힙을 기준으로 작성) 0번째 인덱스와 마지막인덱스를 교환한다.
  • 다시 힙정렬을 진행한다.

heapifyUp() 위쪽으로 재정렬

_heapifyUp() {
    let index = this.heap.length -1;
    const element = this.heap[index];

    while(index > 0){
       //우선순위큐는 이진트리를 기반으로 하기때문에 
       //parentIndex 는 자식 노드의 인덱스에 절반과 비슷하다.
      const parentIndex = Math.floor((index - 1) /2 );
      const parent = this.heap[parentIndex];
        //부모보다 크기때문에 최소힙 성립
      if(element >= parent) break;
        //그렇지 않으면 부모와 자리바꾸기
      this.heap[index] = parent;
      index = parentIndex;
    }
    this.heap[index] = element;
 }
  • 값을 삽입하면 오름차순으로 정렬해야한다. (삽입한 값이 맨뒤에 있다.)
  • 삽입된 위치(index) 값부터 (heap 배열에 push 했으므로 맨끝값) 부모 노드를 탐색하면서 바꿀 값을 찾는다.

heapifyDown() 아래쪽으로 재정렬

_heapifyDown(){
    let index = 0;
    const length = this.heap.length;
    const element = this.heap[0];

    while(true){
    //자식 인덱스를 확인
      let leftChildIndex = 2 * index + 1;
      let rightChildIndex = 2 * index + 2;
      let swapIndex = null;
    //왼쪽자식부터 부모가 더 크다면 바꿔야할 인덱스로 판명
      if(leftChildIndex < length){
        if(this.heap[leftChildIndex] < element){
          swapIndex = leftChildIndex;
        }
      }
    //오른쪽자식
      if(rightChildIndex < length){
      //왼쪽을 안바꿔도되고(null), 오른쪽 자식의 값이 부모보다 작다면 바꿔야한다.
      //왼쪽을 바꿔도되고, 오른쪽 자식의 왼쪽 자식의 값보다 작다면 오른쪽 자식을 바꿔야한다.
        if(
          (swapIndex === null && this.heap[rightChildIndex] < element) ||
          (swapIndex !== null && this.heap[rightChildIndex] < this.heap[leftChildIndex])
        ){
          swapIndex = rightChildIndex;
        }
      }

    //바꿀게없다면 패스
      if(swapIndex === null) break;
    //부모와 자식을 바꾼다.
      this.heap[index] = this.heap[swapIndex];
      index = swapIndex;
    }

    this.heap[index] = element;
  }
  • dequeue 를 하게 되면 맨위에 값이 최대값으로 바뀌기 때문에 자식을 탐색하면서 정렬해야한다.

전체 코드

class PriorityQueue{
  constructor(){
    this.heap = [];
  }

  enqueue(value){
    this.heap.push(value);
    this._heapifyUp();
  }

  dequeue(){
    const min = this.heap[0];
    const end = this.heap.pop();

    if(this.heap.length > 0){
      this.heap[0] = end;
      this._heapifyDown();
    }

    return min;
  }

  _heapifyUp() {
    let index = this.heap.length -1;
    const element = this.heap[index];

    while(index > 0){
      const parentIndex = Math.floor((index - 1) /2 );
      const parent = this.heap[parentIndex];

      if(element >= parent) break;

      this.heap[index] = parent;
      index = parentIndex;
    }
    this.heap[index] = element;
  }

  _heapifyDown(){
    let index = 0;
    const length = this.heap.length;
    const element = this.heap[0];

    while(true){
      let leftChildIndex = 2 * index + 1;
      let rightChildIndex = 2 * index + 2;
      let swapIndex = null;

      if(leftChildIndex < length){
        if(this.heap[leftChildIndex] < element){
          swapIndex = leftChildIndex;
        }
      }

      if(rightChildIndex < length){
        if(
          (swapIndex === null && this.heap[rightChildIndex] < element) ||
          (swapIndex !== null && this.heap[rightChildIndex] < this.heap[leftChildIndex])
        ){
          swapIndex = rightChildIndex;
        }
      }

      if(swapIndex === null) break;

      this.heap[index] = this.heap[swapIndex];
      index = swapIndex;
    }

    this.heap[index] = element;
  }
}
반응형

'Language > Javascript' 카테고리의 다른 글

코딩테스트를 위한 이분탐색  (1) 2024.11.09
[JS] 프로토타입  (0) 2024.09.29
반응형

자바스크립트는 프로토타입 기반의 객체 지향 언어

19.1 객체지향 프로그래밍

추상화 : 다양한 속성 중 프로그램에 필요한 속성만 간추려 내어 표현

const person = {
    name : 'Lee',
    address : 'Seoul'
};

객체 는 속성과 동작을 하나의 단위로 구성한 복합적인 자료구조

 

19.2 상속과 프로토타입

상속 객체의 프로퍼티나 메소드를 다른 객체가 그대로 사용할 수 있는 것

프로토 타입을 사용하는 이유

  • 인스턴스가 동일한 메소드를 중복 소유해 메모리를 불필요하게 낭비하는것을 막기 위해
function Circle(radius){
    this.radius = radius;
}

//생성자 함수에 프로토타입이 바인딩 되어있어 접근할 수 있다.
Circle.prototype.getArea = function() { return Math.PI * this.radius ** 2};

생성자와 프로토타입을 나누어 사용한다는 것은 생성자의 데이터 타입을 상속받는 프로토타입 객체라고 생각할 수 있다.

 

19.3 프로토타입 객체

모든 객체는 [[Prototype]] 내부 슬롯을 가진다.

1. __ proto __ 접근자 프로퍼티

모든 객체는 __ proto __ 접근자 프로퍼티를 통해 자신의 프로토타입 내부 슬롯에 간접적으로 접근할 수 있다.

  • 내부슬롯은 property가 아니기 때문에 직접 접근이 불가하고, 값과 메소드에 간접 접근가능하다.

__ proto __ 접근자 프로퍼티는 상속을 통해 사용된다.

  • __ proto __ 는 Object.prototype의 프로퍼티다. 모든 객체는 object를 상속해 프로토타입에 접근할 수 있다.

프로토타입 체인

  • 서로가 자신의 프로토타입일 때 발생한다.

__ proto __ 코드 내에서 직접 사용하는 것을 권장하지 않는다.

  • Object를 직접상속받지 않는 객체를 만들 수 있기에 프로퍼티를 사용할 수 없는 경우 존재한다.

2. 함수 객체의 prototype 프로퍼티

함수 객체만이 소유하는 prototype 프로퍼티는 생성자 함수가 생성할 인스턴스의 프로토타이블 가리킨다.

  • 화살표 함수와 ES6 메서드 축양 표현으로 정의한 메서드는 prototype 프로퍼티를 소유하지 않는다.
function Person(name) {this.name =  name;}

const me = new Person('Choi');

console.log(Person.prototype === me.__proto__); //true

3. 프로토타입의 constructor 프로퍼티와 생성자 함수

모든 프로토타입은 생성자 프로퍼티를 갖는다.

function Person(name) {this.name =  name;}

const me = new Person('Choi');

console.log(Person === me.constructor); //true

 

19.4 리터럴 표기법에 의해 생성된 객체의 생성자 함수와 프로토타입

리터럴 표기법에 의한 객체 생성 방식과 같이 명시적으로 new 연산자와 함께 생성자 함수를 호출하여 인스턴스를 생성하지 않는 객체 생성 방식도 있다.

//객체 리터럴로 생성된 객체
const obj = {};

//obj 객체의 생성자는 obj가 아닌 Object 생성자 함수
console.log(obj.constructor === Object); // true
  • 객체 리터럴로 생성된 객체가 부모 객체의 constructor을 꼭 가리키지 않는다.\
  • 생성자함수에 인수를 전달않거나 null로 전달하면 Object.prototype을 갖는 빈 객체를 생성한다.

Function 생성자로 만든 함수는 렉시컬 스코프를 만들지 않고 전역 함수인 것처럼 스코프를 생성하며 클로저도 만들지 않는다.

 

19.5 프로토타입의 생성 시점

프로토 타입은 생성자 함수가 생성되는 시점에 더불어 생성된다.

1. 사용자 정의 생성자 함수와 프로토타입 생성 시점

constructor 는 함수 정의가 평가되어 함수 객체를 생성하는 시점에 프로토타입도 더불어 생성된다.

console.log(Person.prototype);// {constructor f}

//생성자 함수
function Person(name) { this.name = name;}

생성자 함수로 만든 객체이기에 프로토타입이 동시에 만들어짐

const Person = name => { this.name = name; }

console.log(Person.prototype);// undefined

화살표함수는 non-constructor 이기에 프로토타입이 생성되지 않는다.

2. 빌트인 생성자 함수와 프로토타입 생성 시점

빌트인함수 : Object, String 등과 같은 함수

빌트인 함수도 생성자 함수가 생성되는 시점에 프로토타입이 생성된다.

객체가 생성되기 이전에 생성자 함수와 프로토타입은 이미 객체화되어 존재한다. 생성자 함수또는 리터럴 표기법으로 객체를 생성하면 프로토타입은 생성된 객체의 [[Prototype]] 내부슬롯에 할당된다.

 

19.6 객체 생성 방식과 프로토타입의 결정

객체생성방식

  • 객체 리터럴
  • Object 생성자 함수
  • 생성자 함수
  • Object.create 메서드
  • 클래스

-> OrdinaryObjectCreate (추상연산) 에 의해 객체가 생성된다는 공통점

프로토타입은 추상연산에 전달되는 인수에 의해 결정된다.

1. 객체 리터럴에 의해 생성된 객체의 프로토타입

const obj = { x: 1};

해당 객체 리터럴은 추상연산 이후에 Object.prototype , Object 생성자 함수와 서로서로 연결된다.

2. Object 생성자 함수에 의해 생성된 객체의 프로토타입

Object 생성자 함수를 호출하면 추상연산이 호출되고, 추상연산에 프로토타입 Object.prototype이 전달된다.

const obj = new Object();
obj.x = 1;

//Object 함수에 의해 생성된 obj 객체는 Object.prototype을 상속받는다.
console.log(obj.constructor === Object)//true
  • Object 함수 생성 방식은 빈객체를 생성하고 프로퍼티를 넣어야한다.

3. 생성자 함수에 의해 생성된 객체의 프로토타입

function Person(name) { this.name = name; }

const me = new Person('Choi');

new 연산자와 함께 생성자함수를 호출하면 추상연산이 수행된다.
추상연산에 의해 전달되는 프로토타입은 생성자 함수에 바인딩 되어있는 객체다.

 

19.7 프로토타입 체인

프로토타입 체인

자바스크립트는 프로토타입이 없는 객체의 프로토타입을 찾을 때 부모역할 프로토타입의 프로퍼티를 순차적으로 검색한다.

-> 자바스크립트가 객체지향 상속을 구현하는 메커니즘

(반대) 스코프 체인 : 프로퍼티가 아닌 식별자를 찾는 체인

Object.prototype 을 프로토타입 체인의 종점이라고 한다.

 

19.8 오버라이딩과 프로퍼티 섀도잉

const Person = (function () {
    //constructor
    function Person(name) { this.name = name;}

    //Prototype Method
    Person.prototype.sayHello = function () {
        console.log("Hi");
    }

    //Return Constructor Function
    return Person;
}());

const me = new Person('Choi');

//Instance Method
//Property Shadowing
me.sayHello = function () {
    console.log("Hey");
}

me 객체의 sayHello 생성으로 인해 prototype의 sayHello 는 프로퍼티 섀도잉 됐다.

delete me.sayHello;

me.sayHello();
  • 인스턴스 메소드는 삭제가 되지만, 프로토타입의 메소드는 삭제되지 않는다.

 

19.9 프로토타입의 교체

부모객체인 프로토타입을 동적으로 변경할 수 있다.

1. 생성자 함수에 의한 프로토타입의 교체

const Person = (function () {
    //constructor
    function Person(name) { this.name = name;}

    //Prototype Method
    Person.prototype = {
        sayHello() {
            console.log(`Hi`);
        }
    }

    //Return Constructor Function
    return Person;
}());

prototype 을 객체리터럴로 교체하면 prototype의 constructor 는 사라진다.

  • 생성자 함수를 객체리터럴에 추가하면 constructor 는 복구된다.

const Person = (function () {
    //constructor
    function Person(name) { this.name = name;}

    //Prototype Method
    Person.prototype = {
        consturctor: Person,
        sayHello() {
            console.log(`Hi`);
        }
    }

    //Return Constructor Function
    return Person;
}());

2. 인스턴스에 의한 프로토타입의 교체

function Person(name){
    this.name = name;
}

const me = new Person('Choi');

const Parent = {
    constructor: Person,
    sayHello() {
        console.log("Hi");
    }
}

Person.prototype = parent;

Object.setPrototypeOf(me, parent);

인스턴스로 프로토타입을 재정의 할때 constructor 역시 만들어줘야 생긴다.

19.10 instanceof 연산자

instanceof
좌변에 객체를 가리키는 식별자, 우변에 생성자 함수를 가리키는 식별자를 피연산자로 받는다.

객체 instanceof 생성자 함수

생성자 함수의 prototype에 바인딩된 객체가 프로토타입 체인 상에 존재하는지 확인

function Person(name) { this.name = name; }

const me = new Person('Choi');

console.log(me instanceof Person); // true

//프로토타입 교체를 한다.
const parent = {};

Object.setPrototypeOf(me, parent);

//프로토타입 교체를 통해 me의 프로토타입은 Person이 아니므로 거짓이 나온다.
console.log(me instanceof Person); // false;

프로퍼티와 생성자 함수간의 연결이 파괴되어도 instanceof는 아무런 영향을 받지 않는다. (프로토타입 체인)

19.11 직접 상속

1. Object.create에 의한 직접 상속

Object.create 는 추상연산을 호출한다.

let obj = Object.create(Object.prototype, { x: {value:1});

장점

  • new 연산자없이 객체생성 가능
  • 프로토타입 지정하면서 객체 생성 가능
  • 객체 리터럴에 의해 생성된 객체도 상속받을 수 있다.

주의

let obj = Object.create(null);

프로토타입의 종점에 위치하는 객체이기에 Object 빌트인 메소드를 사용할 수 없다. (.toString() ...)

2. 객체 리터럴 내부에서 __ proto __ 에 의한 직접 상속

const myProto = {x:10};

//myProto 를 상속받는 obj
const obj = {
    y: 20,
    __proto__: myProto
}

 

19.12 정적 프로퍼티 / 메서드

static 프로퍼티 / 메서드는 생성자 함수로 인스턴스를 생성하지 않아도 참조/ 호출할 수 있는 프로퍼티 /메서드

function Person(name) { this.name = name;}

Person.prototype.sayHello = function () { console.log(`Hi`);};

Person.staticMethod = function () { console.log(`static Hi`)};

const me = new Person('Choi');

//생성자 함수에 추가한 함수
Person.staticMethod()

//생성자 함수가 아니기에 에러
me.staticMethod() //TypeError

 

19.13 프로퍼티 존재 확인

1. in 연산자

key in object

const person = {name = 'Lee'};

console.log('name' in person )//true

상속 받는 모든 프로토타입의 프로퍼티를 확인하므로 주의해야한다.

console.log('toString' in person) //true

has (ES6)

console.log(Reflect.has(person, 'name')); //true

2. Object.prototype.hasOwnProperty 메서드

프로퍼티 키가 객체의 고유 값인 경우에만 반환

console.log(person.hasOwnProperty('name')) // true

console.log(person.hasOwnProperty('toString')) // false

 

19.14 프로퍼티 열거

1. for... in 문

const test = {a : 1, b : 1};

for(const key in test) {
    console.log(key);
}

for...in 문은 객체의 프로토타입 체인 상에 존재하는 모든 프로토타입 프로퍼티 중에서 프로퍼티 어트리뷰트의 값이 true 인 프로퍼티를 순회하며 열거

2. Object.keys/values/entries 메서드

객체 자신만의 고유 프로퍼티만 열거하기 위해서 사용

const person = {
    name: 'Lee',
    addr: 'Seoul',
    __proto__: {age : 20}
};

console.log(Object.keys(person)); //["name", "addr"];
반응형

'Language > Javascript' 카테고리의 다른 글

코딩테스트를 위한 이분탐색  (1) 2024.11.09
코딩테스트를 위한 PriorityQueue  (1) 2024.10.31

+ Recent posts