jyoon dev log

Memoization으로 중복 연산을 방지하며, 작은 부분 문제로 큰 문제를 해결 하며 해를 도출하는 알고리즘 설계 기법. 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 동적 계획법 특징 부분 문제는 중복되며, 상뮈 문제 해결 시 재사용한다. Memoization 기법을 사용한다( 동일한 계산을 반복할 때, 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 따라서 이전에 계산한 값을 메모리에 저장하여 중복 연산 방지함) 다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 때 사용할 수 있다. 1. 최적 부분 구조(Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2. 중복되는 부분 문제 (O..

데큐(Double-ended Queue) 특징 큐와 스택의 장점을 합쳐놓은 자료구조 양쪽 끝에서 삽입과 삭제가 모두 가능 Scroll(입력제한데크) : 입력이 한쪽 끝으로만 가능하도록 설정한 데크 Shelf(출력제한데크) : 출력이 한쪽 끝으로만 가능하도록 설정한 데크

Stack 특징 데이터를 마지막에 밀어 넣고, 마지막에 밀어 넣는 데이터를 먼저 꺼내는 후입 선출(LIFO-Last in First Out)방식의 자료구조. 데이터의 추가와 삭제가 한쪽 방향에서만 일어난다. 스택에 데이터를 밀어 넣는 것을 push라 하고 스택에서 데이터를 꺼내는 것을 pop이라고 한다. pop 메서드와 push 메서드를 사용하면 스택을 쉽게 구현할 수 있다. 스택은 언제나 가장 마지막에 밀어 넣은 최신 데이터를 먼저 취득한다. 스택을 생성자 함수로 구현해 보면 다음과 같다. const Stack = (function () { function stack(array = []) { if (!Array.isArray(array)) { throw new TypeError(`${array} is ..

Queue 특징 shift 메서드와 push 메서드를 사용하면 큐를 쉽게 구현할 수 있다. 큐는 데이터를 마지막에 밀어 넣고, 처음 데이터, 즉 가장 먼저 밀어 넣은 데이터를 먼저 꺼낸다. 선입 선출(FIFO - First In First Out)방식의 자료 구조다. 스택은 언제나 마지막에 밀어 넣은 최신 데이터를 취득하지만 큐는 언제나 데이터를 밀어 넣은 순서대로 취득한다. 큐가 꽉 차서 더 이상 자료를 넣을 수 없는 경우(put 할 수 없는 경우)를 오버플로우(Overflow), 큐가 비어 있어 자료를 꺼낼 수 없는 경우(get 할 수 없는 경우)를 언더플로우(Underflow)라고 한다. 큐를 생성자 함수로 구현해 보면 다음과 같다. const Queue = function () { function..

힙이란? 최대값이나 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리를 기본으로 한 자료구조다 최소힙은 작은 값이 항상 가장 위에 노드에 있게해서 트리의 루트에는 가장 작은 값이 오게하는 최소힙이다. 가장 큰값이 맨 위에 오도록하는 구조가 최대힙이다. 최소힙에 노드 삽입하기 완전 트리에 맨 끝에 노드를 추가한다. 트리가 컴플리트 바이너리 형태를 잃지 않도록 마지막 레벨의 왼쪽부터 채워나간다. 다음 스텝은 자신의 부모 노드와 비교해서 자신이 값이 작으면 부모 노드랑 자리를 바꾼다. 부모 노드가 자기보다 작을 때 까지 반복한다. 완전 이진 트리에서 이루어지니까 한번 돌 때 마다 o(logn)의 시간 복잡도를 가진다. 최소힙에서 노드 꺼내오기 최소힙에서 작은 값은 루트에있으니까 어렵지 않다. 루..