728x90 프로그래밍/자료구조4 최장 증가 부분 수열(LIS, Longest Increasing Subsequence), 자바스크립트로 구현하기 💡최장 증가 부분 수열 (LIS, Longest Increasing Subsequence) 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 한다. 방법 A[i] : 수열의 i 번째 수 D[i] : A[i]를 마지막 값으로 가지는 가장 긴 증가 부분 수열의 길이 수열 A = [3, 5, 7, 1] 첫 번째 방법은 i=0 부터 D[i]를 계산하는데, 각각의 D[i]를 계산할 때마다 앞에 위치한 수들을 모두 확인하여 자신보다 작은 숫자들의 D 값 중 최댓값을 찾고 1을 더해 D[i]를 계산한다. i 0 1 2 3 4 A[i] 0 3 5 7 1 D[i] 0 배열 A에 수열을 다음과 같이 저장.. 2022. 7. 12. 구간 트리, 세그먼트 트리 (Segment Tree), 자바스크립트로 구현 💡세그먼트 트리, 구간 트리 (Segment Tree) 여러 개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터의 합을 가장 빠르고 간단하게 구할 수 있는 자료로 세그먼트 트리가 있다. 구간 트리는 배열의 특정 구간에 대한 질의를 빠르게 하기 위해 사용될 수 있다. 구간 트리는 주어진 배열의 구간들을 표현하는 이진 트리를 만든다. 루트는 배열의 전체 구간을 표현하고, 한 트리의 왼쪽 자식과 오른쪽 자식은 해당 구간의 왼쪽 반과 오른쪽 반을 표현한다. 각 노드는 해당 구간에 대한 계산 결과를 저장해둔다. ✓ 특정 구간의 합을 가장 빠르게 구하는 방법은? 예시 데이터 : 1 9 3 8 4 5 5 9 10 3 4 5 💻 방법1. 단순 배열을 이용해 선형적으로 구하기 0 1 2 3 4 5 6 7 8 9 1.. 2022. 7. 11. 이진 힙(Binary Heap), 자바스크립트로 구현하기 ✓ 힙 (Heap) 힙이란 트리 기반 자료구조로 힙 속성을 만족하는 거의 완전한 트리이다. 힙 속성이란 예를 들어, 최대힙의 경우 부모 노드는 반드시 자식 노드보다 커야 한다는 법칙이다. 따라서 최상위 노드는 최대값을 가지게 된다. 따라서 최상위 노드는 최대값을 가지게 된다. 이러한 힙의 특성으로 힙은 우선수위 큐를 구현하는데 적합한 자료구조이다. 힙은 부모와 자식 노드 간의 관계만이 정의되어 있을 뿐, 현제 또는 사촌 노드 간의 우선수위는 정해진 것이 없다. ✓ 이진 힙 (Binary Heap) 이진 힙은 힙 중에서 가장 널리 쓰이는 형태 중 하나로 이진 트리 형태인 힙이다. 이진 트리는 각 노드의 자식 노드가 반드시 2개 이하인 트리이다. 이진 힙은 완전 이진 트리라는 조건을 만족해야한다. 모든 레벨.. 2022. 7. 6. 이진탐색트리 (Binary Search Tree) 💡이진 탐색 트리 (binary search tree) 트리 구조는 편리한 구조를 전시하는 것 외에 효율적인 탐색을 위해 사용하기도 한다. 트리 구조는 가지고 있는 특징에 따라 여러 가지 이름으로 불리는데 이진 트리(binary tree)와 이진 탐색 트리(binary search tree)가 가장 많이 사용된다. 먼저 이진트리는 자식 노드가 최대 두 개인 노드들루 구성된 트리이다. 두 개의 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 나눌 수 있는데, 이진 트리는 자료의 삽입, 삭제 방법에 따라 정 이진 트리, 완전 이진 트리, 포화이 이진 트리로 나뉘게 된다. 정 이진 트리(Full binary tree) 각 노드가 0개 혹은 2개의 자식 노드를 갖는다. 포화 이진 트리(Perfect binar.. 2022. 7. 6. 이전 1 다음 728x90
