자바스크립트18 최소 스패닝 트리(Minimum Spanning Tree) 알아보기 +) 그 전에 스패닝 트리란?※ 그래프 내 모든 정점을 포함하는 부분 그래프. 최소 스패닝 트리란? (Minimum spanning tree)혹은 Minimum Weight Spanning tree (최소 가중치 스패닝 트리)라고도 불림.가중 + 무방향 그래프의 모든 정점을 연결하면서 사이클을 이루지 않음 + 그래프를 이루는 모든 가중치의 합이 최소인 트리를 말함. 특징그래프 내 N개의 정점이 있다고 할 때, 각 스패닝 트리는 N-1개의 간선을 가진다.한 그래프 내에는 여러 개의 최소 스패닝 트리가 존재할 수 있다.만약 그래프 내 모든 간선의 가중치가 같다면, 모든 스패닝 트리는 항상 최소의 가중치 합을 가진다. 알고리즘프림 알고리즘주어진 그래프에서 한 정점을 선택하여 트리를 만듦.그래프의 모든 간선이 .. 2024. 8. 4. Monotonic Stack에 대하여 알고리즘 문제를 풀다가 처음 마주하는 개념을 알게 되었다. 이름을 알게 된 김에 가볍게 내용을 정리해보았다. Monotonic Stack이란 : 스택 내의 요소들이 단조적으로(Monotonic) 증가/감소하는 스택을 말한다. 아래와 같은 특징을 갖는다고 한다. 한 번 pop된 요소는 다시는 재사용 되지 않는다. 요소를 스택에 추가할 때마나 단조성을 유지한다. → 이러한 특징 때문에 주로 다음/이전의 최소값/최대값(Next/Previous smaller/larger Problem)을 구하는 문제에서 잘 쓰인다. Monotonic Stack의 구현 Monotonic Stack의 구현에는 아래의 과정을 거친다. 아래는 감소하는(Decreasing) 스택을 구하는 과정이다. 기본적으로, 주어진 숫자 목록을 순회.. 2024. 4. 14. [Javascript] 프로토타입 알아보기 - 2 지난 글에 이어서, 코어 자바스크립트를 읽고 프로토타입에 대해 공부한 내용을 정리한다. 메서드 오버라이드(Method Override) : 부모 역할을 하는 객체에 정의된 메서드를 재정의하는 것. var Foo = function (bar) { this.bar = bar; }; Foo.prototype.getBar = function () { return this.bar; }; var foo = new Foo('hello'); foo.getBar = function () { console.log(this.bar + ', World!'); }; foo.getBar(); // hello, World! 가 출력된다 생성자 Foo의 프로토타입에 getBar라는 메서드를 정의한다. 따라서 생성자 Foo 로 만들어.. 2024. 2. 2. [Javascript] 프로토타입 알아보기 - 1 코어 자바스크립트를 읽고, 프로토타입에 대해 공부한 내용을 정리한다. 프로토타입(Prototype) : 자바스크립트의 모든 객체와 연결된, 부모 역할을 담당하는 객체. JS에는 클래스 기반이 아닌, 프로토타입 기반 객체 지향 언어이다. 프로토타입을 통해 객체 지향의 상속 개념을 구현한다. 프로토타입의 개념 다음과 같은 코드가 있을 때, 이 코드를 실행한 결과를 도식화 하면 아래와 같은 그림을 그릴 수 있다. const instance = new Foo(); Foo 생성자 함수를 통해 Foo의 인스턴스인 instance를 생성하고 있다. 이 때, instance의 __proto__([[prototype]]) 프로퍼티가 자동으로 부여되고, 이 프로퍼티는 해당 인스턴스의 부모의 프로퍼티(여기서는 Foo의 pr.. 2024. 1. 24. [Javascript] 콜백 함수 알아보기 코어 자바스크립트를 읽고, 콜백 함수에 대해 공부한 내용을 정리한다. 콜백 함수(Callback Function) : 다른 코드의 인자로 넘겨주는 함수, 매개변수를 통해 다른 함수의 내부로 전달되는 함수. ※ 고차 함수(Higher Order Function): 매개변수를 통해 함수 외부에서 콜백 함수를 전달받은 함수. 콜백 함수를 받은 고차 함수는 원하는 때에 콜백 함수를 실행할 수 있음. 즉, 콜백 함수의 제어권을 다른 함수에 넘겨주는 것. 제어권 고차함수는 콜백 함수에 여러가지 제어권을 가질 수 있다. 1. 호출 시점 고차 함수는 콜백 함수를 자신이 원하는 시점에 실행할 수 있다. var counter = 0; var foo = () => { console.log(counter); if (++cou.. 2024. 1. 21. [Javascript] 클로저 알아보기 - 2 지난 게시물에 이어서 클로저의 사용 예시에 대해 정리한다. 주로 코어 자바스크립트 책을 참고했다. 클로저 활용 사례 1. 콜백 함수 내부에서 외부 데이터 사용 시 콜백 함수란 다른 함수에 인자로 전달되는 함수이다. 즉, 다른 함수에서 이 콜백 함수를 사용하는 주도권을 쥐게 된다. 이러한 콜백 함수에서, 외부 변수를 참조하는 데에는 크게 3가지가 있다. (a) 콜백함수 내부에서 외부 변수를 직접 참조하는 방법(클로저 사용) var nameList = ['Ann', 'Gren', 'Jennifer']; var $ul = document.createElement('ul'); nameList.forEach(function (name) { var $li = document.createElement('li'); $.. 2024. 1. 8. 이전 1 2 3 다음
