Algorithms and Data Structures (11) 썸네일형 리스트형 [알고리즘] 탐욕 알고리즘(Greedy Algorithm) 1. 정의 - 최적해를 구하는 데에 사용되는 근사적인 방법 - 여러 경우에 걸쳐 각각의 결정을 할 때마다 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. - 일반적으로 매 순간마다 하는 선택에 대해 그 선택이 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최정에 전역적인 해답을 도출했다고 해서 그것 또한 최적이라는 보장은 없다. - 하지만 지역적으로 최적이면, 전역적으로도 최적인 문제들이 존재하고 그러한 문제에 적용할 수 있는 알고리즘이 "Greedy Algorithm"이다. (위키백과) 2. 조건 2-1) Greedy choice property: 앞 선택이 이후의 선택에 영향을 주지 않는다. 2-2) Optimal substructure: 부분 문제에서의 최적.. [자료구조] 트리 1. Tree - 연결 리스트의 상위 단계 자료구조. (사실 트리나 연결리스트 모두 그래프의 한 종류임) - 각 노드가 다른 하나의 노드만 가리킬 수 있는 연결 리스트와 달리, 트리는 둘 이상의 다른 노드를 가리키며 부모/자식의 계층 구조를 가진다. - 연결 리스트는 선형, 트리는 비선형 구조의 특징을 갖는다. 그리고 둘다 비순환 그래프이다. - 트리에서 모든 노드가 하나의 루트에서 멀어지는 방식으로 연결된다. 노드가 부모 노드나 같은 레벨의 다른 노드(siblings)를 가리킬 수 없다. 화살표의 방향은 항상 아래쪽으로 향한다. - 트리 구조 대표적 예시) HTML DOM, 컴퓨터 파일시스템, (JS에서 중첩 배열, 중첩 객체 등도 사실 트리다. 특정 객체에 접근하려면 부모 객체를 알아야 한다.) - .. [자료구조] 스택 & 큐 1. Stack - 후입선출(Last In First Out) 구조를 갖는 자료구조이다. - 입출력 방향이 서로 반대다. - 기본 배열을 이용하거나, linked list로 직접 구현할 수 있다. - 함수 호출 스택, 브라우저 뒤로가기, 실행 취소하기, 메일함 등의 기능을 구현할 때 사용한다. - 구현 class Node { constructor(value) { this.value = value; this.next = null; // next => A pointer } } class Stack { constructor() { this.first = null; this.last = null; this.size = 0; } push(val) { const newNode = new Node(val); if(!.. [자료구조] 연결 리스트 1. 단방향 연결 리스트(Singly Linked Lists) - 배열과 같은 선형 자료 구조이다. - 각 요소는 다음 요소를 가리키는 포인터 값을 가지며 인덱스 값은 갖지 않는다. (*배열이 엘리베이터라면 연결리스트는 계단) - 배열에 비해 새로운 항목을 추가하거나 기존 항목을 제거하는 작업이 매우 간단하다. (배열은 shift/unshift 메소드 실행시 순차적 물결효과 발생) - 연결리스트는 요소에 즉시 접근할 필요가 없는 아주 긴 데이터셋을 저장할 때 유용하다. - 구현 * 노드는 value와 포인터(next) 프로퍼티를 가진다. * 리스트는 두 포인터(head와 tail), length 프로퍼티를 갖고 여러 메소드를 내장한다. class Node { constructor (val) { this... [알고리즘] 병합, 퀵, 이진 정렬 1. Merge Sort -1948년 폰 노이만이 최초로 고안함 -분할&정복 방식의 정렬임.( 큰 배열을 작은 하위 배열로 나누고 정렬한 뒤 다시 합침) -배열 하나를 처음부터 끝까지 정렬하는 것보다 정렬된 두 배열을 합치는 일이 더 간단하다라는 아이디어를 이용함 function merge(left, right) { const merged = []; let i = 0, j = 0; while (i [알고리즘] 버블, 선택, 삽입 정렬 1. Bubble Sort -작은 데이터 셋이나, 데이터가 정렬이 거의 끝난 상태라는 걸 알고 있을 때 유용하다. -원리: 정렬을 진행하면서 인접한 두 데이터를 비교하고 큰 값을 바꾸어 가며 가장 큰 값을 가장 끝으로 밀어낸다. -최선: O(n) / 최악:O(n^2) function bubbleSort (arr) { const swap = (arr, idx1, idx2) => { [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]; } for (let i = arr.length; i > 0; i--) { for (let j = 0; j arr[j+1]) { swap(arr, j, j+1); } } } return arr; }.. [알고리즘] Pointers&Sliding window, Divide&Conquer 1. Multi Pointers - 인덱스 등 위치를 가리키는 포인터를 생성하여 시작과 끝 사이를 이동한다. - 선형 구조의 자료(문자열, 배열, 단일/이중 연결 리스트 등)를 다룰 때 유용하다. //두 포인터가 양쪽 끝에서 서로를 향해 이동하는 경우 //*Time Complexity - O(n) //*Space Complexity - O(1) function sumZero(arr) { let left = 0; let right = arr.length -1; while(left 0) { right --; }.. [Design Pattern] 싱글톤 패턴 1. Singleton Pattern - 인스턴스가 단 한 개만 생성되도록 의도한 패턴이다. - 이 패턴의 주 목적은 단일 객체가 전역적으로 접근 가능하도록 하고, 이 객체를 통해 중앙화된 관리를 제공하는 것이다. - 하나의 인스턴스만 필요한 경우, 특정 데이터를 여러 인스턴스에서 공유해야하는 경우 등의 상황에서 사용된다. - 앱의 상태를 관리하는 클래스를 생성할 때 사용할 수 있다. https://devmoony.tistory.com/43 2-1) 클로저를 이용한 함수 예시 const Singleton = (function () { // 인스턴스 변수 let instance; // 싱글톤 객체 생성 function createInstance() { // 객체 생성 및 초기화 const object =.. 이전 1 2 다음