🐣 시작은 코드 비교에서 최근에 백준 14002번: 가장 긴 증가하는 부분 수열 5 문제를 풀다가,다른 사람의 풀이와 내 풀이 사이에서 속도 차이가 유독 크게 나는 걸 발견했다.로직은 같았다.LIS(Longest Increasing Subsequence) 구하고, 실제 수열을 역추적해서 출력한다. 그런데 나는 이렇게 썼다:LinkedList result = new LinkedList();while (idx != -1) { result.addFirst(arr[idx]); idx = prev[idx];}반면, 다른 사람의 코드는 이렇게 배열로 처리하고 있었다:int[] result = new int[length];int pos = length - 1;while (idx != -1) { re..

자료구조 중 힙(Heap)은 특정한 순서에 따라 정렬된 요소들을 저장하는 트리 기반의 자료구조.Heap 은 일반적으로 이진 힙(binary heap)으로 구현되며, 우선순위 큐(priority queue)와 같은 다른 추상 자료형의 구현에 주로 사용된다. Heap은 다음과 같은 특징을 가지고 있다.완전 이진 트리(Complete Binary Tree) : Heap 은 완전 이진 트리의 형태를 가진다. 이는 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고, 마지막 레벨은 왼쪽부터 채워져 있는 형태를 말한다.부모-자식 노드 관계 : Heap의 부모 노드는 항상 자식 노드보다 우선순위가 높거나 같은 값을 가진다. 이러한 특성은 최대 힙(max Heap)에서는 부모 노드가 항상 자식 노드보다 큰 값을 가지..

세그먼트트리 class SegmentTree { long tree[]; // 세그먼트 트리 배열 int treeSize; // 트리의 크기 // 세그먼트 트리 생성자 public SegmentTree(int arrSize) { // 배열 크기에 맞게 트리의 높이 계산 int h = (int) Math.ceil(Math.log(arrSize) / Math.log(2)); // 트리의 크기 계산 this.treeSize = (int) Math.pow(2, h + 1); // 트리 배열 생성 this.tree = new long[treeSize]; } // 세그먼트 트리 초기화 메서드 public long init(long[] arr, int node, int start, int end) { // 시작과 끝이..